ページ

2017/12/28

Simon and Speck Block Ciphers (Crypto, 100)

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を使うと簡単に書けそうだということがわかり、今回使ってみた。
今後も何かとお世話になりそうなのでメモ。

0 件のコメント:

コメントを投稿