Cryptography Reference
In-Depth Information
where l ≤ M ≤ 2l, such that the correct values of at least n
corr
out of l key
bytes are uniquely determined and at least n
in
out of n
corr
are derived from
the filters in
[0,l−1]∪[N −1−l,N −2].
LetP be the set of the partially recovered key bytes, each of which is associated
with a single value, namely, the correct value of that key byte.
Next, a frequency table is built for the l−n
corr
many unknown key bytes
by guessing one j
y+1
from the 8 values
S
N
[y],S
−1
N
[y],S
N
[S
N
[[y]],S
−1
N
[S
−1
N
[y]],S
N
[S
N
[S
N
[y]]],
S
−1
N
[S
−1
N
[S
−1
N
[y]]],S
N
[S
N
[S
N
[S
N
[y]]]] and S
−1
N
[S
−1
N
[S
−1
N
[S
−1
N
[y]]]].
From two successive j values j
y
and j
y+1
, 8 × 8 = 64 candidates for the
key byte K[y] are found. These candidates are weighted according to their
probabilities. The 256 possible values of each unknown key byte K[y] are
grouped into 4 sets of size 64 each. Let G
y
be the set of values obtained from
the above frequency table and let H
1,y
,H
2,y
,H
3,y
be the other sets, called bad
sets. For 0 ≤ y ≤ l−1, let g
y
= P(K[y] ∈ G
y
). Since empirical results show
that g
y
is almost the same for each y, one can use the average g =
l
l−1
y=0
g
y
in place of each g
y
.
After this, a bidirectional search is performed from both ends several times,
each time with exactly one of the sets {G
y
,H
1,y
,H
2,y
,H
3,y
} for each unknown
key byte. The bad sets are used for at most b of the unknown key bytes. The
search algorithm, called BidirKeySearch, takes as inputs the final permutation
S
N
, the final value j
N
, the partially recovered key set P, a set S of l−n
corr
many candidate sets each of size 64 and a d-favorable (t,t
′
)-bisequence B.
For the left end, first one guesses the key bytes K[0],...,K[i
1
] except
those in P. Starting with S
0
and j
0
, the KSA is run until S
i
1
+1
and j
i
1
+1
are obtained. Since the correct value of j
i
1
+1
is known, the tuples leading to
the correct j
i
1
+1
form a set T
i
1
of candidate solutions for K[0...i
1
]. These
tuples are said to “pass the filter” i
1
. Similarly, starting with j
i
1
+1
and each
state S
i
1
+1
associated with each tuple in T
i
1
, the key bytes K[i
1
+1],...,K[i
2
]
excluding those in P are guessed. Thus, a set T
i
2
of candidate solutions is
obtained for K[0...i
2
] passing the filter i
2
, and so on until a stage is reached
where a set T
i
t
of candidate solutions for K[0...i
t
] passing the left critical
filter i
t
would exist.
In the same manner, one starts with S
N
and j
N
and runs the KSA back-
wards until one has a set T
i
t
of candidate solutions for K[i
t
′
+ 1...l − 1]
passing the right critical filter i
t
′
.
Among the set of remaining key bytes
L = {K[i
t
+ 1],...,K[i
t+1
]}\P
on the left, and the set of remaining key bytes
R = {K[i
t
′
+1
+ 1],...,K[i
t
′
]}\P
