Cryptography Reference
In-Depth Information
After the initialization phase, the cipher outputs one bit per clock cycle, which
will be denoted by
o
cycle
in the remainder of this chapter. For the sake of clarity, the
keystream obtained during an execution in which a fault has been injected will be
denoted by
o
cycle
.
The goal of an attacker is the reconstruction of the complete inner state of the
cipher, i.e. the contents of the three state registers: once these data are recovered, it
is possible to reverse-clock the cipher and roll back the inner state to the start of the
initialization. It is possible to determine when the cipher has been fully rolled back
thanks to the peculiar initialization padding, and thus extract the recovered IV and
key bits compromising the security of the scheme.
¯
14.3.2 Attack Technique
The attack which will be presented in this chapter relies on the assumption that the
attacker is able to inject a single bit-flip fault into the internal state of the Trivium
cipher during the a precise clock cycle
t
0
. After the fault injection, the attacker collects
some of bits of the faulty keystream (some hundreds) and then restarts the encrypting
device before injecting a new fault.
The cryptanalysis of Trivium starts with the observation that the relation between
the inner state and the output is purely linear. This implies that, every time an attacker
obtains a single bit of the keystream, he implicitly gains information on the inner
state of the cipher in the form of a linear equation of the state bits.
In particular, the output bit at the
i
th clock cycle can be written as
s
66
⊕
s
93
⊕
s
162
⊕
s
177
⊕
s
243
⊕
s
288
=
o
i
,
thus yielding 66 linear equations binding the first 66 output bits with the internal
state bits. The following 82 keystream bits have quadratic dependencies with the
inner state and the degree of the relation increases quickly afterwards, preventing an
attacker from directly solving the system by brute force.
In order to successfully attack the cipher, an attacker will need more linear equa-
tions involving the state bits; this is achievable by analyzing the differences between
the correct and a faulty keystream. The effect of a single bit-flip fault assumed to be
the fault model employed by the attacker is to substitute an inner state term in the
equations
s
i
with
1. This in turn implies that the difference between the
correct and faulty output bit is equal to the difference between two linear equations:
one representing the correct output, and the other the same equation with the correct
term substituted with the one taking into account the fault.
The only missing point for applying this substitute and subtract technique is that
the attacker must be able to determine which position of the state has been hit by the
bit flipping fault in order to do the proper substitution.
The key to spotting which bit has been altered is observing the different distances
between the two bits involved in the linear output combination for each register. In
¯
s
i
=
s
+
