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
Search WWH ::




Custom Search