SECCON Beginners CTF 2020 Writeup(Crypto: R&B, RSA Calc)
2020/05/23 〜 2020/05/24に開催されたSECCON Beginners CTF 2020にTeam: r0bu5tのCrypto問担当(?)として参加しました。prprhytです。 せっかくのアウトプットする機会なので、手をつけた分は復習も兼ねてWriteupを書きます。
僕自身は解いたのは2問だったのですが、チームメンバーのおかげで順位は44thでした。
反省点も多いので貢献できるように精進します。。
Writeup
crypto: R&B
与えられたもの
- 符号化されたFlag
- 符号化のソースコード
与えられなかったもの
- FORMAT(後述)
符号化されたFlagと符号化を行った際に使われたらしいソースコードが渡されます。 ソースコードを読むと FORMATという文字列に従って、rot13とBase64で符号化するようでした。 例えばFORMAT='BRBB'の時はBase64->rot13->Base64->Base64と符号化するプログラムのようでした。 厳密には符号化したあとにBase64で符号化した場合はB、rot13で符号化したときにはRが符号化後のFLAGの先頭に足されるので、符号化されたFLAGの先頭から順にBかRかを見て対応するデコーダーで復号すればflagを得られました。 最初はちゃんとソースコードを読んでいなくてもっと複雑なことが必要かと思ってたので時間をかけてしまいました。反省。
crypto: RSA Calc
サーバーがカンマ区切りの逆ポーランド記法+αなフォーマットを受け取り、計算式への電子署名を検証をパスするかつ、計算結果が1337のときにフラグが出力される問題です。 逆ポーランド記法の+ αの部分はシンボルFです。シンボルFが入力されるとその時点でのstackから値を一つ取り出して1337であるかチェックします。チェックが通ったらFlagが出力されるというものでした。
また、サーバー側のプログラムは計算式への署名機能と計算式の実行機能を持っていました。
署名機能:
入力: data: カンマ区切りの逆ポーランド記法+αの形式で計算式を渡す
出力: signature(署名)が出力される
制限: 署名のdataにF、または1337が含まれていると署名をしてくれない
計算式の実行機能:
入力: data(計算式), signature
出力: 計算結果, Fが入力され時点での計算結果が1337のときにflagを出力
制限: signatureの検証に失敗するとエラー
解法の方針としてはFlagを取れるような計算式への署名をサーバーの署名機能で打つことはできないので、署名を偽造する方針を取りました。
サーバーに実装されていた署名の式は sig = md mod Nで、mが合成数でm1, m2に因数分解可能なとき、
sig1 = m1d mod N
sig2 = m2d mod N
とすると、
sig == sig1*sig2 mod N
を満たします。
また、サーバー側は受け取った数式をbytes_to_long()でlong型へ変換してから署名を打っていました。
よって、目標の式を1337,Fとしたときにbytes_to_long(b'1337,F')==m1 * m2を満たすm1, m2をサーバーに与えて署名を打ち、
あとは前述の通り、得たsig1,sig2から1337,Fに対応する電子署名をローカルで作成してサーバーの計算機能に式1337,Fと一緒に署名を入力するとFlagを得ることができました。
余談1: 当初はサーバーへのバイナリの送信はecho -e '\x01' | pbcopy をしてncコマンドの入力に貼り付けて送信していたのですが、うまく送信できなかったので、最終的にはGoでsocketクライアントを書いてサーバーとやり取りをしていました。
余談2: 最初はdが小さいと仮定してDLP解けばいいよね...とBSGSアルゴリズムをまわしましたが、dは十分に大きいようで時間がかかりうまく行かなかったため、上記の方針に切り替えました。 あと、色々な検証を@souring001君と進められたので一人でやるよりとても気が楽でした。感謝...!
チームメイトに解いてもらった or 手をつけたけど解けなかった問題
crypto: Noisy equations
詰まっていたら、@souring001君が解いてくれました。感謝...! 連立方程式を解く方針で解けるそうです。
追記2020/05/24 10:30: 参照: qiita.com
crypto: Encrypter
暗号文のサイズの変化具合からブロック暗号っぽいとは思って色々こねくり回し、ラスト30分くらいでCBCモードぽいことに気づきました。が、時間切れでした... 大会終了後にTwitterで他の人のつぶやきを調べたところ、CBC Padding Oracleで解けるようです。 確かに不正な暗号文を投げるとエラーが出ていましたが、Paddingチェックエラー由来だということに気づけませんでした...(終
感想
反省点としては、解くに前半は一つの問題に集中して取り組めなかったことです... 解けなそうと思ってすぐに手放して他の問題をやってしまうことがありました。 適宜休憩とったほうが良いなという反省もあります。 とりあえず、チームメンバーには感謝です🙇 大きく実力不足を感じたので、今後も精進していくぞ..!
