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.