One-Time Pads

Example code: otp.c

The one-time pad (OTP) is an encryption algorithm that provides perfect secrecy, provided it is implemented properly. The pad, which is essentially a key that is the same length as the message, must be used only once (hence the name), kept secret, and, the hard part, generated using some truly random method. It works by XORing the pad and the message together, which makes the ciphertext indistinguishable from randomly generated data.

I want to be clear with the terms here. A one-time pad is not "random". Numbers aren't random. It's just not a property numbers can have. To be pedantic, what is random is the method by which the numbers are generated. Think "random number-generators", not "random-number generators".

A pseudo-random number generator (PRNG), like what your computer normally uses to randomly generate numbers for games, will not work here. Your computer is mindlessly deterministic and is not capable of being a true random number generator by itself. PRNGs exhibit patterns and eventually loop, spitting out the same numbers in the same order as it did when it started. When the pad is generated randomly, each bit in the pad will be statistically independent from every other bit. That is, one value of one bit has no affect on the value on other bits. Because of this, the ciphertext encrypted from a one-time pad is equally likely to decipher into any possible plaintext of the same length. This makes it immune to brute-force attacks. The bits in a PRNG are not statistically independent, making them vulnerable to attack. If you know the value of one bit of the key, you also know something about other bits in the key.

Generally, two parties wanting to communicate using a one-time pad will exchange a large pad, such as a CD filled with randomly generated data, in person before one of them travels somewhere, say another country, where data needs to be sent back securely. As bytes from the pad are used, they are destroyed and never used again. If the pad is 100kB in length, only up to 100kB in data can be transmitted securely. Like most forms of encryption, key management is one of the trickiest parts.

I have provided a simple little C program for encrypting a message using a one-time pad (download link at the top). It encrypts stdin using the one-time pad provided in the file indicated as the first argument. Ciphertext is sent to stdout. As an added bonus, when a second argument is provided, the used bits of the key are written to the file provided in the second filename. I will show you why I added this in a moment.

Suppose you have a file of random data,, as your one-time pad to use in encrypting the source code for this program,

otp < otp.c > otp.c.otp

If you shared the pad with your friend, whom you are trying to communicate with, she can decrypt it with a similar command,

otp < otp.c.otp > otp.c is only 207kB, so your message cannot be any longer than that. Additionally, once 207kB has been sent, you must exchange a new pad before more ciphertext can be transmitted. If you re-use your pad, you compromise the security of the new ciphertext as well as the old ciphertext.

The reason I provided the second option was this: you can use /dev/random directly without losing the pad (assuming you have a operating system that has a /dev/random, as all decent operating systems do).

# encrypt
otp /dev/random random.pad < otp.c > otp.c.otp

# decrypt
otp random.pad < otp.c.opt > otp.c

This is only academic, as the one-time pad is generally exchanged before the plaintext exists. Otherwise you can just exchange the plaintext when you would have normally exchanged the one-time pad! Also, /dev/random is slow. It generates numbers using environmental noise, which is only available at a trickle. If you want to encrypt a 1MB message, it could take days. With shorter messages you can usually speed things up by moving the mouse around or mashing the keyboard (this can be fun).

More on one-time pads next. In particular, I will present two tricks: one that works and one that does not work.

blog comments powered by Disqus

null program

Chris Wellons