Cryptography Reference
In-Depth Information
(3) of Theorem 5.1.1, the subsequent 256 bytes produced by decimating the
keystream after every 255 bytes reveal the entries of the initial permutation
S
r
shifted cyclically. Since S
r
[i
r
+ 1] = 1, the location of the value 1 and
thereby the locations of all other values in S
r
are automatically determined.
Since the conditions for the Finney state are j
r
= i
r
+ 1 and S
r
[j
r
] = 1,
the probability of falling into a Finney state by a fault is 2
−8
× 2
−8
= −16,
assuming that the faults are independent. In other words, after around 2
16
fault injections, the internal state is expected to fall into a Finney state.
An obvious problem is how to detect whether a state is a Finney state. It
turns out that the number of steps, after which a collision of two bytes of the
keystream should occur, gives an indication of whether the state is a Finney
state or a normal RC4 state.
There are N = 256 possible bytes in the keystream. The probability that
no byte is repeated in m successive keystream output bytes of normal RC4
is given by
N(N−1)(N−1+m)
N
m
and the probability that there is at least one
repetition is p = 1−
N(N−1)(N−1+m)
N
m
. Setting p >
2
yields m ≥ 20. This is
nothing but the birthday paradox where there are 256 different birthdays and
m different people.
For Finney states, the case where the colliding output byte has value 1 can
be ignored as it has a very low probability. Assume that the fault is injected
in step x. When the output is not 1, a collision of a byte a steps after the
fault and another byte b steps after the fault can occur if
1. S
x+a
[i
x+a
] + S
x+a
[j
x+a
] = S
x+b
[i
x+b
] + S
x+b
[j
x+b
] + 1 and
2. i
x+a
≤ S
x+a
[i
x+a
] + S
x+a
[j
x+a
] ≤ i
x+b
.
N
and that of Event 2 is
b−
N
. Thus, the
probability that a collision occurs within the first m bytes after the fault
injection is approximately given by
1
The probability of Event 1 is
≈
m
3
1
N
b−a
N
p
′
=
32
17
.
0≤a<b<m
Conditioning p
′
>
2
gives m ≥ 58 and forcing p
′
= 1 yields m ≈ 73.
Algorithm DetectFinney gives a step-by-step description of how to deter-
mine whether the state is a Finney state or not.
Since the average number of bytes required to recognize a Finney state is
around 2
5
and this cost is incurred for each of the 2
16
fault injections, the
number of keystream bytes required to mount the attack is around 2
21
. Note
that the additional 255 × 256 ≈ 2
16
keystream bytes required to recover the
state after detection of the Finney cycle, when added to 2
21
, do not change the
order. The time complexity of the attack is the same as the data complexity.
