Cryptography Reference
In-Depth Information
8.2.2 Differential Fault Attack
This attack relies on collecting three sets of data with the same unknown
key. In each of the following cases, the KSA is performed without any fault.
1. The first set is the first 256 keystream bytes z
r
, r = 1,2,...,256 from
normal RC4.
2. For each t in [0,255], make a fault in S
N
[t] and run the PRGA for 30
steps. Thus, we have 256 output streams, each of length 30. Denote
these streams by X
t
, t = 0,1,...,255.
3. Run the PRGA for 30 steps. Then for each t in [0,255], inject a fault in
S
30
[t] and starting from that step collect longer keystreams Y
t
.
The first non-faulty keystream output byte z
1
depends on the indices i
1
(= 1),
j
1
(= S
N
[1]) and S
N
[i
1
] + S
N
[j
1
]. Thus, except for t = i
1
,j
1
,S
N
[i
1
] +
S
N
[j
1
], the first byte of all the other X
t
streams are all equal to z
1
. Once these
three streams are identified, the values of i
1
, j
1
and S
N
[i
1
]+S
N
[j
1
] are also
known, but which value corresponds to which variable cannot be determined.
Since i
1
is known, we need to differentiate between j
1
and S
N
[i
1
] + S
N
[j
1
].
We continue the same analysis for the following bytes z
2
,z
3
,....
The technique employed to guess the entries of the permutation is called
cascade guessing. For example, whenever two consecutive bytes in the stream
are the two consecutive j
G
values, one may subtract the previous j
G
from the
current one and derive S
G
[i
G
]. Whenever a contradiction is reached, wrong
guesses are eliminated. According to the birthday paradox, a contradiction is
expected after an average of less than 20 observed bytes.
If the considered keystream bytes are far from the faults in item 2 above,
the identification of the three indices become di
cult. One possible solution
is to have many sets with faults injected at different times, similar to Y
t
in
item (3). The complete attack requires injection of 2
10
faults and inspection
of 2
16
keystream bytes.
8.3 Fault Attack Based on Fork Model
This attack model has been considered in [108, Section 7], where the at-
tacker injects a fault either to j
G
or to one of the entries of S
G
that are
located closely after a fixed index i
G
. Repeating this many times, he collects
many instances of RC4 that are identical initially but they diverge at a certain
point. Let round r be the divergence point. As discussed below, the attacker
can iteratively recover all the entries of S
r
, one by one.
Suppose the attacker wants to recover S
r
[u] = v. He waits until the
round r
′
when the index i
G
reaches location u. This happens after at the
