Cryptography Reference
In-Depth Information
P
DES
K
DES
K'
double encryption
with keys K and K'
C
comparison
comparison
DES
K
P
C
DES
K'
comparison
encrypt
with all
possible
keys
decrypt
with all
possible
keys
comparison
correct
pair of keys
Figure 5.8:
Meet-in-the-middle attack against double encryption.
Though our calculation is a bit cleverer than that of the wise men of Gotham, it
is stuck on a naıve level. You know that 2
56
plaintext blocks correspond to an
order of magnitude of 576 million Gbytes. As mentioned in Section 4.4.1, this
could be stored, for example, on 850 million CDs. (However, we would need
a different set of CDs for every plaintext block,
P,...
) This data record has
to be looked up 2
56
times, i.e., roughly 72 quadrillion times. There are very
effective search strategies — arranged in a binary tree, we would find every
entry in 56 steps at most — but these methods work at a snail's pace, unless the
data is on fast hard disks or even in memory. Even if there were such as thing
as a superfast, superdense optical memory that required only one square with
an edge length of 1
µ
m for every bit and where every bit could be addressed
directly, then the bits of this memory required would still fill a square with an
edge length greater than 2 kilometers.
In short, the attack is totally unrealistic in practice. Nevertheless, double DES
encryption is an unloved child. Of course, theoreticians get upset when the double
cost theoretically yields only a tiny fraction of the effect intended. There might
be other considerations. In any event, triple encryption is commonly used today.
Triple-DES
The DES developer Tuchman proposed a method called
Triple-DES
,or
3DES
,
in 1979. Let us use two DES keys,
K
and
K
, again. We use the first key,
K
,
