Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
How does an attacker know when they've cracked a traditional encryption key?
Wikipedia describes the one-time pad:
A 140 character one-time-pad-encoded string subjected to a brute-force attack would eventually reveal every 140 character string possible, including the correct answer – but of all the answers given, there would be no way of knowing which was the correct one.
So if you don't know when you've solved OTP, what is a giveaway when a traditional encryption key is solved?
Encrypted data is (pseudo) random data, i.e. it has maximal entropy (near zero patterns).
A 140 character string which is e.g. English can be compressed to 108-110 characters with an off-the-shelf no-special compression algorithm. A wrongly decrypted 140 character string can be compressed to 138-140 characters.
(BTW the claim 108-110 is not randomly chosen, I actually tried this with 140 characters from a previous answer's paragraph. Longer texts will obviously compress significantly smaller than that, even. Text will usually be something around 1/4 of its original size, and other "useful, non-random data" such as executables or even images will have anywhere from 30-70% of their original size, depending on what it is.)
This makes it rather easy to identify the case where you have found the correct encryption key (actually finding it is a different matter, I invite you to try and brute force 128-bit key, let alone a 256-bit key -- good luck).
Now with an OTP the problem is that unlike with a block or stream cipher where there is some albeit obscure correlation, the transfer function could be (and should be, as the key should be random) totally random, basically anything.
Which means no more and no less than you can get every answer out of an OTP, provided that you fill in the corresponding key, and there's no way of knowing whether that's correct. Every permutation is equally likely, and no bit in the message is related to any other bit (in the message or the key).
Within limits one could allege the same about other encryption systems (since 2128 choices is a huge number, almost "infinite" for most purposes), but in practice it's not the case. The number of permutations is comparatively small (compared to, e.g. 21120), and the bits within the message are not independent of each other, or independent of other bits in the key. Mind you, flipping any bit in an OTP will flip one bit in one character. But flipping one bit in a block cipher will have a 50% chance to flip each and every bit. They're not independent!
Which means that despite there being a huge number of outputs, there is only a very small number (often just one) that actually make sense, and you can identify them by their entropy.
When you encrypt something with a one-time pad, it can be decrypted to any value you want of the same length by changing the bits in the pad. For example, say you have a ciphertext of 5 bytes, hex encoded as e0306814d4. Since the cipher works by simply xoring the plaintext with a key, you can trivially create a key to decrypt the ciphertext to any desired plaintext:
e0306814d4 xor 88550478bb = 68656c6c6f ("hello" in ASCII)
e0306814d4 xor 885f0475f5 = 686f6c6121 ("hola!" in ASCII)
e0306814d4 xor a9101f7dba = 492077696e ("I win" in ASCII)
Since you can construct a key to produce every possible value of the same length, there is no way to know which is the correct value.
This is not the case with "normal" symmetric ciphers with a fixed key length. If an attacker knows something about the plaintext they'll be able to test if the key they guessed is likely to be correct.
Let's use your 140 character string as an example, and let's assume it's 140 ASCII characters. Since ASCII only uses 7 bits, the high bit is always 0, so you have an easy test to check if a key is likely to be correct. The more 1s in high bits the less likely it is to be ASCII (though it could still be UTF-8 or some other encoding).
Say we're using AES-128, that means there are 2128 possible keys, and thus 2128 different possible plaintexts our encrypted value could be decrypted to. Assuming a "perfect" cipher, each different key will flip each bit with 50% probability, and we have 140 bits that we know the value of. That means there's a 2128 / 2140 ≈ 0.02% chance of a key existing that decrypts the ciphertext to valid ASCII by random chance, so if you find a key that produces ASCII from the ciphertext there's a very high chance that it's the correct key. If the decrypted value also turns out to be valid English (or some other language), the chances of it not being the correct key are astronomically low.
In short, you have to know something about the plaintext. That something can be as much as knowing a specific value will be at the start of the plaintext (very common for most file formats) or as simple as knowing some sort of pattern will exist in the plaintext.
With OneTimePads the key needs to be as long as the message. In most uses of key based cryptography the message is longer then the key. As such you can use subsequent encrypted data reverify you guess.
For example if you have a plain text Rob the bank at 10am on the 12th of June with a One Time Pad there is no relation between any of the characters, as such if you guess a OneTimePad key and got the message of Rob the bank at 10am on the 19th of June you would have no indication that the date was incorrectly decrypted.
However if you have a 10MB tar file of 8 bit ascii english and a 128bit key, one bit wrong in the key is going to introduce a large number of errors which should be detectable. (Assuming have prior knowledge of what to expect in the plaintext).
