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?
Asked
Active
Viewed 3,294 times
11
-
1Is 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.) – JAB Jun 16 '10 at 18:25
-
@JAB: You get that automatically with a one time pad...it's just that OTPs are only helpful in certain constrained circumstances. – dmckee --- ex-moderator kitten Jun 16 '10 at 18:32
-
3**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. – dmckee --- ex-moderator kitten Jun 16 '10 at 18:36
3 Answers
8
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.
mcandre
- 22,868
- 20
- 88
- 147
-
...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. – FrustratedWithFormsDesigner Jun 16 '10 at 18:26
-
2... Or just encrypt multiple times. Incidently I'm finishing up Dave Brown's horrible book *Digital Fortress* – Adam Gent Jun 16 '10 at 18:29
-
2@Adam Gent: Don't bother. Almost any other activity is more worthwhile. – FrustratedWithFormsDesigner Jun 16 '10 at 18:31
-
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. – mcandre Jun 16 '10 at 18:41
-
2@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) – Rowland Shaw Jun 16 '10 at 18:45
-
7
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.
tster
- 17,883
- 5
- 53
- 72
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.
Mark Byers
- 811,555
- 193
- 1,581
- 1,452
-
+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. – FrustratedWithFormsDesigner Jun 16 '10 at 18:29
-
1@Frustrated: If you reuse them they lose *all* that wonderful mathematically guaranteed security... – dmckee --- ex-moderator kitten Jun 16 '10 at 18:34
-
3
-
"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? – user151841 Jun 16 '10 at 21:23
-
Perhaps the most famous known reuse of one-time pads: http://en.wikipedia.org/wiki/Venona#Breakthrough – President James K. Polk Jun 16 '10 at 22:43