Cryptography Reference
In-Depth Information
Once the final probability
= P(S
N
[1] = f
1
)
ω
N+1
is computed, one can use Theorem 5.6.3 to get
P(z
N+1
= N + 1−f
1
)
1
N
=
(1 + ω
N+1
).
For N = 256, ω
N+1
= ω
257
≈ 0.0522 and
P(z
257
= 257−f
1
)
≈
1
N
(1 + 0.0522)
≈ 0.0041.
This also conforms to experimental observation.
5.6.2 Biases of z
R
toward r for Initial Keystream Bytes
The biases of z
r
with r −f
r
for the initial keystream output bytes have
already been pointed out. Interestingly, experimental observation reveals bias
of z
r
with f
r−1
too. The results are presented in Table 5.6 which is obtained
from over a hundred million (10
8
) trials with randomly chosen keys of 16
bytes. For proper random association, P(z
r
= f
r−1
) should have been
1
256
,
i.e., approximately 0.0039.
r
P(z
r
= f
r−1
)
1-8
0.0043 0.0039 0.0044 0.0044 0.0044 0.0044 0.0043 0.0043
9-16
0.0043 0.0043 0.0043 0.0042 0.0042 0.0042 0.0042 0.0042
17-24
0.0041 0.0041 0.0041 0.0041 0.0041 0.0040 0.0040 0.0040
25-32
0.0040 0.0040 0.0040 0.0040 0.0040 0.0040 0.0040 0.0040
33-40
0.0039 0.0039 0.0039 0.0039 0.0039 0.0039 0.0039 0.0039
41-48
0.0039 0.0039 0.0039 0.0039 0.0039 0.0039 0.0039 0.0039
TABLE 5.6: Additional bias of the keystream bytes toward the secret key.
A detailed theoretical analysis of the event z
r
= f
r−1
in general and explicit
derivation of a formula for P(z
r
= f
r−1
) appeared in [103]. Before giving the
general proof, let us first explain the case corresponding to r = 3, i.e.,
1
256
.
P(z
3
= f
2
) >
Assume that after the third round of the KSA, S
3
[2] takes the value f
2
, and
is hit by j later in the KSA. Then f
2
is swapped with S
κ
[κ] and consider that
