【BkP2014 Differential Power】TEAの差分電力解析
本エントリは↓の続きです。
問題
we hooked up a power meter to this encryption box. we don’t know the key. that’s what we want to know. you can encrypt any string of 8 characters on the service http://54.218.22.41:6969/string_to_encrypt
準備
本来はサーバに平文を入力した際のasmの各処理で反転したbit数がグラフで表示される問題だったらしいですが、残念ながらサーバは動いていません。 ただ、CTF終了後に公開されたソースコードをコンパイルしたものを実行するとデータの羅列が手に入ります。（本来はこのデータがグラフとしてプロットされていた） 勉強会では下記のランダムな平文を10個暗号化した際の反転したbit数を配布しました。
asmを読む
与えられたasmを読んでいきましょう。asmといっても各行にコメントで処理の概要が書いているので、アセンブラに慣れていない人でもそんなに読むのは難しくありません。2行目でTEA magicという表現があることからもわかるとおり、この暗号アルゴリズムはTEA (Tiny Encryption Algorithm) です。
add $t1, $zero, $zero# clear out $t1 ; 00004820 addi $t1, $t1, 0x9e# TEA magic is 0x9e3779b7 ; 2129009E
与えられた値はこのasmにおけるTEAの各操作におけるbitが反転した数です。
asmを読んでいくと11行目〜14行目にただ鍵の値を読み込んでいるだけ、という操作があります。
lw $t8, $zero, 8# k0 mem[8-23] = k ; 8c180008 lw $s7, $zero, 12# k1 ; 8C17000C lw $s6, $zero, 16# k2 ; 8C160010 lw $t3, $zero, 20# k3 now our keys are in registers ; 8c0b0014
この操作では鍵のbitのうち1が立っている数と同じ数だけbitが反転していることになります。つまりこの処理の反転bit数は鍵のビット和と同じと考えられます。つまり鍵のビット和ではありますが、鍵の情報を手に入れることができました。
同様に他の操作を見ていきましょう。例えば19行目の下記操作はどうでしょう。
add $s4, $s4, $t8# +k0 part 1 is in s4 ; 0298a020
この操作は与えた平文を4bit左シフトさせたものと鍵を足したものです。この演算はXoRではなくaddであるため、桁上りの影響を受けます。つまりこの操作は入力される平文次第でそのビットが反転する数は異なります。複数の平文を試すことで、鍵の条件を絞っていけそうです。
このようにasmの各処理から鍵が満たす複数の条件式が取り出せそうです。この条件式を満たす範囲に鍵の探索範囲を絞ることで、鍵探索を効率化してみましょう。
解答1 SMTソルバー (Z3) で解く
複数の条件式があるので、SMTソルバーの利用を検討しましょう。 ここではMicrosoftが開発した神ツールZ3を利用します。 Z3の利用方法は下記MMA wikiを見るのをおすすめします。
asmから取り出した条件式をひとまとめにしてz3神にお願いしたサンプルコードです。
この方法でもフラグはとれるんですが、私のラップトップ環境では50分程度の時間がかかります。
解答2 SMTソルバーなしで解く
解答1を勉強会で紹介したところ、参加者の方があっという間に改良版を書いて提供してくれました。
katagaitai #10 differential power without SMT Solver — Bitbucket
こちらのコードでは私の環境ではフラグを見つけるまでが１分程度、全部の処理が終わるまででも8分程度でした。 私ももっと早くアルゴリズムを思いついて早く実装する力を身に着けていきたい所存です。
まとめ
この問題面白いですよね。解法のアイディアが分かればそんなに難しく無い問題だとは思いますが、 アセンブラの各処理のビット反転数から鍵を推測するアイディアを今まで見たことがなかったので、 勉強会でとりあげてみました。
Write-up Links
http://mslc.ctf.su/wp/boston-key-party-ctf-differential-power-crypto-400/
