Cryptography Reference
In-Depth Information
fact, the two tapped bits are respectively 27, 15 and 45 positions apart for the first,
second and third registers. The simplest case in determining the fault position occurs
when the faulty bit
s
e
is placed between the beginning of a register and the first
¯
tap (i.e.
e
). In this case, the second nonzero bit
in the keystream difference appears after 27, 15 or 45 clock cycles from the first,
revealing that the faulty bit is being employed by the second output tap of a specific
register. Combining the second appearance with the position of the first nonzero bit
in the keystream difference it is possible to correctly reconstruct the register and the
specific bit in which the flip occurred.
In case a fault occurs outside the aforementioned interval, it is still possible to
infer the position of the fault, albeit the second degree effects of the AND gates on the
feedback must also be taken into account, since they may generate other differences
in the output keystream.
Summing up, the first basic attack to Trivium may be possible by obtaining enough
linear equations in the state bits, adding to the 66 which are straightforward from
the cipher structure those which bind bit differences between the correct and faulty
ciphertexts. Once a whole system of 288 equations in the state bits is obtained, it
is possible to solve it through Gaussian elimination and obtain all the values of the
inner state at a specific time. By clocking back the Trivium cipher, if desired, the
attacker may also recover the original key and the IV employed.
A way to further improve the efficiency of the attack is to precompute a pool
of linear equations for all the possible positions where the fault may hit and store
them in a lookup table. Since the equations depend only on the cipher structure, this
precomputation effort need be done only once. The practical attack to the cipher thus
is reduced to the fault injection and keystream collection parts alone.
The authors of [45] provide an estimate of the average number of faults needed to
recover the whole cipher state, which is around 380. This figure can be significantly
reduced if the attacker is willing to brute-force a small number of the state bits: for
instance, by guessing only eight bits, the number of faults can be reduced to 270,
and by guessing 28 bits the number of faults can be cut in half with respect to the
whole state retrieval.
In the aforementioned article the authors also propose a way to improve even
more upon the number of linear equations obtained from a single fault. The key
idea behind the improvement is the observation of the fact that most of the quadratic
equations of Trivium involve only terms of the form
s
i
s
i
+
1
. These equations may
be efficiently represented by adding a new variable for each quadratic term and thus
needing only twice the amount of memory (288 variables for the state, 287 variables
for all the possible pairs of adjacent bits).
Once all the output equations involving only such quadratic and linear terms have
been precomputed, the attack starts by injecting faults in the same way as in the
basic case. The key difference is that, as soon as it is possible to obtain the value of a
variable from the system, the solver replaces all the occurrences of it with the actual
constant value, thus possibly reducing the degree of some of the quadratic equations
back to 1.
∈[
1
;
66
]∪[
94
;
162
]∪[
178
;
243
]
