Cryptography Reference
In-Depth Information
f(S
1
)
f
2
(S
1
)
= f(f(S
1
))
... f
t
(S
1
)
S
1
...
S
m
f(S
m
)
f
2
(S
m
)
= f(f(S
m
))
... f
t
(S
m
)
This means that each element comes into being by removing eight bits from
an encryption of the fixed plaintext,
P
, and serves as key for the element to
the right of it. But we discard all intermediate results and store only the first
and last columns.
Next, we look for our ciphertext,
R(C)
, reduced to 56 bits, in the right-hand
column. If we find it there in row
k
, then
R(C)
came into being by the encryp-
tion of
P
(and subsequent reduction,
R
), together with the key located in row
k
of the table, column
t
1. That's how we built the table in the first place. We
can compute this key, since we had also stored
S
k
; we 'only' have to transform
it (
t
−
1) times by using function
f
.
−
If we don't find
R(C)
in the last column, we might find it in the last column
but one. If
R(C)
is there, then
f(R(C))
should occur in the last column of the
table. So, let's look for
f(R(C))
in the last column. Now we can understand
why we built the table in exactly this way. Our approach is then relatively easy
in theory:
•
Compute the table and store only the first and last columns.
•
Search for
R(C)
in the last column.
•
If not found, search for
f(R(C))
in the last column.
•
If not found there either, search for
f(f(R(C))
in the last column.
•
...
•
If found, compute the table element in the same row, but one column
earlier.
The method doesn't necessarily lead to the goal, but it's very likely that it does.
It ranges roughly in the middle between the usual brute-force attack (which tests
all possible keys) and the dictionary attack (which tests only probable keys).
In practice, we would create many tables in parallel (since the left columns
are random) and select the
m
and
t
values such that the probability of being
successful is sufficiently large, despite potential 'false alarms': after all, we test
only 56 out of 64 bits for a match with the ciphertext block. The method can
be made faster; see [Denn83, 2.6.3].
