Rick

One-Time Pads

The one-time pad is the only encryption technique that has been mathematically proven to be uncrackable. While hard to use, it has often been the choice for highly sensitive traffic. Soviet spies used one-time pads in the 1940s and -50s. The Washington-Moscow “hot line” also uses one-time pads. However, the technique is hard to use correctly.

Photo courtesy of Cryptomuseum.com. 

To use a one-time pad, Alice and Bob must produce a huge number of random bits and share them secretly. When Alice has a message to send to Bob, she retrieves a number of random bits equal to the length of her message, and uses them to be the message’s key. She applies the exclusive or operation (xor) to the key and the message to produce the encrypted message.

The key must be exactly the same size as the message. The key must also consist of completely random bits that are kept secret from everyone except Alice and Bob.

When Bob receives the message, he retrieves the same bits from his copy of the random bit collection. He must retrieve the same random bits in exactly the same order that Alice used them. Then Bob uses the sequence of random bits to decrypt the message. He applies the xor operation to the message and the key to retrieve the plain text.

When properly used, it is mathematically impossible to crack a message encrypted by a one time pad. This was first described by Claude Shannon in the 1940s as part of the development of information theory. A one-time pad is impossible to crack because knowledge of the cipher text does not reduce uncertainty about the contents of the original, plain text message.

One time pads are not generally practical:

  • It’s hard to provide enough randomly-generated bits to both Bob and Alice to protect all anticipated messages.
  • It’s hard to keep that much data secret.
  • It’s hard to use the bits in the right order at both ends.
  • It’s hard to avoid reusing the bits by mistake.

Web browsers and servers use conventional stream ciphers like RC4 instead of one time pads because they are much easier to use and provide very strong, if not provably impenetrable, security.

When Soviet spies used one-time pads, they used a decimal number code instead of binary bits. In binary, the xor operation is essentially an “add without carry” in which we discard the overflow: in particular, 1+1=0. In a decimal code, add without carry just discards the overflow, as in 7+7 = 4, or 8+8=6. Decryption used the opposite “subtract without borrow” with the same set of digits used as the key.

The one-time pads were printed up in tiny books, and the spies would discard pages of numbers as they were used in messages. Marcus Ranum has a photo of such a book in his One-Time PAD FAQ. The walnut image above shows a one-time pad printed on a rolled-up booklet and hidden inside a walnut.

There is a lot of confusion about one-time pads (see the last section below). Some vendors use the term simply because one-time pads are provably secure, and they hope that the name by itself will convey impenetrability to their product. Such products are called snake oil in the crypto community. Even worse, some people on the Net will try to explain one-time pads and get it wrong. The hardest thing for many people is the notion of entropy or true randomness. No, you don’t get random numbers from Excel!

Related Ciphers

Here are some other cipher terms that often appear in conjunction with one-time pads:

  • Vigenère cipher – a code in which each letter in the plain text is replaced by a corresponding letter taken from one of several different alphabets. The different alphabets are usually constructed by shifting the plain text alphabet by different numbers of steps. The “key” identifies the sequence of alphabets used. Cipher discs are often used to implement Vigenère ciphers.
  • Vernam cipher – A Vigenère cipher in which the alphabet consists only of the binary values 0 and 1. Vernam’s original cipher used a repeating key (reusing the bit stream) but the cipher remained easy to break even with very long keys. He subsequently developed a version where the key did not repeat; this was the first implementation of a one-time pad.
  • Stream cipher – a Vernam cipher in which the key is generated by a pseudo-random number generator, to eliminate the repeating bit stream.

References

Ranum, M. (1995) One-Time-Pad (Vernam’s Cipher) Frequently Asked Questions. web site.

Shannon, C. (1949) Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (4): 656–715.

That’s not a one-time pad!

It’s amazing how subtle a one-time pad really is. On one level they’re deceptively simple: you simply match up the text of your message with a collection of “random bits” you share with the recipient. To decrypt, the recipient matches up a copy of those “random bits” to retrieve the message.

The trick is in the definition of “random bits.”

If all the characters come from a truly unpredictable source, then you have a one-time pad. And, if you really want to use a one-time pad, you must share as many random bits as you imagine you will ever need for messages. That’s a lot of random bits!

No shortcuts are allowed. If you try to ‘compress’ the random bits, or ‘reconstruct’ them using an algorithm, then it’s no longer a one-time pad. If you get them from any sort of structured source then, again, it’s not a one-time pad.

Another essential feature: the collection of random bits must not be shared with anyone except the intended senders and recipients of the messages. If other people can find the set of random bits – for example, if it’s based on a published text of some sort – then it’s not secret enough for a true one-time pad. Someone might get away with using it for a while, but it’s not a really secure approach.

Moreover, the bits must never be used for more than one message. One-time pads have been cracked many times in practice, usually because the random bits were used to encrypt more than one message.

Let me run over some inaccurate examples presented in various web sites as one-time pads. I’ll skip the “snake oil” encryption products that inaccurately claim unbreakability by calling themselves one-time pads. There are enough bogus examples without them.

The Key to Rebecca

Several web pages claim that the spy in Ken Follet’s novel The Key to Rebecca uses a one-time pad. The book describes how the spy used Daphne du Maurier’s classic novel Rebecca as a codebook to encrypt his messages. One particularly mistaken web site claims that the codebook was “du Maurier’s Rebecca of Sunnybrook Farm” (a book actually by author Kate Douglas Wiggin).

To be fair, that particular web site provides a fine description of the encryption process, even if the process is mislabeled. Each message uses the next page in the novel as its key. To encrypt a message, the spy would do an ‘add without carry’ of the characters in the message with corresponding characters taken from that page of the book. To decrypt, the recipient at the Wehrmacht would take the corresponding page of the novel and use the opposite ‘subtract without borrow’ operation to recover the plain text message.

However, this does not describe a one-time pad. This is simply a Vigenère cipher for which the key is taken from a book.

It is not a one-time pad for the simple reason that the key itself – the text of the novel Rebecca – is not random. The key consists of English prose text which itself has numerous patterns. The key will retain detectable patterns when combined with a plain text message in German.

If the book Rebecca consisted entirely of randomly generated characters, then it would come closer to being a one-time pad, though it would be far less entertaining as a mystery-romance novel.

Music CDs, MP3s, etc.

A few web sites claim that you can use a well-known music CD, MP3 recording, or other media file as the random bits for a one-time pad.

It should be obvious what the problem is: if the track contains random noise, then it might be more appropriate for a one-time pad. Music and other entertainment media files, by definition, contain patterns: chords, refrains, voiced words, images, etc. If random noise were entertaining, we wouldn’t have needed to actually broadcast radio signals in the previous century: people would have just listened to the static between stations.

Secrecy

The other problem with these examples are that they all use prepackaged data as the “random data.” Even if the prepackaged data were boring collections of random characters, or audio/visual static, the packages would be available to third parties. Published data is, by definition, not secret. No matter how random it might be, we eliminate the theoretical secrecy of the one-time pad by using data that is available to people besides Alice and Bob.