SECCON 2017 online CTF の問題がGitHubで公開されたので、これを後追いでやってみた記事になります。
後追い記事の一覧はこちら
SECCON 2017 online CTF を後追いでみっちりやってみよう!
問題
Simon and Speck Block Ciphers https://eprint.iacr.org/2013/404.pdf Simon_96_64, ECB, key="SECCON{xxxx}", plain=0x6d564d37426e6e71, cipher=0xbb5d12ba422834b5
100点問題のCrypto。
事前調査
ブロック暗号の一種らしい。
リンク先のPDFを読み込む・・・のは時間がかかりそうなので、まとめたサイトがないかググる。...日本語サイトはなさそう。
Wikipedia: Simon (cipher)
今回Simon and Speckの中でもSimonの方がメインっぽいので、このWikiが近そう。
が、ちらっと読んで放棄。中身わかってなくてもなんとかなるんじゃない?
まずは、
Simon_96_64
これが何を表しているのか、PDFを読んでみる。(というよりは、この数字のセットを探してみる) blockサイズとkey長を指しているっぽい。
Simon block size: 64 key size: 96
解法
既存の暗号方式であること、2013年に発表されていることから、何かしらツールがあると信じて
GithubでSimon Spec
で検索してみる。
おお、たくさん出て来た!20repositoryもHitした。
この中にはもちろん攻撃用・keyを知るためのものはなく、今回のわかっていない桁数が4桁のため、planeをkeyを変えながら暗号化していって、cipherが与えられたものと一致したら終了
というブルートフォースで行けそう。と目星をつける。
そうと決まれば、どれを使うか。今回はちょっと遅いかもしれないけれどpythonがよかったので、
こちらのツールを使わせていただくことに。
inmcm/Simon_Speck_Ciphers
READMEも書かれていてtestコードもあるし、すぐ使えそう。
こちらを使って作成した総当たりプログラムがこちら。
from simon import SimonCipher from itertools import product key_prefix = "SECCON{" plain = 0x6d564d37426e6e71 cipher = 0xbb5d12ba422834b5 candidates = [chr(i) for i in range(48, 48+10)] + \ [chr(i) for i in range(65, 65+26)] + \ [chr(i) for i in range(97, 97+26)] + ["_"] # print(''.join(candidates)) # 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_ for i in product(candidates, repeat=4): key = key_prefix + ''.join(i) + '}' my_simon = SimonCipher(int(key.encode("utf-8").hex(),16), mode='ECB', key_size=96, block_size=64) simon_ciphertext = my_simon.encrypt(plain) if(hex(simon_ciphertext) == hex(cipher)): print("flag: " + key) break
※ candidatesは今回、Vigener3dの時の問題に書いてあった候補と揃えた(flagのためと思われる{}
は除いた)。ここが足りていなかったら永遠に正解は出ないし、余分に入っていたら計算に時間がかかる。一文字違うだけでもエライ違いかも。
どこかにflagに使用される文字列の規定が書いていないか探してみたけど、特に見つからず。不安を感じつつリストアップ。(_
とか!?
とか、入りそう)
しばらく回していると、無事flagをゲットできました。
ちなみに、ちょっといいマシン(MacBook Pro 2016モデル)が偶然うちにあったので、うちの可愛い2011年モデルのMacBook Airと「よーいドン」で回してみたのですよ。
MacBook Pro (13-inch, 2016, Four Thunderbolt 3 Ports) プロセッサ 3.1 GHz Intel Core i5 メモリ 16 GB 2133 MHz LPDDR3 MacBook Air (11-inch, Mid 2011) プロセッサ 1.6 GHz Intel Core i5 メモリ 4 GB 1333 MHz DDR3
Proは3分、Airは8分かかりましたよ。普段そんなに性能差を感じることはないのですが(画像や動画をゴリゴリするときくらい)、こういう時は如実に差が出ますね。
新しいPC欲しい・・・。
itertools
今回「さぁブルートフォースだ!」となった時に、(プログラム的に)効率よく簡単に回す方法を探そうと python ブルートフォース
というなんとも安直なワードで検索してみた。
この辺をみて、itertools
を使うと簡単に書けそうだということがわかり、今回使ってみた。
今後も何かとお世話になりそうなのでメモ。