ストリーム暗号 RC4 の
安全性評価

五十部

孝典

(神戸大学)

共同研究者
大東 俊博 (広島大学)
森井 昌克 (神戸大学)

協力者
塚畝

翼

(神戸大学）
長尾 篤 (神戸大学)
渡辺 優平 (神戸大学）

2012 年 11 月

1

目次
1

要旨

1.1

RC4 アルゴリズムに関する安全性解析 . . . . . . . . . . . . . .

3
3

1.2

SSL3.0/TLS1.0 以上で RC4 を利用する場合の安全性評価 . . . .

4

2

ストリーム暗号 RC4 の構造

63RC4 の安全性について
3.1 識別攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

3.1.1 Multiple Key Distinguisher . . . . . . . . . . . . . . . .
3.1.2 Single Key Distinguisher . . . . . . . . . . . . . . . . . .
内部状態復元攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . .

8
11
11

3.3
3.4

鍵回復攻撃

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
予測攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11
12

3.5
3.6

その他の性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

RC4 の既存攻撃のまとめ . . . . . . . . . . . . . . . . . . . . . .

12
13

RC4 を SSL3.0/TLS1.0 以上で用いた場合の安全性について
4.1 SSL3.0/TLS1.0 での RC4 の利用方法 . . . . . . . . . . . . . . .

14
14

WEP/WPA に対して行われた攻撃の適用可能性 . . . . . . . . .
Broadcast setting での RC4 の安全性 . . . . . . . . . . . . . . .
4.3.1 Mantin-Shamir Attack . . . . . . . . . . . . . . . . . . .

14
15
15

MPS 攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . .

16

すべての平文情報を導出可能な Broadcast RC4 への暗号文単独攻撃

18

はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
キーストリームの新しい Bias . . . . . . . . . . . . . . . . . . .

18
20

5.2.1
5.2.2
5.2.3

Bias of Z1 = 0|Z2 = 0 . . . . . . . . . . . . . . . . . . .
Bias of Z3 = 131 . . . . . . . . . . . . . . . . . . . . . .
Bias of Zr = r . . . . . . . . . . . . . . . . . . . . . . .

20
23
25

5.2.4
5.2.5

Bias of Extended Keylength-dependent bias . . . . . . .
Optimal Bias Set . . . . . . . . . . . . . . . . . . . . . .

28
33

Broadcast RC4 に対する平文解読実験 . . . . . . . . . . . . . .
258 byte 目以降の平文の導出方法 . . . . . . . . . . . . . . . . .
5.4.1 Based Long-term Bias (ABSAB bias) [16] . . . . . . . .

34
38
38

ABSAB bias と optimal bias set を組み合わせた逐次的導出法 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

5.4.3 Experimental Results . . . . . . . . . . . . . . . . . . .
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
44

3.2

4

4.2
4.3

4.3.2
5

5.1
5.2

5.3
5.4

5.4.2

5.5

A 平文解読実験の詳細データ

47

2

要旨

1

本稿では，ストリーム暗号 RC4 に対しての安全性評価結果を報告する．本評
価では，主に以下の二つを行った．

1. RC4 に関してこれまで行われてきた安全性解析の調査.
2. SSL3.0/TLS1.0 以上で RC4 を利用する場合の安全性評価．

1.1

RC4 アルゴリズムに関する安全性解析

代表的なストリーム暗号アルゴリズムに対する攻撃としては，識別攻撃，内部
状態復元攻撃，鍵回復攻撃，予測攻撃が挙げられる. これらの攻撃について現在の RC4 の解析状況について調査した．
識別攻撃は，キーストリームと呼ばれる出力系列を真性乱数と識別する攻撃であり，一つの鍵から生成されたキーストリームを用いる攻撃と複数の鍵から生成されたキーストリームの集合を用いる攻撃に分けられる．それぞれ，single

key (strong) distinguisher, multiple key (weak) distinguisher と呼ばれる．RC4に対しては，226.5 word のキーストリームを用いた single key distinguisher が最も効果的な攻撃として Mantin により提案されている [16]．また multiple key

distinguisher として最も強力なものは，Mantin と Shamir により提案された 300
通りの異なる鍵から生成されたキーストリームの 2 byte 目を利用したものである [17]. この識別攻撃自体が現実的な安全性を脅かさないが，ストリーム暗号の出力が擬似乱数系列であることの安全性の前提が崩れてしまう．
内部状態復元攻撃はキーストリームから秘密鍵と等価な内部状態を求める攻撃である. ある時刻の内部状態を求めることができればそれ以降のキーストリー
ムを求めることができる．内部状態の更新が可逆の場合は，それ以前のキースト
リームも導出できる. RC4 に対しては，2241 の計算量でキーストリームから内部状態をすべて求めるアルゴリズムが Maximov と Khovratovich により提案されている [19]．これは，秘密鍵のサイズを 241 bit 以上にしても安全性が向上しないことを意味する．しかしながら，この攻撃は 128 bit key を用いた場合の安全性には直接影響しない．
鍵回復攻撃は，キーストリームから秘密鍵を直接求める攻撃である．キースト
リームと秘密鍵間の相関を利用して，2122.06 の計算量で 128 bit key を求めるア
ルゴリズムが Sepehrdad らにより提案されている [26]．この攻撃は偏りのある
キーストリームと秘密鍵間の関係式を用いて全数探索の効率化を行うタイプの攻撃で，このアプローチで現実的な計算量で攻撃可能になることは難しいと考えるが，全数探索と比較して大幅に攻撃計算量は削減されている．
予測攻撃は，出力であるキーストリームを予測する攻撃であり，代表的な攻撃として，Mantin の予測攻撃がある．この攻撃では，1 bit の予測が 245 byteのキーストリームを使えば 85 パーセントの確率で成功し，1 byte の予測が 250

byte のキーストリームを使えば 82 パーセントの確率で成功する [16]．

3その他の攻撃としては, Key collision に対する評価 [18, 5]，内部状態から秘密鍵を効果的に求める方法や [23, 2]，キーストリームから鍵長を求める方法 [12]なども提案されている．
以上のように，RC4 のアルゴリズム自体に対する解析は数多く行われているが，現実的な脅威になるような攻撃は現在のところ提案されていない．しかしながら，擬似乱数との識別が容易にでき，全数探索より十分効率的なアルゴリズムが提案されている事実より，厳密な意味で 128 bit security を擁しているとは言
えない．

1.2

SSL3.0/TLS1.0 以上で RC4 を利用する場合の安全性評価

SSL3.0/TLS1.0 では，RC4 の秘密鍵は，master secret と呼ばれる共有秘密情報と乱数から, ハッシュ関数もしくは MAC 関数を用いて生成される．この鍵生成に関して解析を行ったが，脆弱性を見つけることができなかった．そこで本評
価では，セッション毎に秘密鍵は random に生成されるものとした．RC4 の実装
に対する攻撃としては WEP/WPA に対する攻撃が有名であるが，これらの攻撃は基本的には鍵の生成方法の脆弱性を利用した攻撃であるため，SSL3.0/TLS1.0
以上での RC4 に対しての適用は難しいと考える．

SSL3.0/TLS1.0 以上での RC4 を利用した場合の現実的な脅威となりうる攻撃として Broadcast setting での攻撃を考えた．これは，同じ平文をユーザ毎の秘密鍵を用いて暗号化して送る状況を想定する．この setting での攻撃としては，
キーストリームの 2 byte 目が 0 になりやすいことを利用した Mantin と Shamirの攻撃がある [17]. この攻撃では Ω(N ) のユーザ毎の鍵で生成された暗号文から，平文の 2 byte 目を特定することが可能である．ここで，N は RC4 の内部状態のサイズを表すパラメータであり, SSL/TLS では N = 256 のパラメータが用いられる. さらに，Maitra らにより Ω(N 3 ) のユーザ毎の鍵で生成された暗号文か
ら，平文の 2–255 byte 目も高い確率で特定できることが示された [14]．しかし,
上記の 2 つはあくまで理論的な評価であり，実際に Broadcast RC4 への安全性を考える場合，以下の疑問が残る．

1. これらの bias を用いた攻撃がもっとも強力な攻撃なのか．
2. 実際にこれらの bias のみで, 暗号文から平文を求めることができるのか．
3. [17, 14] の評価では, 攻撃で必要な暗号文数を下限で評価しているが，実際の攻撃ではどのくらいの暗号文が必要なのか．
4. 1 byte 目と 256 byte 以降の平文は求めることができるのか．
本評価では，Broadcast RC4 に対する更なる解析を行い，上記の質問に対して回答を与えた．
まず初めに，キーストリームの初めの 257 byte に関して, 既存の bias よりも強力ないくつかの bias を新たに見つけ, 証明を与えた．これらの新しい bias の4

方が既存の bias より強くなる部分に関しては, これらのより強い bias の影響により，既存の bias のみを用いた場合, 平文を一意に決定することができない．そこで, 実際に平文復元攻撃を構成する際は，新しい bias と既存の bias をうまく組み合わせて使う必要がある．我々はこれらの bias を考慮した Broadcast RC4への平文復元攻撃に最適な bias の set (optimal bias set) を導出した．optimal

bias set はキーストリームの初めの 257 byte の最も強い bias の集合と考えることができる.
次に，上記の optimal bias set を用いて，実際に平文解読実験を計算機で行い，攻撃に必要な暗号文数を成功確率と共に見積もった．結果として，232 程度の異なる鍵で生成された暗号文があれば，optimal bias set を用いることにより, 確率 0.5 以上で平文の 1–257 byte の各 byte を復元できる. また 224 程度の暗号文数であっても，Z1 , Z2 , extended keylength-dependent bias などの強い bias の部分に関しては高確率で復元可能である．
さらに, 258 byte 以降の平文を効率よく求める方法を与えた．この手法は Matinにより示された Digraph Repetition bias [16] と，本稿で求めた Z1 –Z257 の opti-

mal bias set を組み合わせて，逐次的に求めていくものである．この手法を用いることにより，234 程度の暗号文から, 258 byte 以降の平文も暗号文のみから求めることができる．この Digraph Repetition bias は long term bias であるため，

258 byte 以降の任意の平文を求めることができる．理論的には，初めの 250 bytes≈ 1000 T bytes の平文は 234 の異なる鍵で生成された暗号文から確率 0.97170.
で導出可能である．
本評価では, Broadcast RC4 の実際的な安全性を評価するために, Broadcast

setting での平文復元攻撃に最適な bias の set を導出し，計算機を用いて必要な暗号文数と成功確率を見積もった．結果として，Broadcast setting で RC4 を利用した場合は 234 程度の暗号文を集めることにより，250 bytes ≈ 1000 T bytesの平文情報を暗号文のみから復元可能である．また 224 程度の暗号文であっても特定の平文 byte を高確率で求めることが可能である. さらに SSL/TLS の場
合，session 毎に異なる鍵が生成されるため, Broadcast setting は Multi session

attack としても考えることができる．Multi session attack では，攻撃対象の平文ブロックが繰り返し複数の session で同じ位置で用いられることを想定している [3]．よって，Broadcast setting，Multi session setting での RC4 の使用を用いる場合，上記の攻撃に注意が必要である．

5

2

ストリーム暗号 RC4 の構造

RC4 は 1987 年に RSA Data Security 社の Rivest によって開発された可変長鍵のストリーム暗号である．RC4 はソフトウェアによる高速処理性能に優れており，Adobe Acrobat や Lotus Notes などの商用のアプリケーションやインター
ネット用のプロトコルである SSL (Secure Sockets Layer) 3.0/TLS (Transport

Layer Security) 1.0，無線 LAN 用のプロトコルである WEP (Wired Equivalent
Privacy) 及び WPA (Wi-Fi Protected Access) などで広く使われており，最も使われているストリーム暗号の一つである.
RC4 は開発されて以来，そのアルゴリズムは非公開であったが，1994 年にソースコードがインターネット上に匿名で流されて実質的に仕様が公開された形になった．しかしながら，RSA Data Security 社は公開されたコードを公式にRC4 と認めておらず，公開されたコードは ARC4(Alleged RC4) や arcfour と表記される RC4 と等価な動作をするアルゴリズムとしてインターネット上で公開されている．本評価では，ARC4 のアルゴリズムを RC4 とみなした上で安全性を評価を行う．

RC4 は可変長の秘密鍵 K を用いる．鍵長は 8 bit から 2048 bit の間で選択できる. RC4 の内部状態 S は N (= 2n ) 個の要素の置換からなり，それぞれの要素
は n ビットの変数である．n は RC4 が処理単位 (ワード長) である. また，RC4
は内部状態の更新で 2 つのポインタ i，j を用いており，それぞれ n bit の変数である．SSL3.0/TLS1.0 以上では 鍵長は 128 bit，n = 8，N = 256 が使われているため，本評価ではこのパラメータのみを扱う．

RC4 のアルゴリズムは鍵スケジューリングアルゴリズム (KSA : Key Scheduling
Algorithm) と擬似乱数生成アルゴリズム (PRNG : Pseudo Random Number
Generator) から構成される．鍵スケジューリングアルゴリズムでは，秘密鍵から N 個の要素の置換で構成される内部状態を生成する．擬似乱数生成アルゴリ
ズムでは，内部状態を更新しながら 1 word 単位でキーストリーム Z1 , . . ., Zr ,. . . を生成する. ここで，r は PRGA のラウンド数である．Zr は平文の r 番目のword Pr と XOR されて，暗号文の r 番目の word Cr を生成する．RC4 のアルゴリズムは Algorithm 1 に示す．ここで，+ は N を法とした算術加算である．

6

Algorithm 1 RC4 Algorithm
KSA(K):
for i = 0 to N − 1 do

PRGA(K):i←0S[i] ← iend forj←0
S ← KSA(K)
loop

j←0
for i = 0 to N − 1 doj ← j + S[i] + K[i mod l]i←i+1
j ← j + S[i]Swap S[i] and S[j]end forSwap S[i] and S[j]Output Z ← S[S[i] + S[j]]end loop7

RC4 の安全性について

3

本章では, 代表的なストリーム暗号アルゴリズムに対する攻撃である識別攻撃，
内部状態復元攻撃，鍵回復攻撃，予測攻撃を中心に既存の結果について述べる．
いくつかの結果に関しては，追試を行い，実験的にサポートした. また今回新たに見つけた解析結果もいくつか加える.

3.1

識別攻撃

キーストリームを真性乱数と識別する識別攻撃は，multiple key distinguisherと single key distinguisher の 2 種類に分けられる．

3.1.1

Multiple Key Distinguisher

multiple key distinguisher は，複数の秘密鍵から生成されたキーストリームの集合を対象にした distinguisher である．RC4 に対する multiple key distingusher
としては, FSE 2001 に Mantin と Shamir の提案したキーストリームの 2 byte 目の Z2 の bias を利用したものがある [17]．この攻撃では，Z2 = 0 になる確率がrandom な場合の 1/256 と比較して 2 倍高い 2/256 である bias を利用している．
これは内部状態が特定の条件を満たしている場合に確率 1 で Z2 = 0 のイベントが発生するためであり，理論的にも証明されている．文献 [17] では，識別に必要な sample 数を見積もるための理論値を以下の定理で与えている.

Theorem 1. [17] 二つの分布 X と Y において，event e の起こる確率が X では
p, Y では p(1+q) である場合，O(1/pq 2 ) の sample があれば，constant probabilityof success で X と Y を識別可能である．
上記のケースでは，e をキーストリームの 2 byte 目が 0 とし，X を真性乱数の分布, Y を RC4 の出力の分布とすると，p = 1/256, q = 1 となる．ここで q はrelative bias と呼ばれる. Theorem 1 より，この bias を利用すると約 200 通りの異なる鍵で暗号化された Z2 の集合があれば，真性乱数と 0.64 の確率で識別することが可能である．また，キーストリームの 1 byte 目の bias を利用した攻撃も,

CRYPTO 2002 で Mironov により提案されている [20]．これは理論的な証明はなく，実験的に Z1 の分布に偏りがあることを求めており，この偏った分布を用いることにより，約 1700 通りの異なる鍵で暗号化された Z1 の集合があれば，真性乱数と高確率で識別することが可能である. この bias の理論的な証明は 2011
年に Sen Gupta らによって行われた [11]. これらの攻撃は初めの数 byte のみを利用した攻撃であり, 初めの数 byte を破棄する実装の場合は防ぐことができる．

FSE 2004 で, Paul と Preneel は，初めの数 byte を捨てても識別攻撃を実行可
能な bias を発見した [24]．これは，Zr+1 と Zr+2
(r = 0 mod 256) において
Zr+1 = Zr+2 になる確率が random な場合と比較して，成立しにくい bias であ8表 1: Zr+1 = Zr+2

(r = 0 mod 256) の negative bias [24] の実験値

Zr+1

Zr+2

Zr+1 = Zr+2 になる確率

relative bias q

1/pq 2 (log 2)

120.0038903282-0.0040759808

23.87727406

257

258

0.0039051189-0.0002895616

31.50768417

513

514

0.0039062651

0.0000038656

43.96175242

769

770

0.0039063384

0.0000226304

38.86275678

1025

1026

0.0039063974

0.0000377344

37.38752028

1281

1282

0.0039064339

0.0000470784

36.74915037

1537

1538

0.0039064805

0.0000590080

36.09745983

1793

1794

0.0039062736

0.0000060416

42.6732758

2049

2050

0.0039063195

0.0000177920

39.55682356

2305

2306

0.0039063602

0.0000282112

38.22674488

2561

2562

0.0039063480

0.0000250880

38.56528602

2817

2817

0.0039062629

0.0000033024

44.41610739

3073

3074

0.0039063370

0.0000222720

38.90881872

3329

3330

0.0039062725

0.0000057600

42.81099952

3585

3586

0.0039063775

0.0000326400

37.80599883

3841

3842

0.0039062429-0.0000018176

46.13906766

4097

4098

0.0039062867

0.0000093952

41.39928939

る．理論的には，Z1 = Z2 になる確率は，1/256 · (1 − 1/256) であり，r > 256
においては，1/256 · (1 − 1/2562 ) になる．Theorem 1 より，Z1 と Z2 では約224 (= 28 · 28×2 ) の sample で，r > 256 においては約 240 (= 28 · 216×2 ) の sample
で理論的には識別可能である．しかしながら，実験的には Z257 と Z258 の場合は 232 で識別可能であったことが報告されている [24]．これは，関連する特定のイベントが起きやすいことに起因しているが，理論的な理由はわかっていない．
我々は詳細にこの nagative bias を見積もるために，240 の random に生成した秘密鍵を用いて計算機実験を行った．表 1 に実験結果を示す．表 1 より， Z1 と Z2においては理論値通りの値で識別可能であり．Z257 と Z258 の場合には，[24] と同様に理論値より非常に高い bias が観測されている．それ以降に関しては，理論的には −2−16 程度の negative relative bias が検出されるべきであるが，実験
では観測できなかった．これは 240 以上の sample 数が必要な bias であるため，実験の sample 数が十分でないことも原因だと考えられる．ただ, この実験により, Z513 と Z514 から Z4097 と Z4098 では，Zr+1 ̸= Zr+2 のイベントの bias を利用した場合, 少なくとも 240 の sample では識別することが難しいことを示唆している．

9

0.003930

Zr = 00.003925

Probability

0.003920
0.003915
0.003910
0.003905
0.003900
50

100
150
Round number (r)

200

250

図 1: Zr = 0 bias の実験値 (1 ≤ r ≤ 255)

表 2: Zr = 0(r = 256, 257) の実験値

Zr0 になる確率relative bias q

1/pq 2 (log 2)

256

0.0039004963−0.0014729472

26.81415714

257

0.0039115301

0.0013517056

27.06200663

FSE 2011 で Maitra らは，出力の 3 byte 目から 255 byte 目の bias を発見した[14]．出力の 2 byte 目が 0 に偏っていることはすでに Mantin と Shamir により示されていたが，文献 [17] では 2 byte 目以降では同様の bias は存在しないと予想されていた. しかしながら，実際には 3 byte 目から 255 byte 目も同様に 0 に偏っていることを実験的も理論的にも示した [14]．これらを使用することで 224の sample で理論的には真性乱数と識別できる．図 1 に 240 の random に生成した秘密鍵を用いた実験値を示す．
我々はさらに 240 の random に生成した秘密鍵を用いて計算機実験を行い，表2 の新しい 0 に関する bias を発見した．これらを用いることにより，256 と 257
byte 目も攻撃に使うことが可能になる. この bias に関する理論的な証明はない
が，それぞれ 226.8 と 227.0 の sample で識別できるため，最初の 255 byte を捨てた実装にも対して最も強力な multiple key distinguisher になる.

10

3.1.2Single Key Distinguisher

Single key distinguisher はランダムに選ばれた一つの秘密鍵から生成された
キーストリームを真性乱数と識別する攻撃である．EUROCRYPT 1997 で Golicは Zr と Zr+2 の最下位ビット間に相関があることを示し，244.7 byte のキースト
リームの観測によって実行可能な識別攻撃を提案した [10]．FSE 2000 で, Fluhrerと McGrew によって Golic の方法が改良され，Zr と Zr+1 間の相関 (Digraph)を利用することで必要なキーストリームの byte 数を 230.6 word まで減少させている [8]．さらに EUROCRYPT 2005 で, Mantin が Digraph の概念をさらに拡張した Digraph Repetition Bias を提案し，必要なキースリーム byte 数を 226.5

word に削減した．これらは，初期キーストリームにのみ発生する bias ではなく,任意の bias において発生する bias であり, long term bias と呼ばれる. そのため，初期のキーストリームを捨てる実装においても有効な攻撃である.

3.2

内部状態復元攻撃

内部状態復元攻撃はキーストリームから秘密鍵と等価な内部状態を求める攻撃である. ASIACRYPT 1998 で Knudsen らによって RC4 に対する内部状態復元攻撃が提案された [13]．ここで, 内部状態は N = 256 の場合，256 の置換と 1 byteの 2 つの pointer i と j で構成されるため，全数探索の計算量は 21700 (≈ 256!) と見積もられる, Knudsen らの方法はキーストリームを利用する枝刈りを備えた木探索アルゴリズムであり，攻撃に要する計算量は初期状態の全数探索の平方根程度である 2779 まで削減される. 具体的にはキーストリームと内部状態で成立する Sr−1 [Zr ] = (Sr−1 [ir ] + Sr−1 [jr ]) mod 256 の検査式を用いて効率的に求めていく．白石らは Knudsen らの木探索アルゴリズムを深さ優先探索に修正することで計算量を削減している [28]．

CRYPTO 2008 で Miximov と Khovratovich により, Knudsen らの攻撃を改良した新しい攻撃方法が提案された [19]．この攻撃では，d-order w-generative

pattern と呼ばれる特定のキーストリームのパターンを利用して 2241 の計算量でキーストリームから内部状態をすべて求めることができる. これは，秘密鍵のサイズを 241 bit 以上にしても安全性が向上しないことを意味する．しかしながらこれ以下の鍵長に関しては安全性の影響はない.

3.3

鍵回復攻撃

鍵回復攻撃は，キーストリームから秘密鍵を求める攻撃である．SAC 2010 で,

Sepehrdad らによりキーストリームと内部状態間, 秘密鍵間の相関を利用して，
2122.06 の計算量で秘密鍵を求めるアルゴリズムが提案されている [26]．この攻撃は偏りのあるキーストリームと秘密鍵間の関係式を用いて全数探索の効率化を行うタイプの攻撃で，このアプローチで Practical な計算量で攻撃可能になることは難しいと考えるが，全数探索と比較して大幅に攻撃計算量は削減されている．

11

Weak key に基づく鍵回復攻撃もいくつか提案されている．Weak key とは，鍵空間の一部に存在している鍵の集合であり，今回のケースでは，全数探索よりも効率的に鍵回復攻撃を実行することが可能な特殊な鍵のクラスである. 1995 年，

Roos が特定の鍵においてキーストリームの先頭と鍵の先頭 byte に強い相関があることを発見し，weak key として定義した [25]．鍵空間全体のうち 2−10.9 の割合で Roos の weak key が存在し，この鍵においては鍵探索の際に 16 bit 分の探索を省略することができる．よって Roos の weak key を利用する攻撃では，鍵の探索において 25.1 (= 216 /210.9 ) bit 分の利得がある．さらに 2011 年，寺村らがpredictive state を用いた weak key を定義し，Roos の weak key もこれに包括されることを示した [29]．Predictive state とは，FSE 2001 で Mantin と Shamirにより示された PRGA における部分的な内部状態からいくつかのキーストリー
ムが予測できる特殊な内部状態である [17]．a word の内部状態から b word のキーストリームが予測できるとき，これを b-predictive a-state と呼ぶ．寺村ら
は predictive state を導く鍵の条件を導出し，weak key として再定義した．寺村らの weak key の能力は predictive state のパラメータ a, b に依存する．特に5-predictive 5-state を用いた攻撃の場合，特定のキーストリームを得る鍵のうち
確率 2−7.1 で weak key が存在し，秘密鍵の 40bit 分の探索を省略できる．鍵探索
における利得は 232.9 bit 分あり，特定のキーストリームに対して 295.1 の計算量で 128 bit 鍵を回復することができる．ただし，この攻撃は特定のキーストリー
ムが観測された場合に実行される攻撃である点が Roos の Weak key とは異なる．
我々は, さらに predictive state を用いる weak key の拡張を行い，同時に weak

key の総数を導出した．まず寺村らの定義した weak key 以外にも predictive state
を導く鍵が存在することを発見し，新たな weak key とした．また，weak key の数はこれまで深く議論されていなかったが，今回その総数についても明確にした．我々の定義した weak key はこれまで提案された寺村らの weak key，Roosの weak key を全て内包しており，その総数は 2118.58 になる. この詳細に関しては文献 [21, 22] を参照されたい.

3.4

予測攻撃

予測攻撃は，出力であるキーストリームを予測する攻撃であり，代表的な攻撃として，EUROCRYPT 2005 で提案された Mantin の予測攻撃がある．この攻撃では， Recyclable Fortuitous State と呼ばれる state を利用し, 1 bit の予測が245 byte のキーストリームを使えば 85 パーセントの確率で成功し，1 byte の予測が 250 byte のキーストリームを使えば 82 パーセントの確率で成功する [16].

3.5

その他の性質

その他の攻撃としては, Key collision に対する評価 [18, 5]，内部状態から秘密鍵を効果的に求める方法や [23, 2]，キーストリームから鍵長を求める方法 [12]なども提案されている．

12

FSE 2009 で松井により, RC4 の Key collision に関する評価が提案された [18].
Key Collision とは，同じキーストリームを生成する異なる鍵のことを表し，一般的には等価鍵と呼ばれる．RC4 において, pointer を除いた内部状態は 21684 (≈ 256!)であるため, birthday paradox により, 鍵長が 105 byte 以上の場合は理想的なKSA であっても collision は発生するが，RC4 の場合は 17 byte key であってもまた実験的にも 24 byte の collision pair が存在することが理論的に示された.

実際に示された. この攻撃は Chen らにより一般化され [5], この攻撃は関連鍵攻
撃により鍵回復攻撃に利用できることも示された [4]．

SAC 2007 で Paul らにより KSA の解析として，内部状態から秘密鍵を効果的に求める方法が提案された [23]. これは，FSE 2008 で Biham らにより更なる攻撃の改良が行われた [2]. この攻撃は，攻撃者が内部状態を知っていることが前提の攻撃であるため，直接的には RC4 の安全性には影響しない．

SAC 2011 で Sen Gupta らにより，鍵の長さに依存した key dependent biasが提案された [12]. この bias を利用することにより, キーストリームから鍵長を求めることができる.

3.6

RC4 の既存攻撃のまとめ

以上のように，RC4 のアルゴリズム自体に対する解析はアルゴリズムが公開され以降, 数多く行われているが，現実的な脅威になるような攻撃は現在のところ提案されていない．しかしながら，擬似乱数との識別が容易にでき，全数探索より十分効率的なアルゴリズムが提案されている事実より，厳密な意味で 128

bit security を擁しているとは言えない．

13

RC4 を SSL3.0/TLS1.0 以上で用いた場合の安全
性について

4

本章では，暗号アルゴリズムとして RC4 を実際に SSL3.0/TLS1.0 に用いた場
合の安全性について評価する.

4.1

SSL3.0/TLS1.0 での RC4 の利用方法

SSL3.0/TLS1.0 では，初めに公開鍵ベースの Handshake プロトコルを行い,
master secret と呼ばれる 48 byte の秘密情報を共有する．そのあとに，その値と乱数からハッシュ関数（MD5, SHA-1）もしくは MAC 関数 (HMAC) 用いて用
途別の session key, 初期ベクトル (IV) を生成する．この鍵生成に関して解析を行ったが，脆弱性を見つけることができなかった．そこで本評価では，セッショ
ン毎に RC4 で用いられる秘密鍵は random に与えられるものとした．鍵の生成の詳細については以下の文献を参照されたい [9, 6]

4.2

WEP/WPA に対して行われた攻撃の適用可能性

WEP/WPA は RC4 を利用した無線 LAN におけるセキュリティプロトコルである．しかしながら, WEP は 2001 年に Fluhrer, Mantin, Shamir により脆弱性を指摘されて以降 [7], 多くの攻撃方法が提案されており, 致命的な欠陥を持つプロトコルである. その中でも強力な攻撃として, SAC 2007 で Vaudenay とVuagnoux により提案された VX attack が挙げられる [30]．VX attack は並列して WEP 鍵の和を計算することができる攻撃であるため，効率的に WEP 鍵を回復することが可能となる．ここで WEP は IV と WEP 鍵をビット連結すること
で秘密鍵を生成し，IV はパケットごとに異なる値が使用される．さらにこれを改良した攻撃が SAC 2010 で Sepehrdad らにより提案され，通信路上のパケッ
トを 9,800 個観測することで確率 0.5 で WEP 鍵が回復されてしまう [26]．この攻撃では新たな攻撃式を提案することでより多くの WEP 鍵の候補値を計算することができる．
また EUROCRYPT 2011 において，4,000 個のパケットを観測するだけで WEP
鍵を回復する攻撃が Sepehrdad らによって提案された [27]．このとき WEP 鍵の回復に成功する確率は 0.5 である．この攻撃は既知の複数の bias を効果的に利用し, 正しい WEP 鍵を効率的に探索する．さらにこの方法を WPA の鍵探索に適用することができ，238 個のパケットを利用することで 128 bit の Temporal

Key を回復することができる．ただし鍵回復に要する計算量は 296 である．ここで Temporal Key は WPA において暗号化と復号の際に利用される鍵であり，事前に共有した秘密鍵から生成される．
以上のように WEP/WPA に対しては様々な攻撃方法が提案されており，無線

LAN においてこれらのセキュリティプロトコルでは，安全に通信を行うことは難しいと考えられる．一方でこれらの攻撃は基本的には秘密鍵の生成方法の脆弱

14

平文 M
k1

kX

k2
C(1)
= RC4(k1, M)

C(2)

ユーザ鍵

C(x)

図 2: Broadcast Setting性を利用した攻撃であるため，SSL3.0/TLS1.0 以上での RC4 に対しての適用は難しいと考える．

4.3

Broadcast setting での RC4 の安全性

SSL3.0/TLS1.0 以上での RC4 で現実的な脅威となりうる攻撃として Broadcast
setting での攻撃が考えられる．Broadcast setting では，同じ平文を異なる秘密
鍵を用いて暗号化して送る場合を想定する．本稿では，この Broadcast setting
での RC4 のことを Broadcast RC4 と呼ぶ. 図 2 に Broadcast setting の概要を示す．この setting は，コンテンツをユーザ毎の秘密鍵で暗号化して SSL/TLS
で送る場合などが，実際のユースケースとして考えられる.

Broadcast RC4 への攻撃は，FSE 2001 に Mantin と Shamir により初めて示された [17]. この攻撃は, mulitple key distinguisher でも利用されたキーストリー
ムの 2 byte 目が 0 になりやすい bias を利用している. この bias を利用することで, Ω(N ) のユーザ毎の鍵で生成された暗号文があれば，平文の 2 byte 目を特定することが理論的に可能である．さらに，FSE2011 で, Maitra らにより Ω(N 3 )のユーザ毎の鍵で生成された暗号文があれば，平文の 2–255 byte 目を特定することができることが理論的に示された [14]．以下これらの攻撃についての詳細を
述べる.

4.3.1

Mantin-Shamir Attack

Mantin-Shamir Attack で用いている bias は以下の Theorem で与えられる.
Theorem 2. [17] KSA の後の PRNG の初期状態が {0 . . . N − 1} の置換の集合から random に選ばれた場合, キーストリームの 2 byte 目が 0 になる確率は約2
N である.
2
N = 256 の場合, 256となる. この bias を用いて Broadcast RC4 への攻撃は次の Theorem で与えられる.

15

Theorem 3. [17] 一通りの平文 M に対して, k 通りの秘密鍵を用いて RC4 で暗号化された暗号文を C (1) . . . C (k) とする. k = Ω(N ) のとき, C (1) . . . C (k) のみから M の 2 byte 目を導出することが可能である.
これは，Theorem 1 の識別攻撃の成功確率より見積もられている．Ci = Pi ⊕Ziの関係式より, Z2 = 0 の場合, C2 = P2 が成立する. ここで Theorem 2 より,

Z2 = 0 は 2 倍の確率で発生する. よって, k = Ω(N ) の C に対して, C2 を値毎に count up して, 最も多く count された C2 を P2 とする. N = 256 の場合, 28
通りの以上の random に生成された秘密鍵で生成された暗号文のみから平文の 2

byte 目を高確率で特定できる.

4.3.2

MPS 攻撃FSE2011 で Maitra らにより, Z2 以外の Z3 − Z255 も同様に 0 に bias していることが示された [14]. Mantin-Shamir の論文では, KSA の後の内部状態がrandom に N の置換の集合から選択されると仮定しているが, Maitra らは KSAの後の内部状態に bias があることを利用している. 具体的には Mantin の示した
以下の KSA 後の bias を利用している.
Proposition 1. [15] KSA のあと，0 ≤ u ≤ N − 1, 0 ≤ v ≤ N − 1 に対して以下が成立する.
{( N −1 v)
1
N −1 v
N −1 N −u−1(v ≤ u)N · ( N )( + (1 − ( N ) ) · ( N ))Pr(S0 [u] = v) =1
N −1 N −u−1
N −1 v+( N )(v > u).
N · ( N )また, この bias を考慮したときに, PRNG での Sr−1 [r] = r に関する bias は次の Lemma で与えられる.

Lemma 1. [14] r ≤ 3, Sr−1 [r] = r になる確率 pr−1,r は,
(( )
)
r−1
1
1
Pr(Sr−1 [r] = r) ≈ Pr(S0 [r] = r) ·−+ 1/N.
NN
このとき, Zr = r に関する bias は以下の Theorem で与えられる.

Theorem 4. [14] 3 ≤ r ≤ 255 において, r 番目の出力が 0 になる確率はPr(Zr = 0) ≈

1
cr
+ 2.
N
N

ここで cr は以下の式で与えられる.
(()r ()N −r−1 ()N −1 )
N −1
N −1
N −1
cr =
+
−
·
N
N
N
)
((
)r−2
N −1
1
−
N
N −1
具体的な cr の bound は以下の通りである.

16

Corollary 1. [14]10.98490994
10.36757467+≥ Pr(Zr = 0) ≥
+
N
N2
N
N2
以上より, これらの bias を用いることで, N = 256 の場合, 224 通り以上のrandom に生成された秘密鍵で生成された暗号文のみから平文の 3–255 byte 目
を高確率で特定できる.
上記の理論値については [11] で更なる詳細な評価が行われ更新された.

Lemma 2. [11] r ≤ 3, Sr−1 [r] = r になる確率は, 次で与えられる.
()r−2 ∑()k ()r−3−kr−t
r−1 ∑Pr(S1 [t] = r) r − t − 1
1
1
+
·
· 1−
Pr(S1 [r] = r)· 1 −N
k! · NNN
t=2
k=0

ここで, Pr(S1 [t] = r) は以下で与えられる.


Pr(S1 [t] = r) =




∑N −1

X=0 Pr(S0 [1] = X ∧ S0 [X] = r)∑

Pr(S0 [1] = r) + w̸=r Pr(S0 [1] = w ∧ S0 [r] = r)∑w̸=t Pr(S0 [1] = w ∧ S0 [t] = r)(t = 1)(t = r)(t ̸= 1, r).

このとき, Zr = r に関する bias は以下の Theorem で与えられる.

Theorem 5. [11] 3 ≤ r ≤ 255 において, r 番目の出力が 0 になる確率はPr(Zr = 0) ≈

1
cr
+ 2.
N
N

ここで cr = NN−1 [N · Pr(Sr−1 [r] = r) − 1].
以上より，Broadcast RC4 への攻撃としては MS 攻撃と MPS 攻撃を用いることにより, 224 以上の暗号文を与えられた場合に平文の 2–255 byte を求めること
ができる.

17

すべての平文情報を導出可能な Broadcast RC4 へ

5の暗号文単独攻撃
本章では，Broadcast RC4 に対する更なる安全性の評価を行う．具体的には新しい Broadcast RC4 への攻撃手法を提案する.

5.1

はじめに

Broadcast RC4 への攻撃としては，Mantin-Shamir の攻撃と Maitra らによる攻撃が知られている. FSE 2001 で，Mantin と Shamir によってキーストリームの 2 byte 目 Z2 の bias を利用した Broadcast RC4 への攻撃が初めて提案された[17]．この攻撃では Z2 が 0 になりやすいことを利用し，1 種類の平文に対して，Ω(N ) の異なる鍵で生成された暗号文を集めることにより，平文の 2 byte 目が特定できることが示された．さらに，FSE 2011 で Maitra らにより，Z3 –Z255 も 0に bias することが示され，Ω(N 3 ) の異なる鍵で暗号化された暗号文から平文の3 byte 目から 255 byte 目も同様に導出できることが示された [14]．
しかしながら，これらは RC4 の bias についてのあくまで理論的な結果であり，これらをもとに実際の Broadcast RC4 に対する平文復元攻撃に応用する際には以下の疑問点が挙げられる.

1. これらの bias を用いた攻撃がもっとも強力なのか?
2. 実際にこれらの bias のみで, 暗号文から平文を求めることができるのか?
3. [17, 14] の評価では, 攻撃で必要な暗号文数を下限 (Ω) で評価しているが，実際の攻撃ではどのくらいの暗号文が必要なのか?
4. 1 byte 目と 256 byte 以降の平文は求めることができるのか?
本章では, 上記のすべての疑問に対しての回答を与える. まず，Z2 = 0 のときの Z1 に関する新しい条件付き bias を提案し, 証明を与える．この bias を Mantinと Shamir の Z2 = 0 の bias と組み合わせて使うことで，理論的には 217 以上の暗号文で平文の 1, 2 byte 目を導出することができる．1 byte 目に関しては，biasがあることはすでに実験的にも理論的にも示させていたが [20, 11]，これを用いてどうのように効果的に平文復元攻撃に応用できるかは分かっていなかった．直接的にこの bias を用いた攻撃を構成すると 224 以上のデータが必要になることが予想される．そのため，この bias は 1/27 のデータ量の約 217 で導出できるた
め，Broadcast RC4 に対する非常に有効な bias である．
さらに，Z3 –Z255 においては Zr = 0 よりも大きな 3 つの新しい bias Z3 =131, Zr = r と extended keylength-dependent bias を示す. ここで, extended
keylength-dependent bias は SAC 2011 で証明された keylength-dependent bias [12]を拡張した新しい bias である. これらの新しい bias については理論的考察を与え, さらに実験的も正しいことを確認した. これらの新しい bias の方が Zr = 0

18

bias より強くなる部分に関しては, Zr = 0 bias のみを用いると新しい bias の影
響により，平文を一意に決定できない．そこで, 実際に平文復元攻撃を構成する
際は，これらの新しい bias と Zr = 0 bias をうまく組み合わせて使う必要がある．我々はこれらの bias を考慮した平文復元攻撃に最適な bias の set (optimal

bias set) を導出した．また, 理論的な証明はないが Z256 と Z257 に関して実験的に攻撃に有効な bias を発見し， optimal bias set に加えた. 具体的には，optimal
bias set はキーストリームの初めの 257 byte の各 byte における最も強い bias の集合である.
次に，上記の optimal bias set を用いて，実際に平文解読実験を計算機で行い，攻撃に必要な sample 数 (暗号文数) を成功確率と共に見積もる．結果として，232程度の異なる鍵で生成された暗号文があれば，optimal bias set を用いることにより, 確率 0.5 以上で平文の 1–257 byte 目の各 byte を復元できる. 1,2 byte 目
や extended keylength-dependent bias などのさらに確率の高い bias は 224 程度の暗号文からでも高確率で推測することが可能である.
最後に, 258 byte 以降を効率よく求める方法を提案する．この方法は EURO-CRYPT 2005 で Matin により示された Digraph Repetition bias [16] と，本稿で求めた Z1 –Z257 の optimal bias set を組み合わせて，逐次的に求めていくものである．この手法を用いることにより，234 程度の暗号文から 258 以降の平文も求めることができる．ここで，この Digraph Repetition bias は, long term bias
であるため，258 byte 以降の任意のすべての平文を暗号文から求めることができる．また, これらの正当性も計算機実験で検証した．
以上より，本稿で, 我々が提案する Broadcast RC4 に対する攻撃はすべての平文情報が暗号文のみから求めることができる初めての Full Plaintext Recovery

Attack である．

19

5.2

キーストリームの新しい Bias

本章では, Broadcast RC4 への攻撃に有効な 4 つの新しい bias, Z1 = 0|Z2 = 0,

Z3 = 131, Zr = r と extended keylength-dependent bias を説明する. Z1 =0|Z2 = 0 bias は，既知の Z2 = 0 bias と組み合わせて用いることにより, P1 を
217 通りの暗号文から求めることができる強力な bias である．Z3 = 131, Zr = rと extended keylength-dependent bias は，Z3 –Z255 においては既知の Zr = 0
よりも大きな 3 つの新しい bias である. まず，各 bias に対しては理論な証明をして与えて, 実験値と比較して正当性を確認する. その後にこれらの特性を考慮して Z1 . . . Z255 に関する bias の中から, Broadcast RC4 への攻撃に最適な set(optimal bias set) を提案する.

5.2.1

Bias of Z1 = 0|Z2 = 0

Z2 = 0 のときの Z1 に関する新しい条件付き bias を提案する. この bias を用いることで, 平文の 1 byte 目に関する効率的な攻撃を構成することができる. さらにこの性質をうまく利用することで, 暗号文単独での key の推測攻撃も可能である.
まず, Z2 = 0 のときの Z1 に関する新しい条件付き bias を以下の Theorem より与える.

Theorem 6. Pr(Z1 = 0|Z2 = 0) は1 (
1) 1 1
Pr(Z1 = 0|Z2 = 0) ≈ · Pr(S0 [1] = 1) + (1 − Pr(S0 [1] = 1)) ·
+ ·
2
N
2 N
である.

Proof. 次の 2 つの case について考える.
• S0 [2] = 0
文献 [17] より, Pr(S0 [2]|Z2 = 0) ≈ 21 であるため, Z2 = 0 が観測された場
合は, Pr(S0 [2] = 0) = 21 .
ここで, S0 [1] = 1 と仮定すると, i = 1 において j = S0 [i] = S0 [1] = 1 となる. このとき,

Z1 = S0 [S0 [i] + S0 [j]] = S0 [S0 [1] + S0 [1]] = S0 [2] = 0,となる. 図 3 にこのイベントを示す.

S0 [1] ̸= 1 の場合に Z1 = 0 になる確率が N1 であるとするとPr(Z1 = 0|S0 [2] = 0) =1
1
(Pr(S0 [1] = 1) + (1 − Pr(S0 [1] = 1)) ).
2
N• S0 [2] ̸= 0
場合に Z1 = 0 になる確率が N1 であるとすると,Pr(Z1 = 0|S0 [2] ̸= 0) =

20

1 1
· .
2 N

0

S0

1

2

3

1

0

1

2

1

0

256

ij
0

Increment3256

i j (=S0[i]=1)
Swap(S0[i], S0[j])
0

1

2

3

1

0

256

ij
Z1 = S1[S1[1] + S1[1]] = S1[2] = 0
図 3: Z1 = 0|Z2 = 0 の Event

以上より,

Pr(Z1 = 0|Z2 = 0) ≈1 (1) 1 1· Pr(S0 [1] = 1) + (1 − Pr(S0 [1] = 1)) ·
+ · .
2
N
2 N

ここで, N = 256 のケースについて考える. Pr(S0 [1] = 1) は, Proposition 1 より求めることができ，

1
Pr(S0 [1] = 1) =
256

((

1
256

)

(
(
)) (
)254 )
1
1= 0.0038966.
+ 1−
256
256

よって，

Pr(Z1 = 0|Z2 = 0)1
1 1
1
(Pr(S0 [1] = 1) + (1 − Pr(S0 [1] = 1))
)+ ·
2
256
2 256
= 0.0058470 = 2−7.418 = 2−8 · (1 + 2−1.009 ).

=240 の random に選択 key から生成された keystream による実験した結果, 実
験値は 0.0058109 = 2−8 · (1 + 2−1.036 ) となり，理論値が十分に正しいことを確認できた．
またこの bias から Pr(Z1 = 0 ∧ Z2 = 0) は,Pr(Z1 = 0 ∧ Z2 = 0) = P (Z2 = 0) · P (Z1 = 0|Z2 = 0),で与えられ, N = 256 のときは,Pr[Z1 = 0 ∧ Z2 = 0] =2
× 2−7.418 = 2−14.418 = 2−16 (1 + 20.996 ).
256

このような bias は digraph bias と呼ばれ, 文献 [8, 11] で検討されているが, Long

term bias としての検討であるため，このような初期のキーストリームにおける21

非常に高い bias は報告されていない.
この Z2 = 0 のときの Z1 = 0 の bias を用いて効果的な Broadcast RC4 への平文復元攻撃が構成できる. また，暗号文単独での内部状態 (鍵) 推測攻撃へも応用可能である.

Broadcast RC4 攻撃 Mantin-Shamir Attack [17] とこの bias を組み合わせる
ことで，P1 を効率よく求める攻撃が構成できる. まず準備として, 求めたい平文に対して，217 の異なる鍵で暗号化された暗号文を得る.

1. 28 の暗号文から平文の 2 byte 目 P2 を特定 [17].
2. 217 の暗号文の 2 byte 目 C2 に対して, C2 ⊕ P2 を計算し Z2 を求める.
3. Z2 = 0 のものを選択. 210 ≈ 217 · 2/256 の暗号文が残る.
4. 残ったものに対して, もっともカウントされている C1 を P1 とする.
Step 4 において, Pr(Z1 = 0|Z2 = 0) = 2−7.418 = 2−8 · (1 + 2−1.009 ) 程度の 0 への bias から, C1 = P1 ⊕ Z1 = P1 になっているものが, Theorem 3
1
より 210 ≈ 2−8 ·(2−1.009)2 の暗号文から特定可能である.
よって 217 の異なる鍵で生成された暗号文から, 平文の 1, 2 byte 目を高確率で導出することができる．1 byte 目に関しては，bias があることはすでに実験的にも理論的にも示させていたが [20, 11]，これを用いてどうのように効果的に Broadcast RC4 への attack に応用できるかは分かっていなかった．単純に, この bias を用いた攻撃を構成すると 224 のオーダーの bias であるため, 224 程度のデータが必要になることが予想される．そのため，この bias は約 1/27 のデータ量の 217 で導出できるため，Broadcast RC4 に対する非常に効果的な攻撃である.
内部状態 (鍵) 推測攻撃 この bias を用いて内部状態推定攻撃にも応用できる.

Z1 = 0, Z2 = 0 が観測されたときに, S0 [1] = 1, S0 [2] = 0 になっている確
率は,
P ((S0 [1] = 1 ∧ S0 [2] = 0)|(Z1 = 0 ∧ Z2 = 0))
P (S0 [1] = 1 ∧ S0 [2] = 0)
· Pr((Z1 = 0 ∧ Z2 = 0)|(S0 [1] = 1 ∧ S0 [2] = 0))=
Pr(Z1 = 0 ∧ Z2 = 0)
1
1
· 255
= 256
· 1 = 2−1.567 ,(1)
2−14.427となる．これに関して計算機で実験を行ったところ, 確率は 2−1.589 となり理論値が正しく近似していることを確認した．よって, これらが観測された
場合, S0 [1] と S0 [2] を 2−1.589 の確率で推測可能であり, random guess の場合の成功確率は 2−16 であるため, 214.41 倍の advantage がある.
さらに, 内部状態-鍵間の Roos の以下の関係式を用いると鍵の推測も可能

22

である.

S0 [1] =1 + K[0] + K[1]S0 [2] =3 + K[0] + K[1] + K[2]これらはそれぞれ 0.371, 0.368 の確率で成立する [23]. そのため, Z1 = 0,

Z2 = 0 が観測されたとき上記を推測した場合の成功確率は, 0.371×0.368×
2−1.589 = 2−4.45 となり, 鍵の推測に対しても 211.55 倍の advantage がある.
この攻撃は, Broadcast setting では暗号文単独で実行可能である. 具体的には，まず, 217 の異なる鍵で生成された暗号文から, 平文の 1, 2 byte 目を導出することができる．その情報を用いて，キーストリームの 1, 2 byte
目が 0 であるものを探し，上記の鍵推測攻撃を実行する.

5.2.2

Bias of Z3 = 131

Z3 に関する新しい bias を提案する. Z3 に関しては, 既存の bias である文献[14, 11] の Zi = 0 3 ≤ i ≤ 255 も, Z3 の場合は bias が理論値と比べてかなり小
さくなることが実験的に知られている. ([14] の Fig. 1, [11] の Fig. 8 参照). そのため, Broadcast RC4 への攻撃を考えた場合, 理論値と比べてかなり多くの暗号文数が必要になる. 我々は, この Z3 に対して, Z3 = 0 と比較して十分強力な

Z3 = 131 の bias を発見した. この確率は以下の Theorem で与えられる.
Theorem 7. Pr(Z3 = 131) はPr（Z3 = 131） ≈ Pr(S0 [1] = 131) · Pr(S0 [2] = 128) +(1 − Pr(S0 [1] = 131) · Pr(S0 [2] = 128)) · 1/N
である.

Proof. S0 [1] = 131 かつ S0 [2] = 128 の場合を考える. i = 1 の場合, j = S0 [1] =131 となり, S0 [1] と S0 [131] の Swap により, S1 [131] = 131 が成立する.
次に, i = 2 の場合, j = 131 + S1 [2] = 131 + S0 [2] = 131 + 128 = 3 となり,S1 [2] と S1 [3] の Swap により, S2 [3] = 128 が成立する.
最後に, i = 3 の場合, j = 3 + S2 [3] = 3 + 128 = 131 となり, S2 [3] と S2 [131]の Swap により, S3 [3] = 131 と S3 [3] = 128 が成立する. このときの出力は
Z3 = S3 [S3 [3] + S3 [131]] = S3 [131 + 128] = 131 となる.
以上より, S0 [1] = 131 かつ S0 [2] = 128 の場合は確率 1 で Z3 = 131 が成立する. 図 4 にこのイベントを示す.
他の場合での Z3 = 131 が成立する確率を 1/N とするとPr（Z3 = 131） ≈Pr(S0 [1] = 131) · Pr(S0 [2] = 128) +(1 − Pr(S0 [1] = 131) · Pr(S0 [2] = 128)) · 1/N.

23

0

S0

1

2

3

131

256

3

131

256

131 128

0

1

S1

2

131

128

0

1

2

S2

0

1

S3

2

3

131

128

131

3

131

131

128

256

i=1
j = S0[1] = 131
i=2
j = 131 + S1[2]= 131 + 128 = 3
i=3
j = 3 + S2[3]= 3 + 128 = 131

256

Z3 = S3[S3[3] + S3[131]]= S3[131 + 128]
= S3[3] = 131

図 4: Z3 = 131 の Event

ここで, N = 256 のケースについて考える. Pr(S0 [1] = 131) と Pr(S0 [2] = 128)
は, Proposition 1 より求めることができ，(()256−1−1 ()131 )1
255
255
Pr(S0 [1] = 131) =·+= 0.0037848.
256
256
256

1
Pr(S0 [2] = 128) =
·
256

((

255
256

)256−2−1

(
+

255
256

)127 )= 0.0038181.

よってPr（Z3 = 131）≈ 0.0039206 = 2−8 · (1 + 2−8.089 ),となる. 240 の random に生成した鍵に対する keystream での実験では,

Pr（Z3 = 131）= 67350014/234 = 0.0039204 = 2−8 · (1 + 2−8.109 ),となり, 理論値は十分正しいことを確認した.
ここで既存の Z3 = 0 の bias との比較を行う. 240 の random に生成した鍵に対する keystream での実験では,

Pr(Z3 = 0) = 0.0039116 = 2−8 · (1 + 2−9.512 ),となった. よって, Z3 = 131 の方が強い bias であることが分かる. そのため,Broadcast RC4 への攻撃で Z3 に対しては, Z3 = 131 が Z3 = 0 よりも多くカウントされることになるため, Z3 = 131 を攻撃に用いる必要がある.

24

0

i=r

j

0

r

Sr - 1

256

Swap(Sr - 1[i], Sr - 1[j])
0

i=r

j

r

0

Sr

256

Zr = Sr[Sr[r] + Sr[j]] = Sr[r] = r
図 5: Zr = r の Event (Case 1)

5.2.3

Bias of Zr = r

Zr = r 3 ≤ r ≤ 255 の bias を提案する. これは，既知の Zr = 0 の biasとほぼ同じオーダーの確率で 3 ≤ r ≤ 255 において存在する bias であるため,Broadcast RC4 に対する攻撃においては重要な bias である.
Zr = r の確率は以下の Theorem で与えられる.
Theorem 8. Pr(Zr = r) は1
1 N −2+ pr−1,r ·
·
+
N
N
N
1
1
1
1
(1 − pr−1,0 ·− pr−1,r ·− (1 − pr−1,0 − pr−1,r ) ·· 2) · ,N
N
N
N

Pr（Zr = r） ≈ pr−1,0 ·である. ここで pr−1,0 = Pr(Sr−1 [r] = 0), pr−1,r = Pr(Sr−1 [r] = r).

Proof. ir = r のとき出力 Zr は,

Zr=

Sr [Sr [ir ] + Sr [jr ]] = Sr [Sr [r] + Sr−1 [ir ]],=Sr [Sr [r] + Sr−1 [ir ]] = Sr [Sr [r] + Sr−1 [r]],で表される.
ここで，次の 4 つの case について考える．

case 1 : Sr−1 [r] = 0 ∧ Sr [r] = r
case 2 : Sr−1 [r] = r ∧ Sr [r] = jr − r (j ̸= r, r + r)
case 3 : Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r − Sr−1 [r]case 4 : Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r
case 1 と case 2 は必ず Zr = r になるイベントで，case 3 と case 4 は必ず Zr ̸= rになるイベントである．以下各 case について Pr(Zr = r) になる確率を導出する．

25

0

Sr - 1

i=r

j

r

j-r

256

Swap(Sr - 1[i], Sr - 1[j])
0

Sr

i=r

j

j-r

r

256

Zr = Sr[Sr[r] + Sr[j]] = Sr[j] = r
図 6: Zr = r の Event (Case 2)

Case 1 : Sr−1 [r] = 0 ∧ Sr [r] = r
このとき，

r)

Zr = Sr [Sr [r] + Sr−1 [r]] = Sr [r + 0] = Sr [r] = r となり，Pr(Zr == 1 となる．Sr [r] は j により指された値であり，文献 [14] より，j > 3 の場合は，j は random にふるまうため，Sr [r] の値も偏りはないと仮定する．このとき，pr−1,0 = Sr−1 [r] = 0 と定義すると，Pr(Sr−1 [r] = 0 ∧ Sr [r] = r) = pr−1,0 ·

1.
N

図 5 にこのイベントを示す.

Case 2 : Sr−1 [r] = r ∧ Sr [r] = jr − r
このとき， Zr = Sr [Sr [r]+Sr−1 [r]] = Sr [jr −r+r] = Sr [jr ] = Sr−1 [r] = r とな
り，Pr(Zr = r)

= 1 となる．Sr [r] は j により指された値であり，文献 [14] より，
j > 3 の場合は，j は random にふるまうため，Sr [r] の値も偏りはないと仮定する．
jr = r のとき, Sr [r] = 0 になり，Zr = Sr [Sr [r]+Sr−1 [r]] = Sr [0+r] = Sr [r] = 0になり，Pr(Zr = r) = 0 である．また jr = r + r のとき, Sr [r] = r になり，
Zr = Sr [Sr [r] + Sr−1 [r]] = Sr [r + r] ̸= r になり，Pr(Zr = r) = 0 である．よって，j ̸= r, r+ の条件を満たす必要がある．
このとき，pr−1,r = Sr−1 [r] = r と定義すると，Pr(Sr−1 [r] = 0 ∧ Sr [r] = ｒ) = pr−1,r ·1 N −2·.
NN

図 6 にこのイベントを示す.

Case 3 : Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r − Sr−1 [r]Zr = Sr [r − Sr−1 [r] + Sr−1 [r]] = Sr [r] = Sr [r] となる. このとき，Sr [r] =r − Sr−1 [r] は Sr−1 [r] ̸= 0 より， r にはならないため，Pr(Zr = r) = 0 となる．
ここで，Pr(Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r − Sr−1 [r]) = (1 − pr−1,0 − pr−1,r ) ·Case 4 : Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r
26

1
.
N

0.003940
Experimental value
Theoretical value
Random

0.003930
0.003920

Probability

0.003910
0.003900
0.003890
0.003880
0.003870
0.003860
0.003850
0

50

100
150
Round number (r)

200

250

図 7: Zr = r の理論値と実験値

このとき，Zr = Sr [r + Sr−1 [r]] となり Sr−1 [r] ̸= 0 より， r にはならないため，

Pr(Zr = r) = 0 となる．ここで，Sr−1 [r] ̸= 0 かつ r > 0 より，r ̸= r − Sr−1 [r]となり，case3 と case4 は独立な event であるため，Pr(Sr−1 [r] ̸= (0, r) ∧ Sr [r] = r − Sr−1 [r]) = (1 − pr−1,0 − pr−1,r ) ·1.
N

以上より， その他の event では Zr = r が N1 の確率で発生すると，

1
1 N −2+ pr−1,r ·
·
+
N
N
N
1
1
1
1
− pr−1,r ·− (1 − pr−1,0 − pr−1,r ) ·· 2) · .
(1 − pr−1,0 ·N
NNN

Pr（Zr = r） ≈ pr−1,0 ·ここで pr−1,r は Lemma 2 により計算可能である. 同様に, pr−1,0 は Lemma 2を変形した以下の()r−2 ∑()k ()r−3−kr−1 ∑r−t1
Pr(S1 [t] = 0) r − t − 1
1
Pr(S1 [r] = 0) 1 −+1−,N
k! · NNN
t=2 k=0

で求めることができる.
図 7 に理論値と 240 のランダムに選択した鍵から生成したキーストリームの実験値の比較のグラフを示す. 弱冠のずれがあるのは, 理論値の計算の際に考慮できていないイベントが影響していると考えられる．そのため，これが完全にこの

bias を証明したとは主張しないが，オーダーは合っているため, 主に影響しているイベントに関しては捕らえられていると考える．この bias は Z3 –Z255 で存在
し, Zr = 0 の bias と同程度であるため，Broadcast RC4 の攻撃の際には, 考慮する必要がある. Zr = 0 と Zr = r の適切な選択については, 5.2.5 節で議論する.

27

表 3: Zr = −r, Zr = 0, Zr = r の実験値の比較

Pr(Zr = −r)

r

5.2.4

−8

−4.811· (1 + 2

Pr(Zr = 0)
· (1 + 2

Pr(Zr = r)

2−8 · (1 + 2−5.383 )2−8 · (1 + 2−7.880 )2−8 · (1 + 2−7.991 )48

2−8 · (1 + 2−5.938 )2−8 · (1 + 2−8.043 )2−8 · (1 + 2−8.350 )64

2−8 · (1 + 2−6.496 )2−8 · (1 + 2−8.244 )2−8 · (1 + 2−8.664 )80

2−8 · (1 + 2−7.224 )2−8 · (1 + 2−8.407 )2−8 · (1 + 2−9.052 )· (1 + 2

96

2

)

112

2−8 · (1 + 2−8.666 ))2−8 · (1 + 2−9.351 )2−8 · (1 + 2−8.747 )2−8 · (1 + 2−9.732 )2· (1 + 2−8.5772· (1 + 2−7.762 )

32

−8

)

−8

2

−7.911

2−7.714

16

−8

)

−8

Bias of Extended Keylength-dependent bias

Extended Keylength-dependent bias として，鍵長 l が 16 byte の場合に Zr =−r (r = 16, 32, 48, 64, 80, 96, 112) となる bias を提案する．表 3 に試行回数 240 における Extended Keylength-dependent bias，Zr = 0，Zr = r の実験値を示す．
表 3 から Extended Keylength-dependent bias が他の 2 つより強力な bias であることが分かる．Extended Keylength-dependent bias は Keylength-dependentbias [12] を拡張した新しい bias である．Keylength-dependent bias は文献 [26]において実験的に示され，文献 [12] で証明が与えられた Zl = −l の bias である．しかし，文献 [26] では l = 16 の場合に r > 48 のパラメータでは役に立たないとして r = 16 の実験値しか記載していない．我々は実験によって r =16, 32, 48, 64, 80, 96, 112 まで Broadcast RC4 への攻撃に有効であることを発見した．図 10 に表 3 の Extended Keylength-dependent bias の実験値 (Experimental
value) と文献 [12] の理論式を用いて導出した確率 (Theoretical value of [12]) のグラフを示す．図 10 から，Experimental value と Theoretical value of [12] に大きなずれがあることが分かる．文献 [12] では l < 48 などの小さいパラメータの場合のみを考えており，また，r = k · l などの鍵 byte を繰り返し使う場合の挙動は考慮していない．このため文献 [12] の理論式は近似式として意味をなしていない．これらの問題点を解決し，未知のイベントを発見して理論的に bias の近似式を構成する．

Zr = −r が成立しているときの内部状態および状態遷移を解析した結果，以下の 3 つの比較的大きな bias を持つイベントから Extended Keylength-dependentbias が満たされることを発見した．
Source Event 1 : Sr−1 [r] = 2r ∧ Sr [r] = −r
Source Event 2 : fr−1 = −r
Source Event 3 : fr−1 ̸= −r ∧ Sr−1 [r] = 028

表 4: E1 , E2 , E3 の実験値と条件付き確率r

Pr(E1 )

Pr(E2 )

Pr(Zr = −r | E2 )Pr(E3 )

Pr(Zr = −r | E3 )160.0000196

0.0038998

0.0266066

0.0030881

0.0185482

320.0000186

0.0078119

0.0057877

0.0036847

0.0242181

48

0.0000169

0.0039107

0.0039338

0.0038805

0.0195860

640.0000160

0.0156367

0.0039003

0.0038698

0.0146792

80

0.0000154

0.0039061

0.0039464

0.0038687

0.0104982

960.0000147

0.0078133

0.0039161

0.0038525

0.0081722

112

0.0000143

0.0039030

0.0039195

0.0038742

0.0066151

このとき fy は

fy =

y
∑

K[x] +x=0

y(y + 1),2とする．以降，各イベントを E1 ，E2 ，E3 と表記する．E1 ，E3 は我々が発見したイベントであり，E2 は Keylength-dependent bias を満たすイベントである．

l = 16 とした場合における各イベントの実験値を表 4 に示す．
Keylength-dependent bias において Pr(Zl = −l | fl−1 = −l) は以下の Lemma
で与えられる．
Lemma 3. [12] fl−1 = −l のとき Zl = −l の確率 Pr(Zl = −l | fl−1 = −l) は，
]]
[
] [
[
][
]N +l−2 [[
]1+l
1
1
1
l
1
1
1
+ 1−
·
+ 1−
1−
1−
+
N
N
N
N
N
N
N
[
]
[
]l+1
1
1
·
+ 1−
Pr(S0 [S0 [l − 1]] = fl−1 ) ,NNである．ここで Pr(S0 [S0 [l − 1]] = fl−1 ) は 1 ≤ l ≤ 32 のとき文献 [12] の Propo-

sition 4 により計算され，l > 32 の場合は 1/N とする．
Zr = −r (r = 16, 32, 48, 64, 80, 96, 112) の確率は以下の Theorem で与えられる．
Theorem 9. Pr(Zr = −r) はPr(Zr = −r)

1+ Pr(Zr = −r | fr−1 = −r) · Pr(fr−1 = −r)
N+Pr(Zr = −r | E3 ) · Pr(E3 )[]11+ 1 − pr−1,2r ·− Pr(fr−1 = −r) − Pr(E3 ) · ,NN≈ pr−1,2r ·である．ここで pr−1,2r = Pr(Sr−1 [r] = 2r)，Pr(E3 ) = Pr(fr−1 ̸= −r∧Sr−1 [r] =

0)．

29

0

Sr - 1

i=r

j

2r

-r

256

Swap(Sr - 1[i], Sr - 1[j])
0

Sr

i=r

j

-r

2r

256

Zr = Sr[Sr[r] + Sr[j]] = Sr[r] = -r
図 8: Zr = −r の Event (Case 1)

Proof. ir = r のとき出力 Zr は,
Zr=

Sr [Sr [ir ] + Sr [jr ]] = Sr [Sr [r] + Sr−1 [ir ]]=Sr [Sr [r] + Sr−1 [ir ]] = Sr [Sr [r] + Sr−1 [r]],で表される.
ここで，次の 3 つの case について考える．

Case 1 : Sr−1 [r] = 2r ∧ Sr [r] = −rCase 2 : fr−1 = −rCase 3 : fr−1 ̸= −r ∧ Sr−1 [r] = 0
Case 1 は必ず Zr = −r になるイベントであり，Case 2 は Lemma 3 を拡張したイベントである．Case 3 は実験的に確認されたイベントであり，Case 3 を構成するイベントの一部については解析が完了している．しかし解析ができていない部分があるので，完全な証明は open problem とする．以下，各 case についてPr(Zr = −r) を導出する．
Case 1 : Sr−1 [r] = 2r ∧ Sr [r] = −r
このとき，Zr = Sr [Sr [r] + Sr−1 [r]] = Sr [(−r) + 2r] = Sr [r] = −r となり
Pr(Zr = −r) = 1 となる．Sr [r] は j により指された値であり，文献 [14] より，
j > 3 の場合は j は random にふるまうため，Sr [r] の値も偏りはないと仮定する．ここで，pr−1,2r = Pr(Sr−1 [r] = 2r) と定義すると，Pr(Sr−1 [r] = 2r ∧ Sr [r] = −r) = pr−1,2r ·1.
N

図 8 にこのイベントを示す．

Case 2 : fr−1 = −r
Lemma 3 を l = 16 の場合に Zr = −r | fr−1 = −r というイベントに拡張して考える．このとき，Sr−1 [r] = 0 ∧ Sr [Sr−2 [r − 1]] = −r であれば，Zr =Sr [Sr [r] + Sr−1 [r]] = Sr [0 + Sr−2 [r − 1]] = Sr [Sr−2 [r − 1]] = −r となる．Lemma30

i = r -1

0

Sr - 2

j

A

A

256

-r
Swap(Sr - 2[i], Sr - 2[j])0Sr - 1

i=r

j

A

0

A

-r

256

Swap(Sr - 1[i], Sr - 1[j])
0

Sr

i=r

j

A

A

0

-r

256

Zr = Sr[Sr[r] + Sr[j]] = Sr[A] = -r
図 9: Zr = −r の Event (Case 2,3)

3 では fl−1 = −l の条件において Sl−1 [l] = 0 ∧ Sl [Sl−2 [l − 1]] = −l となるイベントが考えられている．これを用いると，
[
[
]
1
1
Pr(Zr = −r | E2 ) · Pr(E2 ) ≈ Pr(fr−1 = −r) ·
+ 1−
N
N
[
]]
[
[
]
]1+r
N +r−2 [
[
r]
1
1
1
1
·
+ 1−
1−
1−
+
N
N
N
N
N
]]
[
[
]r+1
1
1
+ 1−
Pr(S0 [S0 [r − 1]] = fr−1 ) .
·NN
図 9 にこのイベントを示す．ここで，fr−1 = −r の成立確率について述べる．鍵長を 16 としたとき，K[x] = K[x mod 16] となる．これを考慮すると r = 16 · kのとき fr−1 = −r は

fr−1

= k · (K[0] + . . . + K[15]) += −16 · k (mod N ),16 · k(16 · k − 1)2となり，

k · (K[0] + . . . + K[15]) = −16 · k −16 · k(16 · k − 1)(mod N ),2を満たす秘密鍵が選択された場合に式が成立する．k = 1, 3, 5, 7 の場合は (K[0] +. . . K[15]) が式を満たすものは 1 通りしかなく確率は 1/N になる．k = 2 および
k = 6 のときには 2 通りとなるため確率は 2/N ，k = 4 のときには 4 通りとなる
ため確率は 4/N に向上することが分かる．この性質は表 4 によって実験的にも確認している．

Case 3 : fr−1 ̸= −r ∧ Sr−1 [r] = 0
このとき，Sr [Sr−2 [r − 1]] = −r であれば，Zr = Sr [Sr [r] + Sr−1 [r]] = Sr [0 +31

表 5: Case 3 の条件付き確率の理論値と実験値

r

Pr(Zr = −r | E3 )16

0.0074864

320.0073027

48

0.0071216

64

0.0069428

80

0.0067656

960.0065898

112

0.0064148

Sr−2 [r − 1]] = Sr [Sr−2 [r − 1]] = −r となる．よって図 9 と同様のイベントにより bias が成立していると考えられる．確率 Pr(Zr = −r|E3 ) は Lemma 3 における Pr(Sl [Sl−2 [l − 1]] = −l|fl−1 = −l) と同様の手順で導出するとPr(Zr = −r|E3 ) =

[
]r+1
1
1
+ 1−
· Pr(S0 [S0 [r − 1]] = −r).
NN

ここで，Pr(S0 [S0 [r − 1]] = −r) はPr(S0 [S0 [r − 1]] = −r) =255∑

Pr(S0 [r − 1] = x ∧ S0 [x] = −r),x=0により算出する．理論値は表 5 に示す．表 4 の実験値と比較すると，大きな差があることがわかる．これより，Case 3 においては未発見のイベントが存在すると考えられる．未発見のイベントの詳細な証明については open ploblem とする．
図 10 における Theoretical value の導出には表 4 の実験値を用いる．
以上より，Pr(Zr = −r)

1+ Pr(Zr = −r | fr−1 = −r) · Pr(fr−1 = −r)
N+Pr(Zr = −r | E3 ) · Pr(E3 )[]11+ 1 − pr−1,2r ·− Pr(fr−1 = −r) − Pr(E3 ) · .
NN≈ pr−1,2r ·ここで pr−1,2r は Lemma 2 を変形した以下の()r−2 ∑()k ()r−3−k
r−1 ∑
r−t
1
1
P r(S1 [t] = 2r) r − t − 1
P r(S1 [r] = 2r) 1 −1−+,N
k! · NNN
t=2
k=0

で求めることができる.
図 10 に Zr = −r (r = 16, 32, 48, 64, 80, 96, 112) の Theorem 9 による理論値のグラフを示す．実験値と理論値に若干の誤差が存在する．これは理論値の計算の際に考慮できていないイベントの影響だと考えられるが，オーダーは合って32

Probability that Zr = -r holds

0.004100Experimental value
Semi-theoretical value
Theoretical value
Theoretical value of [10]Random

0.004050

0.004000

0.003950

0.003900
20

40

60
80
round number (r)

100

120

図 10: Zr = −r の理論値と実験値いるため，理論的考察の観点ではこの近似式で十分だと考える．また，文献 [12]の理論式より良く近似できていることが確認できる．さらに，表 4 に示した各イベントの実験値を Theorem 9 の理論式に代入し，確率を導出した．導出した値を Semi-theoretical value とする．図 10 より，Semi-theoretical value によりTheorem 9 をシミュレートすることで近似精度の改善が確認できた．表 4 の実
験値にそった各イベントの厳密な評価は open ploblem とする．

5.2.5

Optimal Bias Set

表 6 に optimal bias set を示す. P1 , P3 , P32 , P48 , P56 , P80 , P96 , P112 に関しては, 本章で示した既存の bias よりも強力な bias を攻撃に用いる. ここで, Zr = 0[14] と我々の示した Zr = r の比較を行う. 図 11 に Zr = 0 と Zr = r の実験値を示す. この図より P31 までは Zr = r の bias が大きく, それ以降 Zr = 0 が大きくなるため, 表 6 ではそのようになるように選択した. よって optimal bias set
は, Z1 , . . . , Z255 での最も強い bias の set である. これについては次節の実験により，正当性を保証する

33

0.003940

Zr = 0Zr = r

0.003935

Probability

0.003930
0.003925
0.003920
0.003915
0.003910
0.003905
0.003900
20

40
60
80
Round number (r)

100

120

図 11: Zr = 0 と Zr = r の比較 ( 3 ≤ r ≤ 255)

5.3

Broadcast RC4 に対する平文解読実験

我々は, 先ほど定義した optimal bias を用いて，Broadcast RC4 に対する解読実験を行った. 実験の詳細は以下の通りである.

1. ランダムに攻撃対象の平文 P を生成する.
2. 2x のランダムに生成した秘密鍵で P を暗号化して 2x 通りの暗号文を生成する.
3. 生成した暗号文の各 byte に対して, 頻度表を生成し, 最もカウントされているものを optimal bias set で XOR されたものとし, Pi = Ci ⊕ Zi (optimal
bias set) で平文を復元する.
P1 に関しては, 5.2.1 で述べたように Z2 に対する条件付き bias を用いるため, P2を復元したのちに Z2 = 0 になっているものを選択し頻度表を作成する.
上記の実験を, 256 通りの平文に対して, 26 , . . . , 235 通りの秘密から生成された暗号文に対して行った. 図 12 に P1 –P3 , P5 , P16 の実験結果を示す．横軸は攻撃に用いる暗号文数を，縦軸は成功確率を表している．ここで成功確率とは 256
通りの平文のうち何通りが成功したかを示すものである. たとえば任意の byte
において, 256 の平文において, 100 の平文のケースで正しく平文を復元できた場合は成功確率は 0.390625(= 100/256) となる. 図より, P2 に対しては 28 以上の暗号文数から成功確率が上昇し始め, 212 程度で成功確率が 1 になる. これまで,[17] では Ω で見積もられているのみであったが, 今回その暗号文数と成功確率の関係を明らかにした. 同様に P2 , P16 に関しては従来の評価では, 216 以上という評価であったが成功確率を 1 にするためには, 220 程度の暗号文数が必要である.
今回新しく見つけた P3 に関する結果も明らかにした. [14] で示された P5 に関し34

1.000000

Success Probability

0.800000

0.600000

0.400000
P1
P2
P3
P5
P16

0.200000

0.000000
5

10

15

20

25

30

35

The number of ciphertexts (2x)

図 12: P1,2,3,5,16 の暗号文数毎の攻撃成功確率ては, 224 以上の暗号文数から成功確率が上昇し始め, 231 程度で成功確率が 1 になる.
次に, 暗号文数に対する攻撃の成功確率を byte 毎に説明する. 図 13 に暗号文
数が 224 , 228 , 232 , 235 の場合の平文の各 byte の成功確率を示す. ここで Randomに, 平文の各 byte を guess した場合の成功確率は 1/256 = 0.00390625 である.
暗号文数を増やすことに応じて成功確率が上昇し, 232 以上の暗号文数ですべての平文 byte で成功確率が 0.5 を上回る. これは, optimal bias set が最も確率の高い bias set であることを意味し, 最適な set であることが分かる. しかしながら, 235 まで暗号文数を増やしても, 成功確率が 1 にはならない. これは, 1 番高
い bias と 2 番目に高い bias の差が小さいことが原因で成功確率を 1 にするためにはさらに多くの暗号文数が必要であると予想される.
図 14 に頻度表で上位 2 つに対して optimal bias set を XOR した場合の成功確率を示した. これは，2 つの候補に正しい平文が含めれている場合を成功として見積もったため，Random に, 平文の各 byte を guess した場合の成功確率は2/256 = 0.0078125 となる. これによると 234 の暗号文数で成功確率は 1 になった. この場合平文の値は一意には絞れないが, 各 byte は 2 つまで絞りこむことができる. また上位 3 の候補に対して optimal bias set を XOR したものも Table

15 に示す．Appendix にさらに詳細な暗号文数と成功確率の関係を示すグラフを掲載している．ここで平文一種類に対して, 図 13-15 の実験結果を得るためには,

1 CPU core (Intel(R) Core(TM) i7 CPU 920@2.67GHz) で約 1 日かかる. 本評
価では, 256 種類の平文に対し実験を行っている.
Optimal bias set を用いた Broadcast RC4 の平文解読攻撃による攻撃成功確率の平均値を暗号文数毎に表 7 に示す．232 の sample 数があれば, 1–257 byte の平文 byte を平均確率 0.9 以上で推測することが可能である. また，平文の最初の100 byte および 257 byte の解読に成功する確率が 1/256 (or 2/256, 3/256) ·5 になる暗号文数を表 8 に示す．これは random guess に対して 5 倍以上のアドバン

35

テージある暗号文数を最初の 100 byte と 257 byte 全てにおいて評価している．

225 以上で 100 byte の平文を十分高確率で推測可能である.
以上より Broadcast RC4 に対しては, 232 の暗号文数があれば, 1–257 byte の大部分の平文 byte を高確率 (0.9 以上) で決定することが可能である. また, 1,2byte 目や extended keylength-dependent bias などの確率の高い bias は 224 程度の sample で高確率で推測することが可能である.

36

1.000000

Success Probability

0.800000

224
228
232
235

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 13: 暗号文数毎の Pr (1 ≤ r ≤ 257) の攻撃成功確率 (one candidate)

1.000000

Success Probability

0.800000

224
228
232
234

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 14: 暗号文数毎の Pr (1 ≤ r ≤ 257) の攻撃成功確率 (two candidates)37

1.000000

Success Probability

0.800000

224
228
232
234

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 15: 暗号文数毎の Pr (1 ≤ r ≤ 257) の攻撃成功確率 (three candidates)

5.4

258 byte 目以降の平文の導出方法

本節では 258 byte 目以降の平文の効率的な導出方法を提案する．前節までの optimal bias set を用いた方法はキーストリームの初期の byte のみに生じる

bias に注目しており，r ≥ 258 の範囲の Pr の復元には適用できない．r が大き
い平文 byte を復元するためには任意の時刻で生じる bias (long-term bias) を利用する必要がある．最も強力な long-term bias は Mantin によって提案された
digraph repetition bias (ABSAB bias とも呼ばれている) [16] である．我々はZ1 , . . . , Z257 の optimal bias set と ABSAB bias を組み合わせることで P258 以降の平文 byte を逐次的に復元する方法を与える．

5.4.1

Based Long-term Bias (ABSAB bias) [16]ABSAB bias はキーストリームの 2byte 単位のシンボル（digraph）の分布の統計的な偏りのことであり，同じ digraph が短いギャップ S で繰り返されやすいことに注目している．ギャップ S は ABAB なら S は無し，ABCAB なら S は

C ，ABCDAB なら S は CD のように定義される．ギャップ S の長さを G としたとき，ABSAB bias は具体的には以下の式で表すことができる．

Zr || Zr+1 = Zr+2+G || Zr+3+G for G ≥ 0,(2)

ここで || は byte の連結である．式 (2) の成立確率は Theorem 10 で与えられる．

Theorem 10. [16] For small values of G the probability of the pattern ABSAB
in RC4 streams where S is a G-word string is (1 + e(−4−8G)/N /N ) · 1/N 2 .
G の値が異なる ABSAB bias を同時に利用する，すなわち成立確率が異なる
bias を同時に取り扱う場合には以下の Lemma で示される discrimination を利用する．
38

Lemma 4. [16] Let X and Y be two distributions and suppose that the independent events {Ei : 1 ≤ i ≤ k } occur with probabilities pX (Ei ) = pi in X andpY (Ei ) = (1 + bi ) · pi in Y. Then the discrimination D of the distributions is∑2i pi · bi .
この discrimination D は単一の bias の場合は D = p · q 2 のように対応する．

Mantin は bias がある分布とランダムな分布を確率 1 − α で識別するためのサン
プル数を以下の Lemma で与えている．

Lemma 5. [16] The number of samples that is required for distinguishing two
distributions that have discrimination D with success rate 1 − α (for both directions) is (1/D) · (1 − 2α) · log2 1−αα .
この Lemma は Broadcast RC4 の平文復元攻撃において，discrimination Dとサンプル数 Nciphertext が与えられたときに bias を含んだ分布 (式が成立する分布) を 1 つのランダムな分布 (式が成立しない分布) から分離できる確率が一定(constant) になることを示している．この一定の確率を Prdistingush と表記する．

5.4.2

ABSAB bias と optimal bias set を組み合わせた逐次的導出法

Broadcast RC4 の平文復元攻撃において，ABSAB bias は以下の方程式によって利用される．
(Cr || Cr+1 ) ⊕ (Cr+2+G || Cr+3+G )= (Pr ⊕ Zr || Pr+1 ⊕ Zr+1 ) ⊕ (Pr+2+G ⊕ Zr+2+G || Pr+3+G ⊕ Zr+3+G )= (Pr ⊕ Pr+2+G ⊕ Zr ⊕ Zr+2+G || Pr+1 ⊕ Pr+3+G ⊕ Zr+1 ⊕ Zr+3+G ).(3)ABSAB bias のイベントである式 (2) が成立するとき，上式からキーストリームの情報が排除され，平文と暗号文の関係式 (Cr || Cr+1 ) ⊕ (Cr+2+G || Cr+3+G ) =(Pr ⊕ Pr+2+G || Pr+1 ⊕ Pr+3+G ) = (Pr || Pr+1 ) ⊕ (Pr+2+G || Pr+3+G ) が得られる．
しかしながら，ストレートフォワードな方法では，識別攻撃のように G の値が異なる関係式を組み合わせて利用することは困難である．G の値が異なるとき，r を適切に選んだとしても関係式は異なってしまう．例えば，(round r and

G = 1) と (round r + 1 and G = 0) に関する関係式を考えた場合，関係式の右側はそれぞれ (Pr || Pr+1 ) ⊕ (Pr+3 || Pr+4 ) と (Pr+1 || Pr+2 ) ⊕ (Pr+3 || Pr+4 ) のようになる．このように独立した式しか得られない場合，異なる G の ABSAB

bias を集中させて利用できないため，Broadcast RC4 の平文復元攻撃を効率的に実行することが困難となる．
我々は，既知の平文 byte の情報を用いる逐次型の方法によって上記の問題を解決する．例えば，(round r and G = 1) と (round r + 1 and G = 0) に関する関係式を考えた場合，もし Pr ，Pr+1 および Pr+2 の値を事前に推測していたとすると，関係式の左側の未知変数は両方とも (Pr+3 || Pr+4 ) のように同じ表現に

39

なる．このように G が異なる複数の関係式をマージすることで効率的に平文を復元することが可能となる．このとき，P1 , . . . , P257 は optimal bias set から推測するとして，P258 以降の平文 Pr for r = 258, 259, . . . , PM AX を ABSAB biasを使って効率的に復元する方法を以下に与える．ここで，ABSAB bias のパラ
メータは G = 0, 1, . . . , GM AX とする．

Step 1 各暗号文について C258−3−GM AX , C258−2−GM AX , . . . , CPM AX を得て，r =258, . . . , PM AX および G = 0, . . . , GM AX の全ての組み合わせに対して(Cr−3−G || Cr−2−G ) ⊕ (Cr−1 || Cr ) のための頻度表 Tcount [r][G] へカウン
トする．ここで，式 (2) が成立するとき (Cr−3−G || Cr−2−G )⊕(Cr−1 || Cr ) =(Pr−3−G || Pr−2−G ) ⊕ (Pr−1 || Pr ) が成立する．
Step 2 r = 258 をセットする．
Step 3 Pr の値を推測する．
Step 3.1 G = 0, 1, . . . , GM AX の全てに対して，既に推測している
Pr−3−GM AX , . . . , Pr−2 の値を利用して Tcount [r][G] のカウント数を(Pr−1 || Pr ) のための頻度表 Tmarge [r] のカウント数に変換してマージする．
Step 3.2 既に推測している Pr−1 の値を利用して，Tmarge [r] から Pr のための頻度表 Tguess [r] を作る．具体的には，与えられた Pr−1 に対応する Pr のカウント数を Tmarge [r] から抜き出して Tguess [r] にカウント
する．Tguess [r] の中で最も頻度が高い値を正しい Pr として推測する．

Step 4 r をインクリメントする．もし，r = PM AX + 1 であればアルゴリズム終了する．そうでなければ，Step 3 へ．
Tmarge [r] から平文 byte を推測するとき，N 2 − 1 個の誤った候補の全てから正しい候補が識別されるときに正しい値が推測される．誤った候補がランダムな分布になると仮定すると，Tmarge [r] からの推測で正しい候補が得られる確率は(Prdistingush )N −1 となる．Step 3.2 では Pr−1 を用いて Tmarge [r] から Tguess [r]に変換することで，誤った候補の個数を N 2 − 1 から N − 1 へ減らしている．
2

Tguess [r] からの推測で正しい候補が得られる確率は (Prdistingush )N −1 となり，
Tmarge [r] から得る場合と比べて 1/(Prdistingush )N +1 倍高くなる．したがって，
Step 3.2 のテーブルの縮小処理は攻撃を更に最適化できていることがわかる．

5.4.3

Experimental Results

我々のアルゴリズムの有効性を示すために P258 , . . . , P261 (PM AX = 261) を復元する実験を行った．ABSAB bias のパラメータは D の増加が収束する程度の値として GM AX = 63 を選択した (このとき，D = 2−28.0 )．攻撃の際に観測できる暗号文数は 230 から 234 まで変化させることとし，攻撃に利用する P1 , . . . , P257
もこの暗号文から optimal bias set (candidate one) を用いて推測したものを用

40

230
231
232
233
234

1.000000

Success Probability

0.900000
0.8000000.700000
0.600000
0.500000
0.400000
0.300000
0.200000
190

200

210 220 230 240
Round number (r)

250

260

図 16: 暗号文数毎の Pr (192 ≤ r ≤ 257) の攻撃成功確率 (one candidate))

いる．試行回数は 256 回としたとき，P258 , . . . , P261 の復元の成功確率を表 9 に示す．ここで平文一種類に対して, 図 13-15 の実験結果を得るためには, 1 CPUcore (Intel(R) Core(TM) i7 CPU 920@2.67GHz) で約一週間かかる. また，逐次型の方法で用いる P192 , . . . , P257 の復元の成功確率は図 16 に示す．
興味深いことに，暗号文数 234 のときに，逐次型の方法に用いる P1 , . . . , P257
で確率 1 で復元できない byte があるにも関わらず，P258 , . . . , P261 は全て確率 1で復元できている．これは複数の bias を組み合わせて利用することで，逐次型の方法に用いる平文 byte がわずかに誤る程度の影響は受けにくくなっているからと推測できる．本実験では P261 までの復元を実行しているが，ABSAB bias
は long-term bias であるため，それ以後の byte の復元においても同様の確率で遷移していくと考えられる．よって，我々の逐次型の方法は 234 の暗号文で Pr(r ≥ 258) をほぼ確率 1 で復元することができる．
ここで，234 の暗号文が与えられたときの P262 以降の復元成功確率について考える. Lemma 5 と D = 2−28.0 より，234 の暗号文があれば， 確率 Prdistinguish =1 − 10−19 で random stream と識別可能である．そのとき，誤った候補がラン
ダムな分布になると仮定すると, (N − 1) の誤った候補から正しい候補を抽出できる確率は (Prdistinguish )N −1 で抑えられる. よって，我々の攻撃では平文の(257 + X) bytes 目は確率 ((Prdistinguish )N −1 )X = (Prdistinguish )(N −1)·X で復元可能である．たとえば, X = 240 and X = 250 のとき, 成功確率はそれぞれ0.99997, 0.97170 になる.

41

表 6: Optimal bias setrStrongest bias for Zr

Prob.(Theoretical)

Prob.(Experimental)

1

Z1 = 0|Z2 = 0 (Our)

2−8 · (1 + 2−1.009 )2−8 · (1 + 2−1.036 )2Z2 = 0 [17]2−8 · (1 + 20 )2−8 · (1 + 20.002 )3Z3 = 131 (Our)

2−8 · (1 + 2−8.089 )2−8 · (1 + 2−8.109 )−8· (1 + 2−7.581

2−8 · (1 + 2−7.611 )

4Z4 = 0 [14]

2

)

5–15

Zr = r (Our)max: 2−8 · (1 + 2−7.609 )

max: 2−8 · (1 + 2−7.335 )min: 2−8 · (1 + 2−7.718 )min: 2−8 · (1 + 2−7.535 )16Z16 = 240 [12]2−8 · (1 + 2−4.671 )2−8 · (1 + 2−4.811 )17–31

Zr = r (Our)max: 2−8 · (1 + 2−7.740 )

max: 2−8 · (1 + 2−7.576 )min: 2−8· (1 + 2−7.892)

min: 2−8 · (1 + 2−7.839 )2−8 · (1 + 2−5.176 )2−8 · (1 + 2−5.383 )max: 2−8 · (1 + 2−7.896 )

max: 2−8 · (1 + 2−7.868 )min: 2−8 · (1 + 2−8.049 )min: 2−8 · (1 + 2−8.039 )Z48 = 208 (Our)

2−8 · (1 + 2−5.651 )2−8 · (1 + 2−5.938 )49–63

Zt = 0 [14]−864Z64 = 192 (Our)

65–79

Zr = 0 [14]80Z80 = 176 (Our)

81–95

Zr = 0 [14]96Z96 = 160 (Our)

97–111

Zt = 0 [14]112

Z112 = 144 (Our)

113–255

32

Z32 = 224 (Our)

33–47

Zr = 0 [14]48

max: 2 · (1 + 2)−8−8.222
min: 2 · (1 + 2)

max: 2−8 · (1 + 2−8.046 )min: 2−8 · (1 + 2−8.238 )2−8 · (1 + 2−6.085 )2−8 · (1 + 2−6.496 )

max: 2−8 · (1 + 2−8.244 )min: 2−8 · (1 + 2−8.396 )max: 2−8 · (1 + 2−8.223 )min: 2−8 · (1 + 2−8.376 )2−8 · (1 + 2−6.574 )2−8 · (1 + 2−7.224 )max: 2−8 · (1 + 2−8.417 )min: 2−8 · (1 + 2−8.568 )

max: 2−8 · (1 + 2−8.398 )min: 2−8 · (1 + 2−8.565 )2−8 · (1 + 2−6.970 )2−8 · (1 + 2−7.911 )max: 2−8 · (1 + 2−8.589 )min: 2−8 · (1 + 2−8.738 )

max: 2−8 · (1 + 2−8.570 )min: 2−8 · (1 + 2−8.722 )2−8 · (1 + 2−7.300 )2−8 · (1 + 2−8.666 )Zt = 0 [14]max: 2−8 · (1 + 2−8.759 )min: 2−8 · (1 + 2−10.042 )max: 2−8 · (1 + 2−8.760 )
min: 2−8 · (1 + 2−10.041 )256

Z256 ̸= 0 (Our)N/A

2−8 · (1 − 2−9.407 )257

Z257 = 0 (Our)N/A

2−8 · (1 + 2−9.531 )42−8.070表 7: 成功確率の平均値 (1–257 byte)
暗号文数

candidate 1

candidate 2

candidate 3231

0.78499

0.89455

0.9191232

0.91469

0.97662

0.98624233

0.968400.99860

0.999472

340.98302

1

1

2

35

0.989251

1

2

表 8: random guess と比較して advantage のある暗号文数
解読する平文の長さ

candidate 1

candidate 2

candidate 3

100byte

25

2

25

2

225

257byte

229

229

228

表 9: Pr (r ≥ 258) の攻撃成功確率.

# of ciphertexts

P258

P259

P260

P261

230

0.003906 0.003906 0.000000 0.000000

3120.039062 0.007812 0.003906 0.007812

232

0.386719 0.152344 0.070312 0.027344

33

0.964844 0.941406 0.921875 0.902344

34

1.000000 1.000000 1.000000 1.000000

2
2

43

5.5

まとめ

本章では, Broadcast setting で RC4 を使う場合の評価を行った．まず，既知のbias よりも強い 4 つの新しい bias を示し，実験的にも確認した．そして，我々はこれらの bias を考慮した平文復元攻撃に最適な bias の set である optimal bias

set を導出した．次に，上記の optimal bias set を用いて，実際に平文解読実験
を計算機で行い，攻撃に必要な sample 数 (暗号文数) を成功確率と共に見積もった．結果として，232 程度の異なる鍵で生成された暗号文があれば，optimal bias

set を用いることにより, 確率 0.5 以上で平文の 1–255 byte 目の各 byte を復元できる. また, 証明はついていないが Z256 と Z257 に関して実験的に攻撃に有効な

bias を発見した. これをさらに用いることで, 平文の 1–257 byte が復元可能になる.
最後に, 258 byte 以降を効率よくもとめる方法を提案した．この方法は EU-

ROCRYPT2005 で Matin により示された Digraph Repetition bias [16] と，本稿で求めた Z1 –Z257 の optimal bias set を組み合わせて，逐次的に求めていくものである．この手法を用いることにより，234 程度の暗号文から 258 byte 以降の平文も求めることができる．ここで，この Digraph Repetition bias は, longterm bias であるため，258 byte 以降の任意のすべての平文を暗号文から求めることができる．理論的には，初めの 250 bytes ≈ 1000 T bytes の平文は 234 の異なる鍵で生成された暗号文から確率 0.97170. で導出可能である．
以上より，我々の攻撃では, 任意の平文を暗号文のみから導出できる Full Plain-text Recovery Attack でありかつ，現実的なデータ量で攻撃可能である．

44

謝辞
本評価における計算機実験の一部は広島大学情報メディア教育研究センター

HPC グリッドシステムおよび情報爆発 InTrigger プラットフォームを用いて実施した．ここに記して謝意を表す．

参考文献[1] Carlisle M. Adams, Ali Miri, and Michael J. Wiener, editors. Selected
Areas in Cryptography, 14th International Workshop, SAC 2007, Ottawa,
Canada, August 16-17, 2007, Revised Selected Papers, volume 4876 of
Lecture Notes in Computer Science. Springer, 2007.
[2] Eli Biham and Yaniv Carmeli. Eﬃcient reconstruction of rc4 keys frominternal states. In Kaisa Nyberg, editor, FSE, volume 5086 of Lecture
Notes in Computer Science, pages 270–288. Springer, 2008.
[3] Brice Canvel, Alain P. Hiltgen, Serge Vaudenay, and Martin Vuagnoux. Password interception in a ssl/tls channel. In Dan Boneh, editor, CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages
583–599. Springer, 2003.
[4] Jiageng Chen and Atsuko Miyaji. A new practical key recovery attackon the stream cipher rc4 under related-key model. In Xuejia Lai, Moti
Yung, and Dongdai Lin, editors, Inscrypt, volume 6584 of Lecture Notes
in Computer Science, pages 62–76. Springer, 2010.
[5] Jiageng Chen and Atsuko Miyaji. Generalized analysis on key collisionsof stream cipher rc4. IEICE Transactions, 94-A(11):2194–2206, 2011.
[6] T. Dierks and C. Allen. The tls protocol version 1.0, 1999. http://www.
ietf.org/rfc/rfc2246.txt.
[7] Scott R. Fluhrer, Itsik Mantin, and Adi Shamir. Weaknesses in the keyscheduling algorithm of rc4. In Serge Vaudenay and Amr M. Youssef,
editors, Selected Areas in Cryptography, volume 2259 of Lecture Notes in
Computer Science, pages 1–24. Springer, 2001.
[8] Scott R. Fluhrer and David A. McGrew. Statistical analysis of the alleged
rc4 keystream generator. In Bruce Schneier, editor, FSE, volume 1978 of
Lecture Notes in Computer Science, pages 19–30. Springer, 2000.
[9] Alan O. Freier, Philip Karlton, and Paul C. Kocher. The ssl protocol
version 3.0, 1996. http://www.mozilla.org/projects/security/pki/
nss/ssl/draft302.txt.
45

[10] Jovan Dj. Golic. Linear statistical weakness of alleged rc4 keystream generator. In Walter Fumy, editor, EUROCRYPT, volume 1233 of Lecture
Notes in Computer Science, pages 226–238. Springer, 1997.
[11] Sourav Sen Gupta, Subhamoy Maitra, Goutam Paul, and Santanu Sarkar.
(non-)random sequences from (non-)random permutations - analysis of
rc4 stream cipher. Cryptology ePrint Archive, Report 2011/448, 2011.
http://eprint.iacr.org/.
[12] Sourav Sen Gupta, Subhamoy Maitra, Goutam Paul, and Santanu Sarkar.
Proof of empirical rc4 biases and new key correlations. In Ali Miri andSerge Vaudenay, editors, Selected Areas in Cryptography, volume 7118 ofLecture Notes in Computer Science, pages 151–168. Springer, 2011.
[13] Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen, and Sven
Verdoolaege. Analysis methods for (alleged) rc4. In Kazuo Ohta andDingyi Pei, editors, ASIACRYPT, volume 1514 of Lecture Notes in Computer Science, pages 327–341. Springer, 1998.
[14] Subhamoy Maitra, Goutam Paul, and Sourav Sengupta. Attack on broadcast rc4 revisited. In Antoine Joux, editor, FSE, volume 6733 of Lecture
Notes in Computer Science, pages 199–217. Springer, 2011.
[15] Itsik Mantin. Analysis of the stream cipher rc4. Master’s Thesis, The Weizmann Institute of Science, Israel, 2001. http://www.wisdom.weizmann.
ac.il/~itsik/RC4/rc4.html.
[16] Itsik Mantin. Predicting and distinguishing attacks on rc4 keystream generator. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of Lecture
Notes in Computer Science, pages 491–506. Springer, 2005.
[17] Itsik Mantin and Adi Shamir. A practical attack on broadcast rc4. In
Mitsuru Matsui, editor, FSE, volume 2355 of Lecture Notes in Computer
Science, pages 152–164. Springer, 2001.
[18] Mitsuru Matsui. Key collisions of the rc4 stream cipher. In Orr Dunkelman, editor, FSE, volume 5665 of Lecture Notes in Computer Science,
pages 38–50. Springer, 2009.
[19] Alexander Maximov and Dmitry Khovratovich. New state recovery attack
on rc4. In David Wagner, editor, CRYPTO, volume 5157 of Lecture Notes
in Computer Science, pages 297–316. Springer, 2008.
[20] Ilya Mironov. (not so) random shuﬄes of rc4. In Moti Yung, editor,
CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 304–
319. Springer, 2002.

46

[21] Atsushi Nagao, Toshihiro Ohigashi, Takanori Isobe, and Masakatu Morii.
New classes of weak keys on rc4 using predictive state, 2012. Computer
Security Symposium 2012.
[22] Atsushi Nagao, Toshihiro Ohigashi, Takanori Isobe, and Masakatu Morii.
How to expand weak-key space of rc4, 2013. The 30th Symposium on
Cryptography and Information Security (to appear).
[23] Goutam Paul and Subhamoy Maitra. Permutation after rc4 key scheduling
reveals the secret key. In Adams et al. [1], pages 360–377.
[24] Souradyuti Paul and Bart Preneel. A new weakness in the rc4 keystream
generator and an approach to improve the security of the cipher. In Bimal K. Roy and Willi Meier, editors, FSE, volume 3017 of Lecture Notes
in Computer Science, pages 245–259. Springer, 2004.
[25] Andrew Roos. A class of weak keys in the RC4 stream cipher, 1995. Twoposts in sci.crypt.
[26] Pouyan Sepehrdad, Serge Vaudenay, and Martin Vuagnoux. Discovery
and exploitation of new biases in rc4. In Alex Biryukov, Guang Gong, andDouglas R. Stinson, editors, Selected Areas in Cryptography, volume 6544
of Lecture Notes in Computer Science, pages 74–91. Springer, 2010.
[27] Pouyan Sepehrdad, Serge Vaudenay, and Martin Vuagnoux. Statistical
attack on rc4 - distinguishing wpa. In Kenneth G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages
343–363. Springer, 2011.
[28] Yoshiaki Shiraishi, Toshihiro Ohigashi, and Masakatu Morii. Internal-state
reconstruction of a stream cipher rc4. IEICE Transactions, 86-A(10):2636–
2638, 2003.
[29] Ryoichi Teramura, Toshihiro Ohigashi, Hidenori Kuwakado, and Masakatu
Morii. Generalized classes of weak keys on rc4 using predictive state.
IEICE Transactions, 94-A(1):10–18, 2011.
[30] Serge Vaudenay and Martin Vuagnoux. Passive-only key recovery attacks
on rc4. In Adams et al. [1], pages 344–359.

A

平文解読実験の詳細データ

47

218

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 17: Success probability for Pr (1 ≤ r ≤ 257) with 218 samples (one candi-

date)

220

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 18: Success probability for Pr (1 ≤ r ≤ 257) with 220 samples (one candi-

date)

48

222

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 19: Success probability for Pr (1 ≤ r ≤ 257) with 222 samples (one candi-

date)

224

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 20: Success probability for Pr (1 ≤ r ≤ 257) with 224 samples (one candi-

date)

49

226

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 21: Success probability for Pr (1 ≤ r ≤ 257) with 226 samples (one candi-

date)

228

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 22: Success probability for Pr (1 ≤ r ≤ 257) with 228 samples (one candi-

date)

50

230

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 23: Success probability for Pr (1 ≤ r ≤ 257) with 230 samples (one candi-

date)

232

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 24: Success probability for Pr (1 ≤ r ≤ 257) with 232 samples (one candi-

date)

51

235

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 25: Success probability for Pr (1 ≤ r ≤ 257) with 235 samples (one candi-

date)

218

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 26: Success probability for Pr (1 ≤ r ≤ 257) with 218 samples (two candi-dates)

52

220

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 27: Success probability for Pr (1 ≤ r ≤ 257) with 220 samples (two candi-dates)

222

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 28: Success probability for Pr (1 ≤ r ≤ 257) with 222 samples (two candi-dates)

53

224

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 29: Success probability for Pr (1 ≤ r ≤ 257) with 224 samples (two candi-dates)

226

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 30: Success probability for Pr (1 ≤ r ≤ 257) with 226 samples (two candi-dates)

54

228

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 31: Success probability for Pr (1 ≤ r ≤ 257) with 228 samples (two candi-dates)

230

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 32: Success probability for Pr (1 ≤ r ≤ 257) with 230 samples (two candi-dates)

55

232

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 33: Success probability for Pr (1 ≤ r ≤ 257) with 232 samples (two candi-dates)

234

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 34: Success probability for Pr (1 ≤ r ≤ 257) with 234 samples (two candi-dates)

56

218

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 35: Success probability for Pr (1 ≤ r ≤ 257) with 218 samples (threecandidates)

220

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 36: Success probability for Pr (1 ≤ r ≤ 257) with 220 samples (threecandidates)

57

222

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 37: Success probability for Pr (1 ≤ r ≤ 257) with 222 samples (threecandidates)

224

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 38: Success probability for Pr (1 ≤ r ≤ 257) with 224 samples (threecandidates)

58

226

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 39: Success probability for Pr (1 ≤ r ≤ 257) with 226 samples (threecandidates)

228

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 40: Success probability for Pr (1 ≤ r ≤ 257) with 228 samples (threecandidates)

59

230

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 41: Success probability for Pr (1 ≤ r ≤ 257) with 230 samples (threecandidates)

2321.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 42: Success probability for Pr (1 ≤ r ≤ 257) with 232 samples (threecandidates)

60

234

1.000000

Success Probability

0.800000

0.600000

0.400000

0.200000

0.000000
0

50

100
150
Round number (r)

200

250

図 43: Success probability for Pr (1 ≤ r ≤ 257) with 234 samples (threecandidates)

61