Cryptography Reference
In-Depth Information
4.7 Bidirectional Key Search
The main idea behind this approach [10] is to guess K[0],K[1],... using
the left end of the permutation S and guess K[l−1],K[l−2],... using the right
end of S simultaneously. After a number key bytes are guessed, the KSA may
be run (in the forward or in the backward direction, depending on the position
of the guessed key bytes) until a known j
y+1
is encountered. If this matches
with the computed j
y+1
, then the guessing continues, otherwise the partial
key is discarded. The indices y for which j
y+1
's are known act as “filters” for
separating out the wrong candidate keys from the correct ones. This algorithm
can recover secret keys of length 16 bytes with a success probability of 0.1409,
which is almost two times the earlier best known value of 0.0745 reported
in [5].
4.7.1 Sequences of Filter Indices
Here we present the structure and algebraic properties of the sequence of
indices that act as filters for validating the secret key guesses. For simplicity,
l is assumed to be a factor of N.
The secret index j is pseudo-random and may be considered to follow
uniform distribution over the domain [0,N − 1]. Hence, if the values of m
consecutive j's are guessed randomly, the success probability is N
−m
. For N =
256 and m = 8, this probability turns out to be (256)
−8
= 2
−64
. Whereas,
using theoretical framework of this section, one can guess a sequence of j
values with better probability (see Table 4.9).
Definition 4.7.1. (Event A
y
) For 0 ≤ y ≤ N − 1, event A
y
occurs if and
only if the following three conditions hold.
1. S
y
[y] = y and S
y
[j
y+1
] = j
y+1
.
2. j
y+1
≥y.
3. S
N
[y] = S
y+1
[y].
Proposition 4.7.2. For 0 ≤ y ≤ N −1,
y
N−1−y
N −y
N
N −2
N
N −1
N
p
y
= P(A
y
) =
.
Proof: Let us analyze the three cases mentioned in the definition of A
y
.
1. S
y
[y] = y and S
y
[j
y+1
] = j
y+1
occur if j
t
∈{y,j
y+1
}, for 1 ≤ t ≤ y, the
probability of which is (
N−2
N
)
y
.
2. P(j
y+1
≥y) =
N−y
N
.
