オランダのセキュリティ企業「Riscure」が主催する、世界初のAutomotive CTF（と謳う）「RHme3」のオンライン予選が、2017年8月7日 12:00（CET）から2017年8月28日 12:00（CET）まで開催されました。
News - RHme3
https://rhme.riscure.com/3/news
オンライン予選で上位500位以内に入ると、Arduino互換の改造基板がRiscureより送られてきます。 改造基板を用いた本戦は、2017年11月1日から2018年3月1日まで開催される予定です。 オンライン予選の問題は全3問あり「正答数が多い順、同率ならば先に正答した順」で順位が決定します。
当該CTFに参加した結果、オンライン予選を173位で通過し、無事に改造基板を入手する権利を獲得しました。 今回の記事から3回に渡って、当該CTFのWriteUpをお届けします。 今回は第1問のWriteUpです。
第1問
問題名：White Box Unboxing
問題文：Here is a binary implementing a cryptographic algorithm. You provide an input and it produces the corresponding output. Can you extract the key?
問題ファイル：whitebox
問題ファイルの解析
問題名と問題ファイル名から、White-Box暗号（詳細は後述）に関する問題であると推測できます。 問題ファイルのファイル形式を調べると「x86-64 ELF」形式であると分かります。
$ file whitebox
whitebox: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=417f6c8e54c3c7ebf8f76772faae13bdb78ddbce, stripped
実行すると、使用方法が表示されました。
$ ./whitebox
usage:
method a) ./whitebox [16 bytes plaintext]
method b) ./whitebox --stdin
16byteの平文を受け付けるようです。 method a)の方法で実行します。
$ ./whitebox 0123456789abcdef
e2 ce a3 58 25 82 6c 8c 5d 3e 7d 6c ea 9d 98 f1
入力文字列とは異なる16byteの16進数文字列を出力しました。 16byteの平文を16byteの暗号文に暗号化するようです。 method b)の方法でも実行します。
$ ./whitebox --stdin
0123456789abcdef
e2 ce a3 58 25 82 6c 8c 5d 3e 7d 6c ea 9d 98 f1
「--stdin」オプションを付けて実行すると、標準入力待ちになります。 16byteの平文を入力しEnterを押すと、method a)で実行したときと同じ暗号文が出力されました。 途中に改行を入れて実行します。
$ ./whitebox --stdin
0123456789
abcdef
83 f8 1e ec 84 81 e0 83 a7 78 fb 1a 24 45 59 17
異なる暗号文が出力されました。改行も1文字と解釈するようです。 最後の1文字を変えて実行しました。
$ ./whitebox --stdin
0123456789
abcdeX
83 f8 1e ec 84 81 e0 83 a7 78 fb 1a 24 45 59 17
同じ暗号文が出力されました。先頭から16文字しか読み込まないようです。 平文と暗号文が16byteに制限されていることから、16byte（128bit）を処理単位とする暗号アルゴリズムをWhite-Box暗号化しているのであろうと推測できます。 次に、White-Box暗号について説明しつつ、問題ファイルに実装されている暗号アルゴリズムの特定を行います。
White-Box暗号の仕組みと暗号アルゴリズムの特定
White-Box暗号は、2002年にStanley Chowらによる論文「White-Box Cryptography and an AES Implementation」[1]で発表されました。 White-Box暗号は「攻撃者は暗号化（復号）処理が行われる環境をフルコントロール可能」という条件下で、秘密鍵が漏洩しないことを目的とした暗号方式です。 「フルコントロール可能」とは、例えば、暗号化（復号）処理を行うバイナリファイルに対するリバースエンジニアリングや、暗号化（復号）処理中にメモリダンプを実行可能という意味です。 このような前提が当てはまるケースとして、DRMや各種IoT機器などが挙げられます。 White-Box暗号では、内部で計算される値（e.g. AESの場合、SubBytes後の値やMixColumns後の値）を事前に計算しておき、計算結果をルックアップテーブルとして保持しています。 計算に用いる秘密鍵を保持する必要が無くなるため、リバースエンジニアリングやメモリダンプによる単純な秘密鍵の抽出は不可能になります。 秘密鍵を更新すると計算結果が変わるため、ルックアップテーブルも更新する必要があります。 原著論文は [1]ですが、James A. Muirによる調査論文「A Tutorial on White-box AES」[2]が非常に分かり易いので、詳細は当該調査論文を参照して下さい。
「unprotected」なWhite-Box AESのルックアップテーブルは3種類あり、TBoxesTyiTables（8bit入力、32bit出力）とTBoxes（8bit入力、8bit出力）とXORTables（8bit入力、4bit出力）です（ [2], pp.6-8）。 TBoxesTyiTablesとXORTablesは最終ラウンド以外のラウンドで、TBoxesは最終ラウンドで使われます。 AESの最終ラウンドではMixColumnsが行われないので、このような違いがあります。 問題ファイルを逆アセンブルします。 以下は「objdump --no-show-raw-insn -d whitebox」を実行した結果です。 上から眺めていくと、ルックアップテーブルの初期化処理を行っている（と思われる）部分を3箇所見つけました。
32bit値を格納しています。
40116e: movl $0x62574013,0x265048(%rip) # 6661c0 <stdin@@GLIBC_2.2.5+0x1140>
401178: movl $0x23687f6d,0x265042(%rip) # 6661c4 <stdin@@GLIBC_2.2.5+0x1144>
401182: movl $0x5e43543b,0x26503c(%rip) # 6661c8 <stdin@@GLIBC_2.2.5+0x1148>
40118c: movl $0xad120599,0x265036(%rip) # 6661cc <stdin@@GLIBC_2.2.5+0x114c>
401196: movl $0x9ff5e24c,0x265030(%rip) # 6661d0 <stdin@@GLIBC_2.2.5+0x1150>
4011a0: movl $0x8dfbec50,0x26502a(%rip) # 6661d4 <stdin@@GLIBC_2.2.5+0x1154>
4011aa: movl $0xdc3d2ac7,0x265024(%rip) # 6661d8 <stdin@@GLIBC_2.2.5+0x1158>
4011b4: movl $0x1d8b9cb0,0x26501e(%rip) # 6661dc <stdin@@GLIBC_2.2.5+0x115c>
4011be: movl $0x5841563f,0x265018(%rip) # 6661e0 <stdin@@GLIBC_2.2.5+0x1160>
4011c8: movl $0x87fdea5c,0x265012(%rip) # 6661e4 <stdin@@GLIBC_2.2.5+0x1164>
8bit値を格納しています。
45b17c: movb $0x60,0x20a03d(%rip) # 6651c0 <stdin@@GLIBC_2.2.5+0x140>
45b183: movb $0x6b,0x20a037(%rip) # 6651c1 <stdin@@GLIBC_2.2.5+0x141>
45b18a: movb $0x36,0x20a031(%rip) # 6651c2 <stdin@@GLIBC_2.2.5+0x142>
45b191: movb $0xf4,0x20a02b(%rip) # 6651c3 <stdin@@GLIBC_2.2.5+0x143>
45b198: movb $0x88,0x20a025(%rip) # 6651c4 <stdin@@GLIBC_2.2.5+0x144>
45b19f: movb $0xfa,0x20a01f(%rip) # 6651c5 <stdin@@GLIBC_2.2.5+0x145>
45b1a6: movb $0xe8,0x20a019(%rip) # 6651c6 <stdin@@GLIBC_2.2.5+0x146>
45b1ad: movb $0x52,0x20a013(%rip) # 6651c7 <stdin@@GLIBC_2.2.5+0x147>
45b1b4: movb $0x51,0x20a00d(%rip) # 6651c8 <stdin@@GLIBC_2.2.5+0x148>
45b1bb: movb $0x3a,0x20a007(%rip) # 6651c9 <stdin@@GLIBC_2.2.5+0x149>
4bit値（∵0x0から0xf）を格納しています。
462183: movb $0x0,0x202f36(%rip) # 6650c0 <stdin@@GLIBC_2.2.5+0x40>
46218a: movb $0x1,0x202f30(%rip) # 6650c1 <stdin@@GLIBC_2.2.5+0x41>
462191: movb $0x2,0x202f2a(%rip) # 6650c2 <stdin@@GLIBC_2.2.5+0x42>
462198: movb $0x3,0x202f24(%rip) # 6650c3 <stdin@@GLIBC_2.2.5+0x43>
46219f: movb $0x4,0x202f1e(%rip) # 6650c4 <stdin@@GLIBC_2.2.5+0x44>
4621a6: movb $0x5,0x202f18(%rip) # 6650c5 <stdin@@GLIBC_2.2.5+0x45>
4621ad: movb $0x6,0x202f12(%rip) # 6650c6 <stdin@@GLIBC_2.2.5+0x46>
4621b4: movb $0x7,0x202f0c(%rip) # 6650c7 <stdin@@GLIBC_2.2.5+0x47>
4621bb: movb $0x8,0x202f06(%rip) # 6650c8 <stdin@@GLIBC_2.2.5+0x48>
4621c2: movb $0x9,0x202f00(%rip) # 6650c9 <stdin@@GLIBC_2.2.5+0x49>
4621c9: movb $0xa,0x202efa(%rip) # 6650ca <stdin@@GLIBC_2.2.5+0x4a>
4621d0: movb $0xb,0x202ef4(%rip) # 6650cb <stdin@@GLIBC_2.2.5+0x4b>
4621d7: movb $0xc,0x202eee(%rip) # 6650cc <stdin@@GLIBC_2.2.5+0x4c>
4621de: movb $0xd,0x202ee8(%rip) # 6650cd <stdin@@GLIBC_2.2.5+0x4d>
4621e5: movb $0xe,0x202ee2(%rip) # 6650ce <stdin@@GLIBC_2.2.5+0x4e>
4621ec: movb $0xf,0x202edc(%rip) # 6650cf <stdin@@GLIBC_2.2.5+0x4f>
ドンピシャです。 元の暗号アルゴリズムがAESであると分かったところで、次はAESの鍵長を特定します。 IDA Proを用いて解析したり、メモリアクセスのトレースデータをグラフ化したりして、ラウンド数を特定し、鍵長を求めるという方法もありますが、面倒なのでテーブルの行数を数えます。 White-Box AESの$TBoxesTyiTables$は式（1）（[2], pp.7-8）で表されます。
$$TBoxesTyiTables_{i}(x)=Ty_{i\bmod4}(S(x \oplus \hat{k_i})) \quad (0 \leq i \leq 15) \qquad (1)$$
$x$は1byte値、$\hat{k}_{i}$はShiftRows適用後のラウンド鍵の$i$byte目、関数$S$はSubBytesテーブルです。 関数$Ty$はMixColumns（の途中まで）テーブルです（ [2], p.7）。 $TBoxesTyiTables$の要素数は、
$$CountOfTBoxesTyiTablesElements = CountOfRound \times 16 \times 256$$
です。 $TBoxesTyiTables$の初期化処理を行っている部分（32bit値を格納している部分）の行数を数えると$36,864$行ありました。 従って、
$$CountOfRound = 36864 \div 16 \div 256 = 9$$
です。 前述のとおり、$TBoxesTyiTables$は最終ラウンド以外のラウンドで使われるので、アルゴリズム全体では10ラウンドあることになります。 以上より、元の暗号アルゴリズムは「AES-128」であり、鍵長は16byteであると分かりました。
鍵の抽出
式（1）より式（2）が成り立ちます。
$$TBoxesTyiTables_{i}(x) \oplus TBoxesTyiTables_{i}(\acute{x})\\ =Ty_{i\bmod4}(S(x \oplus \hat{k_i} )) \oplus Ty_{i\bmod4}(S(\acute{x} \oplus \hat{k_i})) \quad (0 \leq i \leq 15) \qquad (2)$$
未知の値は$\hat{k}_i$のみなので、式（2）を満たす$\hat{k}_i$の総当たり（256通り）を16回（∵鍵長=16byte）繰り返すことで、ラウンド鍵を抽出できます。 抽出されたラウンド鍵$\hat{k}$はShiftRows適用後であるため、Inverse ShiftRowsを適用して$k$に戻す必要があります。AESのShiftRowsは左シフトなので、右シフトをして元に戻して下さい。 私はここで時間を無駄にしました。
問題ファイルから$TBoxesTyiTables$（32bit値を格納している部分）を抽出します。 スクリプトを作成しても良いですが、面倒なのでobjdumpの出力結果をコピペ&整形します。 AES-128では、1ラウンド目のラウンド鍵はマスター鍵そのものなので、1ラウンド目のラウンド鍵を抽出するのが効率的です （2ラウンド目以降のラウンド鍵は、マスター鍵に対して逆計算可能な鍵拡張を適用して作成されるので、2から10ラウンド目のラウンド鍵を抽出し、マスター鍵を計算することも可能です）。 1ラウンド目のみ抽出すればよいので、1行目から4096行コピペします。 以下がコピペ&整形結果の抜粋です。
$TBoxesTyiTables$を抽出してから気が付きましたが、当該問題における$TBoxesTyiTables$の定義は式（3）のようになっています。
$$ \begin{eqnarray} \left\{ \begin{array}{l} TBoxesTyiTables_{i}(x)=Ty_{i\bmod4}(S(x \oplus \hat{k_i})) \oplus \alpha_{i\bmod4} \quad (0 \leq i \leq 15)\\ \alpha_0 = 0x008097a6\\ \alpha_1 = 0x00f1688c\\ \alpha_2 = 0x004dee5f\\ \alpha_3 = 0x0059cd41\\ \end{array} \right. \end{eqnarray} (3) $$
$TBoxesTyiTables$の値と$Ty$の値が異なることから気が付きました（特に、$TBoxesTyiTables$に0x00000000が無いことから）。 $\alpha_{i\bmod4}$の値は$TBoxesTyiTables$と$Ty$をソートして差分を計算することで分かりました。 いずれにしても、式（2）のようにXOR演算をすると$\alpha_{i\bmod4}$は消えてしまうので、気にしなくても大丈夫です。
以下が式（2）を元に作成した攻撃コードです。 関数$S$と関数$Ty$の値はGoogleやGitHubで願いを込めながら検索し、コピペしてきます。
実行します。
$ ./whitebox_attack.py
key = 61316c5f7434623133355f525f6f5235
ASCII文字コードの範囲に収まっており怪しいので、ASCII文字に変換します。
$ echo "61316c5f7434623133355f525f6f5235" | xxd -r -p
a1l_t4b135_R_oR5
この文字列がFlagでした。
第1問は「unprotected」なWhite-Box暗号であったため、仕組みを知っていれば直ぐに解ける問題でした。 実際のWhite-Box暗号では、各テーブルの前後に一様ランダムに作成した全単射写像や逆行列を持つ行列を連結し、拡散性と攪乱性を向上させています。 詳細は [2]の4章以降を参照して下さい。 次回は、サイドチャネル攻撃に関する問題のWriteUpです。
