RC4／ arcfour の 調 査

2002 年 2 月

白石 善明  の調査¾¼¼¾ 年 ¾ 月

 はじめに  以下  と呼ぶ は  年に  社の    により開発された可変長な秘密鍵を利用できるストリーム暗号である． は，     プロトコルにも暗号化アルゴリズムの一つとして組み込まれ，また   !  プロトコルにも組み込まれている．
 においてはユーザの秘密鍵と初期化ベクトル "# を結合させたものをセッ
ション鍵として利用している．最近，文献 $ % で似通ったセッション鍵を使えば
 の出力系列は似通ったものとなる性質を利用して， & ビットの秘密鍵が推定されるという報告がされている．そして文献 $&% で， を使っている実際の無線 ' 環境でスニファ パケットキャプチャプログラム を動作させて，文献 $ %の攻撃法を利用し，盗聴したパケットから秘密鍵を容易に推定できたと報告されている． では，状態表  (  の場合 &)* 個の値を格納する表 を最初に初期化する鍵スケジューリング部が &)* 個の値をそれぞれ一度ずつ置換して撹拌するという単純な操作のために，新規の "# が直前に使われた "# と似通っていれば出力系列の最初の部分が似通ってしまう．文献 $ + &% の結果は，"# の運用方法を留意していなかった  プロトコル上の欠陥から導かれたものであると言える．逐
次カウントアップされていくような毎回似通った "# を使うのであれば，その "#を ,-) などのハッシュ関数を通したハッシュ値を利用して秘密鍵とあわせてセッ
ション鍵とすれば解決するものであると文献 $ + &% でも指摘され， 社からも同様のコメントが公表されている $.+ %．これらの文献で，"# をハッシュ関数を通して利用すればこの攻撃は適用不可能で， ではそのような処理を行っているために， プロトコルには  プロトコルのようなプロトコル上の欠陥はないと報告されている．
そこで，本報告ではプロトコル上の欠陥についてではなく，暗号アルゴリズム
としての安全性について述べる．

 




記号の定義

 / アルゴリズムで一度に処理する 0 数 ワード長 ． (  が使われることが多い．

 / 時間変数．
 / 時間  に置ける状態表．$0% のバイナリの値が & 行 全パターン あるという表になっている．

 

 ½
/ 状態表  の  行目の値． (   
．








   / 状態表の行を指すポインタ変数．
 / 時刻  における出力 $0% の疑似乱数 ．
 /  の出力系列． (  ½
 ．


/ ある系列



暗号化

 

の時間  の時の 番目の要素の数．

ここでは  の暗号化手法を示す．初期値    ( 1 とし，初期状態  は秘密
鍵を用いてシャッフル 置換 されているとする．暗号化自体は出力系列  と平文を 23 するのみであるため，出力系列のアルゴリズム部を示す．
 の出力は以下の方法で得る．ここでの加算は 4 & とする．

  (   5  (   5      (    +   (     (    5  
 に対する攻撃

統計的な偏りを利用した攻撃 

6 !7 により，   !   88 94  の手法を用いて の出力系列から統計上の弱点を検出する方法が示されている．本節ではその攻撃法について述べる．



による近似のための仮定  の要素は全ての  で一様に分布し，0! 1 と が同数である である．
  は決定論的で既知のものである．
  は一様分布に従う 

．

&





による近似

 の手法による出力系列の近似を行う際に次の & つの近似を用いる．
近似 確率が高い近似 は   によって近似ができる．

   
近似 線形近似
 はその入力変数の任意の線形関数によって近似できる．しかし，全体的な相関係数を最大にするような線形関数で近似する．この論文では線形近似
式は以下ものを使用している．

5





5



まず， の暗号化部で生成される出力  は(    5 
(     5  (     5  (     5 5   5   5












































と変形できる．つまり  を   を使って記述する．近似 より，        55   5   5








という近似式が得られる．
この関係の 0 目について考える．

       55   5   5








まず次のような線形近似を行い，

     5

5      5     5










次に，求まった近似に再度線形近似を行う．

     5

5    5      5








ビット単位の加算は 23 であるため，    5
   

.



を消去できるので，

となり，線形近似を & 回行うことで出力を入力   で近似できることになる．
  は一様分布に従うポインタ変数であり値を特定できない．ここで，微分を行えば異なる時間の  が & つ手に入るので  に近似できる．そこで，特定できる値すなわち  で近似を行うために出力系列の微分を行う．
 

 
一階二進微分は，:  (  5  と表されるため，これを近似すると先程と
同様にして


 
 5    5  が得られる．これを近似すると

 5  (  5  5   

右辺の   を消去できるので，次のようになる．

 5  (  
この式に対して，線形近似を行う．

 5   
すなわち，


 
 
 
 5    5   となり，出力の一階二進微分を  で近似できる．ここまでで，線形近似の回数は
 合計 ) 回となっている．このように出力系列を  で近似できたが，線形近似回数の合計が奇数回の時は中心積率 相関係数を求めるときの式の一部分 が 1 になり，相関係数が打ち消されてしまうためにこの式は用いることができない．
そこで，次の条件を満たす階数の微分により近似を行う．

 線形近似はあまり高確率で成り立たないためできるだけ線形近似回数は少な
いほうが良い．
 相関係数が打ち消されないように線形近似回数は偶数でなければならない．
ここで
似で



階微分を考える． 階微分の場合，

5   と表され， 回の線形近 5    5  




が得られる．  を消去するために，  を次のように式変形する．

 5   (  5  5   5  5
       このときの線形近似の回数は 回となるため， 階微分の線形近似回数は  5 回
であることが分かる．偶数の線形近似回数になる は & であるため，ここでは出力の & 階微分の近似を用いる．その結果，

;

 

(    5       5      5 
























で近似する． と  の和を考えると最下位ビットが常に になることがわかる．
参考までに他の  について考えると，1 になる確率は下位 5 ビット目では
 &  となる．最上位ビットが比較的高い確率で近似できるものの，必ず成り立
つ最下位ビットの近似よりは相関係数が小さくなる．したがって，出力の二階二進微分の最下位ビットと との相関を見るようにする．



相関係数の導出

出力系列と二階二進微分をした線形近似式との相関係数  を求める概要を示す．
相関係数  を求めるために次のことを行う．

      のそれぞれについて 階微分を利用した線形近似が何回行われているかを調べ，全体の相関係数を各々の相関係数の積で表す．
 各状態で線形近似したときの相関をまとめて考えるために，状態間の近似の相関係数  と  間の相関係数 を導入し， に線形近似したときの相関係数を使う．
 全体の相関係数は，上記でまとめられた相関係数の期待値の積となる．
 状態間の近似の相関係数の期待値は & が大きいとき < = となり，考慮しなくても良い．
全体の相関係数  とは， を線形近似したときの相関係数  とする．文献中の定理 & 0! で一様にランダムなブール関数と線形ブール関数の相関係数を表したもの の証明過程で求まった  を必要な分だけ累乗して，その期待値 平均値を求めると，

 (   ( &   と表すことができる． は * 次の中心積率を示し，文献中の  より，


 (

 ½



&

 



 

 
 

 ½ 







 ½

)& 





のようになる．したがって，

 ( &   

)& 
)





( )&



となる．ここで    の長さの出力系列からその統計的偏りを高確率で発見でき
る $*% ことから

&  &
&&)




 

となり，約 & の出力系列があれば二階二進微分した出力系列の線形近似式と出力系列の最下位ビットの間に相関係数が  ( )  &  の相関がみられることに
なる．



統計的な偏りを利用した攻撃のまとめ

文献 $)% では，二進微分を利用して線形近似式を導出している．その結果，次のような統計的偏りを利用した攻撃が可能であることを示している．

 出力系列の二階二進微分をした線形近似式を使うことで，出力系列の最下位ビットが < = となる相関係数が  ( )  &  となる．したがって，出力系列を観測してこのような相関が見られたならば，その乱数は  アルゴリ
ズムであると識別できる．この識別に必要な出力系列の長さは & である．
 相関係数  を逐次求めていくことで，ワード長  が推定できる．



乱数系列から状態表の初期状態を推定する攻撃     の無い   への攻撃
この攻撃は，あらかじめ状態  中のいくつかの値を部分的に推測しておいて，鍵ストリーム  の観測により残りの行に値を割り当てて行く方法である．
 では次の  つの変数            が未知変数となる．この中の .
つの値が既知となれば  つ目の値が決まり， つの値が既知であれば矛盾が生じていないかを確認できる．つまり，矛盾があればその探索を終了すればよい．各  つの変数についてそれぞれ . つの値から推測するには，次のようにすればよい．

>         が既知のとき  (      
により   が求まる．

&>        が既知のとき   (   5  
により    が求まる．

*

.>          が既知のとき
 (        
により  が求まる．

>         が既知のとき  (      
により   が求まる．
攻撃法

> 状態  の初めの  個の値を推測する．
&>    の初期値    は 1 であり既知である．
.> 初めの  8初めの  8 の間は   がいつも既知であるので，  から計算できる もいつも既知になる．したがって残りの & つの未知変数のうち つが既知と






なればもう





つの値を決定でき，状態表に値を割り当てられる．

  が既に割り当てられているとき (    が既知のとき   を決定できる．

  の指す行に既に値が割り当てられているとき (   が既知のとき    を決定でき， を割り当てる．

    が既知 であり，  も既知であったとき  つの未知変数が既知のとき
 矛盾がないか調べる．矛盾があれば探索を終了し，異なる推測値をセットして実行し直す．

>  5 8 目以降
 5 8 目以降になると，あらかじめ推測していた値以外を  が指すようになる．そのとき   は未知になる．  が未知になると，当然   から計算する  も未知になる．さらに  は   の値から計算していたので，
を他の . つの変数から導き出せるまでは他の値の推定ができない．

$ の値が不明なとき % の指しているところに値があるとき   が既知 ， の値が割り当てられているかを調べる．もし割り当てられていたら    が既知 ，      (  
を計算し，それが表の中に割り当てられていないかを調べる．割り当てられていたなら  の値がわかる  が既知になる ．

$ が既知のとき %残りの . つの未知変数のうち & つが既知であれば，残りの未知変数を決定できる． 8 目までとの違いは   も推定する変数に入っており

場合分けが一つ増えることである．

  が指すところに値があれば   が既知ならば ， 8 目までに行った方法で       を推定できる．
   が未知であるとき 推定に失敗すると  が不明となるとき表に  の値があり，かつ  に値が割り当てられていれば   を推定できる．

 . つの未知変数が全て既知になれば，それらの関係を使って矛盾が無いかを調べる．もし矛盾があれば異なる推測値で攻撃処理をやり直し，矛盾がなければそのまま処理を続ける．

)> ．の操作を繰り返し，全ての行に矛盾なく値が割り当てられたなら初期状態  を推定できる．

なお，どの程度の出力系列があればこの攻撃が成功するのかは文献中に記述されていなかった．

    頻度が少ない   への攻撃
前節の攻撃をもとにした ?8 頻度の少ない  への攻撃について説明する．
攻撃の概略
 回毎に ?8 が起こるとする．最初の  ステップは ?8 なしの攻撃と同じアルゴ
リズムを実行するが， ステップを越えた後， の値が未知になると   の ?8
先が分からなくなる．この際   の値を未知のものにして処理を続けるのだが，
 が既知の行を指していて状態表が誤ってしまうこともありえる．これを防ぐために          の中のいくらかを状態表から除く．このときに正しい値を除くことを出来るだけ少なくするように工夫をする 工夫の仕方は記述されていない ．
結果& 回に 回だけ ?8 するような ?8 頻度が少ないときは，あらかじめ割り当てておく正しい値は &)* 個中 1 個で成功確率は )1@となる．しかし，& 回に 回
?8 が起こるような場合では，&)* 個中 &1 個の値をあらかじめ割り当てても成功確率は )1@程度となり，この攻撃法は現実的には使えない．





フルバージョン 

 への攻撃前節までの攻撃では，あらかじめ正しい値を事前にいくつか推測しておく必要があったが，本節ではその推測が不要な攻撃方法について述べる．
概略
攻撃アルゴリズムは，値を割り当てていない初期状態  から始める．
時刻  (  & .      において，   または    に値が割り当てられていないとき，>    に 1    &  の範囲の値  を選ぶ．
&>  を    から計算し，その後    に 1    & 


















の範囲の値 を選ぶ
このように順番に値を状態表に割り当てていく．つまり初期状態の全数探索を行うのであるが，次に述べる値を割り当てる方法や，ある条件での矛盾を考慮しながら探索するようにして探索回数を抑える．

：値の割り当てかた

状態表  の中の値は 1    &    が一度ずつ入っており，それが置換されているだけである．したがって，新しく選ぶ        はそれ
ぞれ，状態表中に既に割り当てられている値を割り当てないようにする．

： の値がまだ  内に割り当てられていないとき (   5   を計算し， が指す行に何らかの値が割り当てられているという矛盾が生じていないかを確かめる．

 割り当てられている 矛盾している 場合
探索に矛盾が生じていることがわかるため，これ以上の探索を行わな
い．以前の処理まで戻り，  や   に異なる値を割り当てて試す．
 割り当てられていない場合矛盾が生じていないため，  (  と値を割り当てて次の処理に進む．

： の値が既に  内に割り当てられているとき (   5   を計算し， が指す行と    の行が異なるという矛盾が生じていないかを確かめる．

  と    が等しい場合
矛盾が生じていないことが分かる．このとき   が一意に定まる．
  と    が等しくない 矛盾している 場合
探索に矛盾が生じている．ここでは全ての   を試し，矛盾が生じていないものがないかを確かめる．それでも矛盾が生じてしまうなら，  に異なる値を割り当てる．

 を観測するたびに & と . の条件のどちらかを実行できる．よってこの条件により矛盾を検出し無駄な探索を減らすことができる．
筆者らはこれらの原理を使って  の暗号化を行う  ステップを順番に実行しながら，状態表に値を当てはめていく方法を与えている．
実験結果
この攻撃によって出力系列からの状態表の復元は，状態表の全数探索の平方根程度の探索回数で済む．これは数値実験でも確認されていた．しかし，表 のように， ) では計算量が大きすぎて実行することができないため， (  で使われる通常の  に対する現実的な攻撃法とは言えないと記述されている．
表/ A0  の攻撃の計算量  48!9
.
&

&
)
&
*
& 

&

& 

 が既知であり，かつ    であるときにはこの攻撃は有効であると言える．



乱数系列から状態表の初期状態を推定する攻撃のまとめ

文献 $% では， つの未知変数            を逐次推定していくことで，出力系列から状態表の初期状態を復元する攻撃法が示されていた．その結果，次のような攻撃が可能であることを示している．

 ?8 頻度が少ないバージョンの  ( を考えたとき， ?8 頻度が& 回に 回のときは初期状態の &)* 個中 1 個の値が既知のときに成功確率が )1@程度， & ?8 頻度が & 回に 回のように高頻度になると &)* 個中 &1個の値が既知でも成功確率は )1@程度，となる．
 フルバージョンの  ビット  の出力系列から未知変数に制限を付けながら初期状態の表に割り当てていく方法では，計算量が状態数 & の全数探索 の平方根程度，つまり約 & 程度で初期状態が推定できる．

& 点目からフルバージョン  の初期状態を推定する攻撃は，
的に攻撃は不可能となる．

1) では計算量 まとめ
本報告書では， に対する暗号化アルゴリズムの安全性について説明した．統計的偏りを利用した  アルゴリズムと特定する識別攻撃は可能であるが，出力系列から初期状態を推定する攻撃はいずれも  ) では不可能なために，現在利用されている  (  の  に対して実用的な攻撃法は存在しないと言える．
 では "# の不注意な取扱いによるプロトコル上の脆弱性が明らかにされたが， の弱点が発見されたのではない． では  プロトコルのようなプ
ロトコル上の問題点は現在のところ発見されていない．

参考文献


  

# 

%




    

'' ( )  ,     $      



 

*

  

    

! "$ $   %&&'

+



 #- " ./. 0' .    $  .*1!2

-22



3'            %&&4 0'    .    

5       $! " 3'      6   1          $

%&&

!

 0'    . 5 #- 7  !  -  6  " 3'         *  %&&8)3 *9 :;$$%%AB%4C

A





 

! 6 

 :  3%44  

" - 1        "

31) ??A

  

E  F 

 

 

??@

$$!B!?

0 6         

=-.>?@)3 *9 :; 0 !8

@0 

  #+<, -! " 3  

3 8!

D 9   D$ 1  

6 <   * - $ 

 

=-.>?C
1D



 

   $$ 4%@14!

 

??C