Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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

share|improve this question
    
For SSL you can use the MAC to see if you found the correct key. –  CodesInChaos Apr 14 at 9:15

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
    
this was the type of answer that i was looking for (although all of the other answers were great too). thanks! –  tau Apr 14 at 18:17

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.

share|improve this answer
    
What @Terry said! The key point is that XORing something with a random string results in a random string. And you don't cryptanalyze random strings, unless they're not really random. –  executifs Apr 14 at 8:49

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.

share|improve this answer

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.

share|improve this answer
1  
Back in World War II, the Soviets accidentally duplicated a large quantity of key material for one time pads, making it pretty easy for US and British intelligence to break these messages. –  Michael Hampton Apr 14 at 20:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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