Cryptography Reference
In-Depth Information
Prob(χ
i
= χ
j
)
= Prob(χ
i
⊕χ
j
= H(Z
i
)⊕H(Z
j
))Prob(H(Z
i
) = H(Z
j
)) +
Prob(χ
i
⊕χ
j
= H(Z
i
)⊕H(Z
j
)⊕1)Prob(H(Z
i
) = H(Z
j
)⊕1)
≈
365
3
6
1
2
+ 2
−81
1−
365
3
6
1
2
=
1
1
3
6
2
81
.
−2
−81
+
2
+
The above analysis shows that there exist biases in the event (χ
i
= χ
j
),
which can be used to mount a distinguishing attack. The probability of the
above event can be written as p
χ
(1 + q
χ
), where p
χ
=
1
2
1
and q
χ
=
3
6
2
80
.
4
2
p
χ
q
χ
= 3
12
2
165
pairs of keystream
word combinations of the form (χ
i
,χ
j
) for a success probability 0.9772. Since
each block of 512 = 2
9
According to Section 6.1, one would require
512
2
≈
2
17
many pairs, the required number of keystream words is approximately
3
12
2
156
≈ 2
19
2
156
= 2
175
.
The distinguisher presented in Theorem 10.3.7 may be extended to other
bits in a similar line as in Section 10.3.2. However, the bias would be weaker
than that presented in Theorem 10.3.7 and so the extended distinguisher
would require more keystream words.
keystream words provides approximately
10.4 Collisions in H
1
, H
2
and State Leakage in Keystream
The previous sections concentrated on the functions g
1
,g
2
. Here, in a
different direction, we study the other two functions h
1
,h
2
. Without loss of
generality, let us focus on the keystream block corresponding to the P array,
i.e., the block of 512 rounds where P is updated in each round and Q remains
constant. As j runs from 0 to 511, let the corresponding output h
1
(P[j ⊟
12]) ⊕ P[j] be denoted by s
j
. Recall that h
1
(x) = Q[x
(0)
] + Q[256 + x
(2)
].
The results presented this section are in terms of the function h
1
. The same
analysis holds for the function h
2
in the other keystream block.
In [40], it has been observed that
⊕s
j+1
= P[j]⊕P[j + 1]) ≈ 2
−16
,
Prob(s
j
(10.13)
where s
j
,s
j+1
are two consecutive keystream output words. A more detailed
study of this observation is studied [105] and a sharper association is found,
which gives twice the above probability. In this section, we essentially present
this and related results of [105].
The following technical result shows that XOR of two words of P is leaked
in the keystream words, if the corresponding values of h
1
(.) collide.
Lemma 10.4.1. For 0 ≤ u = v ≤ 511, s
u
⊕s
v
= P[u] ⊕P[v] if and only if
h
1
(P[u ⊟ 12]) = h
1
(P[v ⊟ 12]).
