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

Question

How can I decrypt a message that was encrypted with a one-time pad? Would I need to get that pad, and then reverse the process? I'm confused here.

Answer 1

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.

Answer 2

While one-time-pad encryption is provably impossible to break, note that it is also extraordinarily rare.

Part of the definition of OTP is that the pad must contain truly random data, and truly random data can be hard to come by for computers. Instead, often the pad is composed of pseudo-random data, which is generally what you get when you ask a computer for a random number.

In this case, you no longer have unbreakable encryption. Instead, you have a message XORed with the output of a deterministic and often reversible algorithm, which can be attacked by reproducing the same pseudo-random string. This attack is particularly devastating if you know what algorithm is used and even more so if you know how the seed is generated. In such a case, the code can be cracked in a matter of seconds. But even without knowing the PRNG seed, often the pattern can be derived from the message itself.

Also, OTP encryption is particularly unwieldy because the key is as long as the encrypted message, and must somehow be transmitted to the recipient without being intercepted. Any software that claims to use OTP encryption that does not require you to exchange a key block as large as your message (or larger) is not using truly random data, and is therefore not using OTP encryption.

Also, one of the key features of OTP is that you cannot reuse old pads. If you reuse an old one even once, that can be enough to allow the code to be broken.

Answer 3

If you don't have the key ...

Brute force the ciphertext (permute it) and analyze the output for potential cleartext in the expected language.

Statistical analysis can assist in the detection of potential human-generated language in the output (maybe chi-squared?)

Answer 4

Assuming the encryption was competently done, the only way to decrypt is to get the pad.

Answer 5

One-time pads are extremely hard to break, in fact they are still used in some situations as if they are done correctly then they are essentially unbreakable. In a one-time pad system every character is changed by a stream of random data which is shared by both sides, without a copy of the pad you will not be able to break the code.

One of the few weaknesses in the system is the random data source. In WWII British one-time pads were being broken and they traced it to a worker whose job it was to pull random numbered balls out of a drum. The way it was supposed to work was that the worker would spin the drum, pull out a ball at random without looking at it, spin again, pick again, etc, etc. The worker started taking shortcuts by pulling out more than one ball after each spin and looking at the numbers, picking out favorites. It introduced patterns which enabled the opposition to break the pads, and lives were lost as a result.

The same is true today with pseudo-random number sources. Encryption protocols that should take millennia to break will really only last for years or decades without a true random data source.