Double DESを破る中間一致攻撃（MITM攻撃）の仕組みとは？

Double DESとは

Double DES（2重DES）は、暗号化にDES暗号を2段階で適用し、復号にはその逆のDES復号を2回使用する方式です。それぞれの段階で独立した鍵を使用するため、実質的な鍵長は56ビット×2＝112ビットに拡大し、単一のDESよりも安全だと考えられてきました。

平文Pと2つの鍵K₁・K₂が与えられると、暗号文Cは次のように生成されます。

C = E_K2(E_K1(P))

復号では、鍵を逆の順序で適用します。

P = D_K1(D_K2(C))

しかし、Double DESには重大な弱点があります。それは「既知平文攻撃」の一種である中間一致攻撃（Meet-in-the-Middle攻撃：MITM攻撃）です。鍵長が112ビットに拡張されていても、この攻撃によって理論的な強度は大きく損なわれます。

中間一致攻撃（MITM攻撃）とは

中間一致攻撃とは、時間と記憶領域（スペース）のトレードオフを利用して計算量を削減する暗号解読手法です。本来必要となる攻撃コストを、この手法によって大幅に引き下げることが可能になります。

この用語は、MerkleとHellmanによって提唱されました。攻撃は、片方の端から暗号化を進め、もう片方の端から復号を進め、両者の結果を中間点で照合します。結果が中間で「出会う（meet-in-the-middle）」ことから、この名称が付けられました。

MITM攻撃では、対象となる問題を2つに分割し、各要素を独立して扱います。これにより、時間Xだけを要する攻撃を、時間Yと記憶容量Zを要する形へと変換できるのです。狙いは、総当たり（ブルートフォース）攻撃に必要な労力を劇的に削減することにあります。攻撃者は解析対象の領域を半分ずつに分けて照合することで、膨大な計算量を現実的に実行可能な規模まで縮小します。

なお、似た名称の「中間者（Man-in-the-Middle）攻撃」はネットワーク攻撃を指し、通信経路に割り込んでログイン認証情報・アカウント情報・クレジットカード番号などを盗み取ることを目的とします。標的になりやすいのは、金融アプリのユーザーやSaaS事業者、ECサイトなど、ログインが必要なサービスです。盗み取った情報は、なりすまし、不正送金、不正なパスワード変更などに悪用される恐れがあります。

Double DESに対するMITM攻撃の手順

鍵K₁とK₂で平文Pを暗号文Cへ変換し、同じ鍵で復号する場合、最初の暗号化で得られる中間値と、最後の復号に関わる中間値Mは必ず一致します。つまり、次の2つの関係式が成り立ちます。

M = E_K1(P) = D_K2(C)

攻撃者の具体的な手順は以下のとおりです。

1. 暗号解読者が平文Pと暗号文Cのペアを1組入手します。
2. K₁のすべての候補（2⁵⁶通り）について暗号化を実行し、得られたすべての中間値Mを記録します。
3. 同様に、K₂のすべての候補について復号を実行し、中間値Mを求めます。
4. 両者のMを照合し、Mが一致するK₁とK₂の組み合わせを探し出します。

一致する組み合わせが1組だけであれば、それが求める鍵K₁とK₂であると特定できます。複数の候補ペアが残る場合は、傍受した別の平文・暗号文ペアを利用して絞り込みを行います。

このように、Double DESの実効的な強度は112ビットどころではなく、約2⁵⁷回の演算（大量の記憶領域を必要とするものの）程度まで低下します。この弱点を克服するため、後にTriple DES（3重DES）などの方式が考案されました。