Advantages of one time pad

Question

I always hear that one time pad'ing something is so great because you won't know if you've successfully decrypted the data. I understand the idea that you can XOR any bits just the same as any other bits and you won't inherently be "alerted" to the fact that you used the right bits, but is this not true of any other encryption algorithms/concepts?

For instance, if you try to brute force data that was symmetrically encrypted in SSL/TLS (which is NOT a one time pad), I imagine you won't know if your brute force attack actually found relevant results unless you check those results against something you were looking for (metadata, valid PDF, valid Word, etc.)

So, if what I said is true, then what is the advantage of a one time pad? Is it simply the length of the key used (the fact it has to be as long as the data)?

Answer 1

It is a matter of redundancy of information.

An attacker wants to decrypt some piece of data, because he is interested in that data, and thus has context information. For instance, assuming a HTTPS connection, the attacker knows that what is encrypted is an HTTP request and an HTTP response, both coming with syntactically correct HTTP headers. It is highly improbable that a sequence of random bits is syntactically correct. Conceptually speaking, the sequence of bits which encodes the HTTP request is redundant, meaning that some of the information could have been omitted since it can be reconstructed (e.g. the header is plain ASCII so every eighth bit is redundant, since it is always 0).

If the attacker tries to do a brute force on, say, a 56-bit DES key (we assume here that the SSL was protected with that algorithm, so that brute force is actually feasible; with a 128-bit AES key, this far exceeds existing technology, and the question becomes devoid of any meaning). There are 2⁵⁶ such keys. However, not all possible decryption keys will yield some cleartext which "makes sense" (i.e. "is a syntactically correct HTTP request"). In fact, probabilities are such that there (most probably) won't be any wrong key which still yields something which looks like a HTTP request. In other words, if the decryption result yields cleartext which has the right format, then the attacker knows that he found both the right key and the right cleartext message.

This is not so with one-time pad. With one-time pad, every syntactically correct cleartext is possible, with equal probabilities. The attacker cannot exclude any potential cleartext which "makes sense" because all cleartexts which make sense are possible. The information theoretic way of expressing it is that the ciphertext cannot give any extra information to the attacker beyond what he already know. To sum up, all the attacker learns is that possible cleartexts are cleartexts which make sense, and he already knew that.

Answer 2

A one time pad offers information theoretic security. This essentially means that the one time pad cannot be broken even if the adversary has unlimited computing power. This is because XOR-ing any data against a truly random key will guarantee that the output be random as well because you are simply flipping bits.

Answer 3

It is extremely important to understand that "One Time Pad" is an element of the actual cipher used, not any particular protocol. For example, SSL or TLS using RC4 is, effectively, implementing a digital One Time Pad, while SSL or TLS using DES or AES is not using one.

One Time Pad refers to the old-school cryptographic technique of printing code pads... actual paper things... that could be used to encrypt and decrypt messages. The pad was effectively the key to be used to encrypt a message.

The strength of a One Time Pad derives from the fact that your messages are generally short and the key is used one and only one time. This makes statistical attacks against the cipher text difficult. However, should you reuse the key, you instantly begin to compromise the overall security of the data, making a statistical cryptanalysis more viable.

There are other important features, however. Since a One Time Pad uses the key only one time, it also means that you get Perfect Forward Secrecy for free. PFS means that should an attacker "break" a key, either through a chosen plaintext, a known plaintext or other cryptanalysis, breaking that key gives you absolutely no information about any previous key or any future key, except, of course, that those keys are not the current key.

In practice, digital one time pads do not change the key after every single message. If they did, that would be fantastic, but it's simply not practical. To offset this deficiency (key reuse) implementations typically include two things. The first is a protocol or method to periodically replace the fixed portion of the key based on time or the amount of data sent. The second is to use some type of random "initialization vector" (think of it as a big salt) that is added to the key before encrypting each message. Rather than changing the entire key, a fixed (typically a relatively large portion of the key) remains fixed for some period of time while the IV (salt) is changed with every message. Since the salt is changing, it must be communicated to the communication partner and is typically sent either in the clear or effectively in the clear.

A wonderful example of a digital one time pad is RC-4. An example of a poor implementation (well known, of course) is WEP, which uses a 24 bit initialization vector. WPA, the first attempt to "fix" this, made the fixed portion of the key larger and added TKIP to periodically change to a random key (fixed portion) while still using RC-4 and IVs.

Answer 4

As Terry says, the main advantage is that it offers information-theoretical security. But on a couple of points you mentioned in the rest of your question:

The length is not an advantage in itself but the fact it means you can never prove what you derived from a guessed key is the actual decrypted data makes it infinitely secure - provided you do not fall victim to its greatest disadvantage: it MUST only be used once. I wrote a script to illustrate what happens when you use a OTP twice: https://github.com/deed02392/crib-dragger

You seem to think that there are no clues offered in cryptographic implementations that you've successfully decrypted something. This is incorrect.

For integrity purposes, there is usually some indication that you've successfully decrypted something. For example TrueCrypt uses a hash of the correctly decrypted data (within the encrypted data block). It is assumed the key and encryption algorithm is so strong that it's not important versus the advantages of integrity it yields.

Answer 5

The advantage of a one-time pad is that each byte(we'll assume 8-bit bytes), is not connected to any other byte of the key. Discovering any single byte of the key gives absolutely no information as to any other byte of the key.

I'm going to simplify a little and forget about things like possible mathematical or timing attacks, but let's compare a block cipher to One Time Pad(OTP).

Brute Force:

If we talk about a 16 byte encrypted payload, with a block cipher that has an 8-byte key, you have to brute-force all of the possibilities for the key and at each attempt check to see if the payload "makes sense". If it makes sense, you can assume you've found the key, or keep trying until you get something that makes sense again. You can then review all the decrypted payloads and know that one of them is the real one.

One-time Pad:

With an OTP, you can brute force each character, which is easy since there are only 256 tries with 8-bit characters. You'll eventually find a bunch of combinations that give you, for instance, a valid header that you'd expect for the encrypted payload. But any of those characters that you've discovered give you absolutely no information as to the rest of the payload. You can't gleam ANY information about the rest of the payload based on the first characters. You'd basically have to know what to expect of the payload in order to guess the key. And even then you could only guess a subset of the keys that could create that payload.