Key Recovery from State Information - RC4: Stream Cipher and Its Variants - page 87

Then, by linearity of expectation, we have

M w τ

n w

E(freq w ) = E(u τ,x )

τ=1 x=1

M w τ

n w

= P(u τ,x = 1)

τ=1 x=1

M w τ

n w

= p w τx .

τ=1 x=1

Corollary 4.5.5. For 0 ≤ w ≤ l− 1, given a threshold H, P(freq w > TH)
can be estimated as 1− T H P(freq w = c), where P(freq w = c)'s are as given

c=0

in Theorem 4.5.4, item 2.

Define the following notation.

q yx = 1−p yx

N −1 ,

for 0 ≤ x ≤M y ,0 ≤ y ≤ N −1.

Theorem 4.5.6. For 0 ≤ w ≤l−1, we have the following.
(1) The expected number of distinct values in Z N occurring in T w is given by

M w τ M w τ

E dist = N − n w

n w

(1−p w τ x )−(N −1) (1−q w τ x ).

τ=1 x=1 τ=1 x=1

(2) The expected number of distinct values in Z N , each occurring exactly c
times in T w , is given by

E c = p(τ) + (N −1) q(τ),

{τ 1 ,τ 2 ,...,τ c }
⊆{1,2,...,n w }

{τ 1 ,τ 2 ,...,τ c }
⊆{1,2,...,n w }

where

0
@

1
A

0
@

1
A

M w τ r

M w r

c

p(τ) = p w τ r x (1−p w τ r x ′ ) (1 −p w r x )

r=1 x=1 x ′ =x x=1

r∈{1,2,...,n w }\
{τ 1 ,τ 2 ,...,τ c }

and

0
@

1
A

0
@

1
A

M wτ r

M w r

c

q(τ) = q w τ r x (1−q w τ r x ′ ) (1−q w r x ) .

r=1 x=1 x ′ =x x=1

r∈{1,2,...,n w }\
{τ 1 ,τ 2 ,...,τ c }