関連キー攻撃

暗号化において、関連キー攻撃とは、攻撃者が、最初は値が不明であるが、キーを結び付ける何らかの数学的関係がわかっている複数の異なるキーによる暗号の動作を観察できる暗号解読の形式です。たとえば、攻撃者は、最初はビットが何であるかを知らなくても、キーの最後の 80 ビットが常に同じであることを知っている場合があります。

KASUMI は、128 ビットのキーを持つ 8 ラウンドの 64 ビット ブロック暗号です。MISTY1 に基づいており、3G の機密性と整合性のアルゴリズムの基礎を形成するために設計されました。

マーク・ブランデンとエイドリアン・エスコットは、KASUMIの5ラウンドと6ラウンドに対する差分関連鍵攻撃について説明しました。^[1] 差分攻撃はビハムとシャミールによって導入されました。関連鍵攻撃はビハムによって初めて導入されました。^[2]差分関連鍵攻撃はケルシーらによって議論されています。^[3]

関連キー攻撃によって失敗した暗号化プロトコルの重要な例として、Wi-Fiワイヤレス ネットワークで使用されるWired Equivalent Privacy (WEP) が挙げられます。WEP で保護されたネットワーク内の各クライアントWi-Fi ネットワーク アダプタとワイヤレス アクセス ポイントは、同じ WEP キーを共有します。暗号化には、ストリーム暗号であるRC4アルゴリズムが使用されます。ストリーム暗号では、同じキーを 2 回使用しないことが重要です。これを防ぐために、WEP では各メッセージ パケットに 24 ビットの初期化ベクトル(IV) が含まれています。そのパケットの RC4 キーは、WEP キーと連結された IV です。WEP キーは手動で変更する必要があり、これは通常まれにしか発生しません。そのため、攻撃者は、パケットの暗号化に使用されるすべてのキーが 1 つの WEP キーを共有していると想定できます。この事実により、WEP は一連の攻撃にさらされ、壊滅的な被害をもたらしました。最も理解しやすいのは、24 ビットの IV では 1,700 万通り弱の可能性しか許されないという事実を利用するものです。誕生日のパラドックスにより、4096 パケットごとに 2 つのパケットが同じ IV を共有し、したがって同じ RC4 キーを共有する可能性が高く、パケットが攻撃される可能性があります。さらに破壊的な攻撃では、RC4 の特定の弱いキーが悪用され、最終的には WEP キー自体が復元される可能性があります。2005 年、米国連邦捜査局の捜査官は、広く入手可能なソフトウェア ツールを使用して約 3 分でこれを実行できることを公に実証しました。

関連キー攻撃を防ぐ 1 つの方法は、暗号化キーが互いに単純な関係を持たないようにプロトコルとアプリケーションを設計することです。たとえば、各暗号化キーは、キー導出関数を使用して基礎となるキー マテリアルから生成できます。

たとえば、WEP の代替であるWi-Fi Protected Access (WPA) では、マスター キー、ワーキング キー、RC4 キーの 3 つのレベルのキーを使用します。マスター WPA キーは各クライアントとアクセス ポイントで共有され、Temporal Key Integrity Protocol (TKIP) と呼ばれるプロトコルで使用され、既知の攻撃方法を阻止できるほど頻繁に新しいワーキング キーが作成されます。ワーキング キーは、より長い 48 ビットの IV と結合され、各パケットの RC4 キーを形成します。この設計は WEP アプローチを模倣しているため、WPA は第 1 世代の Wi-Fi ネットワーク カードで使用できます。これらのカードの一部は、WEP の一部をハードウェアで実装していました。ただし、すべての第 1 世代のアクセス ポイントで WPA を実行できるわけではありません。

もう 1 つのより保守的なアプローチは、通常、強力なキー スケジュールを組み込むことによって、関連キー攻撃を完全に防止するように設計された暗号を使用することです。Wi-Fi Protected Access の新しいバージョンである WPA2 では、部分的にこの理由から、RC4 ではなくAES ブロック暗号を使用しています。AESに対する関連キー攻撃はありますが、RC4 に対する攻撃とは異なり、実装するのは実用的ではありません。WPA2 のキー生成機能は、それらに対してある程度のセキュリティを提供できる可能性があります。多くの古いネットワーク カードは WPA2 を実行できません。