[1106] in cryptography@c2.net mail archive
cracking n-DES?
daemon@ATHENA.MIT.EDU (Steve Bellovin)
Fri Jun 27 21:25:04 1997
From: Steve Bellovin <smb@research.att.com>
To: cryptography@c2.net
Date: Fri, 27 Jun 1997 19:30:27 -0400
A recent book ("The Watchman: The Twisted Life and Crimes of Serial
Hacker Kevin Poulsen", by Jonathan Littman, 1997, Little, Brown)
claims that some of the evidence against Poulsen was a group of
files that were multiply-encrypted with DES. The encryption was
cracked, allegedly by NSA using "a Department of Energy Cray
supercomputer" and a brute-force algorithm. Supposedly, this took
"several months" and cost "hundreds of thousands of dollars".
We can discount the obvious technical mistakes (DES is described
as the "Defense Encryption Standard", a "fifty-six-key technique"
that is "thought to be virtually uncrackable"). And we can readily
assume that NSA didn't use a Cray for such purposes. But several
questions still remain.
First, of course, how strong is multiple DES? The fact of the
cryptanalysis is apparently in the court records, or so I was told
several years ago. But I had never heard any mention of multiple
encryption being used by Poulsen.
There's no mention of how the FBI even knew it was DES that was
used, though the absence of any stronger encryption routine on his
computers may have led to that guess.
Littman says that Poulsen's key was "KPfofip0ST". There's no
description of how 10 bytes of ASCII were mapped into a 56-bit key.
If only the first 8 bytes were used, and the government assumed he
had used a 62-character alphabet, the size of the key space was
~~2^48. Under the simple assumption that he had used the same key
for multiple encryptions, the cost of a brute-force cracking attempt
isn't prohibitive. But -- would the NSA make those two assumptions?
Do they have enough storage for the time-space tradeoff attack on
2DES? Did they have any way of determining how often each file
was encrypted? (Poulsen used random numbers of encryption steps
for each file.)
In short -- what does this incident tell us about the security of
n-DES?
