How does a brute force attack actually determine it has succeeded?

Question

Possible Duplicate:
If someone breaks encryption, how do they know they're successful?

First off, this is not about cracking hashed passwords. I know that a brute-force or dictionary attack knows it cracked the password when it gets in.

However, if an attacker is trying to brute force a message, let's say a message transmitted by a government to its embassy in a foreign country, how does the cracker determine it has finally found the plain-text?

Edited:

As it turns out, my original question was badly written. I stated I wasn't asking about cracking passwords, and then I worded the question as if that were what I was asking, at least partly. For one thing, I talked about MD5, which is a HASHING algorithm, not an algorithm used to encrypt for the purpose of being decrypted. @lucas-kauffman gave a good answer to what I appeared to be asking, and thanks for that, as it was informative nevertheless.

Let me cast this differently to avoid confusion.

Given a cipher-text which was created using public key cryptography, and assuming that an attacker had the resources to use a brute force method to attack it, how would the cracking program decide whether or not it had finally achieved the plain-text? This isn't password-cracking, where the result would be obvious (entrance gained to the thing being attacked). Say that the message's ciphertext was something along the line of "JPOAISUDF89L;JKQWERTYQIOP34JUU890JEROTUQ3-49TJ" (<== just some random characters I typed don't try to "break" it). How would the cracking program decide that it had found the plaintext, given that it didn't know what it was looking for in the first place?

I know a human could look at a trial decryption (presuming such a thing exists) and know that "Attack at midnight" represents an actual message, while "aroOFPS toj34ioA diy66b234" does not (he hopes), but a human isn't going to be involved (given that the process is going to be making hundreds of attempts per second). So the cracker program presumably has to have some way to know that it has hit paydirt, or at least potential paydirt? This would get especially dicey if the sender had encrypted the message twice or three times (Triple DES anyone?).

It just strikes me as incredibly unlikely that a given message encrypted using a secure method could EVER be cracked in finite time, especially if the attacker didn't know what he or she was looking for exactly.

Answer 1

If you have some known plaintext, then you can try all keys and find the one that decrypts to the known plaintext. You might think this would never happen, but it's actually pretty common, due to protocol structure.

Alternatively, if you know the plaintext has some particular structure -- say, it is English text -- you can do trial decryptions and keep only the ones that produce something that looks like sensible English text. For instance, you might check that the high bit of every character is off, or use letter or bigram frequencies.

For these reasons, it would be a mistake to think that this is a serious barrier to an attacker. If the security of your system relies upon the assumption that the attacker won't be able to get known plaintext, or won't be able to recognize a valid decryption, then there's something wrong with the design of your system: it probably isn't as secure as you think it is.

For further details, here is a research paper on the subject:

David Wagner and Steven M. Bellovin. A programmable plaintext recognizer. 1994.

Here's a quote from the paper: "Most types of text can be efficiently attacked: typically [...] we can expect to find the decryption key 90% of the time by using three ciphertext blocks. Moreover, binary executables also fall to our ciphertext-only key search machine so long as the attacker knows for which architecture the binaries were compiled".

Answer 2

Most of the time what happens is that they start with a dictionary and hash every single word in there. They map that hash to that word, so if you have an MD5 hash of a word, you look up that hash in your database and you will receive the corresponding word(s). In the end your password is just a "text" itself.

Another option is that they start by going over every possible combination of letters and numbers, applying a hash to it and comparing that hash with the hash of the password. Modern graphics cards can guess up to 800 million hashes per second. Sometimes they store the hashes in a database, this is called a rainbow table.

The problem you will have is that it will still take a very long time for a long message, also you can get a hash collision. But you can just keep every hash collision, you can just check these afterwards, there won't be hundreds of hash collisions on one simple text.