Cryptography Reference
In-Depth Information
Due to the swap in round r, S
r
[j
r
] is assigned the value of S
r−1
[r]. Thus,
we get
P(z
r
= r−S
r−1
[r]) ≈
2
N
,
for r ≥ 1.
The motivation of rewriting the Glimpse Theorem in the form of Corol-
lary 5.2.2 comes from the fact that relating “z
r
to S
r−1
[r]” will ultimately
relate “z
r
to the secret key bytes,” as the permutations in the initial rounds
of the PRGA have correlations with the secret key.
More details on Glimpse Theorem and its generalizations are discussed
in [110, Chapter 7] and [108, Section 3].
5.3 Biased Permutation Index Selection for the First
Keystream Byte
The index t
1
in S
1
from where the first byte z
1
of RC4 keystream is chosen
is biased. The probability of t
1
= 2 is approximately twice as large as that of
t
1
taking any other value. This result first appeared in [131].
Theorem 5.3.1. Assume that the permutation S
0
after the KSA is chosen
uniformly at random from the set of all possible permutations of Z
N
. Then
the probability distribution of the output index t
1
, that selects the first byte z
1
of the keystream output, is given by
8
<
:
N
for odd x;
1
N
2
N(N−1)
−
for even x= 2;
P(t
1
= x) =
2
N
1
N(N−1)
−
for x = 2.
Proof: In the first round of the PRGA, i
1
is set to 1, j
1
is updated to
S
0
[1]. So after the swap in this round, S
1
[i
1
] contains the value S
0
[j
1
], i.e.,
S
0
[S
0
[1]] and S
1
[j
1
] contains the value S
0
[i
1
], i.e., S
0
[1]. Now,
S
1
[j
1
] = 1
S
0
[1] = 1,
⇐⇒
since S
1
[j
1
] = S
0
[1]
j
1
since j
1
= S
0
[1]
⇐⇒
= 1,
S
1
[1] = 1,
since we started with S
1
[j
1
] = 1
=⇒
S
1
[i
1
] = 1,
since we started with i
1
=⇒
= 1.
Hence,
8
<
1
N
if u = 1 and v = 1;
0
if u= 1 and v = 1;
P(S
1
[i
1
] = u,S
1
[j
1
] = v) =
0
if u= 1 and v = u;
:
1
N(N−1)
otherwise.
