Cryptography Reference
In-Depth Information
We can see that, depending on what we select for
m
,
t
, and the number of
tables, we can decide ourselves what we want to focus on: if we have plenty of
storage available, we can select large
m
and number of tables; if our computer
is very fast, we can work with large
t
; hence the name of the method.
Hellman suggested one million tables with 100 000 rows each computed in par-
allel and one million rounds per row (which could cover a maximum of 10
17
or 100 quadrillion possible values — the key space has 'only' 72 quadrillion
entries). All tables together would require a storage space of roughly one Tbyte
(terabyte, corresponds to one trillion bytes, or one million Mbytes) — no prob-
lem considering the size of current jukeboxes. We would need a 1-Gbit memory,
i.e., 125 Mbytes. All PCs will have this capacity before long. Moreover, we
would have to deploy 10 000 DES chips. That's a bit harder. In 1980, Hellman
estimated 4
µ
s as the time required per encryption for one DES chip. That
would have resulted in a computation time of well over a year.
Of course, current chips are much faster. The VM007 chip produced by VLSI
Technology in 1993 can handle 25 million encryptions per second (that's an
improvement by a factor of 100 compared with 1980 — when using a 32-MHz
clock frequency — and by a factor of 10 compared with the
Deep Crack
chips).
With a tenfold use of such DES chips (i.e., 100 000 units), the time - memory
tradeoff could be done in half a workday. The time required for one-time table
computation is twice that amount.
The encryption modes we will discuss in Section 5.1.1 allow us to push up the
cost of this attack:
•
The time remains the same when using the ECB mode and a known
plaintext. The table can be computed once and for all, i.e., this time is
negligible.
•
In CBC mode, though the plaintext is known, it has to be deemed to be
random. A new table has to be created for every attack so that the time
involved triples.
•
Things are similar with the CFB and OFB modes. However, we need to
know
two
consecutive pairs of ciphertext blocks and plaintext blocks.
The purpose of the time - memory tradeoff is, however, to compute the table
once (at high cost) for a specific plaintext block and then try to find the key in
routine operations relatively quickly. In this constellation, encryption in CBC
mode would be hindering.
