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

Re:searching for ASCII

[2.7182]

Agreed! Also what I do, is before I encode is to switch 1 to 0 and 0 to 1. That'll really confuse'em!

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?

[Lord Byron II]

Exactly right.

Properly encrypted data should be indistinguishable from random noise.

The pigeon hole principle applies to the "decrypted" data. Say you have 16 bytes of data protected by a 16-byte key. Then, there will be lots of keys that produce non-random "decrypted" sequences. But, if you have 1GB of data and a 16-byte key, then there is likely (depending on the nature of the underlying data) only one key that will produce the decrypted data.

It's similar to why there can't exist a generic compression algorithm that *always* shrinks a file.

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

[Anonymous Coward]

Depending on the cipher, this may, or may not work.

A common method to enhance the security of DES is/was to do a encrypt/"decrypt"/encrypt cycle, each with a different key. You may know this method under the name of 3DES. While DES is long broken, 3DES is still considered pretty secure, albeit slow. In contrast, using "tripple-XOR" will most likely not increase the security of a cipher.

And encrypting multiple time with the same key will, for any reasonably secure crypto system*, not increase security. The security incerase in 3DES was due to the increased key length (i.e. the combined length of the 3 keys used in 3DES). Using the same key over and over again does not increase the effective key length.

*Increasing the number of rounds used internally in a crypto system can in some cases increase the security. Usually, cryptoanalists start breaking reduced-rounds versions of ciphers before breaking the full version.

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

[BrotherBeal]

... but I bet you could some how measure how disordered the data stream was and make a guess about weather or not it was encrypted. It seems that encrypted data should also have some level of order to it.

Encryption doesn't work that way, at least not good encryption. The goal of every encryption scheme is to transform a plaintext input into a ciphertext output that is indistinguishable from random noise. Your example of frequency analysis being used to attack ROT13 shows that it's a terrible encryption algorithm because it leaves so much information about the original message embedded in the transformed output. Every time you hear about an encryption scheme being broken, you're hearing about some way to recover information about the plaintext from the ciphertext. That information is what allows adversaries to beat brute-force decryption (although not always by much - a scheme with a keyspace of 2^n is considered broken if an attack is found that requires only 2^n-1 of the keys to be examined).

The OP brings up an interesting point, of knowing when your data is actually decrypted.

This is why a one-time pad is "perfect". A one-time pad leaves absolutely zero information about the original plaintext apart from length (and even that can be obfuscated by null padding). That means that there is no way for an adversary, even through a brute-force attack, to positively identify the original plaintext. Let's say we encrypt "HELLO WORLD" with a one-time pad, and the output is "ZBCHGRTKOP". "ZBCHGRTKOP" could be brute-forced by an adversary and produce "HELLO WORLD", but such an attempt would also produce "BUY MUSTARD" or "URINAL TOWN" or any other string of 10 characters (possibly including nulls - remember padding!). All of these are equally plausible if the one-time pad scheme is implemented perfectly. The point is that, depending on the encryption scheme, in a sense you can't always know that you've done it perfectly. Recreated internal structure is a good signal that you have done it correctly, but if you were trying to decrypt something you knew NOTHING about (couldn't tell it from random noise), you'd have a hell of a time telling whether you screwed up your decryption. Make things any clearer?

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

[maxume]

If the encryption is properly implemented, the repeated cycles should not reveal any information, but it works better to just use a larger key (encrypting twice with 2 different 2 bit keys should be roughly equivalent to encrypting once with a 3 bit key, 4 different 2 bit keys would be equivalent to a 4 bit key and so on, so just going up to a much larger key is probably easier).

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

[smallfries]

Why have you bothered to argue a point that you clearly know nothing about?

Link level encryption. In order to defeat Traffic Analysis it is necessary to fill the channel.

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?

What?

[trifish]

Parallel Algorithm Leads To Crypto Breakthrough

Crypto Breakthrough? Huh? What's that supposed to mean?

I mean, yes, his DES-cracking hardware is about 800x faster than a PC. Where's the "Crypto Breakthrough"?

Re:What?

[Colin Smith]

I mean, yes, his DES-cracking hardware is about 800x faster than a PC. Where's the "Crypto Breakthrough"?

He noticed the previous researcher's "sleep" statements.

 

Re:What?

[QuoteMstr]

I guess "Interesting Thing This Guy Did with Numbers n' Shit" just doesn't have quite the newsworthy ring to it.

Nah, if we adhered to normal journalistic conventions, the headline would read something like "Man Causes Pig to Fly using Homemade Rocket".

Or if this were the New York Times, "In New Development, Swine's Aerial an Inspiration to All" and an editorial the next day, an editorial "Pigs Must Fly Farther, Higher", paired with "Opinionator: Will the Pig Land? Experts Divided. Join the Discussion."

(Then, on Monday, Krugman's "Why we Need Swine Flight Credits" and Ross Douthat's "When will This Liberal Pig Eat Your Children?")

Interesting but not shocking

[Shrike82]

DES is obselete anyway, though the way the decryption was carried out is fairly interesting. A little bit of homework shows that (apparently) a 56-bit DES key was broken in less than a day over ten years ago. So he's a decade late and 66% less efficient!

Re:Interesting but not shocking

[arcade]

apparently?

Loads of us slashdotters was part of distributed.net's effort.

I had 3 of my home computers running rc5des, and about ~200 university computers running it too. :)

And you come up with this "apparantly" thing?! Less than 20 years old, prehaps? Born in the 90s? Not remembering? Harumpfh!

Re:searching for ASCII

[Arancaytar]

Me, I let a Navaho code talker read out the bit stream before transmission.

Isn't it clear?

[QuoteMstr]

One of Slashdot's corporate overlords at VA Research, or Sourceforge, or whatever it's called this week finally heard about Twitter from his nephew, and demanded that Slashdot be made "Web 2.0" relevant. He probably asked about moving Slashdot to the "cloud" too. After being rebuffed with arguments like "that makes no sense" and "we were a blog before blog was a word" and "do you even know what the cloud is", the executive was only dispatched a huff after being told "we're not ready for that yet".

It's the same reason we have the idle section (which if you're sane or over 16, you'll turn off). It's the same reason we have obvious troll stories ("Which editor is better? Visual Studio or a Diseased Chimpanzee? Discuss."). It's why we have pictures in articles, slashvertisments, and and ten times more stories about first person shooters than about functional programming languages.

The Slashdot owners (if not its actual maintainers) see the level of loyalty, tenacity, and clickthrough-friendly stupidity over at Digg and drool all over themselves in MBA-enhanced dollar sign dreams.

Re:Practical value

[QuoteMstr]

DES algorithm is quite similar to AES and Blowfish.

In that they're both block ciphers, yes. That's where the similarity ends; AES doesn't even use a Feistel network. Your comparison is like saying that a flintlock rifle is just like an M1 tank. In other words, you have absolutely no clue what you're talking about.

Re:searching for ASCII

[rubycodez]

I rot-13 everything first, and then I go the extra mile and do it again, cause you can't be too sure

Re:Should be building standardised FPGAs into syst

[SmurfButcher Bob]

10 years ago called, they want their ideas back - starbridgesystems.com

Re:searching for ASCII

[JustOK]

I do rot-6.5, but I do it four times.

What a load of crap!

[ladadadada]

There has been no "crypto breakthrough".

What they have done is created a chip that can do 1.6 billion DES operations per second (compared to 250 million for a GPU card) and then put 176 of them in a 4U server. This lowers the price to performance ratio by around a factor of 6 if you assume that their chip and a GPU are the same price.. By the way, this press release (and research) was made by the company that manufactures the chips in question.

The "massively parallel" algorithm (their term, Dr. Dobbs just copied it) only decrypts a little of the file and looks for ASCII integers because that's what they put in the file before encrypting it. They have not found a way of culling candidate keys without already knowing what sort of data is in the encrypted file. That would be a "crypto breakthrough".

it's a good bit of technology with many uses beyond cryptography that has, unfortunately, been marred by some overly breathless reporting.

Re:searching for ASCII

[Sir_Lewk]

I know you are joking, but I think it should be pointed out that there is no reason this technique can't look for something other than ASCII chars. Most binary files have predictable sequences of bits in them, often some sort of header.

Re:searching for ASCII

[Arthur Grumbine]

I rot-13 everything first, and then I go the extra mile and do it again, cause you can't be too sure

I do rot-6.5, but I do it four times.

You guys are both doing it wrong - wasting CPU cycles to get that additional security. I just do one pass with ROT-26.