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

Chapter 8
Fault Attacks
Several types of faults may occur in a cryptographic device, leading to the
vulnerability of the cipher being used. In the data fault model, the attacker
flips some bits in RAM or internal registers. In the flow fault model, the
attacker makes small changes in the flow of execution, such as skipping an
instruction, changing a memory address etc.
The fault models usually rely on optimistic assumptions and consider a
weaker version of the cipher than the original one. It has been commented
in [71, Section 1.3] that the attacker should have partial control in terms of
number, location, and timing of fault injections. It is also assumed that the
attacker can reset the system with the same key as many times as he wants.
In other words, he can cancel the effects of the previously made faults, go
back to the initial configuration and re-execute the cipher with the same key.
Though the assumptions are optimistic, they are not unrealistic. In addition,
the fault models serve as platforms to evaluate the strength and weaknesses
of the cipher.
So far, only a few fault attacks on RC4 are known. In this chapter, we
give an overview of each of them.
8.1 Hoch and Shamir's Attack
This is the first reported fault attack [71, Section 3.3] on RC4. It is assumed
that the attacker can introduce a fault on a single byte of S after the KSA is
over but before the PRGA begins. Further, the attacker can reset the system
and inject a new fault as many times as desired. Under such a model, the
attacker can analyze the resulting keystreams to reconstruct the internal state.
Note that the attacker can identify the value that is faulted, but not the
location of that value. In other words, if S N [y] = v and the fault changes v
to v ′ , then it is possible to recognize both v and v ′ , but not y. The strategy
is to observe the frequency of each value in the keystream. v would never
appear and v ′ would appear with twice the expected frequency. A keystream
of length 10,000 bytes can reliably find out v and v ′ .
The next step is to identify faults in S N [1]. In the first step of the PRGA,
i 1 = 1 and j 1 = S N [1]. After the swap, S 1 [1] = S N [S N [1]] and S 1 [S N [1]] =