Cryptography Reference
In-Depth Information
In [110, Section 7.2], Glimpse Theorem and Finney cycles are considered
together to prove that P(z
r
= i
r
−1) ≈
N
(1−
N
2
). Applying Theorem 6.1.1,
the number of keystream bytes required for a distinguisher based on this bias
turns out to be 2
40
.
In [122, Section 6], a very small non-uniformity in the distribution of the
first byte of the keystream output is observed (without any proof). This bias is
attributed to the non-uniformity in the permutation after the KSA. The first
detailed theoretical analysis of the distribution of the first keystream byte z
1
is performed in [157].
Another work [139] reported a negative bias in the equality of the first
two keystream output bytes. It claims that P(z
1
= z
2
) =
N
(1 −
N
). The
distinguisher based on this bias requires 2
24
pairs of keystream bytes as per
Theorem 6.1.1.
1
6.2.1 Negative Bias in the First Byte toward Zero
Mironov [122] observed that the first keystream byte of RC4 is slightly
negatively biased toward zero. After almost a decade, it is recently proved
in [157]. We present this result here.
Note that PRGA begins with i
0
= j
0
= 0. In the first round, i
1
= 1 and
j
1
= S
0
[i
1
] = S
0
[1]. First, we show that there is a special path in which z
1
can never be equal to zero.
Lemma 6.2.1. If S
0
[j
1
] = 0, z
1
cannot be 0.
Proof: Suppose S
0
[j
1
] = 0. After the swap in the first round, S
1
[1] =
S
0
[j
1
] = 0 and S
1
[j
1
] = S
0
[1] = j
1
. Now,
= S
1
[S
1
[1] + S
1
[j
1
]]
= S
1
[0 + j
1
]
= S
1
[j
1
]
= j
1
= S
0
[1].
z
1
Now, if z
1
were 0, one must have S
0
[1] = 0 = S
0
[j
1
], implying
1 = j
1
= S
0
[1] = 0,
which is a contradiction. Hence, z
1
cannot be 0.
Next, let us present the main result.
Theorem 6.2.2. Assume that the initial permutation S
0
is randomly chosen
from the set of all possible permutations of {0,...,N −1}. Then
1
N
−
1
P(z
1
= 0) =
N
2
.
