Cryptography Reference
In-Depth Information
2
−16
+ 2
−32
−2
−48
≈ 0.0000152590, which is slightly greater than 2
−16
. Note
that if one checks the equality of two n-bit random integers, the probability
of that event turns out to be 2
−n
only, which is as low as 2
−32
for n = 32.
Now the result given in [40] can be formalized as
Theorem 10.4.3. In HC-128, consider a block of 512 many keystream words
corresponding to the array P. For 0 ≤ u = v ≤ 511,
⊕s
v
) = (P[u]⊕P[v])) = γ
8,32
> 2
−16
.
Prob((s
u
Proof: The result follows from Lemma 10.4.1 and Lemma 10.4.2.
A sharper result which gives twice the above probability is as follows.
Theorem 10.4.4. In HC-128, consider a block of 512 many keystream words
corresponding to the array P. For any u,v, 0 ≤ u= v < 500, if
(s
(0)
u
= s
(0)
v
) & (s
(2)
u
= s
(2)
v
)
,
then
Prob((s
u+12
⊕s
v+12
) = (P[u + 12]⊕P[v + 12])) ≈
1
2
15
.
Proof: From Lemma 10.4.1, s
(b)
⊕s
(b
v
= P[u]
(b)
⊕P[v]
(b)
if and only if
u
h
1
(P[u ⊟ 12])
(b)
= h
1
(P[v ⊟ 12])
(b)
,
for b = 0,1,2,3.
Given that s
(0
u
= s
(0)
v
and s
(2
u
= s
(2
v
, we have
P[u]
(0)
= P[v]
(0)
and P[u]
(2)
= P[v]
(2)
if and only if
h
1
(P[u ⊟ 12])
(0)
= h
1
(P[v ⊟ 12])
(0)
and h
1
(P[u ⊟ 12])
(2)
= h
1
(P[v ⊟ 12])
(2)
.
Thus,
Prob
P[u]
(0)
= P[v]
(0)
& P[u]
(2)
= P[v]
(2)
| s
(0
u
= s
(0)
& s
(2
u
= s
(2)
v
v
h
1
(P[u ⊟ 12])
(0)
= h
1
(P[v ⊟ 12])
(0)
&
h
1
(P[u ⊟ 12])
(2)
= h
1
(P[v ⊟ 12])
(2)
= Prob
= γ
8,16
(from Lemma 10.4.2)
≈
2
15
.
By definition, h
1
(x) = Q[x
(0)
] + Q[256 + x
(2)
]. So the equalities P[u]
(0)
=
P[v]
(0)
and P[u]
(2)
= P[v]
(2)
give h
1
(P[u]) = h
1
(P[v]) and this in turn gives
s
u+12
⊕s
v+12
= P[u + 12]⊕P[v + 12] by Lemma 10.4.1.
The event (s
(0)
u
= s
(2
v
) occurs with probability 2
−16
for a
random stream. If the probability of this event in HC-128 is away from 2
−16
,
we would immediately have a distinguisher. The experimental data does not
reveal any observable bias for this event. However, it would be interesting to
investigate if there exists a bias of very small order for this or a similar event
in HC-128.
The Jenkins' Correlation or Glimpse Theorem (see Section 5.2) is an im-
portant result on the weakness of RC4 stream cipher. This result quanti-
fies the leakage of state information into the keystream of RC4. The leakage
= s
(0)
& s
(2)
u
v