Cryptography Reference
In-Depth Information
on the right, some bytes are common. First, the smaller of these two sets is
guessed and then only those key bytes from the larger set are guessed that
are needed to complete the whole key. One can reduce the candidate keys by
filtering the left half of the key using the right filters and the right half of the
key using the left filters.
In the BidirKeySearch algorithm description, i
0
and i
′
0
denote the two
default filters −1 (a dummy filter) and N −1 respectively.
Let m
1
be the complexity and α be the probability of obtaining a d-
favorable (t,t
′
) bisequence along with the partially recovered key set P, sat-
isfying the input requirements of BidirKeySearch. We require a search com-
plexity of
2(M −l)
n
corr
m
2
=
−n
in
for finding the n
corr
−n
in
many correct key bytes from the filters in
[l,l + M −1]∪[N −1−l,N −2−M].
We need to run the BidirKeySearch algorithm a total of
b
n−n
corr
r
3
r
m
3
=
r=0
times, leading to a success probability
n−n
corr
n−n
corr
r
g
r
(1 −g)
n−n
corr
−r
.
β =
r=n−n
corr
−b
If each run of the BidirKeySearch algorithm consumes τ time, the overall
complexity for the full key recovery is given by m
1
m
2
m
3
τ2
8
and the success
probability is given by αβ. The term 2
8
appears due to guessing the correct
value of j
N
.
For l = 16, d = 4, M = 20, n
corr
= 6, n
in
= 4, experiments with
10 million randomly generated secret keys reveal that α ≈ 0.1537 and g ≈
0.8928. Also, m
1
≈ 2
31
(see Table 4.10) and m
2
≈ 2
5
. With b = 2, β and
m
3
turn out to be 0.9169 and 2
9
(approx.) respectively. Thus, the success
probability is αβ ≈ 0.1409 and the complexity is approximately 2
31+5+9+8
τ =
2
53
τ. Though the the exact estimation of τ is not feasible in theory, τ is
expected to be small, since for wrong filter sequences the search is likely
to terminate in a negligible amount of time. Before [10], the best known
success probability for recovering a 16-byte secret key has been reported in [5]
as 0.0745 and the corresponding time required by Algorithm 4.4.1 is 1572
seconds, but it is not clear how the complexity of this algorithm grows with
increase in probability. Algorithm 4.7.1 [10] achieves better probability, but
with very high time complexity.
