関連鍵攻撃

暗号理論における関連鍵攻撃(かんれんかぎこうげき、英: related-key attack)とは暗号解読の形式の一つで、複数の異なる鍵を使用した暗号処理を攻撃者から観測でき、鍵の値は攻撃開始時には未知であるが、鍵と鍵の間に数学的な関連があることが分かっている、という状況で行われるものである。例えば、攻撃者は鍵の末尾80ビットが常に等しいということが分かっている（攻撃開始時にはその80ビットの内容を知らなくてもよい）といったものである。これは一見、非現実的なモデルのように見える。つまり、例えば暗号化処理を人間が行っていて、何らかの関連を持った秘密鍵を使用することを強要することができる、といった状況でなければ成り立たないように見える。しかし、複雑なプロトコルを使って実装されている現代の暗号の中には、暗号理論の研究者による調査が行われていないものもあり、場合によっては関連鍵攻撃が実現可能なものもある。

WEP

関連鍵攻撃によって攻略された暗号プロトコルで最もよく知られた例としては、Wi-Fi無線ネットワークで使用されるWired Equivalent Privacy(WEP)が挙げられる。WEPで保護されたネットワーク中の無線ネットワークアダプタや無線アクセスポイントは全て同じWEP鍵を共有する。暗号化にはストリーム暗号であるRC4を使用する。ストリーム暗号においては、基本的に一度使用した暗号鍵を再度使用することはできない。そのためWEPでは、同じ鍵が使用されるのを防ぐため、各メッセージパケットに24ビットの初期化ベクトル(IV)が含まれている。各パケットのRC4キーはIVとWEPキーを結合して作られる。ここで、WEPキーの変更は手動で行う必要があり、またWEPキーの変更は通常さほど頻繁には行われない。そのため攻撃者の側からみると、各パケットの暗号鍵には全て同じWEPキーが使われていると仮定できる。このことが、WEPの脆弱性を証明する一連の攻撃のきっかけとなった。最も単純に理解できる方法としては「24ビットのIVが取りうる値はたかだか1700万弱通りしかない」という事実を利用した方法がある。誕生日のパラドックスにより、任意の4096パケットを取得したとき、その中に同じIVを共有しているパケットが2つあるという可能性は高いと言える。そして、これはRC4キーについても同じことが言える。これによりパケットに対する攻撃が可能となる。より致命的な攻撃方法としては、RC4の弱鍵を利用して、最終的にWEPキーを回収する方法がある。2005年には、アメリカ合衆国連邦捜査局が公式のデモンストレーションを行い、広く使用可能なツールを使って約3分で攻撃が可能であることが示された ^[1]。

関連鍵攻撃の防止

関連鍵攻撃を防止するアプローチの一つとしては、プロトコルやアプリケーションを設計する際に、暗号鍵同士が互いに単純な関連性を持たないようにする方法が挙げられる。例えば、暗号鍵を生成するときに、鍵の元となる値を暗号学的ハッシュ関数またはその他の鍵導出関数に掛けるといった方法が考えられる。

例えば、WEPに代わって利用されているWi-Fi Protected Access(WPA)では、キーのレベルに「マスターキー(master key)」「ワーキングキー(working key)」「RC4キー」の3つがある。マスターWPAキーは各クライアント及びアクセスポイントで共有され、TKIPというプロトコルで使用される。ワーキングキーは既知の攻撃を防ぐため一定の頻度で作り直されるが、TKIPはこの処理で使用される。次にワーキングキーを48ビットという長いIVと組み合わせて、各パケットのRC4キーが作られる。この設計はWEPのアプローチを真似たものだが、これは第一世代のWi-Fiネットワークカード（WEPの処理をハードウェアで実装している製品がある）でもWPAを利用できるようにするための措置である。しかしながら、第一世代のアクセスポイント全てでWPAを使用できるわけではない。

また、より慎重なアプローチとしては、関連鍵攻撃を完全に防止するように、強化された鍵スケジュール（英語版）を設計に組み込んだ暗号を使用する方法がある。WPAの新バージョンであるWPA2では、このためRC4の代わりにAESを使用している。 ラウンド数を削減したAES暗号に対する関連鍵攻撃も存在はするが、RC4に対する関連鍵攻撃と異なり、実装上実用的が低く、またWPA2のキー生成関数はこの攻撃に耐性を持つようになっている。古いネットワークカードの多くではWPA2は利用できない。

参考文献

[脚注の使い方]

1. Humphrey Cheung (2005年3月31日). “The Feds can own your WLAN too”. SmallNetBuilder. 2011年12月24日閲覧。