One-Time Pads
It's a meme that never seems to go away. Every time I write about this
cryptanalytic result, or the insecurity of that system, someone starts
crowing about one-time pads. "Every other cryptographic algorithm is
based on some assumption, and one-time pads are the only provably
secure system," they say. "They're the only safe algorithm," they
say. "They're the future," they say.
Well, they're wrong. And step, by step, I will explain why. (Parts of
this essay are taken from my book "Secrets and Lies.")
One-time pads are the simplest of all algorithms, and were invented
early on in the 20th century. The basic idea is that you have a pad of
paper with a bunch of randomly chosen key letters, the same size as the
message, on it. You add one key letter to each plaintext letter, and
never repeat the key letters. (That's the "one-time" part.) For
example, assume the message is IT and the pad letters are CM. You add
I (9) to C (3) to get L (12), or T (20) to M (13) to get G (7). (20 +
13 = 7 mod 26.) Then you burn the paper afterwards. The receiver
reverses the process using his pad of paper, and then burns the key
letters when he's done. This system works with any alphabet, including
a binary one.
One-time pads are the only provably secure cryptosystem. Because the
key is the same size as the plaintext, every possible plaintext is
equally likely. With different keys, the ciphertext DKHS could decrypt
to SELL, STOP, BLUE, or WFSH. With a normal algorithm, such as DES or
AES or even RSA, you can tell which key is correct because only one key
can produce a reasonable plaintext. (Formally, the message size needed
is called the "unicity distance." It's about 19 ASCII bytes for an
English message encrypted with a cipher with a 128-bit block. With a
one-time pad, the unicity distance approaches infinity and it becomes
impossible to recognize plaintext. This is the security
proof.) Because a one-time pad's key is the same size as the message,
it's impossible to tell when you have the correct decryption.
This is the only provably secure cryptosystem we know of.
It's also pretty much useless. Because the key has to be as long as
the message, it doesn't solve the security problem. One way to look at
encryption is that it takes very long secrets -- the message -- and
turns them into very short secrets: the key. With a one-time pad, you
haven't shrunk the secret any. It's just as hard to courier the pad to
the recipient as it is to courier the message itself. Modern
cryptography encrypts large things -- Internet connections, digital
audio and video, telephone conversations, etc. -- and dealing with
one-time pads for those applications is just impracticable.
If you think you know how to do key management, but you don't have much
confidence in your ability to design good ciphers, a one-time pad might
make sense. We're in precisely the opposite situation, however: we
have a hard time getting the key management right (partly because most
applications won't really support couriers with briefcases handcuffed
to their wrists, Marines with rifles guarding the room with the
encryption equipment in it, or thermite charges available for
physically destroying storage media before the bad guys get past the
Marines with rifles guarding the encryption equipment), but we're
pretty confident in our ability to build reasonably strong
algorithms. It's just not the weak point in our systems.
What a one-time pad system does is take a difficult message security
problem -- that's why you need encryption in the first place -- and
turn it into a just-as-difficult key distribution problem. It's a
"solution" that doesn't scale well, doesn't lend itself to mass-market
distribution, is singularly ill-suited to computer networks, and just
plain doesn't work.
The exceptions to this are generally in specialized situations where
simple key management is a solvable problem and the security
requirement is timeshifting. In these situations, the problem isn't
transporting the bits securely, but transporting the bits securely at
the time the message is generated. Securing the bits beforehand is
easy. And there are historical examples of one-time pads being used
successfully, in specialized circumstances. Russian spies used pencil
and paper one-time pads to communicate. (The NSA broke the system
because the Russians reused the same one-time pads. Oops.) An early
Teletype hotline between Washington and Moscow was encrypted using a
one-time pad system. One-time pads were also used successfully in WWII
by the English; spies in locations with radios but no other encoding
equipment were given pads printed on silk, and were able to encode
messages for transmission faster and more securely than by previous
methods involving memorized poetry.
Those examples used real one-time pads. Generally, products that claim
to use a one-time pad actually don't. My guess is that the engineers
quickly realize that they can't possibly implement a one-time pad, so
they use the output of a stream cipher and call that a one-time-pad
generator, or a virtual one-time pad, or almost a one-time pad, or some
other marketing-speak. It's not a one-time pad. The security proof
completely fails when you use a stream cipher.
On the other hand, if you ever find a product that actually uses a
one-time pad, it is almost certainly unusable and/or insecure.
So, let me summarize. One-time pads are useless for all but very
specialized applications, primarily historical and non-computer. And
almost any system that uses a one-time pad is insecure. It will claim
to use a one-time pad, but actually use a two-time pad (oops). Or it
will claims to use a one-time pad, but actually use a steam cipher. Or
it will use a one-time pad, but won't deal with message
re-synchronization and re-transmission attacks. Or it will ignore
message authentication, and be susceptible to bit-flipping attacks and
the like. Or it will fall prey to keystream reuse attacks. Etc.,
etc., etc.
One-time pads may be theoretically secure, but they are not secure in a
practical sense. They replace a cryptographic problem that we know a
lot about solving -- how to design secure algorithms -- with an
implementation problem we have very little hope of solving. They're
not the future. And you should look at anyone who says otherwise with
deep and profound suspicion.
|
