ブロック暗号で使われるECBモードについて(AESに限った話ではないけれど).
Wikipediaでも言及されているが, 平文ブロックが同じであれば暗号ブロックも同じになるという弱点がある. 今回はその弱点を突いた攻撃について考える.
例として適当な平文Pを与える. 1ブロックを16 [bytes]とする.
P1 : HOGEHOGE | PIYOPIYO
P2 : PIYOPIYO | HOGEHOGE
P3 : HOGEHOGE | PIYOPIYO
これらを暗号化した暗号文Cのブロックは
P1 -> C1
P2 -> C2
P3 -> C3
となるが, このときC1 = C3 として得られる.
暗号化(復号)の際に1つ前のブロックに依存しておらず, 各ブロックが独立している. これを利用すると
平文P = P1 | P2 | P3 | P4 に対応する
暗号文C = C1 | C2 | C3 | C4
のブロックを部分的に入れ替えて(改ざんされて)も復号自体は成功するため中間者攻撃される可能性がある.
たとえば暗号文が
C1 | C3 | C2 | C4
C4 | C3 | C2 | C1
のように並び替えられていても受信側は改ざんされていたかどうかわからない(復号したものが文章として正しいかどうかでわかるかもしれないが).
また, 同じ平文ブロックが同じ暗号文ブロックとして出てくるという性質を利用すると
平文P = [ユーザーの入力 + SECRET]
という状況下であれば選択平文攻撃によってSECRETを特定することができる.
CTFではこのSECRETがフラグになっていたりするが, 実際に運用されているサービスにおいてはCookieだったり機密情報だったり, まさしくSECRETなものに置き換えて言えることなので注意.
要するにECBモードは使わないようにしようという話. (HMACで改ざん検知はできるためこの表現は誇張し過ぎかもしれない.)
手を動かす
ではSECRETを特定していこう.
先に方法を説明しておくと1文字ずつブルートフォースである.
SECRETのnバイト目をSn { S1, S2, ...} と表す.
1ブロックは16バイトで, 満たない部分はパディングが行われるが今回は考慮しなくてよいので記述を省略する.
繰り返しになるが平文
P1 = | a a a a a a a a | a a a a a a a a |
P2 = | a a a a a a a a | a a a a a a a a |
P3 = | S1 S2 S3 ... | <- ここは暗号化の際にくっつけられる
に対応する暗号ブロックC1とC2は等しい. ただし1バイトでも異なる場合は全く違う暗号ブロックが生成される(これについてはAESの実装を参照)
この時の入力は'a' * 32 だが, これを 'a' * 31 にしてみると
P1 = | a a a a a a a a | a a a a a a a a |
P2 = | a a a a a a a a | a a a a a a a S1 |
P3 = | S2 S3 ...
P1とP2の最後の1バイトだけが異なる状況が作れた.
このときの暗号ブロックC1, C2は
S1 = a であれば C1 = C2 である.
すこし変える.
P1 = 'a' * 15 + [a-zA-Z0-9]
P2 = 'a' * 15
これはつまり
P1 = | a a a a a a a a | a a a a a a a [a-zA-Z0-9] |
P2 = | a a a a a a a a | a a a a a a a S1 |
P3 = | S2 S3 ...
ふぁっ, なんだこれは.
[a-zA-Z0-9] の総当たりで C1 = C2 となる文字が見つかれば S1 が特定できるではないか. たまげたなぁ.
S1が特定できれば次はS2をやっていく.
基本的にはS1と同じである.
P1 = | a a a a a a a a | a a a a a a S1 [a-zA-Z] |
P2 = | a a a a a a a a | a a a a a a S1 S2 |
P3 = | S3 ...
1バイトずらして P2 の末尾に S2 がくるようにした. あとは総当たりで C1 = C2 となる文字を探せば良い.
あとは同様に1バイトずつ特定していけばSECRETが判明する.
バイト数が多くなってくると, どのブロックとどのブロックが同じかを考えるのは面倒なので 16 [bytes]に区切って重複なしの集合位数の変化で検知すればよさそう.
以下, 検証コード.
今回はSECRETが見ればわかるが, 実行するとちゃんと総当たりで特定していることがわかる.
