nullprogram.com/blog/2008/07/08/
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 XOR
ing 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, random.data
, as
your one-time pad to use in encrypting the source code for this
program,
otp random.data < otp.c > otp.c.otp
If you shared the pad random.data
with your friend, whom
you are trying to communicate with, she can decrypt it with a similar
command,
otp random.data < otp.c.otp > otp.c
random.data
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.