Cryptography Reference
In-Depth Information
r
P(z
r
= r−f
r
)
1-8
0.0053 0.0053 0.0053 0.0053 0.0052 0.0052 0.0051 0.0051
9-16
0.0050 0.0050 0.0049 0.0049 0.0048 0.0048 0.0047 0.0047
17-24
0.0046 0.0046 0.0045 0.0045 0.0044 0.0044 0.0043 0.0043
25-32
0.0043 0.0042 0.0042 0.0042 0.0041 0.0041 0.0041 0.0041
33-40
0.0040 0.0040 0.0040 0.0040 0.0040 0.0040 0.0040 0.0040
41-48
0.0040 0.0040 0.0039 0.0039 0.0039 0.0039 0.0039 0.0039
TABLE 5.5: Klein bias probabilities computed following Theorem 5.6.3
Extension to 256-th and 257th Keystream Bytes
Interestingly, the Klein type biases again reappear after rounds 256 and
257 [103].
During the N-th round of the PRGA, i
N
= N mod N = 0. Taking X = f
0
,
τ = 0 and r = N in Lemma 5.6.1, we can compute the initial probability as
P(S
0
[0] = f
0
)
= P(S
N
[0] = f
0
)
N
N −1
N
1
N
≈
+
(by Corollary 3.1.6).
and hence the final probability
ω
N
= P(S
N−1
[0] = f
0
)
can be easily computed. Now, using Theorem 5.6.3, the bias in 256th round
is given by
P(z
N
= N −f
0
)
1
N
=
(1 + ω
N
).
1
For N = 256, ω
N
= ω
256
≈ 0.1383 and the bias turns out to be
256
(1 +
0.1383) ≈ 0.0044. Experimental results also confirm this bias.
The bias in the 257-th keystream output byte follows from Theorem 3.1.14,
i.e.,
2(N−1)
N −1
N
P(S
N
[S
N
[1]] = K[0] + K[1] + 1) ≈
.
During the (N + 1)-th round, we have, i
N+1
= (N + 1) mod N = 1. Taking
X = f
1
, τ = 1 and r = N + 1 in Lemma 5.6.1, we have the initial probability
as
P(S
1
[1] = f
1
)
= P(S
N
[S
N
[1]] = f
1
)
2(N−1)
N −1
N
=
.
