Shannon and perfect secrecy

Perfect secrecy is the one kind of security that holds against an enemy with unlimited computing power, and Claude Shannon proved exactly what it costs. A cipher has it when the ciphertext tells an eavesdropper nothing at all about the message. Shannon showed in 1945, in a report that stayed classified for four years, that the one-time pad has this property and that nothing else gets it on cheaper terms. That's the moment cryptography stopped being a craft and became a branch of mathematics. Below: the idea with real numbers, what the proof demands, what happened when the Soviets cut corners (the Venona project), and why almost everything we use, cipher.ink included, deliberately falls short of perfect.

The two papers

Shannon was a mathematician at Bell Laboratories, and during the Second World War he worked on secure communications. On September 1, 1945 he wrote a confidential Bell Labs memorandum, A Mathematical Theory of Cryptography. It grew out of his work on information. In 1948 he published A Mathematical Theory of Communication, the founding paper of information theory, and in 1949 the cryptography report was declassified and published as Communication Theory of Secrecy Systems in the Bell System Technical Journal (volume 28, issue 4, pages 656 to 715). Its main result is a proof that every cipher that's theoretically impossible to break has to meet the same requirements as the one-time pad. Before it, people argued about whether any cipher could be called safe. After it, the question had an exact answer.

What perfect secrecy means

Suppose an eavesdropper knows everything about the cipher and has a guess about how likely each message is (an army might send "attack" far more often than a poem). They intercept a ciphertext. The cipher is perfectly secret if, after seeing it, their guesses are exactly what they were before, and every message is as likely as it was. The ciphertext has taught them nothing.

Here's how the one-time pad pulls that off, in letters. Encrypt ATTACK by adding a random key letter to each letter, say the key QZRBTE, with A = 0 up to Z = 25 and wrap-around: A + Q = Q, T + Z = S, T + R = K, A + B = B, C + T = V, K + E = O. The ciphertext is QSKBVO. Now look at it from the interceptor's side. The same ciphertext decrypts to DEFEND under the key NOFXIL, and to SURVEY under the key YYTGRQ. For every six-letter message there's exactly one key that turns it into QSKBVO, and if the key was chosen at random, all those keys were equally likely. So all the messages stay as likely as they were before. There's nothing to compute, and no amount of power helps, because the information simply isn't in the ciphertext. (These numbers are from scripts/examples/perfect-secrecy.mjs.)

What it costs

Shannon's theorem sets the price of perfect secrecy: there must be at least as many possible keys as there are possible messages. For messages of any length, that means a key as long as the message. Add the two other rules that Vernam, Mauborgne and Shannon established. The key must be random, since any pattern in it is a pattern an attacker can use, and it must be used once. A cipher that gives up any of the three stops being perfect. The cost is exactly the problem ciphers were meant to solve, because you have to deliver as much secret key as you'll ever send, safely, in advance. That's why only very high-value traffic ever used pads.

When the rules were broken: Venona

The clearest proof that the rules matter is the Venona project. Soviet intelligence encrypted its messages with one-time pads, which should have been impossible to break. But a factory printed the pads under wartime pressure. After the German advance on Moscow, the manufacturer produced around 35,000 pages of duplicate key numbers, and the duplicates were used for traffic in 1942 and mostly used up by the end of 1945. Two messages encrypted with the same pad page are no longer perfect. Subtract one ciphertext from the other and the key cancels, leaving the difference between the two messages. With the numbers above, QSKBVO minus the ciphertext of DEFEND under the same key is XPOWPH, which is exactly ATTACK minus DEFEND. That lets an analyst peel the two messages apart by guessing common words (the AES playground shows the same thing happening to a modern stream cipher that reuses a nonce).

The US Army's Signal Intelligence Service began Venona on February 1, 1943 at Arlington Hall. The first break came on December 20, 1946, when Meredith Gardner revealed Soviet espionage in the Manhattan Project. Out of some hundreds of thousands of intercepted texts, fewer than 3,000 were partly or fully decrypted over the project's life. That's a small fraction, and it was still enough to identify spies in the United States and Britain, among them Klaus Fuchs, and the spy ring known as the Cambridge Five. The program ended on October 1, 1980, and the material was made public in 1995. Nobody broke the one-time pad. Its users broke the rules.

Shannon's other ideas

• Unicity distance. For a cipher that isn't perfect, how much ciphertext does an enemy need before only one plaintext makes sense? Shannon's answer is the number of bits in the key divided by the redundancy of the language. A simple substitution cipher on English has 26! = 403,291,461,126,605,635,584,000,000 keys, about 88.4 bits. English has roughly 3.2 bits per letter of redundancy by a common estimate, so about 28 letters of ciphertext are enough for the answer to be unique. That's why short cryptograms are ambiguous and long ones are easy (the substitution solver shows it). The figure depends on the estimate of redundancy, so treat it as a rule of thumb.
• Confusion and diffusion. The 1949 paper names two properties a good cipher should have. The relation between the key and the ciphertext should be complicated (confusion), and a change in the message should spread through the whole ciphertext (diffusion). They're the design principles behind the S-boxes and mixing layers of AES, and you can watch diffusion at work in the SHA-256 explorer.
• The enemy knows the system. He put the design assumption plainly: assume the enemy will gain full familiarity with the cipher (Kerckhoffs's principle).

Why we use ciphers that aren't perfect

Almost all real encryption, including AES-GCM, gives up perfect secrecy on purpose. Instead of a key as long as the message, it takes a short key (here 256 bits) and generates a long pseudo-random key stream, which it combines with the message the way the one-time pad does. That stream isn't truly random. Given enough computing power, someone could find the key by trying every one. So the security is computational, not absolute: breaking it takes a search of 2²⁵⁶ steps that nobody can run. The trade is a fair one. A 256-bit key can be handed over in seconds, reused across gigabytes and protected for years, and a one-time pad for the same data can't. ChaCha20 and RC4 are exactly this: an attempt to make a short key behave like a long random one. Perfect ciphers also give no protection against tampering. With a one-time pad, flipping a ciphertext bit flips the same plaintext bit, so a message needs authentication as well (authenticated encryption).

How cipher.ink uses this

cipher.ink doesn't use a one-time pad, and the page about it is clear about the reasons (the one-time pad page has a working pad you can try). Every message does use a key that's used exactly once: a fresh random salt and IV for a passphrase message, a fresh random 256-bit key for a secret link. That's Shannon's "use it once" in practice, even though the key is short and the secrecy computational, and the 12 bytes (96 bits) IV rule keeps GCM from ever making a two-time pad.