One-Time Pads
by Ben Goren
Introduction
People have long sought ways to protect their communications from eavesdroppers. Caesar shifted the letters of the alphabet; modern computers rely on high-powered math and very large numbers. With one exception, all have theoretical weaknesses—though, in fairness, the theoretical weaknesses in some of today’s systems require assuming that every atom in the universe is a supercomputer working to break the message for hundreds of billions of years.
The single exception, a one-time pad, is proveably, absolutely, unbreakable. It’s quite simple in principle, although it is a bit cumbersome to implement in most situations. If you’re willing to sacrifice convenience for confidentiality, though, it truly can’t be beat.
Historical Implementation
One-time pads date back to the early twentieth century, and originally were used for teletype operators. If Alice and Bob wanted communicate securely, they would first get together for a Scrabble party. In addition to whatever fun they had with word games, they would put one (and only one) of every letter into a bag. Then—“shaken, not stirred”—they would mix up the letters in the bag. A single letter would be removed, written down on a pad of paper with a single carbon copy. They would put the letter back in, shake, and repeat until they had a booklet full of random letters. Each would take a copy of the pad, and they would burn the carbon paper.
Let’s assume that this is the result of their Scrabble party:
OQONDALHJHNIJKTLXGHWQSMAKQNMJSCR
EZAILEUMEKTJRAOHKHARFOUKASTUQOBR
SOLWAUKBIXEESKCVHXXFYSSNKLINXNIL
UNJYLWCKBBAHNRFRLHURSCHMDEDZWZMR
AKMDNKAHVWXOQIPDCSFUFZPKSYVFHFJK
RNEHATQGUMBPYTRHMXYBMYGAMMWBMNAE
NUSWXVOHLVVBOFQOWCDJPUUSKMXNLZ
The time has come for Alice to communicate secretly with Bob. Her first message is as follows:
Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.
Before she can send it, she must first strip out spaces and punctuation and convert lower-case characters to upper-case characters. Note that the concept of a one-time pad works equally well with binary data, as you’ll see below—this particular restriction is solely because Alice and Bob’s Scrabble set only has upper-case letters.
CONGRESSSHALLMAKENOLAWRESPECTING
ANESTABLISHMENTOFRELIGIONORPROHI
BITINGTHEFREEEXERCISETHEREOFORAB
RIDGINGTHEFREEDOMOFSPEECHOROFTHE
PRESSORTHERIGHTOFTHEPEOPLEPEACEA
BLYTOASSEMBLEANDTOPETITIONTHEGOV
ERNMENTFORAREDRESSOFGRIEVANCES
Now, it’s time to encrypt the message. Alice takes the first letter of her message and the first letter of her pad, and “adds” them together, wrapping around when she gets to the end of the alphabet. For example, if the first letter of her message was “D” and the first letter of the pad was “C,” the first letter of the encrypted message would be “G.” If the next letter of the message was “Y” and the next letter of the pad was “F,” the next letter of the encrypted message would be “D.” Here’s all three versions laid out:
OQONDALHJHNIJKTLXGHWQSMAKQNMJSCR
CONGRESSSHALLMAKENOLAWRESPECTING
RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY
EZAILEUMEKTJRAOHKHARFOUKASTUQOBR
ANESTABLISHMENTOFRELIGIONORPROHI
FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA
SOLWAUKBIXEESKCVHXXFYSSNKLINXNIL
BITINGTHEFREEEXERCISETHEREOFORAB
UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN
UNJYLWCKBBAHNRFRLHURSCHMDEDZWZMR
RIDGINGTHEFREEDOMOFSPEECHOROFTHE
MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW
AKMDNKAHVWXOQIPDCSFUFZPKSYVFHFJK
PRESSORTHERIGHTOFTHEPEOPLEPEACEA
QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL
RNEHATQGUMBPYTRHMXYBMYGAMMWBMNAE
BLYTOASSEMBLEANDTOPETITIONTHEGOV
TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA
NUSWXVOHLVVBOFQOWCDJPUUSKMXNLZRK
ERNMENTFORAREDRESSOFGRIEVANCES
SMGJCJINANWTTJITPVSPWMDXGNLQQS
Alice then sends the following to Bob:
RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY
FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA
UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN
MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW
QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL
TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA
SMGJCJINANWTTJITPVSPWMDXGNLQQS
Next comes an extremely important step: Alice destroys her pad (or, at least, the parts of it she used for this message).
Alice can now use means she likes to send the message—she could even place it as an advertisement in the paper preceeded by “ULTRA-SECRET MESSAGE TO BOB.” Nobody except for Bob can decrypt the message—or even, for that matter, know that it isn’t truly random gibberish.
When Bob recieves the message, he takes out his copy of the pad and applies the reverse process to read the message. When he’s finished decoding it, he, too, destroys his copy of the pad. Now, there is nobody who has any chance of decrypting the message. If both Alice and Bob destroyed the decrypted versions of the note, nobody will ever know what it said, even if they have the encrypted form and all the resources in the universe.
The reason this works is that every encrypted letter depends on the random process used to generate a matching letter in the pad. In fact, if “they” threaten Bob with thumbscrews, he could supply a fake pad that made the encrypted text decrypt to whatever he wanted:
QMMPSLMVTWGTAJANONRNZAOAJYNWNWNE
ASPECTREISHAUNTINGEUROPETHESPECT
RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY
NIQVCQJLSPSDJNWKWRANZYYHVSFVWZEF
REOFCOMMUNISMALLTHEPOWERSOFOLDEU
FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA
CIPAGAIEIPCEFKWRLGRXVXOTBELKLRGI
ROPEHAVEENTEREDINTOAHOLYALLIANCE
UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN
SHIHFSGVQBMRJDQQTTGSDRXZGSHKIATE
TOEXORCISETHISSPECTREPOPEANDTSAR
MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW
DXXCBHESATOJTJOJIXTTDZQXWLKGZFNZ
METTERNICHANDGUIZOTFRENCHRADICAL
QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL
AYPXIPRMYLNMRLCGNWFBNKSEJVHQXMKK
SANDGERMANPOLICESPIESWHEREISTHEP
TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA
RUMKTVTXKYDKZATFVNRVOLKJRTJLLE
ARTYINOPPOSITIONTHATHASNOTBEEN
SMGJCJINANWTTJITPVSPWMDXGNLQQS
See? The ciphertext is exactly the same, but the pad is completely different, and the revealed message is also completely different. Because there’s an equal chance of any given letter being plucked from the bag, there’s also an equal chance of any given letter being the resulting encrypted character. In fact, Albert and Barbara could have sent the exact same encrypted message in the same paper on the same day, but, because their pad is different, the unencrypted message is also different.
Modern Implementation
Modern computers store everyting in binary form—that is, as a whole heck of a lot of ones and zeroes. Any kind of data that can be stored on a computer can be represented as a string of ones and zeroes. Demonstrating how is beyond the scope of this document, but assume that a simplistic computer uses the following table to translate the alphabet into ones and zeroes:
| Character | Binary Equivalent |
|---|---|
A | 00000 |
B | 00001 |
C | 00010 |
D | 00011 |
E | 00100 |
F | 00101 |
G | 00110 |
H | 00111 |
I | 01000 |
J | 01001 |
K | 01010 |
L | 01011 |
M | 01100 |
N | 01101 |
O | 01110 |
P | 01111 |
Q | 10000 |
R | 10001 |
S | 10010 |
T | 10011 |
U | 10100 |
V | 10101 |
W | 10110 |
X | 10111 |
Y | 11000 |
Z | 11001 |
[space] | 11010 |
. | 11011 |
? | 11100 |
’ | 11101 |
( | 11110 |
) | 11111 |
Obviously, this leaves out all lower-case letters, all numbers, and a lot of punctuation…but it’s enough for an example to make sense. If you want to encode more information, start adding more ones and zeroes.
Here’s how we might encode the message. If you see spaces in your browser, they’re just there for readability; the computer only stores ones and zeroes.
ATTACKAT00000100111001100000000100101011010000001001111010DAWN?NO.00011000001011001101111001101001101011101101111010WAIT.1011000000010001001111011
Next, we get out a coin. Any coin will do, so long as it’s not weighted to favor one side over another. If the coin comes up heads, mark a one; otherwise, a zero. There are 125 bits (a bit is a single instance of a one or a zero) in this message, so we need to flip the coin 125 times:
01001001100001001011110010101110101011111111101011
01110111000100000000101001000010110110111111111111
0001010000111000101100100
In order to combine the two, you need to use a logical function known as XOR. It’s quite simple: if two bits are the same, the resulting bit is 0. If they’re different, the resuting bit is 1. Here’s a table to help:
| Original Bit | Pad Bit | Encrypted Bit |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Let’s now write out the original message, the pad, and the encrypted message:
00000100111001100000000100101011010000001001111010
01001001100001001011110010101110101011111111101011
01001101011000101011110110000101111011110110010001
00011000001011001101111001101001101011101101111010
01110111000100000000101001000010110110111111111111
01101111001111001101010000101011011101010010000101
1011000000010001001111011
0001010000111000101100100
1010010000101001100011111
To recover the original message when given the encrypted version and the pad, again XOR the two streams of bits. Try it above: pick any two of a trio of ones and zeros above, XOR the two, and you’ll get the third.
Again, since your coin has an equal chance of coming up either heads or tails, the resulting encrypted bit has an equal chance of being a one or a zero…and there’s no way to know which was intended without the pad.
Since this would all be done on a computer, the encrypted message would most likely be sent in binary format and the two computers would worry about everything. You could, however, translate either the pad or the encrypted version into letters using the appropriate table above…but that just adds an extra step to the process.
Unless….
From the standpoint of information theory, a one-time pad is perfectly secure (assuming the process used to create the pad is truly random). In reality, there are a few weaknesses worth noting.
First, it’s quite cumbersome. Before two parties can exchange messages securely, both need a copy of the same pad. Anybody who can intercept the pad can read all subsequent messages. If you’ve got a secure way of transmitting the pad…why not use it to transmit the message, as well? When one-time pads are used, the two parties typically meet in person, create the pad, and then use it for subsequent communications.
You need as much data in the pad as in the message. If you’re going to send a novel and encrypt it with a one-time pad, you first need to create a novel-sized pad. One-time pads are usually used for relatively short messages—though, with a CD-ROM filled with random bits, the term “relative” should be used advisedly.
If the pad and message aren’t perfectly synchronized—if they’re shifted by even one position—the result is gibberish; the technique is fragile. (Try it yourself on the above data.) One-time pads should only be used when it’s better to lose the message entirely than have it fall into the worng hands.
If the pad itself is ever reused, and an adversary has a copy of two messages encoded with the same pad, it’s trivial to recover the pad and therefore the contents of the message. Only people with good discipline and understanding of one-time pads should use them.
As with all forms of encryption, a one-time pad can only protect the encrypted form of the message. It doesn’t, for example, protect against somebody installing a camera to look over Alice’s shoulder as she composes her message to Bob. If Bob spills his guts…ah…just before he spills his guts, the encryption is likewise meaningless.
And, finally, should anybody figure out a practical method of time travel, all bets are off.