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 (... for example) 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 : 63 27 8C F1 08 25 2A B9 7E E4 52 03 0E 23 (... alternate pad) Plain : 41 54 54 41 43 4B 20 41 54 20 44 55 53 4B = "ATTACK AT DUSK" 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 (... alternate pad) Plain : 49 20 4C 4F 56 45 20 4D 59 20 4D 4F 4D 21 = "I LOVE MY MOM!" 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 lower than the number of possible messages. The probability of getting 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 the sender 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 the attacker 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 XOR operation, making them relatively 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, they 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 they 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.