[1108] in cryptography@c2.net mail archive
Re: cracking n-DES?
daemon@ATHENA.MIT.EDU (David Wagner)
Fri Jun 27 22:44:52 1997
To: cryptography@c2.net
From: daw@cs.berkeley.edu (David Wagner)
Date: 27 Jun 1997 19:20:02 -0700
There are a number of ways you can implement multiple DES incorrectly.
I wouldn't be surprised if the NSA cracks far more ciphertexts because
of poorly implemented crypto rather than by knowledge of obscure attacks
on well-known ciphers.
Here's one potential failure mode. Imagine Poulsen encrypted a file with
DES with key "KPfofip0ST". Then Poulsen DES-encrypted the ciphertext with
a second key. Finally the program was run a third time. If the program
emits a known header at the beginning of the ciphertext (or even a checksum
over the whole file), breaking this requires at most 3 * 2^{56} work, not
2^{56*3} work. (This is one of the worst dangers of "inner chaining".)
I've heard that the NSA likes to require you to put a header of known text
in your file format if you ask for export permission for your file encryption
program. Perhaps the failure mode above might partially explain why?
Also, lots of software maps ASCII passwords to DES keys in a horrendously
stupid way. (Using only the first 8 characters is one common pitfall, as
you mentioned. Even worse, some commercial software has been known to
lose another 8 bits of entropy because the low bit of each ASCII byte went
into the "parity" bit of the DES key and was promptly ignored.)
And then of course there are all the potential problems with deleting the
plaintext file insecurely. Not to mention the danger of the swap partition
containing sensitive memory contents from the last time you ran the
encryption software.
Finally, one last failure mode. You said Poulsen used n-DES, where n
varied for each file at random. What if he used the same key for the
first step of encryption for each file? Then you could imagine some
scenario like this: find a file for which n=1, recover the key with 2^{56}
work; strip off one step of encryption for all files with n>1, and then
find a file for which n=2 and recover the step 2 key with 2^{56} work;
repeat, to find all the keys in O(2^{56}) work.
There's another theoretical possibility, too. I mentioned above the danger
of software prepending some known header to the ciphertext. It gets even
worse if the software prepends a fixed known header to the plaintext and
IVs are not used especially carefully. If one can get the ECB encryption
of a block of known, fixed data, then there is a very strong attack. The
NSA could use Hellman's time-space tradeoff: do a one-time 2^{56}
precomputation, build a "abridged dictionary" with O(2^{38}) memory,
and thereafter recovering the key given a ECB encryption of the known header
takes only O(2^{38}) computation. It might be in the NSA's interests to
pre-compute one such dictionary for every piece of software with a fixed
known header in the plaintext. With this sort of flaw in the software, and
if Poulsen ran the software three times manually as before, the total effort
required might be as low as 3 * 2^{38}. (However, I consider this failure
mode less likely -- more things have to go wrong.)
You mentioned the time-space tradeoff attack on 2-DES. Most folks are
aware that there's a meet-in-the-middle attack on 2-DES which works with
2^{56} trial encryptions and O(2^{56}) memory. What most folks don't know
is that the memory requirements can be greatly reduced sophisticated
algorithmic enhancements, with not too much cost in the amount of
computation required. This is work by van Oorschot and Wiener. They
estimate that a $10 million machine can break 2-DES in 4 years; roughly
speaking, that means that 2-DES offers only about 17 extra bits of security
over plain DES.
I don't know whether I really consider any of these possibilities as very
likely. It'd certainly help to know what software Poulsen used.
But in any case, there seems to be no shortage of potential failure modes
and conceivable implementation failures. I guess there are an awfully lot
of subtle ways to shoot yourself in the foot in this business.
