Cryptography Reference
In-Depth Information
determine and store all 72 quadrillion ciphertext blocks that can be formed by
encrypting a frequent plaintext block. Such a plaintext block could contain eight
zero bytes, for example (they certainly occur often enough, e.g., in WordPer-
fect; see Section 3.5). In this case, the plaintext block assumes the role of the
probable word we know from earlier sections. This would be less simple tech-
nically: since the ciphertext blocks are 8 bytes long, we need about 850 million
CDs to store them. When using 100-GB magnetic tapes, there would 'only' be
about five million tapes. The media required can be further reduced when using
new (e.g., holographic) methods. But things can be done far more thriftily.
Time-Memory Tradeoff
This is a brute-force method developed by Hellman in 1980 [Hell.troff; Denn83,
2.6.3] with a rather complicated name: it means that we aim at achieving
a tradeoff between time and memory. This method is not limited to DES;
it can be applied to any encryption method. This means that it is a general
cryptanalytic method.
The
time-memory tradeoff
is a refinement of the plaintext attack mentioned
earlier. The trick is to store just a small part of the possible ciphertexts of
a frequent plaintext rather than all of them. The rest is computed during the
analysis. In detail, this looks as follows:
Assume we have a frequent plaintext block,
P
, the corresponding ciphertext,
C
, and some (very easy to compute) function,
R
, which maps the 64-bit blocks
to 56-bit blocks. For example,
R
can be a rule which says that the most signif-
icant bits should be truncated from the 8 bytes that form the 64-bit block. The
following function is then defined for each 56-bit key,
S
:
f(S) = R(E
S
(P))
where
E
S
(P )
is the encryption of
P
with key
S
(
E
=
encryption). We look for
all keys,
S
, in such a way that
f(S) = R(C)
Such an
S
can already be the key searched, but not necessarily, since eight bits
are not tested. To search for this
S
, we randomly select
m
keys,
S
1
,...,S
m
,
and compute the following table with
t
columns and
m
rows for a given
width,
t
:
