Cryptography Reference
In-Depth Information
Hence,
n
P(c
r,n
≥ m)
=
P(c
r,n
= τ)
τ=m
n
=
p
r
(y
1
,y
2
,...,y
τ
).
τ=m
{y
1
,y
2
,...,y
τ
}∈EI
τ
≥ m) gives the success probability with which one can
recover the secret key from the permutation after the r-th round of the KSA.
In Theorem 3.1.5, we observe that as the number r of rounds increase, the
probabilities P(S
r
[y] = f
y
) decrease. Finally, after the KSA, when r = N,
(see Corollary 3.1.6) the probabilities settle to the values as given in Table 3.2.
However, as the events (S
r
[y] = f
y
) are not independent for different y's,
deriving the formulae for the joint probability p
r
(y
1
,y
2
,...,y
τ
) seems to be
extremely tedious.
Consider the first n equations S
N
[y] = f
y
,0 ≤ y ≤ n−1, after the complete
KSA (i.e., r = N). In Table 4.1 (taken from [136]), we provide experimental
results on the probability of having at least m independent correct equations
for different values of n, m, and the key length l, satisfying m ≤l ≤n.
For each probability computation, the complete KSA (with N = 256
rounds) is repeated a million times, each time with a randomly chosen key. We
also compare the values of the exhaustive search complexity and the reduction
due to the above algorithm. Let
Note that P(c
r,n
n
m
n
l
m
2
m
2
+
2
8(l−m)
e = log
2
+|EI
m
|
.
The time complexity of exhaustive search is O(2
8l
) and that of the RecoverKey
algorithm, according to Theorem 4.2.6, is given by O(2
e
). Thus, the reduction
in search complexity due to the algorithm is by a factor O(2
8l−e
). By suitably
choosing the parameters (see Table 4.1), one can achieve the search complexity
O(2
8
2
), i.e., O(2
4l
), which is the square root of the exhaustive key search
complexity.
The results in Table 4.1 show that the probabilities (i.e., the empirical
values of P(c
N,n
≥ m)) in most of the cases are greater than 10%. However,
the algorithm does not use the probabilities to recover the key. For certain
keys the algorithm would be able to recover the keys and for certain other
keys the algorithm will not. The success probability can be interpreted as
the proportion of keys for which the algorithm would be able to successfully
recover the key. The keys, that can be recovered from the permutation after
the KSA using the RecoverKey algorithm, may be considered as weak keys in
RC4.
The last 8 entries corresponding to 16-byte key in Table 4.1 give a flavor
about the relationship between the complexity and the success probability.
