010 | The One-Time Pad

“Perfect secrecy, paid for in advance”

The one-time pad is different.

Used correctly, it does not make a message merely difficult to recover. It provides perfect secrecy. An attacker can possess the ciphertext, understand exactly how the system works, and command unlimited computing power for unlimited time, yet still learn nothing from the ciphertext about which possible plaintext was sent.

Not very little.

Nothing.

That is not a boast from a vendor’s brochure. It is a mathematical property formalised by Claude Shannon in his 1949 Communication Theory of Secrecy Systems: observing the ciphertext does not change the attacker’s probabilities for the possible original messages. The ciphertext contains no usable information with which to choose one plaintext over another.¹

This is encryption reaching perfection.

Naturally, there is a catch.

From Vernam to perfection

The preceding artefact introduced Gilbert Vernam’s teleprinter cipher. Vernam’s system combined the electrical representation of each character with a second sequence of characters supplied by a key tape. The same combining operation, performed again at the receiving end with an identical tape, restored the original message. His patent was filed in 1918 and granted in 1919.²

The decisive refinement was to make the key sequence genuinely random and never use any part of it more than once. Joseph Mauborgne is credited alongside Vernam with developing this into the modern one-time-pad system in 1919.³

For binary data, the operation can be written with disarming simplicity:

Plaintext ⊕ Key = Ciphertext

Applying the same key again reverses it:

Ciphertext ⊕ Key = Plaintext

The symbol ⊕ means exclusive OR, or XOR. It is wonderfully obedient mathematics: combining a value twice with the same key returns the original value.

The cleverness, however, is not really in XOR. The cleverness is in the key.

Suppose an interceptor captures a ciphertext. For every possible plaintext of the correct length, there is exactly one possible key that would transform that plaintext into the captured ciphertext. If every key was generated randomly and is equally possible, the interceptor has no basis for deciding whether the original message was:

ATTACK AT DAWN

or:

RETREAT AT SIX

or:

PLEASE BUY MILK

or any other message of the same length.

Each possible plaintext has a corresponding possible key. The ciphertext cannot tell the interceptor which pairing is the real one.

The message has not merely been scrambled. It has been concealed among every message it could possibly have been.

The four intolerable conditions

Perfect secrecy is available, but the terms and conditions have been drafted by a particularly vindictive mathematician who could teach lawyers a thing or two.

One: The key must be truly random. A predictable sequence, a quotation, a password, or the output of an insufficiently unpredictable generator will contain structure that an attacker may exploit.

Two: The key must be at least as long as the message. A gigabyte of message requires a gigabyte of key material. There is no pleasing little 256-bit secret from which perfect secrecy for unlimited traffic can be conjured. Shannon’s result places a lower bound on the necessary key information, while modern guidance still notes that one-time-pad encryption requires randomness equal in volume to the messages being processed.⁴

Three: The key must remain completely secret. Both sender and recipient require matching copies, delivered and stored without interception, copying, substitution, corruption, or loss.

Four: And every part of the key must be used once, and only once.

Not “once per correspondent”.

Not “once per week”.

Not “once until somebody forgets which page they used”.

Once.

After use, that section of key material must be destroyed and must never reappear.

Break any one of these conditions and the cipher may still look like a one-time pad, but it no longer possesses the property that makes a one-time pad special.

When once becomes twice

Reusing key material is particularly destructive.

If two plaintexts are combined with the same key, an attacker can combine the resulting ciphertexts with each other. The identical key then cancels out, leaving a mathematical relationship between the two original messages.

The attacker may not immediately recover either plaintext, but natural language is full of structure. Words, spaces, standard headings, dates, greetings and predictable phrases provide footholds. A guessed fragment in one message exposes the corresponding fragment in the other. Each recovery enables more guesses, and the supposedly perfect system begins to unravel.

This is sometimes called a two-time pad, which is cryptographic terminology for “you had one rule”.

Project Venona

The VENONA project provides a spectacular historical example. Soviet diplomatic and intelligence messages were protected using one-time pads, but during wartime production the Soviet cryptographic centre manufactured duplicate copies of more than 35,000 supposedly unique key pages and placed them into different pad books. The mathematics had not failed. The random-number generator had not necessarily failed. Manufacturing and key control had failed, allowing Western cryptanalysts to exploit messages protected by duplicated key material.

The world’s strongest cipher was defeated by a production-control problem.

Cybersecurity has rarely improved upon this plot.

Unusually, there is a lot of material publicly available too: most of the recovered content is actually published by the NSA. It is rare indeed to see such comprehensive intelligence product outside of an actual intelligence agency. Indeed, with the internal compartmentalisation necessarily endemic within such organisations, it is rare indeed to see such comprehensive intelligence product even inside of an actual intelligence agency.⁵

The key-management singularity

The one-time pad does not remove the security problem. It relocates it.

Before Alice can send Bob a perfectly secret message, Alice and Bob must already possess identical quantities of perfectly random secret key material. Someone must generate it, copy it accurately, package it, transport it, inventory it, protect it from theft, keep both ends synchronised, prevent accidental reuse, and destroy it reliably after consumption.

Traditional pads were issued in matching pairs. A page of random groups was used for one message and then torn off and destroyed. Some pads were printed on materials designed to be destroyed quickly if an agent faced capture, because key-management procedures occasionally encounter people with guns.⁶

For a handful of short, extremely sensitive messages, that burden may be worthwhile.

For a global company moving terabytes of data each day, it becomes preposterous. Every terabyte of protected traffic would consume a terabyte of previously shared secret randomness at each end. Add more offices, users and communication paths, and the distribution problem grows into a heavily guarded stationery empire, rapidly grinding to a halt as a stationary empire.

There is also an apparently obvious objection:

If you possess a secure method for transporting a secret key as long as the message, why not use it to transport the message?

Sometimes that is exactly the right question.

The answer is that key material can be distributed in advance, before the message exists and before its sender knows when or where it will be needed. A courier or diplomatic pouch can deliver pads during peacetime; the pads can later protect urgent communications sent over exposed radio or telegraph links.

The one-time pad therefore separates the secure transport of secrecy from the later transport of the message.

It does not eliminate secure transport.

It merely schedules it earlier.

Perfect secrecy is not perfect security

There is a second catch, because one catch would apparently have been insufficient.

A basic one-time pad protects confidentiality, but it does not prove who created the message and does not necessarily reveal if the ciphertext has been altered.

With binary XOR encryption, an attacker who flips a bit in the ciphertext causes the corresponding bit to flip in the recovered plaintext. The attacker may not know the entire message, but in some circumstances may still make a meaningful or damaging alteration.

Encryption alone does not provide authenticity. A complete secure system therefore needs a separate mechanism to protect integrity and authenticate the message, with its own keys, procedures and opportunities for humans to improvise.⁷

The one-time pad is thus flawless only at the specific task it mathematically promises.

Humans merely have to avoid mistaking that task for every security property they desire.

The uncertainty has gone somewhere

The one-time pad has something of the shape of Heisenberg’s uncertainty principle, although this is an analogy rather than a claim that quantum mechanics has started issuing cipher pads.

To maximise the attacker’s uncertainty about the plaintext, the system must place at least as much uncertainty into the key. The entropy has not disappeared. It has been moved.

Certainty about confidentiality is purchased with an equal mass of secret randomness.

Make the cryptanalysis problem vanish, and the key-distribution problem expands to occupy the vacated space.

It is also a form of cryptographic thermodynamics:

You cannot win.

You cannot break even.

And you cannot leave the game.

The one-time pad lets you win completely against cryptanalysis. The bill simply arrives through the diplomatic pouch.

That is why it remains the high-water mark against which other encryption is judged, but not the system through which most of the modern world communicates. Practical cryptography accepts computational assumptions and short reusable keys because civilisation prefers an extremely difficult mathematical problem to an impossible global key-delivery operation.

The one-time pad proves something profound.

Perfect secrecy is possible.

Perfect convenience is not.

And security problems do not disappear merely because one part of the system has become mathematically flawless.

They move somewhere less elegant.

Usually into operations.

Usually into logistics.

Usually into the hands of someone with a spreadsheet.

If there is one lesson to take from this entire series, it is this: cybersecurity is always a balance between competing risks, costs and inconveniences. The one-time pad removes the risk of cryptanalysis, but replaces it with the risks and costs of key generation, distribution, storage and destruction. There are risks in acting, but there are also risks in doing nothing. Inaction is still a decision, and it still has consequences.

References & Links

1. https://onlinelibrary.wiley.com/doi/pdf/10.1002/j.1538-7305.1949.tb00928.x ↩︎
2. https://patents.google.com/patent/US1310719A/en ↩︎
3. https://www.nsa.gov/press-room/digital-media-center/biographies/biography-view-page/article/3903416/mg-joseph-o-mauborgne-usa/ ↩︎
4. https://paperzz.com/doc/7280674/communication-theory-of-secrecy-systems ↩︎
5. https://www.nsa.gov/Helpful-Links/NSA-FOIA/Declassification-Transparency-Initiatives/Historical-Releases/Venona/ ↩︎
6. https://www.cia.gov/legacy/museum/artifact/one-time-pads/ ↩︎
7. https://csrc.nist.gov/projects/block-cipher-techniques/bcm/authentication-for-confidentiality-modes ↩︎