SECCON2015 オンライン予選

まとめ

SECCON2015 オンライン予選にチーム 0x0 として出ていました。 200+200+100+100 で計 600 点ほどしかチームに貢献できなかったので人権を得られず終了です。ありがとうございました。

解いたもの

Fragment2

ポートをみると HTTP っぽいけどペイロードがバイナリっぽいので「HTTP2 だろうか……？」などと考えました。 調べてみるとどうやらそうらしいので HTTP2 ヘッダの仕様 を眺めながら手動でデコードしました。

Find the prime numbers

本当は Paillier 暗号とかいう名前の暗号だったらしいのですが勉強不足なので知らず……。 ソースコードを眺めて式変形したり適当に殴ったりして解きました。

まず c*o - h が n^2 の倍数になるので何回か (c,o,h) の組を取得して factor にかけて n の候補を絞ると a,b の値がわかります。オイラーの定理を用いて o の mod n^2 での逆元を求めると c * o^(-1) = (n+1)^(ans-1) (mod n^2) となり ans 以外の値がわかっているので y = x^k (mod z) なる k を求める問題になります。

変形後の問題は x,z が互いに素なら baby-step giant-step というアルゴリズムで O(sqrt(z) * log(z)) ぐらいで解けるのですがそのままだと z が n^2 なので大きすぎてつらいです。そこで c * o^(-1) = (n+1)^s (mod a^2) なる s と c * o^(-1) = (n+1)^t (mod b^2) なる t を求めることを考えます。この s,t は前述のアルゴリズムで求められて、あとはオイラーの定理と拡張ユークリッドの互除法と中国剰余定理あたりを持ってくれば s,t から k が求まります。

これで求めた k を使って ans = k+1 として送ったら弾かれたのでよくわからないまま ans=(k%n)+1 としたら通りました。おしまい。明らかに解き方を間違えてます。

Steganography 1

拡張子の gpjb から gif,png,jpg,bmp あたりが連結されているだけだろうと思い適当に画像を抽出したあと並び替えておしまい。

Steganography 3

スクリーンショットの左側に写し出されているバイナリエディタの表示を適当な OCR にかけるとバイナリが得られるので実行します。すると "flood fill" というメッセージが表示されるので、言われたとおりにスクリーンショット中のバイナリエディタの余白領域にバケツツールで黒を流し込むとキーワードが浮かび上がってきます。

右下で意味深な感じでペイントのウィンドウが開かれていて「やられた……」という気持ちになりました。