Cryptography Reference
In-Depth Information
with some additional new results to devise a more e
cient algorithm for key
recovery.
The key retrieval algorithm in [5] considers 6 types of events for guessing
one j value:
1. j
y+1
= S
N
[y].
2. j
y+1
= S
−1
[y].
N
3. j
y+1
= S
N
[S
N
[[y]].
4. j
y+1
= S
−1
N
[S
−1
N
[y]].
5. j
y+1
= S
N
[S
N
[S
N
[y]]].
6. j
y+1
= S
−1
N
[S
−1
N
[S
−1
N
[y]]].
From two successive j values j
y
and j
y+1
, 6×6 = 36 candidates for the key
byte K[y] are obtained. They are weighted according to their probabilities.
In addition, the Equations (4.10) of Section 4.3 [15] are also used. The sum
s of the key bytes is guessed first. Then, for all m-byte combinations of l key
bytes, the selected m key bytes under consideration are assigned values with
the highest weight.
The remaining l −m key bytes are solved as follows. For each group of
four bytes, some of them are already guessed (being part of the selected m-
combination). New candidates for the remaining (being part of the other l−m
key bytes) ones are found using the sum information (i.e., C
y
values) in these
4-byte sequence. The values for these are then fixed one by one, by trying all
possible candidates through a selected depth h.
The correctness of a key can be verified by the same technique as discussed
for Algorithm 4.2.1, i.e., by running the KSA and comparing the resulting
permutation with the permutation at hand.
In Table 4.3, we present some experimental data from [5], that corresponds
to the best success probabilities obtained by running Algorithm 4.4.1. The
implementation was performed on a 2.67GHz Intel CPU with 2GB RAM.
The success probabilities are derived from 10000 randomly generated key-
state table pairs.
4.5 Byte by Byte Recovery
This technique, reported in [134, Sections 2.3, 3.4], exploits all entries
of both the permutations S
N
and S
−
N
to narrow down the range of possible
values of j in each round of the KSA to only two values in Z
N
with a very good
and constant success probability (> 0.37). The estimates of the two successive
