こちらは脆弱エンジニアの Advent Calendar 2024 の6日目の記事になります

はじめに

おばけですです👻
アウトプット活動をしてみたいとツイートしていたところ、
CODE BLUEのアフターパーティーでお会いした脆弱さんに拾っていただき、このアドカレに誘っていただきました。
YouTubeで投稿されている数々の脆弱ネタがツボにクリーンヒット間違いなし。
これを機にアウトプット活動を頑張っていこうと思います👊∂

この記事の中身は？

4ROUNDのAESに対するintegral攻撃についてを書きます👻

セキュリティキャンプ2022の暗号解読ゼミで行った内容を、記事という形でアウトプットします。暗号解読ゼミでは各々が取り組みたいテーマに対して、講師陣の方々に文献、読み方、理解の手ほどきやコーディングのアドバイス等を頂きました。つまり全部です。

当時のコードやスライドが乗っかっているGitHubのリポジトリはこちらです。

AES(Advanced Encryption Standard)ってなぁに

一言でいうと、世界のスタンダードレベルに使われている共通鍵暗号です👻
共通鍵暗号の中でも、データを一定のサイズ（ブロック単位）で処理するブロック暗号に分類されます。

お手元のスマホのWi-Fi、ネットワーク一覧をご覧ください！
なんだか末尾にWPA3とかWPA2とか書いているWi-Fiが見えてきませんか？？？？？学生の方だと、よく使うであろうWi-Fi、eduroamがWPA2です。Wi-Fiのプロパティ欄にあるセキュリティの種類で確認できます。
端的に言うと、このWPA3やWPA2で使われている暗号化アルゴリズムがAESです。なんて身近なんだ。。。。

このAESは、暗号として決められたように運用すればとても強い暗号です。強いのもそのはず、AESは米国商務省標準技術局(NIST)によって強い暗号の公募を行ったことで、世界中から寄せられた暗号の中から選ばれたものだからです。AESが選ばれた過程については、こちらの記事にかかれてありますので、ぜひご覧ください。

AESには、以下の特徴があります。

要件
ブロック長	128bit
鍵長	128, 192, 256bit
構造	SPN構造

また、鍵長に応じたラウンド数は以下です

鍵長	ラウンド数
128bit	10回
192bit	12回
256bit	14回

今回は、鍵長が128bitのAES(AES-128)について取り扱います。
以下がAES(-128)のアルゴリズムです。アルゴリズムの詳細を書いてしまうと長くなってしまうので画像だけで失礼します。こちらはセキュキャン内での発表資料で用いたものです。

integral攻撃ってなぁに

integral攻撃は、AESのようなブロック暗号に対して適用される暗号解析手法の一つです👻
この攻撃では、特定の入力におけるブロックの統計的特性(integral特性)を利用して、暗号の内部状態や鍵を推測しようとします。

通常、良いブロック暗号は「入力データに非線形性や拡散性を持たせる処理を適用することで、ランダム性の高い出力を生成する」という特徴を持っています。しかし。その過程で意図せず伝搬される特定のパターンや性質を突くのがintegral攻撃のポイントです。

この手法では、以下の4つのIntegral Propertyを使用します。

1. ALL (A): 
   集合内のすべての値が等しい回数出現する。
   例: nビットのデータ空間で 2^n 通りの値がある場合、それぞれが等しい頻度で現れる。

2. BALANCE (B): 
   集合内のすべての値の排他的論理和（XOR）が0になる。

3. CONSTANT (C): 
   集合内のすべての値が一定（固定値）である。

4. UNKNOWN (U): 
   集合がランダムな値から生成された場合と区別がつかない。

これだけ言われてもなんじゃこれって感じですよね。次の章あたりで具体的にAES上でのIntegral Propertyの話を入れようと思います。元論文から引用しまくります。

integral攻撃ではまず、攻撃者が上に書いたような特性があるような入力を作成します。これによって、暗号アルゴリズムの内部が特定のパターンを持つようにする、といった前提が必須です。このように、好きに入力を操作できる状況での攻撃のことを 選択平文攻撃（CPA） と呼びます。

一般的に暗号のアルゴリズム自体は世に公開されています。それを用いて、この平文が暗号内部でどのように伝搬されているか、また出力がどうなったかを解析することで、鍵を推測したりするのがintegral攻撃です。

攻撃していくよ！

誤解のないように先に述べます。AES-128は当記事の執筆時点では脆弱ではありません。しかしそれはAES-128を正しく扱った場合です。AES(Advanced Encryption Standard)ってなぁにの章で、AES-128は10ROUNDと書いた気がします。この10ROUNDを4ROUNDにまで落としてやっと、このintegral攻撃は適用可能になります。非脆弱だな〜。

AESの元となる Rijndael の場合、以下のようなインテグラル識別子を持ちます。

引用: Integral Cryptanalysiの Table3. A four-round fourth-order integral for Rijndael with 232 texts.

この図に準拠した説明をします。まず攻撃者は、左上から右下にかけた対角成分がALL(A)となるような2^32個の平文を用意します。すると、1ROUND目の暗号化終了時に、各行はACCCと、同じ形を取るようになります。2ROUND目終了時には、各行が持つ値は変化するものの、それぞれALL特性を持つようになります。次の3ROUND目終了時には更に変化し、すべてのセルで同じALL特性をとります。4ROUND目終了時には、すべてのセルがBALANCE(B)特性（すべての値のXORが0になる特性）を持つ状態になります。
つまり4ROUNDのAESは、特定の入力に対して偏りのある出力を返しているため、ここが攻撃の鍵となります。

以下に、攻撃で用いるコードを乗せます。4ROUNDのAES-128のコードはこちら

01 from aes_128 import *

02 def make_integral_text():
03     """
04     integral攻撃で用いる文章集合の配列作成
05     int型で len = 16
06     """
07     text_set = []
08     for i in range(256):
09         tmp = []
10         all_A = i
11         tmp.append(hex(all_A)[2:].zfill(2))
12         for _ in range(15):
13             tmp.append("00")
14         text_set.append("".join(tmp))

15     key = '5468617473206D79204B756E67204675'
16     enc_text_set = []
17     for message in text_set:
18         aes_128 = AES_128(message, key, N=4) 
19         enc_text_set.append(aes_128.encrypt())
20     return enc_text_set

21 if __name__ == '__main__':
22     import itertools
23     enc_text_set = make_integral_text()
24     cand = []
25     for block in range(16):
26         cand_block = []
27         for cand_tmp in range(256):
28             tmp = 0
29             for i in range(256):
30                 tmp ^= AES_128.aes_inv_sbox[enc_text_set[i][block] ^ cand_tmp]
31             if tmp == 0:
32                 cand_block.append(cand_tmp)
33         cand.append(cand_block)

34     test_p_text = '54776F204F6E65204E696E652054776F'  # テスト用平文
35     test_key = '5468617473206D79204B756E67204675'  # テスト用鍵
36     aes_128 = AES_128(test_p_text, test_key, N=4)
37     test_c_text = aes_128.encrypt()  # テスト用暗号文

38     for i in itertools.product(*cand):
39         key = AES_128.inv_make_round_key(list(i), 4)[0]
40         bin_128 = []
41         for i in range(16):
42             bin_128.append(bin(key[i])[2:].zfill(8))
43         key_tmp = "".join(bin_128)
44         aes_128_tmp = AES_128(test_p_text, key_tmp, N=4)
45         if aes_128_tmp.encrypt() == test_c_text:
46             ans_key = key
47             print(ans_key)

48     print(ans_key == [84, 104, 97, 116, 115, 32, 109, 121, 32, 75, 117, 110, 103, 32, 70, 117])

~~アドカレの投稿時間が間に合うかわからなかったのでとりあえず全部乗っけてしまいましたが、間に合いそうなので~~以下に各要素の解説を載せます👍️

まずここで、対角成分をALL特性(A)とした平文集合を用意します。

07     text_set = []
08     for i in range(256):  # 256個の平文集合を準備
09         tmp = []
10         all_A = i
11         tmp.append(hex(all_A)[2:].zfill(2))  # ALL特性(A)のバイト
12         for _ in range(15):  # その他のバイトはCONSTANT特性(C)
13             tmp.append("00")
14         text_set.append("".join(tmp))

次に、そのすべてを4ROUNDのAES-128に流し込みます。

17     for message in text_set:  # 平文集合を暗号化
18         aes_128 = AES_128(message, key, N=4)  # 4ラウンドAESを使用
19         enc_text_set.append(aes_128.encrypt())
20     return enc_text_set

ここからは、鍵の一部分の候補のリストを準備します。

24     cand = []
25     for block in range(16):  # 16バイトそれぞれに対して鍵の候補を探索
26         cand_block = []
27         for cand_tmp in range(256):  # 候補バイトを全探索
28             tmp = 0
29             for i in range(256):  # XOR結果を計算してBALANCE特性(B)を確認
30                 tmp ^= AES_128.aes_inv_sbox[enc_text_set[i][block] ^ cand_tmp]
31             if tmp == 0:  # XORが0なら候補として追加
32                 cand_block.append(cand_tmp)
33         cand.append(cand_block)

先程の鍵の一部分の候補の直積を全探索します。

38     for i in itertools.product(*cand): # 部分鍵候補を全探索
39         key = AES_128.inv_make_round_key(list(i), 4)[0] # 鍵を復元
40         bin_128 = []
41         for i in range(16):
42             bin_128.append(bin(key[i])[2:].zfill(8))
43         key_tmp = "".join(bin_128)
44         aes_128_tmp = AES_128(test_p_text, key_tmp, N=4)
45         if aes_128_tmp.encrypt() == test_c_text: # 暗号文が一致するか確認!
46             ans_key = key
47             print(ans_key)

念の為、最初に設定した鍵とans_keyが等しいか48行目で確認しています。

以上が4ROUNDのAES-128に対するIntegral攻撃です。ブロック暗号に対する攻撃ではよく、内部状態を推測して攻撃を行うことがあります。締めの言葉を生み出すのが苦手なので次の章はGPT様に書いてもらいます。読まなくて良いです。

最後に

このように、暗号解析は「解読する」というプロセスそのものが非常に知的で魅力的です✨🧠💡複雑な仕組みを紐解いていく中で、隠れた規則性を見つけたり🔍、予想外の挙動に気づく瞬間が何よりの醍醐味です🎉🚀
この記事を読んで少しでも「暗号、面白そう！😆🔑」と思っていただけたら、ぜひ手を動かしてチャレンジしてみてください！💪🔥
これからも一緒に暗号の楽しさを探求していきましょう👊✨🎶

参考文献(簡略、当記事登場順)

WPA3 WILL ENHANCE WI-FI SECURITY

AESが選ばれるまでの歴史

Integral攻撃の最新動向とMISTY1等への適用

Integral Cryptanalysis