RC4の内部状態の状態遷移解析

ネットワーク上を流れる情報の保護には暗号技術が不可欠である．共通鍵暗号は単純な暗号化関数の繰り返しによりデータを撹拌するため，数論に基づく公開鍵暗号方式に比べて高速かつコンパクトな実装が可能であり，主に音声データやデータ通信の暗号化に用いられている．ストリーム暗号は共通鍵暗号方式の一種であり，RC4 という状態遷移型暗号が有名である．RC4 は秘密鍵により初期内部状態を作り出すKSA とその初期内部状態を用いて鍵系列を作り出すPRGA の２つのシンプルなアルゴリズムにより構成されており，内部状態を遷移させながら擬似乱数を生成する．この内部状態をS ボックスと呼び，そのサイズは2^n で一般的にはn = 8 が用いられる．RC4 は十分な安全性とシンプルなアルゴリズムによりSSL やWEPなど多くのアプリケーションで広く使われている．RC4 の脆弱性に関する研究に，Recyclable States(あるラウンドのスワップ動作によりスワップされた値がスワップされる前の値と同一のものになる) という特殊な内部状態の状態遷移特性を用いてRC4 の内部状態を解析する状態復元攻撃，KSA に対する既知IV(initial value : 同一の秘密鍵に対して鍵系列を毎回変えるために秘密鍵に付加される値) 攻撃と関連鍵攻撃，秘密鍵によらずKSA 直後の内部状態に偏りがあることを用いたdistinguish 攻撃などがある．これらはいずれもKSA に着目するか，秘密鍵に対してなんらかの特殊な仮定を想定する．
本研究ではRC4 のPRGA に着目し，内部状態の状態遷移において一般化できるような特性を見つけ出すことで内部状態の状態遷移を推定し，既存研究よりも効率的に初期内部状態を復元することを目的とする．

Top