Cryptography Reference
In-Depth Information
Substituting the values above in Equation (6.3), we get
z
r
= 0 & S
r−1
[r] = r
P
2
4
x=r−y
3
S
r
[x + y] = 0 & S
r
[r] = x
5
S
r−1
[r] = y
=
P
P
y=r
2
3
4
5
1
N(N −1)
S
r−1
[r] = y
=
P
0 +
y=r
x=r−y
x=0
(N −2)
1
N(N −1)
S
r−1
[r] = y
=
P
y=r
N −2
N(N −1)
S
r−1
[r] = y
=
P
y=r
S
r−1
[r] = r
N −2
N(N −1)
N −2
N(N −1)
=
1−P
=
(1−p
r−1,r
)
Now, let us state the main theorem on the bias of RC4 initial bytes from
rounds 3 to 255.
Theorem 6.2.9. For 3 ≤ r ≤ 255, the probability that the r-th RC4 keystream
byte is equal to 0 is
N
+
c
r
1
P(z
r
= 0) =
N
2
,
.
N
2
N−1
−
N
where the value of c
r
is
p
r−1,r
Proof: Adding the expressions of Lemma 6.2.7 and 6.2.8, one obtains
2
N −2
N(N −1)
P(z
r
= 0)
= p
r−1,r
N
+
(1−p
r−1,r
)
p
r−1,r
N −1
+
N −2
N(N −1)
=
1
N
+
1
N −1
−
1
N
=
p
r−1,r
.
(6.5)
p
r−1,r
. Note
N
2
N−1
1
c
N
2
, with the value of c
r
as
−
N
Hence, P(z
r
= 0) =
N
+
that the values p
r−1,r
can be explicitly calculated using Lemma 6.2.5.
In Theorem 6.2.9, the parameter c
r
that quantifies the bias is a function of
r. The next result is a corollary of Theorem 6.2.9 that provides exact numeric
bounds on P(z
r
= 0) within the interval 3 ≤ r ≤ 255, depending on the
corresponding bounds of c
r
within the same interval.