Slashdot Mirror
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."
Agreed! Also what I do, is before I encode is to switch 1 to 0 and 0 to 1. That'll really confuse'em!
Apps could load a custom config into the chip to run faster.
Deleted
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.
politicians are like babies' nappies: they should both be changed regularly and for the same reasons
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"?
FIrst post!
Your encryption was cracked, and you didn't post first.
Just not your day. :)
Do what thou wilt shall be the whole of the Law
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!
You can advertise in this sig from as little as £99.99 a month!
Me, I let a Navaho code talker read out the bit stream before transmission.
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.
You can advertise in this sig from as little as £99.99 a month!
...reminded of the little box hidden in an answering machine in that movie Sneakers? lulz
Living With a Nerd
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.
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.
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.
# cat
Damn, my RAM is full of llamas.
I rot-13 everything first, and then I go the extra mile and do it again, cause you can't be too sure
i would expect as much, it's within the cia's self interest to prevent the existence of a encryption algorithm they can't crack or don't already have a key too.
10 years ago called, they want their ideas back - starbridgesystems.com
help me i've cloned myself and can't remember which one I am
Yeah, well Xilinx pursued this in the early 90s with a swappable FPGA with an open architecture. That was discontinued pretty quickly, though.
The main issue is that apps aren't slow in the right way. Very few apps these days are in fact ALU-bound. With GPU resources and SSE, even fewer need extra ALU power, and the hard limits come from memory access speed (especially random access, as required by a great many algorithms). FPGAs don't really make this any easier (except insofar as they can offer *small* local caches which are blisteringly fast).
Also, any application domain which does have a speed problem tends to get hardware accelerator support pretty quickly - think of H.264 encoding, for instance. Whatever can be done on an FPGA is already done in various other products. None-the-less, a generic FPGA in every computer would reduce the need for all this custom silicon.
Personally I like the idea, but I fear it is too "niche" to ever make it as a standard PC component.
OTOH, what Intel etc. might consider is putting some FPGAable "special instructions" in the ISA, then attaching some FPGA resources that can be programmed in a relatively simple manner to execute some specially-needed instruction. I used to dream of this back in the early 90s when I was writing texture-mapping software ... the bit-twiddling there can take several instructions, whereas a few custom FPGA cells could do the same thing in one inst. But then, the programmer would want to implement pipelining on anything > 1 cycle, and that could be interesting to interface back to the main core.
For the niche applications where this all makes sense, you can buy some pretty awesome development kits. Pico Computing (mentioned in TFA) look to make interesting products, but there is also the whole XGameStation thing which - thanks to its nature - can easily be repurposed.
I do rot-6.5, but I do it four times.
rewriting history since 2109
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.
Sig matters not. Judge me by my sig, do you?
Brute-forcing DES doesn't require any creative algorithm to be run in parallel. You have 2^56 possible keys, split them amongst 2^n crackers and each cracker has to process 2^(56-n) keys. Not too hard.
And loading an array of DES cracker cores onto an array of chips isn't novel either, ie:
http://en.wikipedia.org/wiki/EFF_DES_cracker (using ASICs)
http://www.copacobana.org/ (using FPGAs)
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.
"linux is just DOS with a UNIX like syntax" -- Galactic Dominator (944134)
There are a run-time reconfigurable FPGAs on the market, but they still take time to switch(something like 200 microseconds). Not terribly long on our scale, but not exactly fast for the CPU.
The real problem is that FPGAs are generally more expensive for anything that you can mass-produce. FPGAs shine if you want something custom and parallel, like this cluster, and can be cost-competitive compared to getting your own silicon made for prototypes.
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.
Now that I think about it, I'm pretty sure everything I just said is completely wrong.
While I can't argue that NSA hasn't been able to decode DES from an early point, it's not all doom and gloom. From the same Wikipedia page are several sources confirming that Lucifer, as initially conceived by IBM, was vulnerable to differential cryptanalysis, and the NSA's modifications, back in 1974, significantly strengthened the subsequent DES algorithm. This wasn't confirmed until 1990. Before we dismiss any government involvement out of hand, lets consider all sides. Relevant passage from Wikipedia: Some of the suspicions about hidden weaknesses in the S-boxes were allayed in 1990, with the independent discovery and open publication by Eli Biham and Adi Shamir of differential cryptanalysis, a general method for breaking block ciphers. The S-boxes of DES were much more resistant to the attack than if they had been chosen at random, strongly suggesting that IBM knew about the technique back in the 1970s. This was indeed the case — in 1994, Don Coppersmith published some of the original design criteria for the S-boxes. According to Steven Levy, IBM Watson researchers discovered differential cryptanalytic attacks in 1974 and were asked by the NSA to keep the technique secret.
It turns out that there are attacks on 3DES that mean that the effective strength is still only 112 bits, not 168, even if you're using three different keys. Since 2 keys are just as strong, it lets you use a 128-bit or 160-bit source of randomness to generate them.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
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.
You can't legislate goodness. Let each to his own destiny, by will of his freely made choices.
ROT-26 has several interesting properties that make it unique among encryption algorithms,and only by knowing it's strengths and weaknesses can you decide if it is the right tool for your use case. For one, ROT-26 (and the entire ROT family of ciphers) are unique among encryption strategies in their heavy reliance on avoiding hostile interception altogether. Even if intercepted, like many of the latest stenographic or hidden volume techniques, a ROT-26 cyphertext nearly always succeeds at being completely unidentifiable as an encrypted document. It has, however, been singled out (fairly In my opinion) for being vulnerable to a trivial known-ciphertext attack that may be employed by any minimally literate expert. Although praised for it's universal hardware support and unbeatable performance (a constant time implementation of the algorithm has been discovered(!)), nonetheless, securing your data using ROT-26 is increasingly viewed as unwise.