DESはどのように破られたのか

DESには2^56個の可能な鍵があり、これは約7京（72,057,594,037,927,936）個の鍵に相当します。非常に大きく聞こえますが、十分な計算能力があれば体系的に探索できる有限の空間です。

鍵空間の全探索（ブルートフォース）では、正しい鍵を見つけるまでに平均して鍵空間の半分を調べる必要があります。DESの場合、これは約2^55回の試行復号に相当し、現代のハードウェアでは1回あたり数回の演算で済みます。

1997年、RSA Data Securityは、DESで暗号化されたメッセージを解読した人に10,000ドルの賞金を提供しました。Rocke Verserは、インターネットに接続された数万台のコンピューターによる分散コンピューティングの取り組みを統括しました。

96日間の探索の末、鍵が見つかりました。平文は「強力な暗号技術は世界をより安全な場所にします」でした。この取り組みは、DESの解読には数か月と大規模な協調が必要ではあるものの、実際に解読可能であることを示しました。

Electronic Frontier Foundationは、1998年に25万ドルをかけてDeep Crackを構築しました。Deep Crackには1,856個の専用ASICが搭載され、それぞれが毎秒250万個のDES鍵を検査できたため、合計で毎秒900億個を超える鍵を検査できました。

Deep Crackは、DESの鍵空間全体を平均約9日で探索できました。これは、25万ドルを投じた決意ある攻撃者であれば、2週間未満でDESを解読できることの証明でした。

DES Challenges II-1（1998年2月）では、Deep Crackがdistributed.netのボランティアコンピューティングネットワークと連携し、わずか39日でDESを解読しました。Challenges II-2（1998年7月）は56時間で解読されました。

わずか1年で、96日から56時間へと大幅に短縮されたことは、ハードウェアの性能向上と協調体制の改善によって、ブルートフォース攻撃がいかに速く加速するかを示しました。

1999年1月、EFFのDeep Crackはdistributed.netと連携し、わずか22時間15分でDES Challenge IIIを解読し、RSA Securityから10,000ドルの賞金を獲得しました。

この、DESが24時間未満で解読可能であることを決定的に示した実証によって、DESの安全性を擁護する議論は事実上終わりました。NISTはその直後にDESの後継を選定するプロセスを開始し、それがAESとなりました。

Distributed.netは、一般のインターネットユーザーがCPUサイクルを提供するボランティアコンピューティングの取り組みを組織しました。最盛期には、数十万台のコンピューターが参加しました。

各コンピューターは鍵空間の異なる部分を検査し、中央サーバーによって調整されました。これは、暗号解読のための分散コンピューティングというモデルを先駆けたものであり、現在でも古い暗号の解読などのチャレンジに使われています。

鍵空間の全探索が機能するのは、各DES復号が高速であり（ハードウェア上ではマイクロ秒単位）、それぞれが独立しているためです。鍵Nの検査と鍵N+1の検査の間には依存関係がないため、何台のマシンにも完全に並列化できます。

この、いわゆる恥ずかしいほど並列化しやすい性質により、ハードウェアを2倍にすると所要時間は正確に半分になります。マシンを追加すれば線形に高速化できるため、攻撃者にとって費用対効果が高くなります。

Eli BihamとAdi Shamirは1990年に差分解読法を発表しました。これは、入力ペアの差分が暗号のラウンドを通じてどのように伝播するかを利用する手法です。DESに対しては、理論上2^47個の選択平文が必要です。

DESのS-boxは後に、差分解読法への耐性を考慮して設計されていたことが明らかになりました。これは、NSAが1970年代にこの手法を知っていたことを示唆します。この攻撃は理論的には impressive ですが、実際にはハードウェアによるブルートフォースに太刀打ちできません。

Mitsuru Matsuiは1993年に線形解読法を発表しました。この手法では、DESを攻撃するために2^43個の既知平文が必要です。Matsuiはこの攻撃を実装し、1994年に実験的にDESを解読して、理論分析を裏付けました。

線形解読法は、S-boxの動作に対する線形近似を見つけ、それを統計的な偏りとともに利用して鍵ビットを復元します。理論上はブルートフォースよりはるかに少ないデータで済みますが、ハードウェア攻撃が登場するまでは実用的ではありませんでした。

差分解読法は1990年に発表されましたが、選択平文を必要とするため、ほとんどの実際の状況では実用的ではありません。線形解読法は1993年に発表され、既知平文で機能しますが、2^43個の既知平文が必要です。

ハードウェアによるブルートフォース攻撃（Deep Crack）は、1999年に22時間でDESを解読しました。実際には、理論的な暗号解読技術の進展よりもハードウェア攻撃のほうが破壊的でした。特別な平文と暗号文の組み合わせをまったく必要としなかったためです。

DESが公開の場で記録に残る形で解読されたことは、政策に直ちに影響を与えました。DES Challenge Iが成功したのと同じ1997年に、NISTはAESの競争選定プロセスを開始しました。この競争は、DESの標準化プロセスの弱点を避けることを明確な目的として設計されました。

AESの開発中、銀行や政府機関は暫定措置として3DESへの移行を始めました。DESの解読に要した期間が、AESの採用に向けた取り組みの緊急性とスケジュールを直接決定しました。

DES解読の歴史についての理解度を確認しましょう。

DESは次第に速く解読されるようになりました。1997年には96日、1998年には56時間、1999年には22時間でした。EFFの25万ドルのDeep Crackは専用ASICを使い、毎秒900億個の鍵を検査しました。

差分解読法（2^47個の選択平文）と線形解読法（2^43個の既知平文）も理論上はDESを解読できますが、実用上の決定打となったのはハードウェアによるブルートフォースでした。22時間での解読によって、実用可能な暗号としてのDESの役割は終わりました。