Fault Attacks - RC4: Stream Cipher and Its Variants - page 210

Thus, when i st and x are unknown, the average case time complexity of Con-
structPerm is given by ⌈A⌉!N 3 , and following the same analysis as in Theo-
rem 8.4.18, the average case time complexity of InvertStuckPRGA is given by
O R 2 N + ⌈A⌉!N 3

. Plugging in N = 256 and R = 8, we get A = 0 and the
time complexity becomes

8 2 256 + 256 3 ≈ 2 25 .

8.4.4 Detecting the Stuck-At Fault
The analysis so far assumes that the keystream bytes from the point when
j G got stuck is available to the attacker. In practice, the attacker has access
to the keystream output bytes only. By analyzing the keystream, he should
be able to determine the interval during which j G remains stuck at a certain
value. After the fault detection, he can run the InvertStuckPRGA algorithm
on the keystream bytes obtained during that interval.
Theoretically determining the exact point when j G gets stuck appears to
be extremely tedious. However, we describe a simple test which can distin-
guish between a sequence of normal RC4 keystream bytes when j G is pseudo-
randomly updated and a sequence of RC4 keystream bytes when j G is stuck.
The following theorem shows that the number of conflict sets from the PartRe-
solvePerm algorithm when j G is pseudo-randomly updated is much more than
that when j G is stuck at a certain value.

Theorem 8.4.21. Assume that the index j G is pseudo-randomly updated in
each round of the PRGA. Then the expected number of conflict sets after
the execution of the PartResolvePerm algorithm, when the candidate pairs
are formed by considering all the keystream bytes in each run, is bounded by
(R−1)(N −1)− N−1
N

.

Proof: The candidate pairs are of the form (z (ρ+1)N+(y+1) ,z ρN+y ) and
the corresponding output indices are

t ρ,y = a N−ρ+y−1 + a N−ρ+y ,

where the range of y depends on ρ as follows. The range is 1 ≤ y ≤ N for
0 ≤ρ ≤ R−3 and it is 1 ≤y ≤ N −1 for ρ = R−2.
Let x ρ,y = 1 if

= suc 1 (z (ρ+1)N+(y+1) );
otherwise, let x ρ,y = 0. Then the total number of wrong entries in the array
Next after the execution of the PartResolvePerm algorithm is given by

z ρN+y

R−3 N N−1

X = x ρ,y + x R−2,y .

ρ=0 y=1 y=1