Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Parallel Algorithm Leads To Crypto Breakthrough

timothy posted more than 4 years ago | from the how-about-cluster-some-ipads dept.

Encryption 186

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

cancel ×

186 comments

searching for ASCII (-1, Offtopic)

roman_mir (125474) | more than 4 years ago | (#30948336)

Finally, in your face, everyone who is not using binary to encode your messages and sticks to silly data-structures like XML with ASCII in it.

Re:searching for ASCII (3, Funny)

2.7182 (819680) | more than 4 years ago | (#30948356)

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

Re:searching for ASCII (1)

starbugs (1670420) | more than 4 years ago | (#30948424)

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

Re:searching for ASCII (3, Funny)

rubycodez (864176) | more than 4 years ago | (#30948656)

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

Re:searching for ASCII (3, Funny)

JustOK (667959) | more than 4 years ago | (#30948882)

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

Re:searching for ASCII (3, Funny)

Arthur Grumbine (1086397) | more than 4 years ago | (#30949544)

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.

Re:searching for ASCII (0)

Anonymous Coward | more than 4 years ago | (#30948484)

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

Re:searching for ASCII (1)

ZeroExistenZ (721849) | more than 4 years ago | (#30949362)

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

Re:searching for ASCII (4, Funny)

Arancaytar (966377) | more than 4 years ago | (#30948488)

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

Re:searching for ASCII (1)

Sulphur (1548251) | more than 4 years ago | (#30949060)

I can't understand a word of it either.

Another win for Linux, the death of MS approaches (-1, Flamebait)

Anonymous Coward | more than 4 years ago | (#30948468)

Yet again Linux shows how superior open sourced software is in comparison to closed source, proprietary code like Windows. Were this algorithm to run under Windows, it would be slowed down so much by all the DRM checking the key-cracking code (assuming it would let that code run at all) that it probably wouldn't achieve a hundredth the throughput.

Not only that, but this being open source software, people can inspect the code and make it even faster.

Microsoft: your days are numbered.

MOD PARENT UP (0)

Anonymous Coward | more than 4 years ago | (#30948568)

The truth needs to be spread!

Re:searching for ASCII (0)

Anonymous Coward | more than 4 years ago | (#30948866)

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

Re:searching for ASCII (0)

Anonymous Coward | more than 4 years ago | (#30948938)

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

Re:searching for ASCII (0)

Anonymous Coward | more than 4 years ago | (#30949166)

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

Re:searching for ASCII (4, Insightful)

Sir_Lewk (967686) | more than 4 years ago | (#30949168)

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.

Svefg cbfg! (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#30948340)

Svefg cbfg!

Too bad... (2, Insightful)

mister_playboy (1474163) | more than 4 years ago | (#30948430)

FIrst post!

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

Just not your day. :)

Re:Too bad... (2, Funny)

NatasRevol (731260) | more than 4 years ago | (#30949956)

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

Should be building standardised FPGAs into systems (4, Interesting)

Colin Smith (2679) | more than 4 years ago | (#30948360)

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

 

Re:Should be building standardised FPGAs into syst (2, Interesting)

bcmm (768152) | more than 4 years ago | (#30948620)

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

Re:Should be building standardised FPGAs into syst (3, Informative)

SmurfButcher Bob (313810) | more than 4 years ago | (#30948820)

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

Re:Should be building standardised FPGAs into syst (2, Informative)

Zerth (26112) | more than 4 years ago | (#30949412)

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.

Re:Should be building standardised FPGAs into syst (2, Informative)

Anonymous Coward | more than 4 years ago | (#30948848)

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:Should be building standardised FPGAs into syst (1)

Hurricane78 (562437) | more than 4 years ago | (#30949606)

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.

Re:Should be building standardised FPGAs into syst (1)

Vintermann (400722) | more than 4 years ago | (#30949772)

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.

How do you know when it's decrypted? (5, Interesting)

petes_PoV (912422) | more than 4 years ago | (#30948378)

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? (1)

Endymion (12816) | more than 4 years ago | (#30948474)

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? (1)

petes_PoV (912422) | more than 4 years ago | (#30948840)

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? (1)

fluffy99 (870997) | more than 4 years ago | (#30949190)

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? (1)

QuoteMstr (55051) | more than 4 years ago | (#30949326)

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

They sure do [wikipedia.org] .

Re:How do you know when it's decrypted? (3, Insightful)

smallfries (601545) | more than 4 years ago | (#30949512)

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

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

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

bytesex (112972) | more than 4 years ago | (#30949930)

You must be airforce.

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

Hurricane78 (562437) | more than 4 years ago | (#30949682)

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? (1)

olsmeister (1488789) | more than 4 years ago | (#30948478)

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

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

Anonymous Coward | more than 4 years ago | (#30948596)

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? (2, Interesting)

txoof (553270) | more than 4 years ago | (#30948624)

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? (5, Informative)

Anonymous Coward | more than 4 years ago | (#30948772)

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.

Correction on 3DES (1)

willijar (99554) | more than 4 years ago | (#30949602)

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

Re:How do you know when it's decrypted? (4, Informative)

maxume (22995) | more than 4 years ago | (#30948860)

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? (1)

Fnord666 (889225) | more than 4 years ago | (#30949792)

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? (1)

bobdotorg (598873) | more than 4 years ago | (#30948982)

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? (1)

TheRaven64 (641858) | more than 4 years ago | (#30949140)

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? (1)

smallfries (601545) | more than 4 years ago | (#30949680)

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? (3, Informative)

Lord Byron II (671689) | more than 4 years ago | (#30948536)

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? (1)

txoof (553270) | more than 4 years ago | (#30948602)

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? (3, Insightful)

BrotherBeal (1100283) | more than 4 years ago | (#30948844)

... 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? (1)

Arancaytar (966377) | more than 4 years ago | (#30948616)

That's easy - the (uncompressed) clear text is going to be considerably less entropic [wikipedia.org] 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? (1, Insightful)

noidentity (188756) | more than 4 years ago | (#30948626)

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? (1)

Sir_Lewk (967686) | more than 4 years ago | (#30949292)

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? (1)

owlstead (636356) | more than 4 years ago | (#30949582)

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? (1)

SlideRuleGuy (987445) | more than 4 years ago | (#30949110)

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 [wikipedia.org]

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

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

TRS80NT (695421) | more than 4 years ago | (#30949266)

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? (1)

bytesex (112972) | more than 4 years ago | (#30950012)

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

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

Lord Ender (156273) | more than 4 years ago | (#30949302)

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? (0)

Anonymous Coward | more than 4 years ago | (#30949590)

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? (1)

Dracolytch (714699) | more than 4 years ago | (#30949746)

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

I'm safe (1, Funny)

Anonymous Coward | more than 4 years ago | (#30948382)

Moved to 57-bit DES years ago.

WTF???? (0, Offtopic)

Anonymous Coward | more than 4 years ago | (#30948408)

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

Isn't it clear? (4, Insightful)

QuoteMstr (55051) | more than 4 years ago | (#30948564)

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? (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#30948790)

"Which editor is better? Visual Studio or a Diseased Chimpanzee? Discuss."

On principal, I choose the Diseased Chimpanzee.

It's why we have ... ten times more stories about first person shooters than about functional programming languages.

But really, who cares about functional programming languages?

The Slashdot owners ... drool all over themselves in MBA-enhanced dollar sign dreams.

Ding ding ding. We have a winner.

What? (4, Insightful)

trifish (826353) | more than 4 years ago | (#30948418)

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? (0)

Anonymous Coward | more than 4 years ago | (#30948604)

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? (4, Funny)

QuoteMstr (55051) | more than 4 years ago | (#30948728)

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? (3, Funny)

Colin Smith (2679) | more than 4 years ago | (#30948710)

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.

 

Interesting but not shocking (3, Informative)

Shrike82 (1471633) | more than 4 years ago | (#30948440)

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 [wikipedia.org] over ten years ago. So he's a decade late and 66% less efficient!

Re:Interesting but not shocking (4, Informative)

arcade (16638) | more than 4 years ago | (#30948570)

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 (1)

lambent (234167) | more than 4 years ago | (#30948892)

harumph indeed. kids these days.

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

Defective by design (0)

Anonymous Coward | more than 4 years ago | (#30948646)

DES was obsolete from the day it was invented. Whose idea was it to use 56 bits instead of 64? [wikipedia.org] 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 (2, Insightful)

Truekaiser (724672) | more than 4 years ago | (#30948808)

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 (1)

ShadowRangerRIT (1301549) | more than 4 years ago | (#30949766)

Stop mixing up the CIA with the NSA.

Practical value (2, Interesting)

buruonbrails (1247370) | more than 4 years ago | (#30948450)

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 (2, Interesting)

Shrike82 (1471633) | more than 4 years ago | (#30948516)

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 (1)

afidel (530433) | more than 4 years ago | (#30949296)

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 (4, Insightful)

QuoteMstr (55051) | more than 4 years ago | (#30948614)

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 (1, Funny)

Anonymous Coward | more than 4 years ago | (#30948768)

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 (0, Troll)

QuoteMstr (55051) | more than 4 years ago | (#30948800)

Straight out of Newton's Rape Manual [gnxp.com] .

Re:Practical value (1)

aunt edna (924333) | more than 4 years ago | (#30949382)

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 (1)

Sir_Lewk (967686) | more than 4 years ago | (#30949952)

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 (1)

I cant believe its n (1103137) | more than 4 years ago | (#30949958)

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

Anyone else... (2, Funny)

Pojut (1027544) | more than 4 years ago | (#30948554)

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

double the key (0)

StripedCow (776465) | more than 4 years ago | (#30948632)

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

Re:double the key (1)

godrik (1287354) | more than 4 years ago | (#30949064)

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

Why the facebook link? (0)

Anonymous Coward | more than 4 years ago | (#30948668)

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? (1)

delinear (991444) | more than 4 years ago | (#30949600)

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

Impressive (1)

palmerj3 (900866) | more than 4 years ago | (#30948754)

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

What? (0)

Anonymous Coward | more than 4 years ago | (#30948762)

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 (0)

Anonymous Coward | more than 4 years ago | (#30948816)

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.

FrOst pist (-1, Redundant)

Anonymous Coward | more than 4 years ago | (#30948834)

posts on 5Usenet Are

Worthless (1)

dawilcox (1409483) | more than 4 years ago | (#30948870)

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 (1)

Sir_Lewk (967686) | more than 4 years ago | (#30949874)

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.

What a load of crap! (5, Informative)

ladadadada (454328) | more than 4 years ago | (#30948936)

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! (1)

owlstead (636356) | more than 4 years ago | (#30949710)

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! (1)

Arthur Grumbine (1086397) | more than 4 years ago | (#30949830)

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

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

Breakthrough? meh. (2, Informative)

gmarsh (839707) | more than 4 years ago | (#30948960)

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 [wikipedia.org] (using ASICs)
http://www.copacobana.org/ [copacobana.org] (using FPGAs)

algorithm? (1)

Bobtree (105901) | more than 4 years ago | (#30949372)

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.

Old news.... (1)

ZonkerWilliam (953437) | more than 4 years ago | (#30949526)

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

12-year old technology, today! (0)

Anonymous Coward | more than 4 years ago | (#30949768)

The EFF DES cracker [wikipedia.org] 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 [copacobana.org] , 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 [google.co.uk] ", it's not exactly hard to find).

Imagine (0)

Anonymous Coward | more than 4 years ago | (#30949780)

...a Beowulf cluster of those!

That why I always (0)

Anonymous Coward | more than 4 years ago | (#30950020)

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

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...