Cryptography Reference
In-Depth Information
assumed by the authors is a random 32-bit wide fault on a random entry of either
P
or
Q
. Although it is possible to attack the cipher injecting the fault before it is clocked
for the first time, the authors point out that injecting the faults at step
i
268 lowers
the number of faults needed to break the scheme. The attack reconstructs the inner
state of the cipher at round
i
=
024 and then, by virtue of the fact that the round
function of HC-128 is bijective, the cipher is rolled back to its initial state.
In order to perform the attack, at first a fault collection phase is performed, record-
ing the faulty keystream for rounds
i
=
1
,
for each time a fault is injected.
After every fault injection the stream cipher is fully reset. The first observation on
the effects of the faults is that the position of the word struck by the fault determines
uniquely the way in which the difference spreads through the table, since the offsets
which select the values to be mixed together are fixed (they only depend on
j
, which
is regularly cycling through the entries as
i
grows). In the same way, it is possible to
track down the effect of the changes up to the produced keystream. The authors sug-
gest transforming the sequence of differences between correct and faulty keystreams
into a sequence of bits, where a 0 value means “the two words are the same” and a
1 means “there is a difference between faulty and fault free ciphertexts”. It is then
possible to uniquely map a sequence obtained in this way to a range of positions in
either the
P
or the
Q
table where the fault has happened.
After a full recovery of the position of the induced faults, the next step is to
understand the actual form of the fault induced by the attacker (i.e. which bits have
changed). This is manageable since, from the previous analysis, the attacker is able
to distinguish which of the three values of the output function has been affected by
a fault, and thus selects the one for which the nonlinear term obtained through the
lookup on the other state table is untouched. This in turn implies that the attacker is
in possession of a faulty and a fault-free word of the inner state, both masked with
the same XOR mask, and is thus able to derive the actual fault injected into the state.
By repeating this technique and reusing the fault values obtained in the analysis,
it is possible to disclose all the fault patterns injected for the whole cipher. For an
in-depth case by case analysis we refer you to the full paper, which provides accurate
tables of the differences.
After the fault patterns have been recovered for each faulty keystream, the attacker
is now in possession of a vast amount of differential information on the encryptions
(namely, a fault for each word is required for the attack to succeed). Due to the
additive nature of the output function, it is possible to recover the input values of the
output function for all the cycles between 512 and 1023 (which employ one term
from the
Q
table and one from
P
) and reuse the information to deduce the ones
for 1
∈[
268
,
1535
]
535 (which, conversely, are built from a single value from
P
and two lookups from
Q
). After this phase, the attacker has gathered information
on the values before the last XOR performed by the output function and knows the
keystream; the last step is thus to build a large system of very sparse linear equations
in the state bits (roughly 1
,
024
<
i
<
1
,
10
4
) and, by solving it, obtain all the values of the
.
8
×
inner state.
From experimental results, obtained by the authors through synthetic simulation,
the final equation system has an effective rank of 1,022, thus leaving two bits of the
