Cryptography Reference
In-Depth Information
is possible that particular conditions of the two indices lead to extremely short and
regular permutation cycles of the inner state. In particular, Finney [140] observed
in 1994 that, in the case where the two conditions
j
=
i
+
1 and
S
[
j
]=
1 hold,
the RC4 cipher enters a short cycle of size 256
255. During this cycle, every 256
steps the cipher shifts its internal state one byte to the left and outputs a fixed byte
of the state. This in turn implies that the whole ordered content of the state is output
as a keystream during the short cycle in which the cipher is operating. A further
observation is the fact that, if the cipher is set in one of the states belonging to a short
cycle, it will never exit it, thus enabling an attacker to recognize the peculiar condition
through observing the periodicity of the output. During regular working conditions,
RC4 will never be in one of these states, since the initial key setup procedure sets
both
i
and
j
to zero, thus placing the cipher outside the short cycles.
·
14.2.2 Impossible States and Faults
Whilst RC4 cannot enter the short cycles on its own, it is possible to force it into
one of the states belonging to them through a proper fault injection. In 2005, Biham,
Granboulan and Nguyen [45] proposed a fault attack against RC4 which exploits
this possibility. The fault assumption made is that the attacker is able to modify the
value of either
i
or
j
at random during the execution of the RC4 algorithm. No
particular assumptions are made on which fault pattern is injected into the values
except that only one of them is modified. The attack technique is thus split into
two parts: understanding how probable it is that the cipher enters a short cycle and
recognizing the short cycling output with the smallest number of faulty bytes in
order to reconstruct the inner state with the smallest possible amount of keystream
information.
The probability that a random fault in either
i
or
j
will force the cipher into an
otherwise impossible state is 2
−
16
. This is because of the fact that the new value set
will match the first condition (
j
1) with probability 2
−
8
, given two indices
=
i
+
over eight bits and the probability that
S
1 for a randomly selected value of
j
is exactly 2
−
8
because the state holds 256 different values. This observation implies
that the attacker is able to obtain an exploitable fault by injecting on average 2
16
faults during the cipher operation, taking care to restart the enciphering device after
each unsuccessful trial.
In order to detect if the cipher has entered one of Finney's states, the most naïve
approach implies recording twice the bytes of a short cycle and acknowledging the
effective periodicity of the output, thus requiring the attacker to obtain 2
[
j
]=
=
2
17
bytes of the keystream. In order to reduce the quantity of keystream to be gathered
each time before a reliable check can be done, it is useful to observe the frequency
of the repetitions of the output byte values.
In regular working conditions, the cipher selects the output bytes pseudorandomly,
thus resulting in a repetition in the output roughly every 256
2
·
255
·
256
=
16 bytes because
