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?

[Endymion]

While this is likely an issue in the general case, I suspect that in common use we already do have a good idea of what the "answer" looks like. You likely know what software did the encryption, and therefore what structures in the data to expect. Knowing where the data came from tells you a lot before you even start any of the brute-force math.

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

[olsmeister]

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

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]

or three times! better, encrypt it, descrypt with a different key and then encrypt again with a third key. i know, i'll call it 3DES.

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

[txoof]

That's a really interesting question. I'm not a math or cryptography person, so I'm just guessing here, 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. If you use something like rot-13 (which I know is a cypher not strictly encryption) to cypher an english message you can do some simple statistical analysis and make some intelligent guesses as to wich letter cypher letter corresponds to 'e' and 'a' and 'z' and so forth.

Perhaps some sort of similar thinking can be applied to a chunk of data to determine if it's just random junk or has something embedded in it. Are there any crypto or math people out there that can comment on this?

The OP brings up an interesting point, of knowing when your data is actually decrypted. For plain text, it should be pretty easy to just do a quick scan for english/french/whatever words, for pictures, it would be fairly easy to look for things like jpeg headers. But what if it's some sort of proprietary data or just a chunk of a file? How do you know if you're successful?

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

[Arancaytar]

That's easy - the (uncompressed) clear text is going to be considerably less entropic than average, and even most compression algorithms cannot raise the entropy to the same level as that of a random message.

The key-space in DES 56 (ie, 2^56) is considerably smaller than the number of possible messages with that length (might be 2^(1000*x) for a text multiple kB message). If one of these 2^56 keys decrypts the message to a coherent clear text out of 2^1000, it's extremely unlikely to be a chance result.

If you encrypted random data, then it would take a long while, but after searching the whole key space the eavesdropper would eventually conclude that there is no clear text.

You were probably thinking of a one-time-pad, where the key contains exactly as many bits of random noise as the message is long. That gives every clear message of the right length exactly the same likelihood, and really does make it impossible to know when you've succeeded - or to determine whether the message is random noise or not.

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?

[noidentity]

Any realistic encryption format will include verification information (a checksum at the very least) so the decrypter knows that it was successful. Otherwise it wouldn't even be able to tell you that you mistyped your password.

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?

[petes_PoV]

Yes, I accept your point. Now let's modify the situation to real life. When most governments send encrypted data, they don't just say "ooooh, we've got some sensitive data to send, we'd better encrypt it" as that alone tells a baddie that there's something going on - as the level of encrypted data increases. Further, you don't just send *all* your traffic encrypted either, as it's still prone to monitoring the volume of traffic.

Instead, you fill the channel, all of the time. Some of the traffic is proper encrypted data and some of it is just random padding (or if you really want to screw with them, encrypted random padding). While it may be possible to brute-force 1 particular message, until you can do a brute-force decryption in real time, encryption, even with weak keys, will almost always egt through securely. (You could nuance it further, but inserting decoy data with artifically weakened keys. too).

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?

[bobdotorg]

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

Not always better. For example, the text you are reading now was encrypted with ROT13. Twice.

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

[SlideRuleGuy]

Folks need to use Rivest's Package Transform (i.e., all-or-nothing encryption). This increases the difficulty by forcing a cryptanalyst to decrypt an entire (multi-block) message instead of just individual blocks, before looking for plaintext.

http://en.wikipedia.org/wiki/All-or-nothing_transform

(Or just switch to AES...duh.)

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

[TheRaven64]

The canonical example of a bad cypher is an XOR cypher, where every bit in the input stream is XOR'd with a key. If you do this twice, with two separate keys, then you have done the equivalent of XOR it once with the key generated by XORing the two keys. As such, it is no more secure (but also no less secure).

With a perfect cypher, there is no relationship between the two applications, so if you encrypt it twice then you double the amount of effort required to crack it. However, for most decent cyphers the difficulty of decrypting it is roughly proportional to the length of the key, so adding one bit to the key length gives you as much security as encrypting it twice.

The 3DES algorithm uses three 56-bit keys, but is much easier to break than using DES with one 168-bit key. It was created because you can use it with DES-accelerating hardware (at a third of the speed of single DES), while using DES with a longer key would typically require new hardware.

Of course, this isn't always the case. There are some attacks that take less time on the 192-bit key version of AES turns out to be harder to crack than the 256-bit key version.

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

[fluffy99]

Yes, I accept your point. Now let's modify the situation to real life. When most governments send encrypted data, they don't just say "ooooh, we've got some sensitive data to send, we'd better encrypt it" as that alone tells a baddie that there's something going on - as the level of encrypted data increases. Further, you don't just send *all* your traffic encrypted either, as it's still prone to monitoring the volume of traffic.

Instead, you fill the channel, all of the time. Some of the traffic is proper encrypted data and some of it is just random padding (or if you really want to screw with them, encrypted random padding).
While it may be possible to brute-force 1 particular message, until you can do a brute-force decryption in real time, encryption, even with weak keys, will almost always egt through securely. (You could nuance it further, but inserting decoy data with artifically weakened keys. too).

Now lets switch to this reality. Military encryptors just encrypt the entire classified traffic channels. They don't "fill the channel" with garbage as it costs real money and bandwidth to do that. Granted they encrypt all traffic on that channel so the overall traffic has varying levels of sensitivity or classification, but they certainly don't generate garbage padding to confuse the enemy.

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

[TRS80NT]

A good question. An analog from simpler times:
More years ago than I care to count on my fingers I was a cryptanalyst in...let's say, near, the Mideast. The traffic we were intercepting and working on was in Russian, Italian or one of several dialects of Arabic, none of which I speak, or more to the point, read. But when you are applying decryption techniques you don't necessarily have to know what exactly what the message says to make progress, just what the plaintext should LOOK like.

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

[Sir_Lewk]

The problem with that is to confirm the checksum your cracker may have to decrypt a much larger portion of the message each time, slowing down the process.

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

[Lord Ender]

The answer to your question is implementation-specific.

If you're cracking encrypted email, you know you're looking for plain text, so that test is easy. Cracking TrueCrypt partitions? Use whatever algorithm TC uses to determine whether or not a password matches (TC has some deterministic means of distinguishing this, for use in its plausible deniability feature).

Cracking SSL? Look for the one which decrypts to HTTP.

Cracking general disk encryption products? Look for filesystem structures.

The only time the problem you mention could trip you up is when you have no idea what format the underlying data is in. In that case, you can test for entropy or try some other tricks.

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

[QuoteMstr]

They don't "fill the channel" with garbage as it costs real money and bandwidth to do that.

They sure do.

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?

[owlstead]

Many encryption schemes (for secure messaging, say SSL) include a MAC or HMAC (secure checksum) with a *different* session key. So finding the MAC key is not always the same as finding the encryption key.

You know the password is correct by generating a key from a password (say, using PKCS#5 password based encryption key generation scheme), and sending back an encrypted challenge. Using DES for this scheme is a terrible idea (known plaintext - all the encrypted "characters" are known).

Anyway, most encrypted data (not passwords, they are normally not encrypted) is data wrapped in either ASN.1 DER encoded structures (CMS or PKCS#7) or (e.g.) XML encoded structures. Then there is the padding of the last block which is also generally known. Knowing the (partial) plain text of some of the encrypted blocks is simply not an issue.

Yes, you can encrypt twice, if needed with two different algorithms. Yes, this would mean that plain text is hard to detect. If you use the same key and the same algorithm, double encryption is probably cryptographically slightly worse compared to simply increasing the number of rounds of the algorithm. There is simply no good substitute for Increasing the key length and using a good cryptographic algorithm like AES (for any key size).

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

[Anonymous Coward]

umm, no actually. Random data looks, well, random. When you suddenly have lots of organized and repeating data, it's pretty darn easy to spot. I've actually made the assessment several thousand times using wireshark. 1. Yep, that looks like its encrypted random crap. 2. Nope, that's nice and organized binary protocol exchanges. They're just automating it to "decrypt fixed-size blocks" locking for things that look like ASCII. Fairly simple concept, but someone actually has to take the time to build one.

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

[smallfries]

You seem to confuse several basic notions in cryptography. Firstly what you are describing as an XOR cipher includes one-time-pads (you haven't mentioned if the key is as big as the input or not), which are certainly not "bad" in any sense.

With a perfect cipher there should be no information leaked into the ciphertext, or as Shannon put it there should be no advantage in knowing the ciphertext. So all perfect ciphers have the property that if you use them multiple times under multiple keys then the effort to break them remains constant.

When you say the difficulty of decrypting is roughly proportional to the length of the key, you of course mean that the difficulty of decrypting is roughly proportional to the size of the key-space, or O(2^n) where n is the length of the key.

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

[Hurricane78]

Exactly. Why would you crack it, if not because there’s something in there that you wanted. Which implies you know what it is or means.

And if it’s not in there anyway, then not cracking it is OK. Since, well, you don’t want it anyway.

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

[Dracolytch]

Execpt the vast, vast, vast majority of data that's sent isn't random at all. In fact, it's extremely not-random. If you open a file in a hex editor (even a binary instead of ascii file), there are patterns, there is text, there are markers to show you what you have. Heck, in many files, the first 4-8 bytes of the file will tell you exactly what kind of file it is. While it's not a super-easy problem, it's easier than you're making it out to be.

~D

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

[Fnord666]

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).

Now you start getting into the number theoretic part of cryptography relating to groups, rings, etc. What you have said above does not necessarily hold true though, and can be disproved through a simple counterexample.

Consider a 2 bit key and a 2 bit data block where the exnryption/decryption operation is to XOR the two together. We can perform the same operation a second time using a second, independent key. Now what is the strength? It still remains only 2 bits, because in the end their is an equivalent third key that will produce the same ciphertext from the cleartext. You can find the third key in this case by XORing the two keys together. The point is that brute force will turn up this third key with no more effort than was required for a single key.

As for the question of knowing when you have decrypted the text, there are methods of identifying a small number of candicate decryptions for . In many cases, you may not know the contents of the file but you might know its type. If you know that, there are often known values at specific locations in the file, particularly in the header. Let's say for example that we find a computer that has an encrypted document that is most likely a spreadsheet and that I also find excel 2003 loaded on the same computer. I can begin by assuming that the file format is an excel format appropriate to that version and that it will probably have the headers associated with that format on it when it is decrypted. For each key we decrypt the first block, check out the bytes that we know in the header, and flag any match for further investigation. because crypto algorithms are natural randomizers, false positives should occur with no more frequency than a random selection would predict. If the document in question was a letter in a known language such as English, we could further reduce the false positives by performing a basic letter frequency count in the decrypted result. If it were text source code, we should expect to see only ASCII chars below 128. If the resulting sample decryption block has half of its byte values above 127, then it probably isn't the right key.

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

[bytesex]

You must be airforce.

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

[bytesex]

That's very interesting. Are you sure you should be posting this ?

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

[petes_PoV]

To be fair, military radio links usually use a spread-spectrum ECCM technique which is designed to make it very hard (pref. impossible) to monitor if a transmission is actually being made by spreading the energy of the transmission across a wide enough spectrum, it becomes undetectable and also impossible to jam.
So mil-spec comms are different from government radio links (to their agents or operatives) or satellite links.

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

[tepples]

it works better to just use a larger key

That's not always easy, especially if you have sunk a lot of money into crypto hardware that supports only short keys. That's one reason why triple DES took off: existing DES ASICs could still handle it.

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

[TheRaven64]

Firstly what you are describing as an XOR cipher includes one-time-pads (you haven't mentioned if the key is as big as the input or not), which are certainly not "bad" in any sense.

A one time pad used in this way is an XOR cypher with an infinite key length (or, at least, one as long as the message). My point is still valid for one time pads. Using two one time pads with an XOR mechanism does not buy you any extra security. It is equivalent to using one one-time pad with different values.

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

[TRS80NT]

Heh, heh. Soon after I got out of the Army, a writer for Rolling Stone was reminiscing about his days in the Navy. They had had approximately the same mission we had, just offset a little bit geographically. I'm not sure if he got in trouble for it, but he "declassified" a LOT of information.
Let me just repeat the motto of the Army Security Agency: In God we trust, everyone else we monitor.

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

[smallfries]

You also claimed that a perfect cipher would require twice the effort to break after two applications. This seemed to be the thrust of your main point. Do you still think that is valid?

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?

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

[onionman]

Your point is correct. You have to have additional information about the traffic. Often this comes in the form of frequency analysis of the trial decryption, or a known block of plaintext that is part of the formatting or protocol of the message (the standard example is the date of the message that the Nazi's often placed in their Enigma encrypted messages; if you know the date of the intercept, then you've got a pretty good guess for the plaintext for the first half dozen letter, so it's easier to test if a key is correct.)

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

[Eil]

When brute-forcing a key, you have to have some idea of what the decrypted data looks like. If you're cracking a hard drive, for example, you'd check for a valid partition table. If you're cracking a text file, you'd check it for natural language words. An HTTPS packet probably has HTML tags somewhere inside, etc. In order to crack a packet of encrypted data, you need to know these things:

* The encryption algorithm
* The properties of its implementation (key length, any key derivation functions, the kind of padding used, etc)
* Context regarding the packet's purpose and origin (where it came from, what generated it, what it likely contains, etc)

And that's assuming that the encryption is weak enough to be cracked in the first place. (E.g., if it's AES-256, forget about it.) It would be a rather rare case that you had a chunk of data, knew exactly how it was encrypted, but didn't have any other context to go with it.

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

[Anonymous Coward]

Basically right, but your comment on security of DES with 168-bit key is false:

Quoting Wikipedia:
http://en.wikipedia.org/wiki/Data_Encryption_Standard

It is known that the maximum cryptographic security of DES is limited to about 64 bits, even when independently choosing all round subkeys instead of deriving them from a key, which would otherwise permit a security of 768 bits.

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

[pclminion]

Depends whether the cipher is "idempotent" or not. If a cipher is idempotent, then encrypting with key A followed by key B is the same as encrypting just a single time with some key C. Clearly, this is no more secure than just encrypting once, since you only need to find key C. If a cipher is NOT idempotent, the result of encrypting by A and then by B can't be reproduced by any single key C.

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

[Peter Amstutz]

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.

You get Triple-DES.

Also, consider that encryption algorithms are not magic. Having no distinguishable pattern to attacker is the goal, but the data is not actually random! Encryption comes down to applying a set of mathematical transformations on your data which leaves "fingerprints" in the cyphertext if you know what to look for. Applying more than one algorithm or the same algorithm more than once at best adds a security-through-obscurity aspect to hinder reverse engineering, at worst may introduce patterns that make your cyphertext easier to attack compared to simply increasing the key size used with a single well designed algorithm.

IANASR (I am not a security researcher)

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

[Daffy Duck]

No, DES is not a group.

Let's say there was a 2-bit version of DES as in your example. For a 2-bit data block, there are 2^2 = 4 possible values. That means there are 4! = 24 possible permutations, but there are only 2^2 = 4 keys. So not all the possible permutations are generatable by a single key, and what Campbell and Weiner proved in 1993 was that successive applications of DES with different keys produce (in general) one of those "lost" permutations that can't be done with a single key.

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

[Impy the Impiuos Imp]

> 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?

Well, in this case they're talking about a 56-bit almost-prime number that factors into two primes roughly half the size. The encryption relies on this, so if you can do it, the decoding is straightforward.

As for a brute force method, there are probably algorithms that can guestimate based on how far from random your candidate decoding is, the further the better.

Also, I'm sure the CIA has computers that crank everything through every known language, backwards and forwards, with other simpler, intermediate encodings applied, vowels left out, Soundex algorithm applied and not, etc. et al.

Of course that, in and of itself, is quite a significant project. Anyway, if I had their resources, that's what I'd do.

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

[Impy the Impiuos Imp]

And, of course, if it's truly important, like during WWII, you just flat-out hire hundreds of people to look at the stuff you're generating.

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

[Anonymous Coward]

If you're clever about your encryption, I believe it would also be smart to employ stenographic methods in at least one of the encryption layers. Somebody would believe they cracked your code, but essentially they're viewing garbage information. (And if you're clever about what you put in the garbage layer, you could really mislead your opponent in funny and interesting ways.) Yet remaining somewhere still encrypted within the garbage they decrypted is your actual real information.

I'd suspect there are some limitations to this, like it might not work so well with plain text or some types of simple data as a container as it would with video, audio, and image data as the container. But if all your data streams had higher bandwidth items that were still worth encrypting, then I don't see why this wouldn't work.

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

[Anonymous Coward]

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?

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?

That is where 3DES comes into picture. Encrypt-decrypt-encrypt effectively making the key length=3*56=158

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

[Anonymous Coward]

In certain contexts, 3DES is roughly equivalent to an hypotetical DES with a 112 bits keys. In the same context, double encryption only marginaly increase security.

See meet in the middle. This is probably applicable to any kind of multi encryptions.

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

[sticky.pirate]

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?

Multiply encrypting will only increase your security if there isn't some other key that you could have used that yields the same results. For example, if we use "E(M,K)" means "Encrypt message M with key K" then encrypting twice would be E(E(M,K1),K2). The problem is, if there is some OTHER key K3 such that E(M,K3) = E(E(M,K1),K2), then you really haven't added any security by doing that.

Obligatory disclaimer: everything I know about cryptography I learned from reading Bruce Schneier's books, and they're all in storage at the moment

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

[Fnord666]

No, DES is not a group.

I agree and I appreciate that you pointed that out. I probably should have stated it. That is why 3DES turns out to be stronger than DES. I was speaking to the more general assertion that seemed to be claimed by the parent post which implied that multiple encryptions with different keys would always yield increased effective key length.

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

[DrJimbo]

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.

This is a very good point. The book Battle of Wits: The Complete Story of Codebreaking in World War II explains in great detail how various Axis codes were broken by the Allies. Knowing what the "answer" looked like was essential for much of the codebreaking. In fact, Turing's masterful technique to use machines to automatically decrypt messages encrypted by the more advanced German Enigma machines relied on knowing exactly a portion of the plaintext of one of the messages. Once one message was cracked this way they were usually able to rather quickly decrypt all the other messages that used the same key that day.

Much of the WW-II vintage decryption was based on exploiting patterns in the plaintext (such as letter or word frequency) that left a trace in the encrypted messages. It is amazing how extremely subtle patterns were detected and then exploited. IMO, most of WW-II codebreaking was based on these subtle patterns. The other part of the codebreaking involved stealing the keys (codebooks, etc.) from the enemy.

As you suggest, if there is no pattern in the plaintext then breaking the encryption is much harder and often impossible.

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

[DrJimbo]

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?

If both algorithms are known and susceptable to brute force then when you combine them you are still susceptable to a known plaintext attack where you decrypt the encrypted message with alogorithm B and encrypt the known plaintext with algorithm A and then look for a match. This increases your storage requirements but only doubles the amount of "CPU" needed.

IMO (IANAC) using one alogorithm with a doubled key size 2 * N will be much more secure then encrypting twice using two algorithms with keysize N.

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

[VortexCortex]

But... DES is a block cipher. The algo. E(E(M,K1),K2) == E(M,K3) where K3 is some other key is only true if E is simply operating on K in a stream like fashion (like XOR).

Transposing the keys produces a different output stream in DES... E(E(M,K1),K2) =/= E(E(M,K2),K1).
There is no "magic" K3 that will produce the same sequence of encrypted bytes as taking the encrypted output of E(M,K1) and encrypting it again via K2.

This is simple to demonstrate with a car analogy: With BLOCK ciphers there is no magic "getting in a car" that equals "getting into a car" then putting that car inside another car.

With stream ciphers: There IS a magic "getting into a car" that equals "getting into a car", driving a ways and "getting into a different car".

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

[fluffy99]

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.

You just proved my point sir! Link-level encryption is exactly what I'm talking about. The entire communications circuit betweem sites is encrypted if the connected networks or systems are classified. It is generally done using NSA type-1 encryptors. There is no distinction made about the actual traffic traversing the link. There is no requirement what so ever to fill the channel with extra garbage and it generally is not done.

You'll see end-end encryption on the unclass networks in the form of individually encrypted emails or encrypted files, or perhaps even the use of ipsec for select communications. Are you suggesting that we should just add random traffic that looks encrypted but is just garbage? Again, its not done becauses bandwidth costs money and it isn't needed.

To confuse this even more, quite often the black side of the encryptors are connected to the unclass networks, and the encrypted traffic traverses/tunnels unclassified links. That would technically be link-level encryption between the classified sites, but could also be considered end-end encryption since the unclass link contains some encrypted and non-encrytped traffic.

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

[fluffy99]

Indeed, the main intent of the spread spectrum techniques is to prevent jamming and identifying the source location of a transmission. No sense having your soldier sending out a beacon for his location on the battlefield.

This technique does a layer of security, but it's a secondary benefit as encryption is normally done for classified transmissions anyway.

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

[fluffy99]

Close, different branch. Despite smallfries assertion that I don't know anything, I happen to be deeply involved in encryption and classified miltary networks.

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

[Anonymous Coward]

One Time Pad - easy!

#!/usr/bin/python
import Tkinter as tk

import tkSimpleDialog
import tkFileDialog
import sys
import random
# Set root window
root = tk.Tk()

root.geometry("1x1")
# Simple XOR encryption, using the sum of ASCII values from the key to seed the random number generator, and
# then generate 'random' numbers to XOR the bytes from the file

filex = tkFileDialog.askopenfile(title='Choose a file to XOR')
if filex == None:
        sys.exit()

xor_file = filex.name
password=tkSimpleDialog.askstring(xor_file,"Enter password:", show="*")
if password == None:
        sys.exit()
# now seed random number generator with the integer value of the chars in the password concatenated together
# e.g. password "ABC" will translate into "65"+"66"+"67"="656667"
psalt=""
for i in range(len(password)):
        px = ord(password[i])
        pc = str(px)
        psalt = psalt+pc
psalti=int(psalt)
random.seed(psalti) # random range now seeded with password
# now do it...
inputf = open(xor_file, "rb")
memstring = inputf.read()
inputf.close()
out_string = ""
for k in memstring:
        p = random.randrange(0,255,1)
        b = ord(k)
        t = b^p # xor byte with 'random' byte
        z = chr(t)
        out_string = out_string + z # build output string
# Done. Now write string to file on disk
output = open(xor_file, 'wb')
output.write(out_string)
output.close()
passw=tkSimpleDialog.askstring(xor_file,"OK, done!",initialvalue="Click OK")

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

[smallfries]

You've said two things that are the opposite of each other. You've claimed:

The entire communications circuit betweem sites is encrypted if the connected networks or systems are classified.

Which is entirely correct. But you've also claimed:

Again, its not done becauses bandwidth costs money and it isn't needed.

When you encrypt a circuit (as opposed to the traffic on it) then the circuit is in constant use, and uses constant bandwidth. You cannot encrypt a circuit at the link-level, and save bandwidth. It is an contradiction. So you were correct in one of your claims, but when you claimed the opposite as well, you were wrong.

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

[Anonymous Coward]

Only for a front door ... or brute force attack.

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

[fluffy99]

You've said two things that are the opposite of each other. You've claimed:

The entire communications circuit betweem sites is encrypted if the connected networks or systems are classified.

Which is entirely correct. But you've also claimed:

Again, its not done becauses bandwidth costs money and it isn't needed.

When you encrypt a circuit (as opposed to the traffic on it) then the circuit is in constant use, and uses constant bandwidth. You cannot encrypt a circuit at the link-level, and save bandwidth. It is an contradiction. So you were correct in one of your claims, but when you claimed the opposite as well, you were wrong.

I think you're misunderstanding how military network encryption works. I probably added to that confusion by not making the distinction between the circuit and the site-site link.

Think of the miltary encryptors as vpn boxes doing tunneling with encryption between classified sites. If there is a dedicated telco circuit, the actual circuit between the encryptors isn't encrypted, but rather all of the data passed over it is encrypted. Yes, technically a circuit is a fixed bandwidth and gets padded out with "zeros". The padding is obvious to anyone sniffing the telco circuit itself. The encryptors don't add any bogus traffic between themselves.

Also, it's pretty common for the encrypted traffic to travel between sites over an existing unclassified network connection. In that case, encrypted and non-encrypted traffic exists on that link.

You made the contention that additional traffic is added to prevent traffic analysis. That simply is not true in any of the typical military encryption setups. Not for networks, radio coms, or any other communication methods I work with.

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

[smallfries]

You made the contention that additional traffic is added to prevent traffic analysis. That simply is not true in any of the typical military encryption setups. Not for networks, radio coms, or any other communication methods I work with.

I can believe this, and my initial claim that you didn't know what you were talking about was clearly wrong. But, just because the systems that you have worked with are not designed to resist traffic analysis does not mean that no there are no such systems.

A couple of examples (the idea of link encryption to defeat traffic analysis is textbook stuff, but sadly none of the authors that I checked actually included references). The application that sprang to mind originally is Xor-Trees designed to resist traffic analysis and provide data secrecy for command and control links. A weaker example that tries to prevent analysis without full utilisation of the link is the randomised approach in FreeNet.

Another example that I can't find a citation for is some VPN products max out the link constantly to avoid traffic analysis. My own background used to be the telecoms world, so I'm using a slightly difference meaning of link level to you. In that world you do actually encrypt the circuit, either padding with random values, or relying on a cipher that doesn't reveal the presence of an empty stream (e.g AES in CBC).

I'm safe

[Anonymous Coward]

Moved to 57-bit DES years ago.

WTF????

[Anonymous Coward]

Totally off-topic, but WTF is with the Facebook and Twitter links on all of the stories? Who fucking cares?

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?

[Anonymous Coward]

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"?

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

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?")

Re:What?

[Anonymous Coward]

It's hardly 800x faster!

The project uses a cluster of 100+ FPGAs. It's not really a fair comparison to put up a single PC against a cluster of custom logic on FPGAs. The result that one FPGA can process 1.6 billion blocks/sec versus a CPU/GPU which can only perform 200+ million is the interesting part.

I would like to see the power/performance tradeoff of GPUs vs. FPGAs.

Re:What?

[DigitAl56K]

"What?" indeed.

This is exactly the same technique as the EFF DES cracker used in 1998, except using FGPAs instead of custom chips.

http://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/HTML/19980716_eff_des_faq.html#howsitwork

Re:What?

[Anonymous Coward]

Yeah, he obviously talked about his entire hardware. Not a single component of his hardware.

Re:What?

[jasonq]

Coffee, nostrils, keyboard.

Re:What?

[Anonymous Coward]

Next, on Hannity. "Flying Pigs; America's New Socialist Threat"

Re:searching for ASCII

[starbugs]

I sometimes throw in a random 2, then when I need to decrypt everything, they're easy to take out.

Too bad...

[mister_playboy]

FIrst post!

Your encryption was cracked, and you didn't post first.

Just not your day. :)

Re:Too bad...

[NatasRevol]

Don't blame him. He's not using FPGAs so his encryption takes a long time!

Re:Too bad...

[Runaway1956]

Don't be cruel. This IS the best day he's ever had. And, it's all downhill from here! Don't tell him that though - we would hate to be responsible for another failure suicide.

Re:Too bad...

[travisco_nabisco]

With the way his day is going it wouldn't be a failure suicide it would be a failed failure suicide.

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:Interesting but not shocking

[lambent]

harumph indeed. kids these days.

i covertly appropriated several computer labs at the time to contribute to the effort. man, those were the days.

Re:Interesting but not shocking

[Shrike82]

I wasn't personally involved in the decryption effort, so I naturally assumed it was probably some kind of scam carried out by a consortium of international security agencies, trying to convince us that all the encrypted pornography on our hard drives wasn't actually safe from outside scrutiny. Of course I could be wrong, so I covered myself both ways by inserting the qualifier "apparently". I'm a child of the 80's since you ask, but sadly at the time of the distributed.net decryption event I was limited to either an archaic 486 at home, or the "computers" at my college. I use speech marks as when an operating system is so bogged down in security software and access controls that word processing causes a lockdown (complete with flashing lights, armed guards and your name being entered onto a register for cyber-terrorists), the device it's running on pretty much ceases to be useful as a computational device.

Re:Interesting but not shocking

[steelfood]

Yeah, yeah, we'll get off your lawn.

Re:Interesting but not shocking

[arcade]

And *stay* off it!

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: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:Practical value

[Anonymous Coward]

They are both phallic symbols of patriarchal society?

Nobody has ever made a gun which has a big inwards hole where projectiles are received, QED.

Re:Practical value

[QuoteMstr]

Straight out of Newton's Rape Manual.

Re:Practical value

[afidel]

No, 3DES does not triple the keyspace, it doubles it to 112 bits assuming all three keys are independent. If you use the two key method where k3=k1 then you only get ~80bit strength. 3DES is also obsoleted by the fact that a single round of 128bit AES can be completed faster then three rounds of DES, in fact 256bit AES is generally at least as fast as 3DES.

Re:Practical value

[aunt edna]

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.

Hey, try a dose of maturity -- you might get to like it.
And then, you just might learn to behave better when replying to a post.
Or not.

Re:Practical value

[Sir_Lewk]

In the real world, not everyone is all touchy feely with each other all the time. You are the one that needs to do some maturing if you can't even handle a (rather mellow) harshly worded response directed at someone else.

Hell, it was even a rather insightful post, without any profanity to boot!

Re:Practical value

[I cant believe its n]

RACF passtickets on IBM mainframes are based on DES. Only valid for a few minutes though.

Re:Practical value

[Shrike82]

If the three keys are independent, then can you explain how the keyspace only doubles? You need all three keys to successfully decrypt a 64-bit data block and there is no relation between any of the three keys, so sucessfully guessing one key doesn't give you any information about the other two, nor does it net you the original data. If I'm wrong by all means correct me (again) but please explain in more detail your assertion.

Re:Practical value

[Lisandro]

DES has little to do with Blowfish, in particular, besides being both block cyphers.

Re:Practical value

[billstewart]

It only doubles because there are attacks that can take advantage of the structure - you're basically splitting it into a 112-bit part and a 56-bit part plus storage, and while they're not currently practical, if you had the horsepower necessary to crack 112 bits you'd have enough to do the 2^56 storage as well.

Re:Practical value

[afidel]

Explanation, and if you want to do a deep dive here's a good book on the subject by Adi Shamir of RSA fame.

Re:Practical value

[Anonymous Coward]

Really? What polynomial does DES use?

Re:Practical value

[aunt edna]

In the real world, not everyone is all touchy feely with each other all the time. You are the one that needs to do some maturing if you can't even handle a (rather mellow) harshly worded response directed at someone else.

Hell, it was even a rather insightful post, without any profanity to boot!

Oh well, here you go:
The real world -- substitute 'my' for 'the real', perhaps?
Not everyone -- usual overstatement lacking reason.
All touchy feely -- see above.
All the time -- ditto.
Can't handle -- missing the point, there (you, that is.)
Directed at someone else -- think about that, do.

Hope that helps.

Re:Practical value

[Sir_Lewk]

Hope that helps? That doesn't even parse in my brain as english!

Go take your meds.

Re:Practical value

[aunt edna]

Thanks - I understand now: confused by your over-estimating your own limited abilities ....

Re:Practical value

[Sir_Lewk]

I was commenting on your inability to actually form complete and coherent sentences in english. What your response does to address my assertion that you need to grow the hell up if you get offended by a strongly worded post on the internet, I have no fucking idea.

Re:searching for ASCII

[Anonymous Coward]

I would encode both 1 and 0 to zeros.
Try to decrypt that!

Re:searching for ASCII

[Arancaytar]

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

Anyone else...

[Pojut]

...reminded of the little box hidden in an answering machine in that movie Sneakers? lulz

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:Isn't it clear?

[TubeSteak]

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.

I would auction my left kidney for more stories about Duke Nukem Forever.

Perhaps we could set it up as a /. poll:
Would you pay
()1-10
()11-100
()101-1,000
()1001-10,000
()10,001-1,000,000
()I already bought CowboyNeal's

Re:Isn't it clear?

[alexo]

I would auction my left kidney for more stories about Duke Nukem Forever.

OK, here's a bunch of titles:
1. Is DNF dead? (TFA says: yes)
2. Is DNF really dead? (TFA says: yes)
3. Is DNF really really dead? (TFA says: yes)
4. Will DNF be resurrected? (TFA says: no)
5. The status of DNF (TFA says: dead) ...

Re:Isn't it clear?

[treeves]

wait, so you have to be both insane AND under 16 to read Idle? Wow. Exclusive membership, that club.

Re:Isn't it clear?

[harmonise]

It's also why Slashdot lacks a secure login and access via IPv6. Slashdot has lost its nerd cred.

MOD PARENT UP

[Anonymous Coward]

The truth needs to be spread!

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.

double the key

[StripedCow]

Solution: just double the number of bits in the key, and we're comfortably safe again...

Re:double the key

[godrik]

well, It does not work that easily for DES. Since all the cleverness of the algorithm lies in how the bit of the key are used in the feistel cipher.

However, the Triple-DES algorithm uses 3 DES calss to generate a cipher of 112 bit (equivalent security). TDES (k1,k2,k3, msg) is DES_encrypt(k1,DES_decrypt(k2,(DES_encrypt(k3,msg))).

Defective by design

[Anonymous Coward]

DES was obsolete from the day it was invented. Whose idea was it to use 56 bits instead of 64? Our friends at NSA, who pushed for 48 bits and settled for 56. It seems that 56 bits was within THEIR capabilities back in the mid-70's but it wasn't so easy that anyone else was expected to do it.

My guess is that NSA has been able to rip through DES like a hot knife through butter, and they have been able to do it since the DES spec was published.

Re:Defective by design

[Truekaiser]

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.

Re:Defective by design

[ShadowRangerRIT]

Stop mixing up the CIA with the NSA.

Re:Defective by design

[Anonymous Coward]

It's hard as they share the same credit union.

Re:Defective by design

[keckbug]

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.

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

Why the facebook link?

[Anonymous Coward]

Or does CmdrDildo and crew really think that people should do like some of the submitters do; link to a blog that links to a science article? Fucking bullshit is what it is.

Re:Why the facebook link?

[delinear]

I have to admit I didn't even notice the facebook/twitter links at first, and even after reading the first few comments I didn't notice them and had to scroll up and search the page for 30 seconds to see the two tiny icons. What's slightly more intrusive are the seemingly endless "Why the facebook/twitter link" comments (which, annoyingly, can't be turned off with a little bit of custom css).

Re:Why the facebook link?

[Anonymous Coward]

oh my. it upsets you that people have their say to the point that you're willing to annoy others by doing the same thing? get a fucking life you cunt.

Impressive

[palmerj3]

Impressive, but how long would it take to crack Chuck Norris? Never, that's how long.

What?

[Anonymous Coward]

You're telling me that using FPGAs is a breakthrough? First time they broke DES as I recall they were using the exact same technology. The only "breakthrough" here is that he used *more* FPGAs than anyone else to break DES. Wooopidoo...

Nothing new

[Anonymous Coward]

Nothing new there.

DES has been attacked in practice by brute force for some time. EFF built the Deep Crack maching using custom ASIC chips in 1998, and in 2006 COPACABANA was built out of cheap FPGA for the same purpose.

Re:Should be building standardised FPGAs into syst

[SmurfButcher Bob]

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

Re:Should be building standardised FPGAs into syst

[Anonymous Coward]

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.

Re:searching for ASCII

[Anonymous Coward]

Yeah, so how again do you encode your messages to have an entropy close enough to random noise? Encypting *twice*?

Worthless

[dawilcox]

DES was already shown to be insecure. That's why they hacked DES to become Triple-DES. Let's see you break RSA like that. I'd be interested.

Re:Worthless

[Sir_Lewk]

That's not how you break RSA at all. You break RSA with integer factorization, generally with a general number field sieve. It is thought that factoring 1024 bit RSA keys will become practical with a few dozen thousand dollars of equipment in a few years.

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:What a load of crap!

[owlstead]

With DES CBC encryption you only have to know what is in any of the encoded blocks. If they use a standard padding mechanism you can use the first to last block as IV, the key is brute force and the last block has to end with XX XX 80 00 00 00 00 00 after decryption or something similar.

Encryption algorithms are supposed to protect against known plain text attacks and for good reason. It's not a "crypto breakthrough" because it is just a more effective way to brute force DES. Of course this *is* useful for knowing the current state of DES attacks and for certain persons interested in breaking that old DES encrypted file.

So it is interesting news, but not a breakthrough.

Re:What a load of crap!

[Arthur Grumbine]

...that has, unfortunately, been marred by some overly breathless reporting.

Well, it seems to have gotten someone all hot and bothered.

Re:What a load of crap!

[Rich0]

Well, they can look for patterns that suggest that the message contains a certain type of content (for example, frequency analysis would easily identify text of almost any language), although if you have to do that on every key that obviously greatly slows the process, and you can't just run the whole thing on a single block.

Usually you know something about the person sending a message and possible topics under discussion, so that can give you words to grep for, which is probably a lot cheaper than frequency analysis (although you might need to decrypt more than one block).

You can also mount a chosen plaintext attack, although that only works if you know where in a message that will end up, or you check entire messages (which obviously means more work). Think that a competitor is evesdropping on your board meetings? Then you carelessly handle lots of documents with some super-critical project with a unique name that would be easy to spot in a grep, and then see if it turns up in your competitor's encrypted communications.

Re:searching for ASCII

[Anonymous Coward]

As far as I understand, it is searching for ASCII password candidates, not ASCII data.

Breakthrough? meh.

[gmarsh]

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)

Re:searching for ASCII

[Sulphur]

I can't understand a word of it either.

Re:searching for ASCII

[Anonymous Coward]

Question is, what do you have to hide? I can only assume you are a criminal.

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

[ZeroExistenZ]

You can compress that effectively to one bit like that. Imagine how fast you would send over a bluray movie...

algorithm?

[Bobtree]

Brute force search of the entire problem space is not an ALGORITHM breakthrough. This is a measure of hardware and how "embarrassingly parallel" the problem is.

Re:Should be building standardised FPGAs into syst

[Zerth]

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.

Old news....

[ZonkerWilliam]

Who uses DES? In the VPN's I setup and manage its at minimum AES-192.

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.

Correction on 3DES

[willijar]

3DEs uses 2 keys but 3 cycles - one key is used twice

Re:Correction on 3DES

[Anonymous Coward]

It should not. It's possible to use the same key twice, but at that point you go down to a key strength of 112bit. 3DES usually uses 3 keys for 168bit.

Re:Correction on 3DES

[BitZtream]

Not entirely correct. 3DES has 3 keying options.

You can use 2 keys, you can also use 1 key for all 3 operations, but the preferred mode, and they only one I've ever seen implemented uses 3 unique keys. Using 1 key is effectively the same as DES, so its pointless. Using 2 keys may be seen in some crappy implementations of it, but as I said, I've never seen an implementation that did that, and you'd certainly not be interoperable with any other software that expects the 3 key system.

http://en.wikipedia.org/wiki/Triple_DES

Re:Should be building standardised FPGAs into syst

[Hurricane78]

Isn’t that, what Transmeta was all about?

I always wondered why it failed. It certainly wasn’t because of the idea or because of me.

12-year old technology, today!

[Anonymous Coward]

The EFF DES cracker from 1998 could crack DES in 2 and a half days. Now, 12 years later, they've just equalled that performance?

OK, the people in TFA used 176 FPGAs rather than 1856 ASICs, which is presumably slightly cheaper.

So perhaps a better comparison would be the FPGA-based COPACOBANA codebreaker, which used FPGAs and took a week to break DES back in 2006.

This is not a "breakthrough", it isn't even novel.

(By the way, that EFF DES cracker page was the first result on a web search for "des cracker", it's not exactly hard to find).

Re:12-year old technology, today!

[Eric Smith]

OK, the people in TFA used 176 FPGAs rather than 1856 ASICs, which is presumably slightly cheaper.

FPGAs of any respectable size are going to be more expensive than the ASICs. The point of using FPGAs isn't cost, but rather that if next week you want to brute-force a different cipher, or do protein folding, or some other massively parallel task, the FPGAs can do it, while the ASICs can't.

Re:Should be building standardised FPGAs into syst

[Vintermann]

Why would it be because of you? I wasn't going to blame Transmeta's failure on you, but since you said that, I may have to suspect you anyway.

Imagine

[Anonymous Coward]

...a Beowulf cluster of those!

That why I always

[Anonymous Coward]

...convert my text to EBCDIC before I encrypt!

Re:Should be building standardised FPGAs into syst

[0100010001010011]

I would love a generic FPGA with some basic support. I would kill for a DNG -> JPG/TIFF batch processor after 'developing' all my Digital negatives.

Same with encoding x264 video.

A that could just do those two things would easily be worth some money.

Shhhhhhh

[scorp1us]

Zip it. Ladies and gentlemen of the jury, ex-zip-it A. Look! I'm "Zippy" Longstocking! When a problem comes along, you must zip it! Zip it good! Zip! Would you like to have a suckle of my "zipple"?

Re:Shhhhhhh

[Pseudonym]

I don't know who modded you a troll, but perhaps for extra clue, you might want to say "I'm GZippy Longstocking!" next time.

But you're absolutely right: this attack only works because the plaintext is highly redundant. Remove the redundancy and the attack won't work.

Still, usually leaves a header lying around, and even if there isn't, most real encryption protocols provide some mechanism to be able to tell if you're decrypting real data or not without processing very much of the stream. As soon as you have that, you have an attack vector.

So while PGP (with single DES) is not vulnerable to this precise attack, it's vulnerable to an attack that's very close to it. If it takes six days instead of three, big deal.

Re:searching for ASCII

[rdavidson3]

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

But, they'll figure that one out eventually. How about leaving all the 0's as 0's and switching the 1's to 0's. That should do the trick ;)

Re:searching for ASCII

[MartinSchou]

I prefer ROT29, but then again Danish has three additional vowels: Æ, Ø and Å.

no problems here

[OrangeTide]

I don't use numbers in my passwords.

Re:searching for ASCII

[Jeffrey_Walsh VA]

Not exactly lossless compression.

Re:Should be building standardised FPGAs into syst

[Anonymous Coward]

I know that Synopsys has their Confirma system for FPGA prototyping of larger (ASIC) designs.

This is for verification in your chip design flow.

What else is out there?

3DES still only 112 bits even with 3 keys

[billstewart]

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.

Re:3DES still only 112 bits even with 3 keys

[fatphil]

Cracking cost is not proportional to time. Cracking cost is proportional to the product of the amount of equipment used times the time it's being used. In order to reduce the time cost by 2^56, you need to multiply the equipment cost by 2^56 - that's what MITM does. The total real cost has remained the same - 2^168. The Biham approach, as applied by Lucks to 3DES, while reducing the time to 2^90, increase the space to 2^88, for a total cost of 2^178 - a net loss. 2 keys are clearly weaker than 3.

FPGAs vs. ASICs (and 176 chips vs. 1800)

[billstewart]

Actually, EFF's Deep Crack used ASICs, not FPGAs. They're custom-designed chips that only do one thing, while FPGAs let you download the design into the chips. ASICs are much denser (because they use only the transistors they need and a bit of interconnection, instead of using gate structures that let you download the gate designs into them), and are much cheaper (assuming you're making enough of them to amortize the setup costs.) A typical design cycle is to prototype your application in FPGAs, work the bugs out, and then burn it into ASICs for production. Also, Deep Crack used 1856 ASICs vs. 176 FPGAs here, so 10 times as many of them. (It would be nice if they'd announced whether they were doing anything new with the algorithms, though.)

One of the fun things about living in Silicon Valley is that the culture assumes a lot of technical knowledge. There used to be a billboard that just said "FPGA2ASIC" (on a license-plate background) with a phone number and web site, which assumed that enough people would not only understand what service they were selling, but would be looking for someone to do it for them.

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.

Re:Should be building standardised FPGAs into syst

[digitalunity]

Linus?

Re:Should be building standardised FPGAs into syst

[Zerth]

I'm not terribly familiar with full prototyping suites, I had just looked into runtime changeable FPGAs, especially partially reconfigurable ones like the Atmel AT40K that let you change portions of the FPGA without losing state.

I think Altera either has or is partnered with somebody that has verification/analysis tools for their FPGAs.

Re:searching for ASCII

[Ant P.]

You're all wrong! The only way to really be sure is XOR the data with itself, they'll never be able to decrypt that

Be sure to drink your Ovaltine.

[Anonymous Coward]

Ovaltine? A crummy commercial? Son of a bitch!

Re:Should be building standardised FPGAs into syst

[Impy the Impiuos Imp]

Still, FPGA >> GPU.

GPU = specialized, massively parallel computations

FPGA = programmable algorithms that are essentially executed as if they were custom hardware circuitry. There is no processor, per se.

I often wondered if anyone had done a BOINC for Seti@Home or any other project that ran on commercially-available FPGAs.

Re:searching for ASCII

[MaskedSlacker]

You've confused self-XOR with nuking from orbit I see. Understandable.

Re:searching for ASCII

[Bobb Sledd]

Ha ha.. you guys are dumb. Everyone knows ROT-26 is insecure. It leaves out the number characters! So I do a ROT-36 and include numbers too.

Re:searching for ASCII

[goose-incarnated]

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

I used to do rot-pi, but then everyone said I was irrational

Use with Care... ROT-26 for expert use only

[yareckon]

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.

Re:searching for ASCII

[JustOK]

yah, but if you don't encode numbers, think how long it would take to decode them.

Re:searching for ASCII

[JustOK]

I used rot-weiller, but people said it was too ruff.

Imagine using rot-i

Hmm

[RichiH]

So could I generally increase security by including a few NULs and other non-ASCII/UTF numbers? And keep binary save for ever?

I know the attack is against DES and most relevant protocols needs ASCII armoring for binary anyway, but this angle plopped into my head immediately.

Re:searching for ASCII

[badkarmadayaccount]

I need weed... Right now... Please...

Re:searching for ASCII

[sciengines]

As published in scientific papers in 2006 COPACOBANA, www.copacobana.org provides 2^35 keys per second. And RIVYERA it's successor broke DES in a day 2008. Both are commercial available products of the firm SciEngines gmbH, www.sciengines.com whith is a spin-off of the original university project. 2007 their personal key recovery tool showed that des key recovery is simple even for the standard user.

• COPACOBANA, 600 Watts, 3HU, 120 XILINX Spartan-3 1000 FPGAs published: How to Break DES for 8980 €
• RIVYERA, 900 Watts, 3HU, 128 XILINX Spartan-3 5000 FPGAs announced Juli 2008:to break DES in a day