How do brute force decryption attacks know when they've found the right solution? [closed]

Question

How do brute-force attacks on encrypted data know when they've found the right key to decrypt the data? Is there a way to know that data's been decrypted, other than having a human looking at it? What if it's not human-friendly data?

Floreated

Is it possible for someone to encrypt data in such a way so that it can be decrypted in multiple ways, producing multiple valid, but differing, results? (With only one of them being the correct one, perhaps.) – Granduncle

@JAB: You get that automatically with a one time pad...it's just that OTPs are only helpful in certain constrained circumstances. – Penstemon

Answer to this non-programming related question: by taking advantage of the known or expected properties of the plain text with respect to redundancy and format. Alice can make Eve's life harder by efficiently compressing the plain text before ciphering. – Penstemon

Answer 1

Cryptanalysts hope to have known ciphertext and plaintext. A key which decrypts that ciphertext to that plaintext is certainly the right key.

Without known plaintext, the data's format must be known. For example, plaintext HTML contains tags. A phone directory plaintext contains phone numbers. And so on.

Chile

...which is why you should write your ultra-super-secret messages in a secret private language before applying encryption. ;) ...of course that language could still be deciphered, but it would make the job of cracking the messages a lot harder. – Traprock

... Or just encrypt multiple times. Incidently I'm finishing up Dave Brown's horrible book Digital Fortress – Topsoil

@Adam Gent: Don't bother. Almost any other activity is more worthwhile. – Traprock

If you hate Digital Fortress, you'll also hate The Code Conspiracy. And the portion of Transformers where they decrypt and translate the Decepticon language. – Chile

@Adam Gent encrypting multiple times is the same as a single complicated encryption -- it's an old concept, that was applied during the second world war (Enigma and friends) – Keister

@Rowland Shaw I didn't say it was good idea :) – Topsoil

Answer 2

It depends on the encryption method. For instance, with RSA encryption, if you are looking for the private key you know you have found it when the public key is a multiple of the number in question.

Ritualist

Answer 3

It depends on the algorithm. With many algorithms there is only one correct decryption key. When you have the key you can easily verify it is the correct key in polynomial time.

With some algorithms though it is impossible to know when you have the right key. All plain texts (of the correct length) could give the output. An example of such a scheme is a one-time pad with XOR encryption. However if a one-time pad is reused ciphertexts can be XORed with each other to remove the key and then the two plaintext messages can be extracted by using techniques such as frequency analysis to determine what sort of data it is and what the most likely decryptions are.

Dialectician

+1 for one-time pads! ...though I thought they were called one-time pads because they couldn't be reused... or maybe they can but it's strongly recommended against. – Traprock

@Frustrated: If you reuse them they lose all that wonderful mathematically guaranteed security... – Penstemon

If you reuse them, they are two-time pads. – Cale

"When you have the key you can easily verify it is the correct key in polynomial time." How do they verify that it's the correct key? Is a brute force attack then simply verifying all possible keys? – Floreated

Perhaps the most famous known reuse of one-time pads: en.wikipedia.org/wiki/Venona#Breakthrough – Arv