What we want from cryptography

Cryptography is the mathematics of keeping messages safe from the people who handle them on the way. Before any of the mathematics, it’s worth being clear about what “safe” means, and who it’s safe from. This page sets that out, with the cast of characters every book on the subject uses, and ends with the toolbox cryptography offers.

1 · Alice, Bob and the wire

Alice wants to send a message to Bob: they had dinner last night, Alice paid, and Bob owes Alice $20, so the message says which account to pay it into. Between them is a wire: a cable, a radio link, the internet, a postal service. Anyone with access to the wire can do things to the message on the way. Two of them turn up everywhere: Eve, who listens (an eavesdropper), and Mallory, who meddles (malicious).

Alice and Bob first appeared in 1978, in the paper that introduced RSA, one of the first ways to encrypt with a key that can be made public; Eve and Mallory joined them later. (And where these pages need a sample of English to count letters in, it’s Alice’s too: the first chapter of Lewis Carroll’s Alice’s Adventures in Wonderland.)

Alice sends Bob a message (change it if you like); choose who’s on the wire, and whether the message is encrypted. Eve only reads it, and learns who had dinner with whom, and Alice’s account number. Mallory puts their own account number in its place, or sends a message of their own as “Alice”. Encrypted, the message on the wire is its bytes (as hex) mixed with a secret key that only Alice and Bob have. Encrypting keeps Eve out, but look at what Bob receives when Mallory interferes: nothing says anything’s wrong.

Each kind of attacker takes away something different, and so there are three things we want:

Confidentiality: only Bob can read the message. Eve, with a copy of everything on the wire, learns nothing from it.
Integrity: if the message is changed on the way, Bob can tell.
Authenticity: Bob can tell that the message really came from Alice.

Encryption, scrambling a message with a secret key so that only someone with the key can unscramble it, gives the first. It’s what most people think cryptography is. But, as the figure shows, it doesn’t give the other two.

2 · Hiding isn’t protecting

It’s tempting to think an encrypted message is safe from changes too: if Mallory can’t read it, how could they change it to say anything useful? Here’s how.

Many ciphers work by mixing the message with a stream of secret key bits using XOR (“exclusive or”). XOR compares two bits and gives 1 if they’re different, 0 if they’re the same:

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

XORing with a key bit of 1 flips the message bit; XORing with 0 leaves it alone. XOR the result with the same key again and every flip is undone: that’s decryption. Bytes are XORed bit by bit, eight at a time (written ⊕).

Now suppose Mallory knows what the message says at some point. Say Alice’s payments app sends requests in a fixed layout, so the account number is always in the same place, and Mallory knows Alice’s account number (it’s on every bill Alice sends). Each ciphertext byte there is message ⊕ key. Mallory XORs it with (the old message ⊕ the new message). The old message cancels itself, leaving new message ⊕ key: exactly what Alice would have sent for the new message. Mallory never needs the key.

Alice’s request, encrypted by XORing each byte with a byte of key (written in hex, two digits a byte). Mallory knows the layout and Alice’s account, so knows the last four characters say 4821. XORing just those four bytes of ciphertext with (4821 ⊕ Mallory’s account) makes Bob decrypt Mallory’s account number, and pay the $20 into it, without Mallory using a single byte of the key. Try another account, or a new key: it works every time (checked in the tests for 50 random keys).

This works against the one-time pad, the one cipher that’s provably unbreakable: its secrecy is perfect, and it still lets Mallory do this. A cipher hides; it doesn’t protect. Integrity and authenticity need a different tool: a check value sent with the message that only someone with the key can make, so that any change, or a message made up by someone else, fails the check.

3 · Only the key is secret

Should Alice and Bob keep the method of encryption secret too? It seems like it can only help. In 1883 Auguste Kerckhoffs, a Dutch linguist writing about military ciphers, argued the opposite: a system should stay secure even if the enemy knows everything about it except the key. Claude Shannon put it more bluntly in 1949: “the enemy knows the system.”

The reasons are practical:

Methods leak. Machines are captured, manuals copied, software taken apart. The encryption on DVDs was kept secret, and was worked out from a software player and broken in 1999. The cipher in a widely used contactless transport card was reconstructed from microscope photographs of the chip in 2007 and found to be weak.
Keys are easy to change; methods aren’t. If a key leaks, make a new one. If a secret method leaks, every device that uses it has to be replaced.
Only public methods get tested. A published cipher is attacked by everyone who’d like the credit for breaking it. One that survives years of that is far more trustworthy than one only its designers have seen.

So everything on this site assumes the attacker knows exactly how the cipher works. The only secret is the key, and the whole question is whether knowing everything else helps them find it.

4 · What the attacker can do

Attackers differ in what they can get hold of, and a cipher has to stand up to the strongest of them. In increasing order of power:

The attacker has	For example
Ciphertext only: encrypted messages, nothing else	Eve recording a radio link
Known plaintext: some messages and their encryptions	Letters that all begin “Dear”, web requests that all begin the same way, the weather report sent at 6 every morning
Chosen plaintext: encryptions of messages they choose	Getting a target to encrypt something: sending them a message they’ll forward on, or a web page whose script makes their browser send requests
Chosen ciphertext: decryptions of ciphertexts they choose, or at least whether they decrypted cleanly	Sending a server altered ciphertexts and watching its error messages

The old ciphers on the next page fall to ciphertext alone. A modern cipher is expected to survive all four, and more: for it to count as broken, the attacker needn’t find the key, or even read a message. Learning anything at all is enough.

5 · What “secure” means: a game

“Learning anything at all” can be made exact, as a game. The attacker chooses two messages of the same length, A and B. The cipher secretly tosses a coin, encrypts one of them with a fresh key, and hands over the ciphertext. The attacker says which it was. Guessing wins half the time; the cipher is secure if no attacker can do noticeably better than that. Shafi Goldwasser and Silvio Micali set this out in the early 1980s, and it’s still how ciphers are judged.

Play the game. Choose two messages, encrypt one, and say which. Against Caesar’s cipher (every letter shifted by the same random amount), the messages AAAAA and ABCDE are easy to tell apart: a single shift keeps all the letters the same, or all different. The computer plays the same way: it checks whether one shift could turn A into the ciphertext, and whether one could turn B into it. Against Caesar it wins all 1,000 rounds (pinned in the tests). Against the one-time pad, a fresh shift for every letter, both messages could always have made the ciphertext, and it does no better than tossing a coin: about half.

The game shows why “the attacker can’t read the message” isn’t enough. Caesar’s ciphertext doesn’t spell out the message, but it gives away which letters repeat, and the attacker chose messages that differ in exactly that. A secure cipher gives away nothing an attacker could choose to exploit, apart from the length.

The game also demands that encrypting the same message twice gives different ciphertexts. If it didn’t, the attacker could simply ask for the encryption of A (they’re allowed to, as a chosen-plaintext attacker) and compare. That’s why real encryption mixes in a fresh random number every time.

6 · Trying every key

Whatever the cipher, one attack always works: try every key until one decrypts a known message correctly. It’s called brute force, and the only defence is having too many keys to try. A key of n bits has 2ⁿ possible values, so each extra bit doubles the work.

A toy cipher with a key of the chosen length (a few rounds of multiplying and shifting a 32-bit block). Hide a key, then let your browser try every key in turn until one turns a known block into the known ciphertext. Below, the speed it measured, applied to longer keys: how long trying every one would take this browser, and a million computers like it. A real cipher takes longer to try than this toy, which only makes the times longer.

Each bit doubles the time, and that adds up astonishingly fast. DES, the standard cipher from 1977, has a 56-bit key: in 1998 a machine built for the purpose found one by trying keys in under three days. A 128-bit key isn’t, by any margin: even a million computers like yours, running for the age of the universe (about 14 billion years), would try a tiny fraction of the keys. So brute force sets a floor on key sizes, and modern ciphers use keys of 128 or 256 bits. The real attacks are the ones that avoid trying every key, and finding those is what breaking a cipher means.

7 · The toolbox

Each of the things we want has its own tools:

We want	The tool	What it does
Confidentiality	A cipher	Scrambles a message with a key that Alice and Bob share
Integrity and authenticity	A message authentication code (MAC)	A check value that only someone with the shared key can make
A fingerprint of some data	A hash function	A short value that changes completely if the data changes at all
A shared key, agreed in public	Key exchange	Alice and Bob agree a key that Eve, hearing everything, can’t work out
Messages anyone can check	Digital signatures	Only Alice can make one; anyone can check it with Alice’s public key
Unpredictable keys	Random numbers	Keys an attacker can’t guess (see Randomness)

Real systems, such as the padlock in a browser or an encrypted chat, combine all of these.

Summary

Alice sends Bob a message; Eve listens, Mallory meddles.
We want confidentiality (only Bob reads it), integrity (changes are detected) and authenticity (it really came from Alice).
Encryption gives confidentiality only: with XOR ciphers, Mallory can change a known part of a message without the key.
Kerckhoffs’s principle: assume the attacker knows the method; only the key is secret.
Attackers may have ciphertext only, known plaintext, chosen plaintext, or chosen ciphertext. Secure means they learn nothing: they can’t even tell which of two messages they chose was encrypted.
Brute force always works in principle; each key bit doubles it, and 128 bits puts it out of reach.