You are here

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.

 

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.

There is a lot of confusion about one-time pads (see the article). 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.

Wordpress tag: 
Post category: 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer