バランスを取りたい

よくCTFの記事を書きます

SECCON Beginners CTF 2018 Crypto + Scoring

SECCON Beginners CTF 2018でCrypto4問とスコア周りの検討をした話を書きます。 詳細なWriteupについては他で結構上がってるので、解き方の流れとか解説とかを書きます。

また、この記事は自分の担当部分について感想を書いているのであって、解くのに必要な知識等を丁寧に解説するものではありません。

[Warmup] Veni, vidi, vici (559 solves)

"Veni, vidi, vici"というのはシーザーが言った「来た、見た、勝った」のラテン語ということで、問題名からも何の暗号を使っているかは一目瞭然です。

実際の問題ではフラグを3つの部分に分割してそれぞれでちょっと異なる暗号化方法にしました。

Part1: ROT13

これは一番わかりやすいし最初に試すやつですね。

数字の取り扱いに困ってる人が見受けられましたが、ROTではアルファベット以外の文字は無視されることが多いです。 一応 ctf4b が成立するように復号しないといけないので数字はそのままで問題ないことがわかります。

The first part of the flag is: ctf4b{n0more

Part2: ROT18

ROT13では復号にもROT13すれば終わってしまうので、Part2は鍵を変えたバージョンです。

ここで復号後の文字列が読めない場合どの鍵が正解かわからなくなってしまうのですが、今回は The second part of ... という文を入れて鍵がわかるようにしています。 復号には 26 - 18 = 6 ということでROT6すれば終わりです。

The second part of the flag is: _cLass!cal_c

Part3: ROT180

まさかのPart3で人間が読める文字が登場。 文字を180度させてROT180、みたいな感じです。

人間の目ではRがどう見ても大文字だと思うんですが、なぜか小文字でのsubmitが多かったです。環境によって小文字に見えるということは無いはずですが……。 こういう部分を無意識でしっかり合わせられると強いと思います。

ちなみに180度回転はこのサイトでやりました: Lunicode

{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

The third part of the flag is: Rypt0graphy}

Flag: ctf4b{n0more_cLass!cal_cRypt0gr4phy}

RSA is Power (143 solves)

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

RSAをちゃんと見たことがあればN, E, Cが何を示しているか、またNが明らかに小さいことがわかるはず。

鍵長は256bitで、この程度であれば最近のラップトップ環境でも数分で素因数分解を終えることができます。

使うツールとしてはyafuを想定していましたが、Writeupを見る感じmsieveの人が多かったみたいです。 最終的に素因数分解するアルゴリズムは多分同じなので変わらないと思います。

……がしかし。 factordbを使って解いたというWriteupがいくつか上がっていてびっくり。

factordbでは解けないものと思っていましたが、factordbは投稿された合成数を勝手に素因数分解してキャッシュするようで、コンテスト後半はそれで解けてしまう状態になっていたみたいです。

factordbお前……。

なんだかんだでツールを使って素因数分解するとp, qとして2つの素数が出ます。素因数分解にかかる時間はスペックによりますがyafu+MBP(2017)で2分くらいだったかな？

299681192390656691733849646142066664329
324144336644773773047359441106332937713

Flag: ctf4b{5imple_rs4_1s_3asy_f0r_u}

Streaming (113 solves)

暗号問題では往々にして謎のコードが配布され、そこで実装されている更に謎の暗号アルゴリズムを読み解き、復号コードを実装するといった問題が出題されます。 Streamingではそれを模して作問しました。

内容としては線形合同法(16bit)による予測可能な乱数と何故か2バイト単位のリトルエンディアン？っぽい形式で出力されていることの2点がメインになっています。

後者は引っかかる人がいるかなと思って付け足したんですがあんまり引っかかっている様子がなく残念。

Flag: ctf4b{lcg-is-easily-predictable}

Well Known (17 solves)

ここまでの3問さすがに簡単すぎたなーと思って易しめのガチ問を投入。

Signerというクラス名から署名アルゴリズムっぽいことは想像できますが、実際に何のアルゴリズムなのかはわかりません。

コード内に出てくる文字(p, q, g, x, y, r, s)あたりからElGamal, DSAあたりまで絞っていく必要があります。この辺は日本語Wikipediaにも載ってるので常識の範囲。 今回はDSAでした。

次に from flag import FLAG からxにフラグが入っていることを確認します。 xは秘密鍵なのでこの問題はKey recovery attackをしろと言っていることになります。

またWikipediaを見ると、「kに2度同じ値が使われている」とDSAを破ることができると書いてあります。 kは入力のSHA1から生成されているので、SHA1が同じになるデータを用意するとこの攻撃が使えます。

しかしSHA1が同じになるということはSHA256の入力も同じになるわけで、kに2度同じ値が使われていても得られる情報は増えず解くことができません。

勘のいいひとはここでピンとくるはず。SHA1が同じになるといえばSHAtteredですね。

入力としては2KBまでしか受け付けないので適当なところで切ったSHAtteredの組を入れると、

  • kに同じ値を使っている
  • 出力sが異なる

という条件を満たすことができます。

\begin{align*} s_1 = k^{-1}(H(m_1) + xr) \pmod q \\ s_2 = k^{-1}(H(m_2) + xr) \pmod q \end{align*}

から、x, k以外の値はすべてわかっているので連立させて解くとxの値を入手できます。

ctf4b{be_c4reful_w1th_k}

余談

Scoring

今回のBeginners CTFでは問題が少々簡単なこと以外は普通のCTFと同じように運営したいという思いがあり、流行の動的スコアを導入しました。

動的スコアでは解いた人数によって問題の点数が決定されるため、参加者の感じる難易度と実際の点数が剥離しにくいという大きなメリットがあります。 デメリットとしては時間が経って点数が落ち着くまで問題の難易度が読めないという点くらいだと思います。

DEFCONなどではかなり急激に点数が下がるアルゴリズムを採用していますが、Beginners CTFではそれよりも減少が穏やかになるようにしました。 結果として最終的な点数配分はいい感じだったように見えます。

早く解かないと点数が少なくなってしまうという誤解を生む懸念がありましたが、百聞は一見に如かずということで今回はこのルールを導入してみました。 これで今後動的スコアのCTFに出ても安心ですね！