Meet-in-the-Middleと時間・メモリトレードオフ

MITM攻撃は暗号を2つの部分に分け、それぞれを独立して攻撃します。攻撃者は一方の端からテーブルを作成し、もう一方の端から一致する値を検索します。O(2^n) のメモリを使うことで、攻撃の計算量を O(2^{2n}) から O(2^n) に削減できます。

Double-DESはDESを2回適用します。C = DES_{K2}(DES_{K1}(P)) です。鍵空間は 2^{112} です。MITM攻撃では、すべての 2^{56} 個の K1 について DES_{K1}(P) を計算して保存します。次に、すべての 2^{56} 個の K2 について DES_{K2}^{-1}(C) を計算し、テーブルを検索します。一致した (K1, K2) が候補です。合計の作業量はわずか 2^{57} です。

手順1：すべての可能な K1 で平文 P を暗号化し、T[DES_{K1}(P)] = K1 というテーブルを作成します。手順2：各 K2 について暗号文 C を復号し、v = DES^{-1}_{K2}(C) を求めます。v ∈ T かどうかを確認します。T[v] = K1 が存在する場合は、2つ目の平文と暗号文の組で (K1, K2) を検証します。通常は1～2個の誤った一致が生じるため、それらを破棄します。

Triple-DES（3DES）は3つの鍵 K1,K2,K3 を使用します。C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))) です。MITM攻撃は適用できますが、より弱い形になります。2鍵3DES（K3=K1）では、必要な作業量が 2^{112} に削減されます。3鍵3DESにも 2^{112} のMITM攻撃が存在するため、168ビットの鍵を使用していても、実効的なセキュリティは約112ビットにとどまります。

Hellman（1980）は、(start_point, end_point) のチェーンからなるテーブルを事前計算し、オフラインの鍵探索を高速化する方法を提案しました。対象のハッシュ値または暗号文が与えられると、それを含むチェーンをHellmanテーブルから検索します。トレードオフは P = N（時間 × メモリ = 空間の定数）です。これはレインボーテーブルの基礎となっています。

レインボーテーブル（Oechslin、2003）は、チェーンの各位置で異なる還元関数を使用することでHellmanテーブルを改良し、誤警報（チェーンの融合）を排除します。ソルトなしのパスワードハッシュの解析に効果的です。検索には O(table_size/chain_length) の時間がかかります。

ソルトとは、ハッシュ化する前にパスワードの先頭へ付加するランダムな値です。H(salt||password) のように使用します。同じパスワードでも異なるソルトを使えば異なるハッシュ値になるため、別のソルトが使われていれば、「password」用のレインボーテーブルは役に立ちません。ソルトはハッシュ値と一緒に保存する必要があります。

AES-128（10ラウンド）に対するMITM攻撃では、通常ラウンド5で分割し、前半5ラウンドを順方向に暗号化し、後半5ラウンドを逆方向に復号して、中央で一致させます。最良の既知の攻撃であるバイクリーク攻撃では、2^{128} が 2^{126.1} に削減されます。実用的ではありませんが、AESにMITM型の手法に対するセキュリティマージンがないことを示しています。

Merkle-Damgard型ハッシュでは、構成によってはMITMにより総当たりより高速に原像を見つけられます。攻撃では、IVから始めてメッセージブロックのテーブルを作成し、対象のハッシュ値から逆方向に検索します。全ラウンドのSHA-256に対しては、依然として約 2^{255} の計算量が必要で、総当たりからの改善はありません。

分解攻撃はMITMをr方向の分割へ一般化したものです。暗号を3方向に分割する場合、ラウンドの前方1/3を暗号化し、チェーンの中央で一致させ、後方1/3を逆方向に復号します。必要な計算量は O(2^{n*2/3})、メモリ量は O(2^{n/3}) で、より均衡の取れたトレードオフになります。

プロトコルでは、次の方法でMITM攻撃を防止できます。高エントロピーのパスワードからKDFで長い鍵を導出して列挙可能な鍵空間を狭めること、鍵がデバイスから外へ出ないハードウェアトークン（FIDO2）を使用すること、または公開鍵認証を使用して列挙対象となる共有秘密をなくすことです。

MITM攻撃は暗号を半分に分割し、2^n のメモリを使って計算時間を 2^{2n} から 2^n に削減します。Double-DESを破ることができ、3DESは対策されていますが実効的なセキュリティは112ビットです。レインボーテーブルはパスワード解析にMITMの考え方を利用しますが、ソルトによって防止できます。次はタイミング攻撃とサイドチャネル攻撃です。