RC4 は最も有名なストリーム暗号で1987 年にRSA Data Security のRon Rivest によって開発された. ストリーム暗号とは, ビット単位またはバイト単位で暗号化を行う共通鍵暗号の一種である. ストリーム暗号の特徴として, データサイズが決まっていなくても逐次暗号化できるという利点がある. RC4 は秘密鍵をもとに擬似乱数を生成し, その擬似乱数と平文の排他的論理和をとることで暗号化を行う. RC4はWired Equivalent Privacy(WEP)やWi-Fi Protected Access(WPA),SSL,SSH など多くのソフトウェアで使用されている. RC4 のアルゴリズムは当初秘匿とされていたが,1994年リバースエンジニアリングによって公開されて以来RC4の脆弱性に関する研究が多くなされてきた. しかしそのシンプルなアルゴリズムと強い安全性により, 開発から20年以上経った今でも商用的に広く利用されている. RC4の解析は主に2 つのアプローチが存在する. Key SchedulingAlgorithm(以下KSA とする) の脆弱性に着目して解析を行う方法と, Pseudo-Random Generation Algorithm(以下PRGA とする) の脆弱性に着目して解析を行う方法である. KSA に対する攻撃には, 初期内部状態が秘密鍵の一次結合に関して偏りがあることを利用した鍵復元攻撃など多くの攻撃が提案されている. PRGA に関しては, 秘密鍵によらず初期内部状態に偏りがあることを理論的に示し, distinguisherの提案や初期内部状態を復元する状態復元攻撃などがあげられる. また最近ではRC4 には鍵長が短い場合にも等価鍵が存在することが理論的に示され,さらにRC4の初期内部状態が2 バイトのみ異なる内部状態をつくり出す秘密鍵のペアが存在することも理論的に示されている.そこで本研究では2バイトのみ異なる内部状態の状態遷移を観察し,出力差分や初期差分位置から初期内部状態を導き出すことを目的とする.

Top