2020 集中コースLトラック 【暗号ファジングトラック】応募課題 集中コースLトラックには3つのゼミがあります。 L-I 暗号解読チャレンジゼミ L-II 暗号のままで計算しようゼミ L-III エクスプロイト自動化ゼミ 以下のゼミ別の設問をよく読んで、自由記載解答欄に回答を書いてください。 ============================================================================== L-I 暗号解読チャレンジゼミ 応募課題 ============================================================================== 暗号解読の手法は多数ありますが、特に公開鍵暗号では理論的手法が、秘密鍵暗号では アルゴリズム的手法が多いです(※注1)。この分け方をした場合、理論的な共通部分が 少ないですから、両方をこのゼミで実施するにはとてもではありませんが時間が足りま せん。それゆえ、今回はこのうちどちらか一つに絞って応募いただきたいと思います。 ・応募に際し文字数は気にしません。フォームへの文字数を超過した場合は Qiita や 　gist、個人ブログを活用していただいて構いません(※注2)し、それによる減点をす 　ることはありません。好きなだけ、調べたこと/理解できていないことを書きたいだ 　け書いてください。多少誤っていても問題ありません。 ・コピペをしようが、ほとんど理解できていないまま覚え込んだことを書こうが構い 　ませんが、できれば理解したものを書いてください。そして理解できていないこと 　は理解できていないと明確に書いてよいです。理解できていないことは恥ずべきこ 　とではありませんし、わからなければ今から学べばよいのです。 ・参考資料は(最後にまとめてでも構わないので)明記してください。そして、可能な 　限り、より一次資料(具体的には提案論文)に近い資料にチャレンジしてください。 　いずれにせよ、最終的には提案論文を読んで実装するところまでを1日でできるよう 　になれると思います。 ※注1:公開鍵暗号に対するアルゴリズム的な手法、秘密鍵暗号に対する理論的手法も 　　　当然ながら存在しますから、実際には各自調べて頂いた所感で選んでもらえれ 　　　ばと思います。 ※注2:他の方に見えないよう、private gistや限定公開機能を利用してください。 ■問1：あなたは公開鍵・秘密鍵暗号のどちらで応募しますか。理由も併記してください。 　以降、問n = 2, 3, 4 に対し、公開鍵暗号を選択した方は問n-P、秘密鍵暗号を選択し 　た方は問n-Sに進んでください。 ------------------------- ▼選択問題 ＜公開鍵暗号＞ ------------------------- ■問2-P：RSA暗号に対する解読手法を一つ取り上げ、解説してください。簡単なものでも 　構いませんが、可能な限り自分の理解の限界に挑戦してもらえると嬉しいです。 ■問3-P：あなたの好きな公開鍵暗号を一つ取り上げ、解説し、実装してください。 　実装言語は問いませんが、キャンプ当日に読んで理解できる程度のコメントを書いてく 　ださい (理解できるのであればなしでもOKです)。 ■問4-P：問3-Pで取り上げた暗号は応募時点で「安全」ですか？ 　解読手法があればそれを一つ解説し、安全ならばその理由を解説してください。 ------------------------- ▼選択問題 ＜秘密鍵暗号＞ ------------------------- ■問2-S：AES暗号に対する解読手法を一つ取り上げ、解説してください。簡単なものでも 　構いませんが、可能な限り自分の理解の限界に挑戦してもらえると嬉しいです。 ■問3-S：あなたの好きな秘密鍵暗号を一つ取り上げ、解説し、実装してください。 　実装言語は問いませんが、キャンプ当日に読んで理解できる程度のコメントを書いてく 　ださい (理解できるのであればなしでもOKです)。 ■問4-S：問3-Sで取り上げた暗号は応募時点で「安全」ですか？ 　解読手法があればそれを一つ解説し、安全ならばその理由を解説してください. ---------------------------- ■問4(補足)：解読手法があり、余裕があるならば、それを実装してください. ■問5：自己アピール可能な事柄があればここに書いてください. ■問5(補足)：これまでの実績や本課題を進める過程で実装した他のスクリプト等が存在 　するgithubリポジトリや学んだ結果を書いたブログ記事があればそれも掲載いただいて 　構いません。何もなければ美味しいカレーの作り方でも研究室の話でもなんでもOKです。 ============================================================================== L-II 暗号のままで計算しようゼミ ============================================================================== 採点は加点式、かつ部分点が存在します。原則的に文字数制限はありません。ただし、 意味的に同一の内容であればより短いものを高得点とする場合があります。長過ぎるこ とによる減点はありません。 ■問1：準同型暗号は若い分野です。そのため、全体像を把握するためには様々な断片的 　情報をつなぎ合わせる必要があります。この課題はあなたの意欲と調査力を問う課題 　です。準同型暗号について、あなたの知るところを述べなさい。 　ただし、その際に以下のいずれかまたは両方の指示を満たしなさい。 1.Garbled Circuit、秘密分散を用いたもの、TEE、Morpheusなど(ここでいう"など"は具 　体的に上げていないものでも良いことを明示的に示す)のセキュアに計算処理を実行す 　る準同型暗号以外の仕組みに比べて、準同型暗号が持つメリットとデメリットを述べ 　なさい。 2.準同型暗号を用いることで実現できそうなアイデアについて、可能な限り具体的に述 　べなさい。ただし、実用的である必要はありません。 完全な回答でない場合でも採点において考慮することがあります。また、上記の指示 を満たす限りあなたの興味のままに調べた内容を書いてください。余計なことを書い て減点されることはありません。 調査する取っ掛かりになるであろうワード、文献や実装を以下に並べます。 加法準同型暗号、乗法準同型暗号、部分準同型暗号(Partial Homomorphic Encryption)、 LHE(Leveled Homomorphic Encryption)、完全準同型暗号(Fully Homomorphic Encryption)、 Paillier暗号、RSA暗号、ElGamal暗号、BFV、BGV、CKKS、GSW、TFHE、格子暗号、 LWE(Learning With Error)、NTRU、SVP(Short Vector Problem) - クラウドを支えるこれからの暗号技術 第13章 光成滋生・著 秀和システム・出版 - https://eprint.iacr.org/2018/421 - https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf - https://eprint.iacr.org/2011/277 - https://github.com/shaih/HElib - https://github.com/Microsoft/SEAL - https://github.com/virtualsecureplatform/kvsp - https://github.com/CEA-LIST/Cingulata - https://tfhe.github.io/tfhe/ - https://qiita.com/kenmaro/items/416657efca2ff296169b ■問2：この課題はあなたの基礎的なプログラミング能力を見るためのものです。 　原則的により計算量が少ない実装により高い得点をつけ、コードやコメントから 　理解度が読み取れるものはそうでないものよりも高い得点をつけます。 この課題では、整数係数多項式の剰余演算を実装してもらいます。剰余演算とは、割った 余りを求める操作のことです。ただし、法、つまり割る側となる多項式はnを自然数として Xⁿ+1のかたちに限られるものとします。また剰余演算を行う対象の多項式は高々2n-1次と します。つまり、剰余演算の対象となる整数係数多項式をaとすると、aのi次の係数をaᵢと するとき、aᵢは全て整数であって、a=a₀+a₁X+...+a₂ₙ₋₁X²ⁿ⁻¹のように表せます。 具体例として以下の式を与えます。 3X³-X²+1 ≡ -3X+2 mod X²+1 今、n=1024とし、入力として多項式の係数を2n要素の64bit符号付き整数(int64_t)配列と して表現したものが与えられるものとします。出力となる多項式をn要素の64bit符号付き 整数の配列として返す関数を実装しなさい。ただし、出力となる多項式の係数がオーバー フローを起こさないように入力の係数の大きさが制限されていることは保証されているも のとします。 提出するプログラムは以下の条件を満たすようにしてください。 ・別途提供される「kadai2.zip」の中のコードの該当コメント部分を書き換えて製作すること。 ・言語はC,C++,Pythonのいずれかであること。 ・ライブラリはネットで無償で入手可能または添付によってこちらに提出できるもので 　あれば好きなものを用いて構いません。 ・チェック用の入力と出力の組は別途提供します。 ・少なくとも１ヶ月後の自分が理解するのに十分と考える程度のコメントをつけること。 ・計算量やコード量の削減などで特別な工夫を施した場合はそのことがわかるように 　コメントをつけてください。ただし、数式を書きたい場合など必要な場合はコメント 　ではなく別ファイルで記述しても構いません。その場合はどの部分について述べているか 　対応がわかるようにしてください。 ・プログラムが完成しなかった場合は、その場所にどのような処理を書けばいいかを 　コメントで書くと採点で考慮することがあります。 ・こちらでも実行可能になるように配慮してください。 下記のものはヒントです。 ・Pythonを用いる場合、numpyの多項式型に変換して剰余を求めても構いせん。 ・法となる多項式がXⁿ+1のかたちに限られていることを利用した最適化を施すことができます。 　入力の次数も制限されていることに留意しましょう。 ・余談ともいえますが、この課題で挙げた例でX=10にしてみると、実は整数の剰余は多項式の 　剰余の特殊な場合と考えることもできます。 ■問3：あなたが書き足りなかったことや、過去に自分で作ったものや本ゼミに関連しそうな 　知識や経験などのアピールしたいことを自由に記述しなさい。 　特にない場合は未回答でも構いません。 ============================================================================== L-III エクスプロイト自動化ゼミ 応募課題 ============================================================================== 本ゼミではエクスプロイト自動生成技術であるAutomatic Exploit Generation(以下AEG) について体系的に学び、様々なアプローチを実装します。 以下の設問は全て完答する事が望ましいですが絶対条件ではありません。 また回答には出来る限り試行の過程を残してください。 ■問1：Zeratool (https://github.com/ChrisTheCoolHut/Zeratool) のREADMEを参考に 　しながら同レポジトリ内の challenges/demo_bin に対する攻撃コードを自動生成して 　ください。No eXecute (NX) bitを有効にした時とそうでない時の動作の違いを説明し 　てください。 ■問2：AEG (https://security.ece.cmu.edu/aeg/aeg-current.pdf) を読み、同論文内で 　定義されているアルゴリズムBUG-FINDとEXPLOIT-GENのZeratool上での実装を調査して 　ください。Zeratoolのソースコード(python)を読み、それぞれのアルゴリズムに対応 　する関数の処理についてなるべく詳しく説明してください。 ■問3：Zeratoolのようなシンボリック実行を用いたAEGとファジングの違いをそれぞれ 　の利点と欠点を挙げながら説明してください。説明には"State Space Explosion"と 　"Exploit derivability"の2つの単語を必ず使ってください。 　※単語は和訳が存在しないため原語を載せていますが当然回答は日本語で構いません。 ■問4：その他自己アピール可能な事柄があればここに書いてください。 ==============================================================================