Cryptography Reference
In-Depth Information
From Lemma 10.2.3 and the construction of ζ
i
, we have
p
b
if b = 0,1;
Prob(m
b
= 1) =
1−p
b
if 2 ≤ b < 32.
This gives
E(M) ≈ 1 +
1
2
+ 30(1−
1
3
)
=
21.5.
Theorem 10.2.4 shows the correlation of the HC-128 keystream word s
i
with its linear approximation ζ
i
.
10.3 Distinguishing Attacks on HC-128
Linear approximation of the feedback functions g
1
,g
2
can be used to mount
distinguishing attacks on HC-128. Primarily, there are three distinguishers for
HC-128. Since addition and XOR-operation exactly match for the least signif-
icant bit (LSB), no approximation is needed to devise a distinguisher based on
the LSB's of the keystream words. Such a distinguisher was proposed by Wu,
the designer himself, in [187]. We discuss this in Section 10.3.1. Subsequently,
in [105], extension of this distinguisher to 30 other bits were presented. We
discuss this work in Section 10.3.2. Both the above distinguishers work across
two blocks of HC-128 keystream, where each block consists of 512 consecutive
keystream words. In Section 10.3.3, we present the distinguisher of [106] that
is spread over three blocks of the keystream.
10.3.1 Wu's LSB-Based Distinguisher
This result appeared in the original design proposal [187]. Though the
keystream words of HC-128 are generated using both the arrays P and Q,
the updates of P and Q arrays are independent. For 512 many iterations,
the array P is updated with the older values from P itself. For the next 512
many iterations, the array Q is updated with the older values of Q. In this
way, alternating updates of P and Q continue. Table 10.1 illustrates how the
keystream words s
i
's are related to the array elements P[i]'s and Q[i]'s.
In general, for 0 ≤ (i mod 1024) < 512, the keystream output word of
HC-128 is produced as
s
i
= h
1
(P[i ⊟ 12])⊕P[i mod 512],
following an update of P[i mod 512] via addition of g
1
(P[i⊟3],P[i⊟10],P[i⊟
