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

Here z 2 is the second byte of the faulty stream. Experimental results confirm
that at this point on average 240 entries of S are recovered and the rest can
be found from the original keystream. Wrong guesses of S N [S N [1]] can be
eliminated through inconsistency of the collected equations or by comparing
the original keystream with the stream generated from the recovered S N .
We summarize the above strategy of Hoch and Shamir in the form of
Algorithm HS-FaultAttack.

Input: The non-faulty keystream.
Output: The permutation S N after the KSA.
for 2 16 iterations do

1

Apply a fault to a single byte of the S N table; 2

Generate a faulty keystream of length 1024; 3

Identify the fault;

4

end
For faults affecting S N [1], form equations of the form (8.3); 5

repeat 6

Use the equations to infer the entries of S N from the known 7

entries;
Guess an unknown entry whenever necessary; 8

until all entries of S N are known ;
Check the recovered state for consistency with the non-faulty

9

keystream;
If inconsistent, go to Step 8 to change the guesses and continue;

10

Algorithm 8.1.1: HS-FaultAttack

The algorithm requires 2 16 fault injections. Each of the data complexity
and the time complexity is of the order of 2 26 .

8.2 Impossible and Differential Fault Attacks
In [16], two fault attack models were proposed. One of them is called the
impossible fault attack [16, Section 3] that exploits the Finney cycle. Another
one is called the differential fault attack [16, Section 4]. We describe both of
them in this section.

8.2.1 Impossible Fault Attack
In the impossible fault attack model, the attacker repeatedly injects faults
into either register i G or register j G , until a Finney state is identified. If at
PRGA step r, S r

is identified to be in a Finney state, then according to Item