NSA Spy Machine and DES

[pcw@access.digex.net (Peter Wayner)]

It is a fun game to contemplate the powers of the machine that Cray
Research is creating for the NSA. Early reports note that it will have
512,000 SIMD processors. 

The proceedings of Crypto 92 contains a paper I wrote describing a slightly
strange design for a DES cracking machine that used "off-the-shelf"
associative memory chips built by Coherent Research Inc in Syracuse, NY.
(Incidentally,
the chips  still aren't "on-the-shelf" yet.) Each line in the chip had 42
bits and a really, really dumb processor. That meant you could get 1024
processors on a chip. They weren't packed very densely and I'm sure it
would be possible to get 16k or maybe even 64k processors on the chip
today.

The processors are really dumb. They take 57126 cycles to encrypt one
64 bit block of data with a 56 bit key using standard DES. At 50 Mhz,
it took 1 million chips to search the entire DES keyspace in one day.
That was 1 billion processors running at once. I calculated at the 
time that this would cost $30 million in the 92 paper. I've revised this
and I think it is eminently possible to get it for about $2 million
if you bargain with the fabrication plants. This is, though, just a
guess. 

It was also possible to estimate how long it would take to crack UNIX
passwords. A 2 million processor machine could knock off all 7 character
passwords composed of alphanumeric characters (A-Z, a-z, 0-9) in one
day. 

Given that the processors I used are probably as dumb as could ever
be invented, I think it is fair to say that 7 character passwords 
could be cracked by this new Cray in four days. Also, DES could be
cracked in 2000 days using this machine and a very brute force approach.

But let's give the NSA/SRC some credit. These new SIMD processors are probably
smarter. Let's say that they're  64 bit wide RISC machines which can only
access their own local on chip memory. If they can run 2 times faster (100
MHz) and do DES encryption in 1000 cycles, then this means that the brute
force attack on DES could be done in 4 days. Bam. 

Is it fair to do DES in 1000 cycles? There are 16 rounds and each round
consists of passing a value through an S Box and adding it in with a
key and part of the result. The most time consuming part is computing 
the sbox result. There are 8 sboxes in play that operate on 4 bits at
a time. Lets assume that they compute the sboxes by looking them up in
a table. If it takes 4 cycles to go to memory and an extra cycle to 
add in the result, then that is 40 cycles to compute the sbox. 

The key computation involves several shifts and some more adds. Let's
say 10 cycles. Use the other 14 cycles for book keeping and that leaves
64 cycles per round or 1024 cycles to do the encryption. That translates
into  4 days per DES attack.

Could it go faster? On chip memory access could be done in one cycle.
You might be able to push things down to 24 cycles per round. That would
get you near 1 day per attack. I don't see going any faster.

Is it fair to assume that you can build 512,000 low-grade 64 bit processors
for a price? The newspaper stated that the contract was worth $4.5 million.
Let's allocate $512,000 for the SIMD chips. That $1 a processor. Let's
say  you can get 800,000 transistors for $10 in bulk quantities today. That's
80,000 transistors per processor. It seems reasonable to me that you can
get a pretty okay 64 bit processor with some local memory for that amount
if you strip away all of the cache management, floating point and
multiplication. 
But this really isn't my area of expertise. I would welcome more informed
analysis. 

The best data point, though, would be some papers about the Processor-In-
Memory project run by the Supercomputing Research Center in Bowie, MD. 
This is a semi-public project and there have been some pre-prints
circulating. They built some early machines that added a few processors to
each memory chip. You could write to these chips like normal memory until
you flipped a logic
line. Then all writes would be routed to the processors which would treated
the write as an instruction. There were something like 8 or 16 processors on 
a chip. I can't seem to find my copies of them. They would give great
insight into the past work of the NSA. 

Given this, I conclude that this new machine is the first public
acknowledgement that the NSA will have the ability to use a brute-force
attack on DES in about 4 days. It also implies that 7 character
alphanumeric UNIX passwords can be knocked off in no time of consequence. 

These are all back of the envelope computations about people pushing the
technological envelope. I would enjoy hearing about any arguments or
suggestions that people have about the details. 

The RISKS? Passwords _REALLY_ need to be longer. DES needs to be replaced by
triple-DES or something similar.