Parallel Algorithm Leads To Crypto Breakthrough

Hugh Pickens writes "Dr. Dobbs reports that a cracking algorithm using brute force methods can analyze the entire DES 56-bit keyspace with a throughput of over 280 billion keys per second, the highest-known benchmark speeds for 56-bit DES decryption and can accomplish a key recovery that would take years to perform on a PC, even with GPU acceleration, in less than three days using a single, hardware-accelerated server with a cluster of 176 FPGAs. The massively parallel algorithm iteratively decrypts fixed-size blocks of data to find keys that decrypt into ASCII numbers. Candidate keys that are found in this way can then be more thoroughly tested to determine which candidate key is correct." Update by timothy, 2010-01-29 19:05 GMT: Reader Stefan Baumgart writes to point out prior brute-force methods using reprogrammable chips, including Copacobana (PDF), have achieved even shorter cracking times for DES-56. See also this 2005 book review of Brute Force, about the EFF's distributed DES-breaking effort that succeeded in 1997 in cracking a DES-encrypted message. "'This DES cracking algorithm demonstrates a practical, scalable approach to accelerated cryptography,' says David Hulton, an expert in code cracking and cryptography. 'Previous methods of acceleration using clustered CPUs show increasingly poor results due to non-linear power consumption and escalating system costs as more CPUs are added. Using FPGAs allows us to devote exactly the amount of silicon resources needed to meet performance and cost goals, without incurring significant parallel processing overhead.' Although 56-bit DES is now considered obsolete, having been replaced by newer and more secure Advanced Encryption Standard (AES) encryption methods, DES continues to serve an important role in cryptographic research, and in the development and auditing of current and future block-based encryption algorithms."

Comments

Should be building standardised FPGAs into systems

[Colin Smith]

Apps could load a custom config into the chip to run faster.

 

How do you know when it's decrypted?

[petes_PoV]

Apart form the trivial case where some ASCII, or a picture pops up, how can a decrypter know when the block or stream of apparently random data has been decrypted?

If I was to start transmitting some random data and told people it was encrypted with DES 56 bit, but in fact it wasn't - it was just random data. Then, apart from exhaustively testing it with every possible key, how could they demonstrate that it was NOT encrypted as claimed?
It does seem to me that one of the problems with decrypting "stuff" is that you need to have some idea what the "answer" will look like. Without that you can't ever be certain when you've succeeded.

Re:How do you know when it's decrypted?

[txoof]

Even if it's ASCII or a picture, just encrypt it twice.

I've always wondered what would happen if you were to encrypt a file over and over again, with different keys. Would that lead to any greater security, or would somehow leave more and more obvious clues as to how the data was encrypted? What would happen if you encrypted over and over using the same key?

Re:How do you know when it's decrypted?

[microbox]

And encrypting multiple time with the same key will, for any reasonably secure crypto system*, not increase security.

I understand that from a theoretical point of view, but from a practical point of view -- how would you break an encrypted file if it is doubly encrypted, even if you knew both algorithms involved. How do you solve the problem of recognizing if you'd actually decrypted with the first key, so that you can start working with the second key?? Haven't you increased the key-space to an exponent of itself (in practical terms), and therefore created something vastly more secure?

Practical value

[buruonbrails]

DES algorithm is quite similar to AES and Blowfish. I wonder, if this method (with a few modifications) could be used to crack AES and Blowfish-encrypted messages? Besides, many people still use DES and Triple-DES.

Re:Practical value

[Shrike82]

In the case of Triple-DES you're dealing with three times as many bits for the key, so you move fairly rapidly from decryption in three days to several billion years. Other ecryption algorithms use even more bits, and more complex key schemes so, while the work is interesting, we can still hide porn on our PCs without fear.

Re:Should be building standardised FPGAs into syst

[bcmm]

How fast can an FPGA be reconfigured? I suspect that they would not lend themselves to task switching as readily as CPUs do, and the potential of FPGAs to accelerate day-to-day tasks would be somewhat reduced if only one process could use it at a time.

Re:Should be building standardised FPGAs into syst

[digitalunity]

There could be a market for this. I see 2 obvious applications.

First application would be for photo and movie processing. An FPGA that could be configured by photoshop plugins or other linear movie editing programs could see dramatic speedups.

Another would be finite element analysis, in CAD/CAM applications or others such as Inventor, Simulia, Catia, MathCad, etc.

I see some desire for GPGPU in these areas but with a little added complexity, I think these applications would see a big speedup even over GPGPU.