Cryptography Reference
In-Depth Information
Subtracting, we get the result. Note that the term 2
r
stands for the number
of ways in which a set of r indices may be a filter or a non-filter.
As an illustration, we present C
d,F
for different values of d and F with
l = 16 in Table 4.10.
F
32
20
16
12
8
2
27.81
2
27.31
2
24.72
2
18.11
2
3.58
d = 2
d = 3
2
30.56
2
30.38
2
29.02
2
24.86
2
15.95
2
31.47
2
31.35
2
30.38
2
27.17
2
20.14
d = 4
TABLE 4.10: C
d,F
for different F and d values with l = 16.
Though we have assumed that l divides N in the above analysis, the same
idea works when l is not a factor of N. One only needs to map the indices
from the right end of S to the appropriate key bytes.
4.7.2 Application of Filter Sequences in Bidirectional Key
Search
The theoretical properties of filter sequences discussed in the previous
subsection can be used to devise a novel key retrieval algorithm.
Suppose that after the RC4 KSA is over, the final permutation S
N
and
the final value j
N
of the index j are known. The update rule for the KSA is
j
y+1
= j
y
+ S
y
[y] + K[y],
0 ≤ y ≤N −1.
Since S
0
is the identity permutation and j
0
= 0, we have j
1
= K[0]. Thus, if
index 0 is a filter, then K[0] is known. Again, if index N − 2 is a filter, then
j
N−1
is known and hence K[l−1] = K[N −1] can be determined as
j
N
−j
N−1
−S
N−1
[N −1] = j
N
−j
N−1
−S
N
[j
N
].
Moreover, if two consecutive indices y−1 and y happen to be filters, 1 ≤y ≤
N−2, then j
y
and j
y+1
are known and S
y
[y] = y from the definition of filters.
Thus, the correct value of the key byte K[y mod l] can be extracted as
K[y mod l] = j
y+1
−j
y
−y.
For complete key recovery, apart from the knowledge of the final permu-
tation S
N
and the final value j
N
of the pseudo-random index j, we also need
to assume that a d-favorable (t,t
′
)-bisequence exists. Given such a sequence,
our algorithm does not require one to guess more than d many key bytes at a
time. For faster performance, one should keep d small (typically, 4).
The basic strategy for full key recovery is as follows. First, a partial key
recovery is performed using the filters in the interval
[0,M −1]∪[N −1−M,N −2],
