Re:Parallel Algorithm Leads to Crypto Breakthrough
by redmage on Friday January 29, 2010 @09:31AM
(#1086489)
I think their point was this:
When using a Pico FPGA cluster, however, each FPGA is able
to perform 1.6 billion DES operations per second. A cluster
of 176 FPGAs, installed into a single server using standard
PCI Express slots, is capable of processing more than 280
billion DES operations per second. This means that a key
recovery that would take years to perform on a PC, even
with GPU acceleration, could be accomplished in less than
three days on the FPGA cluster.
So, they managed to brute-force DES a lot faster. No crypto breakthrough, please move along. :)
This should have been titled "FPGA cluster brute-forces DES in record time" or something like that.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by cperciva on Friday January 29, 2010 @10:20AM
(#1086586)
FPGA cluster brute-forces DES in record time
Even that isn't true. Deep Crack took 56 hours (matching the "less than three days" claimed in the article), while the combined Deep Crack + Distributed.Net effort took less than 24 hours.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by redmage on Friday January 29, 2010 @10:48AM
(#1086678)
Sorry, my bad. I didn't bother to research, just pulled that from the article.
Pico Computing has announced that it has achieved the
highest-known benchmark speeds for 56-bit DES decryption,
with reported throughput of over 280 billion keys per
second achieved using a single, hardware-accelerated server.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by redmage on Friday January 29, 2010 @12:02PM
(#1086877)
What can I say? Pico Computing likes to brag and Dr. Dobb's published an article about it. As you said in your first comment, there's nothing new about this.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by NateLawson on Friday January 29, 2010 @03:00PM
(#1087405)
1998's DES cracker implemented on today's FPGAs is faster. There is no algorithmic advance -- this is just a thinly-disguised ad for their particular FPGA card. Moving right along...
Re:Parallel Algorithm Leads to Crypto Breakthrough
by CWuestefeld on Friday January 29, 2010 @10:03AM
(#1086546)
I've often wondered how you know when you've actually found the solution.
The massively parallel algorithm iteratively decrypts fixed-size blocks of data to find keys that decrypt into ASCII numbers. This technique is often used for recovering the keys of encrypted files containing known types of data.
This doesn't make sense to me. I mean, what if I didn't encrypt ASCII numbers? What if it's, say, an email message that's predominantly text in, say, UTF-8 or UTF-16?
And it seems to me that as we develop richer ways to encode data, it also makes it correspondingly difficult to decrypt that data.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by cperciva on Friday January 29, 2010 @10:32AM
(#1086632)
The field of cryptography developed in the context of nation-state actors and idiots who use crypto wrong. (Come to think of it, not much has changed.) In WW2, a lot of crypto was broken thanks to known plaintexts -- e.g., "Today's weather is..." -- or chosen plaintexts -- e.g., "Submarine sighted at...". This was made easier, of course, by the fact that military structures tend to use very consistent communications formats.
You're quite right that you can slow down a brute force attack by making the input data hard to recognize -- one trivial approach is to pad it to a large size and then apply an all-or-nothing transform -- but by the time this sort of mechanism was feasible, brute force key searches stopped being useful due to increased key lengths.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by eru on Friday January 29, 2010 @10:51AM
(#1086688)
As far as I know the allies used to spot the plaintext word "EINS" in the Enigma ciphertexts. This was helped by the omission of numbers --- or anything besides letters --- from the Enigma's alphabet. They did not even have a space key.
Re:Parallel Algorithm Leads to Crypto Breakthrough
by moron4hire on Friday January 29, 2010 @10:31AM
(#1086623)
Not sure about UTF-16, but UTF-8 is backwards compatible with ASCII. A lot of decryption requires having a general idea of what the message contains. If you know that the message is standard English text, then that gives you huge opportunities, like finding keys that make parts of the message decrypt to the word "the".
This should have been titled "FPGA cluster brute-forces DES in record time" or something like that.
Even that isn't true. Deep Crack took 56 hours (matching the "less than three days" claimed in the article), while the combined Deep Crack + Distributed.Net effort took less than 24 hours.
The massively parallel algorithm iteratively decrypts fixed-size blocks of data to find keys that decrypt into ASCII numbers. This technique is often used for recovering the keys of encrypted files containing known types of data.
This doesn't make sense to me. I mean, what if I didn't encrypt ASCII numbers? What if it's, say, an email message that's predominantly text in, say, UTF-8 or UTF-16?
And it seems to me that as we develop richer ways to encode data, it also makes it correspondingly difficult to decrypt that data.
You're quite right that you can slow down a brute force attack by making the input data hard to recognize -- one trivial approach is to pad it to a large size and then apply an all-or-nothing transform -- but by the time this sort of mechanism was feasible, brute force key searches stopped being useful due to increased key lengths.
http://www.copacobana.org/
And it cracked DES in about 9 days iirc, @35 billion keys / second.