You are here

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.

Post category: 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer