Cryptography Reference
In-Depth Information
S
N
[1] and the first keystream output byte is given by
S
1
[S
1
[1] + S
1
[S
N
[1]]
z
1
=
S
1
[S
N
[S
N
[1]] + S
N
[1]]
=
w.h.p.
=
S
N
[S
N
[S
N
[1]] + S
N
[1]],
(8.1)
where w.h.p. stands for “with high probability.” Thus, if z
1
is changed as a
result of the fault, then one of the following three cases must be true.
1. S
N
[1] was at fault.
2. S
N
[S
N
[1]] was at fault.
3. S
N
[S
N
[1] + S
N
[S
N
[1]]] was at fault.
Case 3 is the easiest to detect, since we know the original value at the index
S
N
[1] + S
N
[S
N
[1]]. For distinguishing between Cases 1 and 2, the attacker
needs to inspect the second byte z
2
. In the second round of PRGA, i
2
= 2
and j
2
= j
1
+ S
1
[2] = S
N
[1] + S
1
[2]. Thus, after the swap, the second
keystream byte is given by
= S
2
[S
2
[2] + S
2
[S
N
[1] + S
1
[2]]]
= S
2
[S
1
[S
N
[1] + S
1
[2]] + S
1
[2]].
z
2
(8.2)
Thus, if Case 1 occurs, then both z
1
and z
2
would be at fault. If Case 2 occurs,
then only z
1
is at fault and with high probability z
2
would not be faulted.
For faults which affected S
N
[1] and thereby changed its value from v to
v
′
, the attacker can utilize Equation (8.1) to write
S
N
[v
′
+ S
N
[v
′
]] = z
1
(8.3)
where z
1
is the first byte of the faulty keystream. For each fault in S
N
[1], an
equation similar to Equation (8.3) can be found. After collecting many such
equations, the attacker starts deducing values at other indices of S
N
, using
the knowledge of S
N
[1].
Example 8.1.1. Suppose the value at S
N
[1] was v = 26. Assume that the
first fault gives v
′
= 1 and z
1
= 41. From Equation (8.3), we get S
N
[1 + 26] =
S
N
[27] to be 41. Suppose another fault gives v
′
= 27 and z
1
= 14. Then
S
N
[27 + 41] = S
N
[68] = 14.
The attackers continue deriving the entries of S
N
as above in a chain-like
fashion until the equations no longer reveal any new entry of S
N
. If in the end,
the value of S
N
[S
N
[1]] is not yet recovered, its value can be guessed. From the
knowledge of S
N
[S
N
[1]], the attacker may continue a similar analysis with the
second output byte. Assuming S
N
[2] = t is known and noting the fact that
S
1
and S
2
of Equation (8.2) can be replaced by S
N
with high probability,
one may write
S
N
[S
N
[S
N
[1] + t] + t]
w.h.p
= z
2
.