Cryptography Reference
In-Depth Information
Proof: If x
1
= x
2
(this happens with probability 2
−m
), then H(x
1
) =
H(x
2
) happens with probability 1. If x
1
= x
2
(this happens with proba-
bility 1 − 2
−m
), then H(x
1
) = H(x
2
) happens with probability 2
−n
. Thus,
Prob(H(x
1
) = H(x
2
)) = 2
−m
1 + (1−2
−m
)2
−n
.
For HC-128 S-box, whose outputs are H(ξ
i
) and H(ξ
j
), we have m = 80
and n = 1. According to Theorem 10.3.1, Prob(H(ξ
i
) = H(ξ
j
)) =
2
+ 2
−81
.
Hence, for 1024τ + 10 ≤ j < i < 1024τ + 511,
Prob
[s
i
]
0
⊕[s
i−1024
]
0
⊕[s
i−3
]
10
⊕[s
i−10
]
8
⊕[s
i−1023
]
23
= [s
j
]
0
⊕[s
j−1024
]
0
⊕[s
j−3
]
10
⊕[s
j−10
]
8
⊕[s
j−1023
]
23
=
2
+ 2
−81
.
Thus, one can mount a distinguisher based on the equality of the least
significant bits of the keystream word combinations s
i
⊕s
i−1024
⊕ (s
i−3
10)⊕(s
i−10
8)⊕(s
i−1023
23) and s
j
⊕(s
j−3
10)⊕(s
j−10
8) ⊕ (s
j−1023
23). According to Section 6.1, this distinguisher requires
approximately 2
164
many equations of the above form or a total of 2
156
many
keystream words for a success probability 0.9772.
⊕s
j−1024
10.3.2 Extension of Wu's Distinguisher to Other Bits
It has been commented in [187] that the distinguishing attack exploiting
the other 31 bits would not be effective due to the use of modulo addition. In
contrary to the belief of the designer of HC-128, a recent work [105] has shown
that the distinguisher works for all the bits (except one) in the keystream
words. We present this extension in this Section.
There exist biases in the equality of 31 out of the 32 bits (except the second
least significant bit) of the word combinations
s
i
⊕s
i−1024
⊕(s
i−3
10)⊕(s
i−10
8)⊕(s
i−1023
23)
⊕(s
j−3
10)⊕(s
j−10
8)⊕(s
j−1023
23).
Thus, we have a distinguisher for each of those 31 bits separately.
The analysis generalizes the idea of Section 10.3.1 by applying Corol-
lary 10.2.2. Refer to the visualization of the array P as explained in Table 10.1
of Section 10.3.1 and focus on Equation (10.3):
and s
j
⊕s
j−1024
s
i−1024
⊕h
′
1
(z
i−1024
)
s
i
⊕h
1
(z
i
)
=
s
i−3
⊕h
1
(z
i−3
),s
i−10
⊕h
1
(z
i−10
),s
i−1023
⊕h
′
1
(z
i−1023
)
+ g
1
.
Again let us replace the two “+” operations (one inside and one outside) g
1
by “⊕.” Then as per the discussion following Corollary 10.2.2, one can write,
for 10 ≤ i mod 1024 < 511,
[s
i
]
b
⊕[s
i−1024
]
b
⊕[s
i−3
]
10+b
⊕[s
i−10
]
8+b
⊕[s
i−1023
]
23+b
[h
1
(z
i
)]
b
⊕[h
′
1
(z
i−1024
)]
b
⊕[h
1
(z
i−3
)
10+b
]
⊕[h
1
(z
i−10
)]
8+b
⊕[h
′
1
(z
i−1023
)]
23+b
=
