How can I decode a message that was encrypted with a one-time pad?

One-Time Pad is unbreakable, assuming the pad is perfectly random, kept secret, used only once, and no plaintext is known. This is due to the properties of the exclusive-or (xor) operation.

Here's its truth table:

A xor B = X

A | B | X
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Number of 0s in column A = 2
Number of 1s in column A = 2
Number of 0s in column B = 2
Number of 1s in column B = 2
Number of 0s in column X = 2
Number of 1s in column X = 2

Note that it introduces no bit-skew - the number of 0s and 1s in the inputs are equal to the number of 0s and 1s in the output, i.e. two of each. Furthermore, if you know only one element from a row, you cannot predict the values of the other two, since they are equally probable.

For example, let's say we know that X is 0. There's an equal probability that A = 0 and B = 0, or A = 1 and B = 1. Now let's say we know that X is 1. There's an equal probability that A = 0 and B = 1, or A = 1 and B = 0. It's impossible to predict. So, if you only know one element, you cannot possibly determine any information about A or B.

The next interesting property is that it is reversible, i.e.

A xor A = 0
B xor B = 0

A xor 0 = A
B xor 0 = B

A xor B xor B  =  A xor 0  =  A
A xor B xor A  =  B xor 0  =  B

So, if we take any value and xor it with itself, the result is cancelled out and it always results in 0. This means that, if we xor a value A with a value B, then later xor that result with either A or B, we get B or A respectively. The operation is reversible.

This lends well to cryptography, because:

  • xor introduces no bitskew
  • xor has equally probable inputs for any given output
  • given any two of A, B, X we can compute the third

As such, the following is perfectly secure:

ciphertext = message xor key

but only if message is the same length as key, key is perfectly random, key is only used once, and only one element is known to an attacker. If they know the ciphertext, but not the key or message, it's useless to them. They cannot possibly break it. In order to decrypt the message, you must know the entire key and the ciphertext.

Keep in mind that the key must be completely random, i.e. every bit must have an equal probability of being 1 or 0, and be completely independent of all other bits in the key.

This actually turns out to be rather impractical, for a few reasons:

  • Generating perfectly random keys is hard. Software generators (and many hardware generators) often have minuscule biases and odd repeating properties. It's almost impossible to gain truly random data in anything but tiny amounts.
  • If the attacker knows the ciphertext and can correctly guess parts of the message (e.g. he knows it's a Windows executable, and therefore must start with MZ) he can get the corresponding key bits for the known range. These bits are useless for decrypting other parts of the message, but can reveal patterns in the key if it's poorly generated.
  • You must be able to distribute the key, and your key must be equally as long as your message. If you can keep your key 100% secret between those of you who are authorised to read the message, why not just keep your message 100% secret instead?

The weak link here is your random number generator. The security of the one time pad is entirely limited by the security of your generator. Since a perfect generator is almost impossible, a perfect one-time pad is almost impossible too.

The final problem is that the key can only be used once. If you use it for two different messages, and the attacker knows both ciphertexts, he can xor them together to get the xor of the two plaintexts. This leaks all sorts of information (e.g. which bits are equal) and completely breaks the cipher.

So, in conclusion, in a perfect one-time pad you need to know the ciphertext and key in order to decrypt it, but perfect one-time pads are almost impossible.

Tags:

Encryption

Recent Posts