Cryptography Reference
In-Depth Information
ν
a
denote the numbers of fortuitous and non-fortuitous states of length a re-
spectively, then the knowledge of non-fortuitous states reduces the length of
the keystream output segment required for the occurrence of any a-predictive
a-state by N N
a+1
(
φ
a
−
1
φ
a
+ν
a
).
The concept of recyclable states is introduced in [109, Section 4]. Suppose
A = (S
G
,i
G
,j
G
) is an a-state and let I be the minimal interval containing
the a permutation entries of A. Suppose that in every a-compliant state, the
permutation S
′G
after i
G
leaves I satisfies again the permutation constraints
of A. Then A is said to be recyclable. Based on the analysis of these states,
one can mount what is called the recycling attack (described in [109, Section
4]) which can predict a single byte from 2
50
samples of keystream bytes with
a success probability of 82%.
The above methods of partial state recovery do not have much cryptana-
lytic significance and hence we avoid detailed discussion on them. Rather, we
focus on the important milestones of complete state recovery in the subsequent
sections.
5.8.2 Knudsen et al.'s Attack and Its Improvements
Knudsen et al. [87] discovered for the first time that a branch and bound
strategy reduces the complexity for recovering the internal state much below
that of exhaustive search.
The output of RC4 at time (PRGA round) r is
z
r
= S
r
[S
r
[i
r
] + S
r
[j
r
]]
(5.4)
The attack of [87] first considers a simplified version of RC4 in which there
is no swap and then proceeds to incorporate the feature of swap.
The following result is immediate.
Theorem 5.8.1. If the swap operation of RC4 is omitted, the keystream
becomes cyclic with a period of 2
n+1
, where each index and each permutation
entry is of n bits.
Proof: Since there is no swap operation, the permutation is constant and
so we denote it by S
G
, without any subscript. From Equation (5.4),
z
r+2
n+1
= S
G
[S
G
[i
r+2
n+1
] + S
G
[j
r+2
n+1
]].
Now, i
r+2
n
= i
r
. Applying j
r
= j
r−1
+ S
G
[i
r
] repeatedly, we have
2
n
−1
j
r+2
n
= j
r
S
G
[u]
+
u=0
= j
r
+ 2
n−1
(mod 2
n
).
