2

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?

  • So are you saying that an exhaustive key search is the same for OTP and traditional encryption methods? Identifying a key is solved only results in being able to identify plaintext data? Therefore, OTP being mathematically unbreakable is just because it has a larger key space? en.m.wikipedia.org/wiki/One-time_pad "In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked..." – Daveba123 Jan 16 at 13:23
  • What I mean by traditional "encryption key" is a non one-time-pad key. – Daveba123 Jan 16 at 13:52
2

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.

  • How interesting. Thank you for the detailed comment. – Daveba123 Jan 16 at 16:18
  • "random data, i.e. it has near zero entropy" - zero entropy means no randomness at all. – AndrolGenhald Jan 16 at 16:25
  • @AndrolGenhald: Wow, yes of course, sorry. Will correct. – Damon Jan 16 at 16:42
1

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.

  • That's very interesting. Thank you for the thorough answer. I now understand how traditional brute force decryption works and is able to determine if a key has been successfully cracked however I'm still stuck on why One Time Pad keys behave differently. Sure there's a potential for an absurdly long key, but why can't the same methodology be used--try a key and see if it makes usable data with OTP? – Daveba123 Jan 16 at 15:33
  • @Daveba123 does that help? – AndrolGenhald Jan 16 at 16:25
  • Well stated! I often use the converse argument that I can chose a Key for different messages that always produces "hello", so there is no way to distinguish one "hello" or "Shakespeare Play" from another. It's important to note that the reason it's called a "One Time Pad" is it rapidly becomes breakable if used more than once. – user10216038 Jan 16 at 17:43
  • @Daveba123 Essentially, all plain texts are equally probable in a OTP. Say I give you an OTP encrypted message and tell you to decrypt it. You can just try random keys until you get SOMETHING - Attack orders, a shopping list, a web form submission... They're all equally possible for a given length. Even if you know the general content - Attack orders, or something, they key bits of information would need to be known (attack target, time) for you to know if you'd decrypted properly. Earlington/0600 is as likely as Washington/2030, for example. – Adonalsium Jan 16 at 17:51
  • Don't get wrapped up in the idea of Plain Text. Although historically that was the use and most examples use it for ease of presentation, One Time Pad keys or Messages need not be plain text, and the pattern to identify the correct key/pad decryption need not be text either. Nor can entropy checks be depended upon if the message was compressed (as it should be) prior to encryption. – user10216038 Jan 16 at 18:00
0

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

  • That helps, but now I'm hung up with: "with a One Time Pad there is no relation between any of the characters". Perhaps I need a better understanding of how traditional key is broken and confirmed as such. Why does it make it easier to detect errors between OTP vs traditional key? – Daveba123 Jan 16 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.