Cryptography Reference
In-Depth Information
most N − 1 steps. With probability at least (
N−
N
)
N−1
≈
e
, the index j
G
in
the intermediate rounds does not visit u, thereby keeping the entry v at u.
Given this, due to Corollary 5.2.2, with probability
2
N
the following holds.
= r
′
−S
r
′
−1
[i
r
′
]
= u−S
r
′
−1
[u]
= u−v.
z
r
′
When v does not remain at index u till round r
′
, the probability of which is
approximately 1−e, the equality z
r
′
= u−v holds due to random association
with probability approximately
1
N
. Hence,
P(v = u−z
r
′
) ≈
1
e
2
N
+ (1−e)
1
N
1
N
1 +
1
e
=
.
Since the attacker has many instances of RC4 diverging from a single point,
he may employ a simple voting mechanism to estimate v as the most frequent
value of u − z
r
′
. As reported in [108], the complete internal state can be
recovered with 80% success probability by injecting around 2
14
faults.
8.4 Fault Attack with Pseudo-Random Index Stuck
In this section, we describe a technique to recover the RC4 permutation
completely when the value of the pseudo-random index j
G
is stuck at some
value x from a point when i
G
= i
st
. This analysis first appeared in [104]
and requires 8N keystream output bytes su
ce to retrieve the permutation in
around O(N) time when x and i
st
are known and in O(N
3
) time when they
are unknown. Further, if one has a total of 2
16
keystream bytes after j
G
is
stuck, then the complete state can be recovered in just 2
8
time complexity,
irrespective of whether i
G
and j
G
are known or unknown.
A fault where the value of the index j
G
is stuck at some value x (0 ≤ x≤
N−1) during the PRGA, is called a stuck-at fault. The corresponding PRGA
is termed as StuckPRGA, presented in Algorithm 8.4.1.
Apart from the cryptanalytic significance, studying RC4 with j
G
stuck
at some value reveals nice combinatorial structures. First, an internal state
on any step becomes a restricted permutation over some fixed initial state.
Secondly, if one considers consecutive outputs at steps r,r + 257,r + 514 and
so on, then the resulting keystream sequence
• either consists of the same values (in very few cases), or
