2021 集中コースLトラック 【暗号数理実装トラック】応募課題 集中コースLトラックには4つのゼミがあります。 L-I 暗号解読チャレンジゼミ L-II 暗号のままで計算しようゼミ L-III 準同型暗号アプリケーション開発ゼミ L-IV 暗号の脆弱性や攻撃手法を理解して説明しようゼミ 以下のゼミ別の設問をよく読んで、自由記載解答欄に回答を書いてください。 Lトラックの中であれば、複数のゼミに応募しても構いません。 その場合、応募したいゼミすべての応募課題を提出してください。 複数のゼミに応募する際は、ゼミの優先志望順位を書いてください。 ※他のトラック（A, B, C, D, X, Y, Z)との併願はできません。 ■2021年4月19日更新：L-II 課題2.2の解説例について下記3箇所を修正しました。 [1箇所目]修正前： l=2の場合は、分解元の法はP=255となり、1桁目が最初の要素、2桁目が2つ目の要素となるような組で分解後の各桁が表されるとして、231→(8,-2) 　↓ [1箇所目]修正後： l=2の場合は、分解元の法はP=256となり、1桁目が最初の要素、2桁目が2つ目の要素となるような組で分解後の各桁が表されるとして、232→(8,-2) [2箇所目]修正前： 231の例では、8-2*16= -24 ≡ 231(mod 255)であり、 　↓ [2箇所目]修正後： 232の例では、8-2*16= -24 ≡ 232(mod 256)であり、 [3箇所目]修正前： ・デバッグとしては分解した結果がちゃんと下に戻せるかチェックしてみるのもよいでしょう。 　↓ [3箇所目]修正後： ・デバッグとしては分解した結果がちゃんと元に戻せるかチェックしてみるのもよいでしょう。 ============================================================================== L-I 暗号解読チャレンジゼミ 応募課題 ============================================================================== 暗号解読の手法は多数ありますが、特に公開鍵暗号では理論的手法が、秘密鍵暗号では アルゴリズム的手法が多いです(※注1)。この分け方をした場合、理論的な共通部分が 少ないですから、両方をこのゼミで実施するにはとてもではありませんが時間が足りま せん。それゆえ、今回はこのうちどちらか一つに絞って応募いただきたいと思います。 ・応募に際し文字数は気にしません。フォームへの文字数を超過した場合は Qiita や 　gist、個人ブログを活用していただいて構いません(※注2)し、それによる減点をす 　ることはありません。好きなだけ、調べたこと/理解できていないことを書きたいだ 　け書いてください。多少誤っていても問題ありません。 ・コピペをしようが、ほとんど理解できていないまま覚え込んだことを書こうが構い 　ませんが、できれば理解したものを書いてください。そして理解できていないこと 　は理解できていないと明確に書いてよいです。理解できていないことは恥ずべきこ 　とではありませんし、わからなければ今から学べばよいのです。 　このことから、応募課題に対して完全に正答する必要はありません。 ・参考資料は(最後にまとめてでも構わないので)明記してください。そして、可能な 　限り、より一次資料(具体的には提案論文)に近い資料にチャレンジしてください。 　いずれにせよ、最終的には提案論文を読んで実装するところまでを1日でできるよう 　になれると思います。 ※注1:公開鍵暗号に対するアルゴリズム的な手法、秘密鍵暗号に対する理論的手法も 　　　当然ながら存在しますから、実際には各自調べて頂いた所感で選んでもらえれ 　　　ばと思います。 ※注2:他の方に見えないよう、private gistや限定公開機能を利用してください。 ■問1：あなたは公開鍵・秘密鍵暗号のどちらで応募しますか。理由も併記してください。 　以降、問n = 2, 3, 4 に対し、公開鍵暗号を選択した方は問n-P、秘密鍵暗号を選択し 　た方は問n-Sに進んでください。 ------------------------- ▼選択問題 ＜公開鍵暗号＞ ------------------------- ■問2-P：Schmidt-Samoa暗号について解説し、実装してください。 ■問2-P(発展)： Schmidt-Samoa暗号という暗号には、暗号として"役に立たない"レベルの瑕疵が存在します。 もしもこれに気づけた場合は、それについて解説してください。 ■問3-P：あなたの好きな公開鍵暗号を一つ取り上げ、解説し、実装してください。 　実装言語は問いませんが、あなた以外の人が読んで理解できる程度のコメントを書いてく 　ださい (理解できるのであればなしでもOKです)。 ■問4-P：問3-Pで取り上げた暗号は応募時点で「安全」ですか？ 　解読手法があればそれを一つ解説し、安全ならばその理由を解説してください。 ------------------------- ▼選択問題 ＜秘密鍵暗号＞ ------------------------- ■問2-S：FEAL-4暗号に対する解読手法を一つ取り上げ、解説してください。簡単なものでも 　構いませんが、可能な限り自分の理解の限界に挑戦してもらえると嬉しいです。 ■問3-S：あなたの好きな秘密鍵暗号を一つ取り上げ、解説し、実装してください。 　実装言語は問いませんが、あなた以外の人が読んで理解できる程度のコメントを書いてく 　ださい (理解できるのであればなしでもOKです)。 ■問4-S：問3-Sで取り上げた暗号は応募時点で「安全」ですか？ 　解読手法があればそれを一つ解説し、安全ならばその理由を解説してください. ---------------------------- ■問4(補足)：解読手法があり、余裕があるならば、それを実装してください. ■問5：自己アピール可能な事柄があればここに書いてください. ■問5(補足)：これまでの実績や本課題を進める過程で実装した他のスクリプト等が存在 　するgithubリポジトリや学んだ結果を書いたブログ記事があればそれも掲載いただいて 　構いません。何もなければ美味しいカレーの作り方でも研究室の話でもなんでもOKです。 ============================================================================== L-II 暗号のままで計算しようゼミ ============================================================================== # 前文 採点は加点式、かつ部分点が存在します。原則的に文字数制限はありません。ただし、意味的に同一の内容であればより短いものを高得点とする場合があります。長過ぎることによる減点はありません。 フォームの文字数制限を超える場合は、フォームに記載した情報が閲覧のための必要十分条件となるような手段であればどのような手段で提出しても構いません。(URLを知っている人間だけが閲覧できる手段でURLをフォームに記載するなど) 最低限解くべき課題は調査課題1問(課題1)、プログラミング課題1問(課題2.1・課題2.2のいずれか)の構成です。問題文が長いように見えますが、誤解がないように可能な限りの注意を払ったのと、最小限の回答をする際に不必要な苦労をすることがないように配慮したことが要因と考えています。 # 課題１ 準同型暗号は若い分野です。そのため、全体像を把握するためには様々な断片的情報をつなぎ合わせる必要があります。この課題はあなたの意欲と調査力を問う課題です。 準同型暗号について、あなたの知るところを述べなさい。ただし、その際に以下の指示を満たしなさい。 ・Garbled Circuit、秘密分散を用いたもの、TEE(Trusted Execution Environment)など(ここでいう"など"は具体的に上げていないものでも良いことを明示的に示す)の１つ以上のセキュアに計算処理を実行する準同型暗号以外の仕組み(一般に秘密計算、秘匿計算、Secure Computationなどと呼ばれる)に比べて、準同型暗号が持つメリットとデメリットを述べなさい。 完全な回答でない場合でも採点において考慮することがあります。また、上記の指示を満たす限りあなたの興味のままに調べた内容を書いてください。興味が在るが理解できなかったことはその旨を記述するだけでも結構です。余計なことを書いて減点されることはありません。引用は可能な限り明記してください。 調査する取っ掛かりになるであろうワード、文献や実装を以下に並べます。あくまで参考であり、これらの全ての文献やワードについて説明ないし触れる必要はなく、またこれらの文献を全く引かなくても問題ありません。 加法準同型暗号(Additively Homomoephic Encryption)、乗法準同型暗号(Multiplicatively Homomorphic Encryption)、部分準同型暗号(Partial Homomorphic Encryption)、LHE(Leveled Homomorphic Encryption)、完全準同型暗号(Fully Homomorphic Encryption)、Paillier暗号、RSA暗号、ElGamal暗号、BFV(Brakerski/Fan-Vercauteren)、BGV(Brakerski-Gentry-Vaikuntanathan)、CKKS(Cheon-Kim-Kim-Song)、GSW(Gentry-Sahai-Waters)、TFHE(Torus Fully Homomorphic Encryption)、格子暗号(lattice encryption)、LWE(Learning With Error)、LWR(Learning With Rounding)、NTRU、SVP(Short Vector Problem) Intel SGX、AMD SEV、Intel TME、ARM Trustzone、RISC-V Keystone クラウドを支えるこれからの暗号技術　第１３章　光成滋生・著　秀和システム・出版(https://herumi.github.io/ango/) 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 https://qiita.com/Cliffford/items/2f155f40a1c3eec288cf https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions https://www.slideshare.net/suzaki/3teeintel-sgx-arm-trustzone-riscv-keystone # 課題２ この課題はあなたの基礎的なプログラミング能力を見るためのものです。採点基準は以下の３点です。一言で言うと、理解度、計算量、独自実装か否か、の順で評価します。 ・コードやコメントから理解度が読み取れるものはそうでないものよりも高い得点をつけます。 ・アルゴリズムへの理解度が同等な場合は、原則的に、計算量が少ない実装に対して高い得点をつけます。ここでいうアルゴリズムへの理解度は講師の考える最適に最も近いアルゴリズムのことではなく、実際に提出したアルゴリズムのことです。つまり、何処からか引っ張ってきた内容を理解していない実装よりも、低速でも説明のしっかりとしたものに高い点をつける場合があります。 ・コード自体がコピーであったとしても、出典が明記されており、かつそのアルゴリズムを理解していることがコメントから読み取れる場合は、同等の理解度で同じアルゴリズムを独自実装した場合に準ずる評価とします。 以下の２つの課題（課題2.1・課題2.2）のうち、いずれかまたは両方に回答しなさい。 いずれの課題もTFHEの実装に必要な要素を切り出したものであり、課題のための課題ではないことを明記しておきます。課題2.2に関しては昨年度これが必要な部分で詰まる様子が見受けられたために試験的に設けた課題ですので、できなくとも気に病む必要はありません。 提出するプログラムは以下の条件を満たすようにしてください。 ・別途提供されるコードの該当コメント部分を書き換えて製作すること。ただし、該当コメント部分以外の部分の同じファイル内に該当コメント部分で使用する関数を定義することやincludeやimport文を追加するなどは認められる。 ・言語はC,C++,Rust,Pythonのいずれかであること。 ・ライブラリはネットで無償で入手可能または添付によってこちらに提出できるものであれば好きなものを用いて構いません。 ・チェック用の入力と出力の組及びテスト用のシェルスクリプトはコードとともに別途提供します。 ・少なくとも１ヶ月後の自分が理解するのに十分と考える程度のコメントをつけること。 ・計算量やコード量の削減などで特別な工夫を施した場合はそのことがわかるようにコメントをつけてください。ただし、数式を書きたい場合など必要な場合はコメントではなく別ファイルで記述しても構いません。その場合はどの部分について述べているか対応がわかるようにしてください。 ・プログラムが完成しなかった場合は、その場所にどのような処理を書けばいいか、あるいはプログラムのどの行が誤っていると思われるかをコメントで書くと採点で考慮することがあります。 ・こちらでも実行可能になるように配慮してください。 ## 課題2.1 この課題では、整数係数多項式の剰余演算を実装してもらいます。剰余演算とは、割った余りを求める操作のことです。ただし、法、つまり割る側となる多項式はnを自然数としてX^n+1のかたちに限られるものとします。また剰余演算を行う対象の多項式は高々2n-1次とします。つまり、剰余演算の対象となる整数係数多項式をaとすると、aのi次の係数をa_iとするとき、a_iは全て整数であって、a = a_0 + a_1 X + ... + a_{2n-1} X^{2n-1} のように表せます。 具体例として以下の式を与えます。 3X^3-X^2+1 ≡ -3X+2 mod X^2+1 今、n=1024とし、入力として多項式の係数を2n要素の64bit符号付き整数(int64_t)配列として表現したものが与えられるものとします。出力となる多項式をn要素の64bit符号付き整数の配列として返す関数を実装しなさい。ただし、出力となる多項式の係数がオーバーフローを起こさないように入力の係数の大きさが制限されていることは保証されているものとします。 下記のものはヒントです。 ・法となる多項式がX^n+1のかたちに限られていることを利用した最適化を施すことができます。入力の次数も制限されていることに留意しましょう。 ・余談ともいえますが、この課題で挙げた例でX=10にしてみると、実は整数の剰余は多項式の剰余の特殊な場合と考えることもできます。 ## 課題2.2 この課題では、Pを法とする剰余環上の符号なし整数を、複数桁のPより小さい基数p(簡単のためpはPを割り切るとします)の符号付き整数に分解する操作(Decomposition)を実装してもらいます。この分解をもう少し詳しく述べると、分解元の数は[0,P)の範囲の整数で、分解結果はP/p桁(個)の[-p/2,p/2)の範囲に値を取る符号付きの数です。簡単のために、この課題ではこれ以降、ある0でない非負整数lを用いて、P=2^{4l}、p=16と限定します。変換先の各桁は[-16/2,16/2)つまり、{-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}のいずれかの値を取るものとします。 具体例を考えます。l=1の場合を考えると分解元の法はP=2^4=16でこれは単に剰余環上の符号の取り直しなので、→で分解を表すとすると、 15→-1 3→3 となります。 l=2の場合は、分解元の法はP=256となり、1桁目が最初の要素、2桁目が2つ目の要素となるような組で分解後の各桁が表されるとして、 232→(8,-2) 31→(-1,2) となります。232の例では、8-2*16= -24 ≡ 232(mod 256)であり、31の例では-1+2*16=31となっているので正しい結果となっています。 今、l=4とし、入力として16bitの符号なし整数(uint16_t)が入力として与えられるものとします。今説明したような変換の出力を、1桁目が最初の要素、2桁目が2つ目の要素となるような4要素の8bit符号付き整数(int8_t)の配列として返す関数を実装しなさい。 下記のものはヒントです。 ・分解先の桁の範囲で8を含まず-8を含むのは2の補数表現ではこちらが扱いやすいためです。 ・ナイーブには一番上の桁から決めるのが簡単でしょう。 ・16進数への基数変換をして、それから符号付きに直すというアプローチもあります。 ・配列の要素の順番を指定しています。順番は逆になっていたりしませんか。 ・デバッグとしては分解した結果がちゃんと元に戻せるかチェックしてみるのもよいでしょう。 # 課題３ あなたが書き足りなかったことや、過去に自分で作ったものや本ゼミに関連しそうな知識や経験などのアピールしたいことを自由に記述しなさい。特にない場合は未回答でも構いません。 ============================================================================== L-III 準同型暗号アプリケーション開発ゼミ ============================================================================== 本ゼミでは完全準同型暗号の一種である TFHE(Torus Fully Homomorphic Encryption) を利用したアプリケーションの開発を行います。TFHE では論理演算のみ可能であるため、アプリケーションは論理回路を元に構成されます。そのため、このゼミでは準同型暗号に関する一般的な知識と論理回路に関する知識があると望ましいです。 解答においては以下の事項に注意してください。 - 解答は加点方式で評価します。オプション問題は点数が低く設定されているため余裕がある場合に解答してください。 - 完全な解答・実装でない場合でも部分的に評価を行います。余計なことや誤ったことを書いて減点されることはありません。 - 解答の文字数制限はありませんが、できる限り整った文章で解答してください。 - 文献調査を行った場合は URL 等の出典を明記してください。参考にする文献はQiitaやブログ記事など、どのようなものでも構いませんが、論文を読むと良い経験になるかと思います。 - じっくりと取り組むことをお勧めします。 ■問1: 準同型暗号の概要に関する問題です。この問題ではあなたの準同型暗号に関する知識と調査力について評価します。 - 1.1: 準同型暗号には可能な演算の種類や回数によって、大きく以下のような種類に分けられます。 - 加法準同型暗号(Additively HE) - 制限付き準同型暗号(Somewhat HE) - 完全準同型暗号(Fully HE) 実現可能な演算の観点からそれぞれの違いについて述べてください。 ※ これらの手法をまとめたサーベイ論文が存在するため参考にするといいでしょう。 - 1.2: あなたが準同型暗号を用いて作成したいアプリケーションについて述べてください。また、それに関連する先行研究について調査し、概要をまとめてください。作成したいアプリケーションと全く同一の先行研究が存在しても構いません。 - 1.3(オプション問題): 完全準同型暗号を用いた応用研究では、Bootstrapping 処理を行わない Leveled HE による応用が主流です。この理由について考察してください。 ■問2: 論理回路に関する問題です。この問題ではあなたの論理回路に関する知識と応用アプリケーションの実装に必要な実装力を評価します。 - 2.1: 論理ゲートNOT,NAND,AND,OR,XOR を用いて4bitの加算器を設計して回路図を示してください。設計では以下の点に注意してください - 利用する論理ゲートは一種類でも複数種類でもよい。 - 最下位ビットのキャリー入力と最上位ビットのキャリー出力は必要ない。 - 回路図は KiCAD や draw.io, PowerPoint 等のツールないしは手書きで作成する。 - ブロックごとに回路を設計して全体の回路図はブロック同士の接続で示してもよい(例:https://upload.wikimedia.org/wikipedia/ja/d/db/Full_adder.png この場合、半加算器の回路図を別途示してください) - 2.2: 問2.1 で設計した 4bit加算器を TFHE上で実装し、動作することを確認してください。TFHE の使い方は公式サイトのチュートリアル(https://tfhe.github.io/tfhe/coding.html)が参考になります。別添の提出用テンプレートコードはC言語で記述されていますが、以下の要件を満たしていれば他の言語を使っても構いません。 - 準同型暗号の手法としては TFHE を用いる。(TFHE の公式実装である必要はありません) - 秘密鍵生成から入力の暗号化、全加算器での計算、結果の復号を行い、計算結果が正しいことを平文での計算結果を元に検証する。 - 計算処理にかかった時間を標準出力に出力する。(単位はミリ秒) - ビルドに必要な手順をコメントやREADME, Makefile に書き添付する。 ■問3: このゼミやセキュリティキャンプに対する熱意を語ってください。また、アピールできるものがあれば紹介してください。 ============================================================================== L-IV 暗号の脆弱性や攻撃手法を理解して説明しようゼミ ============================================================================== # 全体に関する説明(採点方法や課題の取り組み方について) ## 採点基準について 参考にした文献は(一次情報やkurenaifの動画などを含めて)必ず記載してください。 参考文献の記載がない場合は大幅減点をする可能性があります。 この事前課題では3つの脆弱性に関する設問+1つの自由課題で構成されています。 1つの脆弱性(あるいは自由課題)を深堀りして取り組んでいただいても良いですし、浅くすべての設問に答えても構いません。 深ければ深いほど高得点であり、多くの設問に答えられていればいるほど高得点です。 採点の比重としては A. すべての設問に関して、アドバイザリーや論文、参考文献に書かれているまま答える B. 一つの設問に関して、アドバイザリーや論文、参考文献に書いていないところまで自主的に気になるところを調査し答える。 であれば、合計得点は A < B となるように行います。 よって、自分が興味を持ってより深ぼった内容があれば積極的にアピールしていただければと思います。 時間の使い方としては、一つの脆弱性を調べ尽くしてやることがなくなったら次の脆弱性の調査をすることをおすすめします。 すべての設問に関して、答えそのものよりも導出過程に重きを置いています。 なぜそのようなコードや答えになったのか、わかりやすく書いていただけるとと思います。 計算ミスや実装ミスに関しては大きくは減点しませんが、ミスを防ぐ工夫であったり検証する工夫に関しては加点します。 ぜひそういったものもあればアピールしてください。 ## 使用可能言語について 今回の応募課題で取り上げる脆弱性、及び言語のシェアを考慮し以下を使用可能言語とします。 ビルド方法、計算結果も合わせて記載をよろしくおねがいします。 人が読むことを考慮し、コメント等を振っていただけると助かります。 C, C++, Rust, Go, Python, Ruby, Java, php # 課題 以下の内容から好きな問題を好きなだけ答えてください。 すべてに答える必要はありません。 採点基準に関しては前述したものを参考にしてください。 ## 1. CVE-2020-28052 ### 1-1. CVE-2020-28052 の内容・原因を簡潔に述べてください ### 1-2. 2つの異なるパスワードをランダムに生成し、それをA, Bとします Aをハッシュ化したものと、Bをこの脆弱性がある比較関数で比較した場合、どの程度の確率で一致してしまうのか求めてください。 導出が困難である場合、簡単にするための前提条件を置いて求めても構いません。 もし可能であれば、その前提条件の妥当性に触れて書いてみてください。 この問題の答え方としては「AとBが一致する確率は XXXX% である。」 という表現方法の他にも、様々な視点で結果を整理することが可能です。(最悪ケース、最良ケースなど) 結果の整理に関してもぜひ工夫をしてみてください。 ### 1-3. その他この脆弱性に関して調査等してみたことがあれば記述してください。 ## 2. CVE-2020-1472 ### 2-1. CVE-2020-1472の内容を簡潔に述べてください。 ### 2-2. この脆弱性の原因の一つに、「IVが0で固定されていた」と言ったものがあります。 ではもし仮にIVが0以外の値で固定されていた場合、同様の攻撃手法は成立するでしょうか？ 「IVがこの値であれば成功する」「途中までは成功するがここから先は難しい」等あればその旨を書いてください。 ### 2-3. その他この脆弱性に関して調査等してみたことがあれば記述してください。 ## 3. https://www.ambionics.io/blog/php-mt-rand-prediction このブログを読み、以下の内容に答えてください。 ### 3-1. このブログには2つの値でメルセンヌ・ツイスタの内部状態を復元できると言っているように見えます。具体的に、どのような条件で内部状態を復元できるのでしょうか？ なるべく詳細に、正確に答えてください。 ### 3-2. 一般に、メルセンヌ・ツイスタは624次元の内部状態を持つため、624個の連続した値が必要だと言われていますが、この攻撃手法を用いることにより乱数予測は簡単になるのでしょうか？ どういった条件で、どの程度簡単になるのか記述してください。 ### 3-3. 他に興味のある内容や調査してみた内容があれば記述してください。 ## 4. 自由課題 自分の興味のある暗号技術に対する攻撃方法や脆弱性に関する情報を調べ、わかったこと、わからなかったこと、調べたこと等あれば自由に述べてください。 ## 5. その他 CTFや競技プログラミングの成績、GitHubアカウントや研究内容や成果など、自由にアピールしてください。 暗号に関係ない内容でも構いません。 特になければ好きなYouTuber等でもかまいません。