Cryptography Reference
In-Depth Information
of the Birthday paradox. On the other hand, when cycling in Finney's states, the
selection of the output bytes
o
s
s
i
+
s
j
is driven only by the value of
s
i
, since the
value of
s
j
is fixed to 1 because of the peculiarity of the state. This in turn implies
that the selection of the output byte will be driven by different indices except for the
case where a value of the array is swapped twice. The authors of [45] determined that
this results experimentally in a duplicate output byte occurring once approximately
every 80 bytes, which enables an attacker to successfully discard a faulty output if
duplications in the output occur more frequently than that (the authors suggest that
every keystream with a duplicated byte occurring more frequently than once every
30 bytes can be safely discarded).
After obtaining the exploitable faulty keystream an attacker needs to reconstruct
the inner state of the cipher. The simplest way to do this is to select a random byte and
read the state by skipping 255 bytes at a time in the obtained keystream, exploiting
the fact that, while the location taken from the state array is the same every 256
outputs, the content of the state is rotated a single byte to the left every 256 cycles.
A quicker way to obtain the state is to exploit the information leaked by the order of
the output bytes, which enables the attacker to infer a couple of consecutive values
in the inner state, thus reducing the possible state space, together with the fact that,
when the output byte is equal to 1,
s
i
+
=
=
i
.
The authors of the attack report that the average number of keystream bytes to be
obtained before a Finney state is correctly entered and the inner state is recovered is
around 2
21
on average, considering also the faulty keystream which gets discarded
by the aforementioned duplicated output frequency test.
In addition to the presented impossible cryptanalysis on RC4, the authors of the
same paper also propose a common differential cryptanalysis on the same cipher.
The key point of the second method is to inject faults precisely one per inner state
byte and then deduce from the position and value of the faulty outputs which cell
has been damaged. Whilst this attack requires significantly less faults than the other
one, the required fault model is rather stringent, since it implies both perfect timing
and quite selective locality in injecting the faults.
s
j
14.3 Differential Fault Analysis of Trivium
14.3.1 Cipher Description
Trivium is a stream cipher selected by the eSTREAM project as one of the most
promising ones for hardware implementation. Proposed by De Cannière and Preneel
in [116], this cipher was to be as simple as possible without sacrificing security.
As a consequence, the architecture of the keystream generation algorithm does not
involve many components: it only employs three registers and a couple of two-input
one-output logical XOR and AND gates.
