はじめに
こんにちは, g2 と申します.
当初は物理エンジンの話をする予定だったんですが, いろいろ事情があってやめました.
さて, 本題に入りますが, 僕は12月9, 10日に SECCON 2017 for CTF という大会に参加してきました(オンラインです).
CTF って? という方は Wikipedia をどうぞ.
Wikipedia – CTF
東工大からは僕の知る限り2チームが出場しました. 一方はrogyから, もう一方はtraPから1チームずつです.
実は本番ではrogyの方ではなくtraPの方に参加していたりしていなかったり
こういう大きな大会はあまり出たことがなく CTF の経験も浅いので, 簡単な問題しか解けませんでしたが, その中の数問を, 紹介をかねて解説してみたいと思います.
解説(writeup)
Run me!
問題はこんな感じです.
—– RunMe.py
import sys
sys.setrecursionlimit(99999)
def f(n):
return n if n < 2 else f(n-2) + f(n-1)
print “SECCON{” + str(f(11011))[:32] + “}”
—–
問題を要約すると, フィボナッチ数列の第11011項目を求めて, その先頭32桁を出力してください, という問題です.
何も悪くなさそうに見えますが, 実際にこれを実行してみるとどうなるでしょうか. 実は, このプログラムは終了しません.
このプログラム, フィボナッチ数列の第n項を求める方法がよくないのです.
ちょっと 第5項目を求めてみましょう. ここでは, fib(0), fib(1) に関数値を分解していきます.
なんか計算回数が多いですね. この手法, 実は無駄な計算をしています.
一度計算した fib(2) が２回目以降に出現した時, これをもう一度計算し直しています.
なので, 一度計算した fib(n) の値をメモしておけば, 計算回数を減らすことができます.
また, 動的計画法や末尾再帰によって解決するという手法もあるので, 好きなのを選んで実装するといいと思います(ちなみに僕は末尾再帰による計算を選びました).
python で書くとこんな感じ (慣れてないので, もっと簡単に書けるという意見もあるかもしれませんが許してください).
SHA-1 is dead
問題はこんな感じ.
http://sha1.pwn.seccon.jp/
Upload two files satisfy following conditions:
1. file1 != file2
2. SHA1(file1) == SHA1(file2)
3. SHA256(file1) SHA256(file2)
4. 2017KiB < sizeof(file1) < 2018KiB
5. 2017KiB < sizeof(file2) < 2018KiB
* 1KiB = 1024 bytes
この問題を解くには, ハッシュ関数 とは何かをざっくりでも良いので理解する必要があります. ここで言っているのは, 二つのファイルのデータが異なっているにもかかわらずSHA1によって得られるハッシュ値が同一であるようなペアを探してください, というものです. わずかに異なった箇所が存在する2つのデータをハッシュ関数に通しても全く異なるハッシュ値が得られるといった性質からもわかる通り, これを自分で特定するのは至難の技(少なくとも大会時間内には自力では求められない)です. そこで, google 先生に聞いてみましょう.
すると, こんな記事が見つかります.
この中の Attack proof と書かれているところから2つのpdfファイルをダウンロードしてハッシュ値を計算すると, 異なるファイルであるにもかかわらず同じ値が得られます. ってことはこの二つを提出すれば終わりじゃない？って思うかもしれませんが, 残念ながらこれらのファイルは426kb程度であり, 問題文における条件4, 5を満たしていません. ちょっとデータを変えるとハッシュ値が崩れるだろうし, どうやって解こうかなぁと考えつつ上記リンク先をぶらついていたところ, How did you leverage the PDF format for this attack? と書かれた項目が気になり画像を見てみたところ, こんなものが.
この画像曰く, 計算したところは一部分だけで, それ以外のpdfを構成するデータは計算の前後に付け加えたものですよ, とのこと.
ってことは, 適当にデータの末尾に無駄なデータをくっつけてデータ容量を稼げばいいんじゃないか？ と思ったので実際にやってみたところ, 双方のハッシュ値が同じのままで容量を増やすことに成功しました！
というわけでこれを提出してフラグを手に入れたわけです. めでたしめでたし.
さいごに
上で紹介した問題は CTF のジャンルで言う所の, PPC(競技プログラミング的なもの), Crypto(暗号を解いたりする問題) の分野にそれぞれ該当しますが, CTF にはこれらの他にも多くのジャンルが存在しています. 気になった方はgoogle先生に聞いてみたり, 実際に CTF の常設サイト (CpawCTF, ksnctfなどなど) に行って問題を解いてみるといいかもしれません.
というわけで, 僕に記事は以上です.
ここまでご覧いただき, ありがとうございました！