yoshi-camp 2020 参加記
はじめに
yoshi-campを去年に引き続き今年も開催しました。今回はコロナの影響でオンライン開催となり、discord上で発表者が画面共有をする方法を取りました。 参加者はtheoremoonとptr-yudai、僕の3人のみで、3/11, 12日に行いました。 前回はtheoremoonとptr-yudaiの2人が発表したのですが、今回は僕も発表しました。
講義内容としては、現代暗号をメインに取り扱っています。
LLLとCrypto by theoremoon
はじめは格子やSVPといった、LLLを使う上で必要となる概念の解説から始まりました。 その点を踏まえた上で、
- Markle-Hellman Knapsack暗号
- Rolling Hash
- Approximate GCD
のケースにおいてどのような行列をLLLに適応すれば解けるのかを勉強しました。
HITCON CTF 2019 Quals - not so hard RSA writeup by yoshiking
これはタイトルの通りで、HITCONで出されたnot so hard RSAという問題を題材に実際にLLLを使って問題を解いてみよう講義でした。 いくつかのwriteupがあったのですが、hellmanさんのwriteupを参考に講義をしました。
theoremoonは理論ベースで、僕は実際に問題を解いて見ようと言った形でした。 ただ、LLLを適応する上で行列を作れてそうでも、値がうまく出ないケースや近似値を用いてもうまく出る原理、スケーリングする値など、わからない箇所が山ほどありました。
LLL難しい〜〜〜
猫と解く楕円曲線暗号 by ptr-yudai
弊チーム楕円曲線担当が実際にいろいろな攻撃手法を解説してくれました。 スライドの目次なんですが、
といった、どこかで見たことがあるような目次となっていました。
理論解説→CTFで出題された問題を解くと言った流れで演習をしました。 扱った攻撃手法については、
- Polig-Hellman, baby-step giant-step(sageのdiscrete_log)
- Pohlig-Hellman Attack
- MOV Attack(ちょっとだけ)
- SSSA Attack
を主にしました。 楕円曲線群から加群への写像を考えたりで、頭が爆発しそうなりましたが、なんとか無事終えました。
楕円曲線と少し仲良くなれた気がします。
最後に
zer0pts CTF 2020の準備、運営でドタバタしつつも、なんとかyoshi-camp 2020を行えて良かったです。 また、運営で忙しかったのに、資料をなんとか作成して講義をしてくれたtheoremoon, ptr-yudaiにも感謝です。
おまけ
zer0pts CTF 2020では、私yoshikingはdirty laundryという問題を作成したのですが、非想定解で解けることを防ぐことができず多大なるご迷惑？をおかけしたことを心より深くお詫び申し上げます。
想定解ではLLLを使ってほしかったのですが、paillierで用いる乱数をprngの256bitの値を使ってしまった結果、LLLを使わなくても解ける解法が存在しました（むしろこちらで解いている人が多いと思う）。 幸い、非想定解でもある程度の難易度は保ったままなので良かったのですが、LLLで解いてくれた人には申し訳無さがあります。
prngを埋め込むのミスった〜〜〜〜〜〜うわ〜〜〜〜ん（作問はギリギリにせずに前もって作り、繰り返しチェックをしましょう）
おわり
