暗号解読とストリーム暗号

RC4

　ストリーム暗号では、KSAに共有の秘密とする暗号化鍵、および通常公開されているIVを入力することで内部状態を初期化する。またその初期化された内部状態をPRGAに入力することでキーストリームを出力する。

　ストリーム暗号はその内部状態の構成の違いから「線形フィードバックシフトレジスタ（LFSR：Linear Feedback ShiftRegister）型」と「状態遷移型」の2つに区別できる。前者はLFSRから得られるビット列を非線形関数に通すことでキーストリームを生成する方法であり、後者はレジスタ内の情報をスワップなどでランダムに入れ替え、それらの情報自体をキーストリームとして出力する方法である。RC4は状態遷移型の代表的な暗号である（図3-1）。

　RC4は1987年にRSA Security社のRon Rivestによって開発されたストリーム暗号である。前述のように、RC4は開発当初からそのアルゴリズムは非公開とされてきた。しかし1994年にインターネット上にRC4と等価な処理を行うアルゴリズムがRSA Security社の承諾なく公開された。RSA Security社はRC4のアルゴリズムを現在でも公開していない。このRC4と等価な暗号化処理を行うストリーム暗号を正式にはArcfour（Alleged RC4）と呼ぶが、混乱を避けるためArcfourをRC4と呼ぶことにする。

　RC4の特長として非常に短いコードで記述できる点、ソフトウエア上で非常に高速に動作する点などが挙げられる。WEPだけでなく、サーバ／ブラウザ間通信の標準プロトコルであるSecure Sockets Layer（SSL）/Transport Layer Security（TLS）など、さまざまな標準規格に採用されている。

　RC4は8ビットから2,048ビットの間から鍵長を選択できるが、鍵長の安全なパラメータとしては128ビット以上が推奨されている。RC4の内部状態は2^{n}個の要素を持つ配列と2個のポインタから構成されている。nは可変の値であり、一般的にn=8が採用される。したがって、一般には、1バイトの配列を256個有し、2個のポインタを用いて、その配列要素を入れ替えていくアルゴリズムになっている。つまり、RC4のKSA、PRGAはスワップ処理を中心としたアルゴリズムなのである（図3-2）。

RC4の安全性

　RC4自体の解読法に関しては、鍵の全数探索よりも効率的な鍵導出法が知られているものの、現実的な時間で鍵を導出する方法は与えられていない。

　筆者らの研究グループもRC4の解読に取り組み、キーストリームから内部状態（初期値）を推定する方法、さらに鍵を推定する方法を提案している。前者は、内部状態である256バイトの配列のうち、70バイト程度が既知であれば、ほかの186バイトを高い確率で推定する方法であり、後者は鍵の全数探索よりも効率的な鍵導出方法（計算量は2^{96}）である。

　しかしながら、筆者らを含めて、RC4に関しては、キーストリームが既知であるという理想的な条件であったとしても、現実的な計算量で鍵を導出できるところまでは至っていない。RC4の最大の欠点は鍵とKSAでの処理を行った後での初期値との相関性、さらに初期値とキーストリームとの相関性にある。

　特に初期値とキーストリームの初期の時刻での相関が高いことが問題であり、キーストリームの初期の値（例えば、最初に出力されるキーストリームの1Kバイト）を捨てることによって、安全性を高めることが可能である。次回ではRC4を用いた無線LAN暗号方式であるWEPとその解読法について解説する。