The One-Time Pad
================
+ Create a "pad" consisting of true random numbers that is as long as the message.
+ Do a simple bitwise XOR of the pad into the plaintext to obtain the ciphertext.
+ Receiver does a bitwise XOR of the pad into the ciphertext to recover the plaintext.
+ Very important that the pad is only used one time!
This method is unbreakable!
Consider the message "ATTACK AT DAWN". In hex this is
Plain : 41 54 54 41 43 4B 20 41 54 20 44 41 57 4E = "ATTACK AT DAWN"
Pad : 63 27 8C F1 08 25 2A B9 7E E4 52 17 0A 26
Cipher: 22 73 D8 B0 4B 6E 0A F8 2A C4 16 56 5D 68
Here each byte of the cipher text is obtained by doing a bitwise exclusive OR with a byte from
the one-time-pad (OTP). Note that the OTP contains purely random numbers in a sequence that is
as long as the message.
Example calculation:
41 0100, 0001
XOR 63 0110, 0011
------ ----------
22 0010, 0010
This is unbreakable because every possible pad is equally likely. Thus every possible decryption
is equally likely and there is no way to recognize the true decryption. For example, a machine
able to check every possible decryption will find the message above. But it will also find
Cipher: 22 73 D8 B0 4B 6E 0A F8 2A C4 16 56 5D 68
Pad : 6B 53 94 FF 1D 2B 2A B5 73 E4 5B 19 10 49
Plain : 49 20 4C 4F 56 45 20 4D 59 20 4D 4F 4D 21 = "I LOVE MY MOM!"
It will also find
Cipher: 22 73 D8 B0 4B 6E 0A F8 2A C4 16 56 5D 68
Pad : 63 27 8C F1 08 25 2A B9 7E E4 52 03 0E 23
Plain : 41 54 54 41 43 4B 20 41 54 20 44 55 53 4B = "ATTACK AT DUSK"
In fact, it will find every possible message that could exist of length 14 bytes! This isn't an
issue for brute force attacks against "typical" encryption algorithms because the small key size
means that the number of possible decryptions is vastly less than the number of possible
messages. The probability of obtaining two plausible decryptions from the same ciphertext is
vanishingly small.
The OTP is practical in some circumstances.
1. Prepare a large number of random numbers from a very high quality source of randomness
(ideally something based on quantum mechanics, such as radioactive decay). Burn these numbers
to a DVD and make two copies of the DVD.
2. Distribute the DVD over a secure channel (such as a face to face meeting) to the two
principles.
3. When one of the principles wishes to send an encrypted message to the other he or she XORs
some bytes from the DVD into the message (for example, email) and sends the result. Obviously
this is facilitated with the help of some suitable software.
4. The receiver XORs the same bytes from the DVD to recover the message. If synchronization is
lost it is an O(n) operation to recover it. While annoying, this is not a major problem.
This is unsuitable if
1. The amount of data to encrypt is very large (sharing racks of DVDs is not too practical).
2. The principles don't have a secure channel over which they can share the pad. Note that a OTP
is generally much larger than a normal key, thus a moderately high-bandwidth secure channel
is necessary... those tend to be hard to find.
3. You are worried about DVDs being stolen or find manipulating them to be awkward and
impractical.
4. You don't have a good source of randomness. Random sources tend to be very slow. It may be
feasible for you to produce truly random 128 bit keys but very difficult to produce 600 MiB
of truly random data.
Although "unbreakable", the OTP is subject to three modes of attack.
1. The attacker might be able to steal a copy of the pad. Once done it is trivial for him/her to
read all messages that use bytes from the pad.
2. If the principles use some bytes from the pad more than once, and if the attacker knows or
guesses this, the attacker can XOR two ciphertexts together to cancel the random pad yielding
two plaintexts XORed together. The statistics of the plaintexts come through the XORing
operation making them relaitvely easy to separate.
3. If the random numbers in the pad are imperfect, the attacker might be able to predict them
well enough to decrypt (or partially decrypt) messages. If the attacker can get a
plaintext/ciphertext pair he can XOR them together to view a fragment of the pad. The
attacker could then attack the random number generator to try and compute the other parts of
the pad from the parts he or she can see.
If the pad contained perfect random numbers, this would be impossible because no amount of
knowledge of a random sequence allows you to predict the rest of the sequence. This
"unpredictability property" of random sequences is their most defining characteristic.
To amplify the last point, consider the case where the plaintext contains a known header in
front of the data. The attacker can easily recover the pad used to encrypt the header by just
XORing the known header text into the ciphertext. However, this does not help AT ALL in figuring
out what bytes where used to encrypt the data portion. The unpredictability of random numbers
makes such computations impossible even in principle. Such is the power of randomness.