Brute-force attacking One Time Pads feasible?

Question

I have a ciphertext encoded with One Time Pad. I do not know the key. How can I find the possible keys which when decoded, will result in a meaningful plain text?

Answer 1

The interesting property for the one time pad is that every plausible plaintext (given the length constraint, i.e. of same length as the ciphertext, maybe including some padding) has a corresponding key which produces a certain ciphertext.

As mentioned in the comment by CodesInChaos, this key can be retrieved by simply XORing both plaintext and ciphertext (if you are using the XOR variant of the one time pad ... for the addition variant you'll have to subtract).

Also, assuming a random key, every plaintext has the same probability, given the ciphertext, as it has without knowing the ciphertext (apart from the length).

This is known as perfect secrecy – you can get no information from the ciphertext about the plaintext which you didn't know before (apart from the length, but this can be hidden to a certain degree by padding, too).

Every cryptosystem with the perfect secrecy property must have a key as least as long as the messages, and each key must be used only once. This is why a one-time pad or other perfect encryption systems are not used often in practice.

Answer 2

You will need more than one ciphertext encrypted with the same key to do that. The one time pad is perfectly secret if the key is used only once (Which is why its called the one time pad).

The only way for you to find the actual key without more ciphertexts is to try all possible key combinations (i.e. brute force it), but this could take a long long time if your ciphertext is also long.

If you manage to get more than one ciphertext, you could XOR the two ciphertexts together and use crib dragging techniques to determine the contents of the plaintext. This is possible because the xor of two ciphertexts is the same as xoring the two plaintexts together:

Let:
c1 = p1 xor k
c2 = p2 xor k

Then:
c1 xor c2 = (p1 xor k) xor (p2 xor k)
c1 xor c2 = p1 xor k xor p2 xor k          (associative property of xor)
c1 xor c2 = p1 xor p2 xor k xor k          
c1 xor c2 = p1 xor p2 xor 0                (k xor k = 0)
c1 xor c2 = p1 xor p2                      (x xor 0 = x)

See the link i posted to see how this relationship can be used to uncover the plaintext.

Also, notice that the above property would not hold if i had two keys k1, k2 instead of just k.

Answer 3

To remain immunized from cryptanalysis One-Time-Pad must be encoded with a perfectly random key, which is not easy to do. Any pattern in the key will make its corresponding plausible plaintext into unlikely to be a randomized result. For example, if you encrypt your message P with a key K=0101010101010..., to get a ciphertext C, then, a cryptanalyst will conclude that P is your plaintext because the key K' that would encrypt P to an arbitrary C is likely to be highly randomized. This is a subtle point that undermines many users.