Crack it yourself

A sturdy padlock hanging open with a hairline crack across its body, and a magnifying lens beside it.

In every chapter before this one, everything worked. You pressed a button and the math did what it promised. Here everything is broken. Four puzzles, and each one holds a mistake somebody really made — in an app, in a wifi standard, in the database of a website. You are the attacker now. That's the game, and at the same time the lesson: in almost every leak that makes the news, the math isn't broken. It was used the wrong way.

Words you'll need in a moment

Capture the flag (CTF): A contest where you get puzzles like these. You're handed a file, a message or a website that hides something, and you have to break into it yourself. Worldwide, every weekend, free, and you don't need to know anything to get started.
Flag: The short piece of text hidden inside such a puzzle, usually in the form flag{something}. Find the flag and you've proven you were inside. There's one in puzzle 1 below.
Key space: The number of keys that exist. With Caesar there are 25 of them, with AES256 there are 2²⁵⁶. If the key space is small enough, nobody has to be clever: you simply try them all.
Brute force: Exactly that: trying everything until something comes out. No trick, no insight, only computing time. It's the attack every secret writing has to survive, and the reason keys are so long.
Word list: A file of passwords people really choose, in order of how often. The biggest ones floating around freely run into the hundreds of millions. An attacker starts there, not at aaaa.

Puzzle 1 — 25 keys is not a lock

Someone dropped a note. There's nonsense on it, but it's Caesar nonsense: every letter shifted along by a fixed number of places, as in chapter 4. You don't know the number of places. You don't need to.

Crack the Caesar

Everything happens in your browser. Nothing is sent to the server.

Click Try all 25 shifts. The demo shifts the text back 25 times and puts all the results underneath each other.
Work down the list until you see English. Note which shift that was, and read off the flag.
Click Let the computer choose. Now nobody is reading along: the demo counts for each line how English the letters lie and points one out by itself. See whether it picks the same one you did.
Encrypt something with it yourself. Type ordinary text in the box, click all 25 again and take the line you want. Shift 19 forwards is shift 7 back, because together they make 26.

The note

What went wrong here: a key space of 25

Caesar has no weak math. The adding up is perfect. There are simply 25 possible keys, and a computer tries 25 of them in less time than you need to count them. That's called brute force, and it isn't an attack on the secret writing but on its size. AES256 from chapter 4 does exactly the same kind of work as Caesar, with exactly the same openness about how it works — only there are 2²⁵⁶ keys instead of 25, and that's where brute force runs aground.

Puzzle 2 — the sports club's database

A sports club's website has been hacked. The member list is online: name and password hash, nothing more. The club did it "properly" — there are no passwords in it, only SHA-256 from chapter 2. Four members.

sam:9970626666560a32465d4ce10d28f3233365af833e15eed59884d9477862c379
noor:89ebdcadc16b41410b4a4e9a5e023d2dda67b2cf9a2a75f8c8231140acfe173a
jules:51aa8f7f35a1d0a8da0f6f3479d68363ee8577b64b98760a4da3b175520def29
kaya:0b742571b3431c26e550563d27040186a22b9fb4e8af277ba2c5acf4b50d3e56

Turn a word list loose on the leak

Everything happens in your browser. Nothing is sent to the server. The demo reads the hashes above straight off this page.

Click Crack the leak. The demo hashes every word from a list of a few dozen and compares them with the four hashes.
Look at how many milliseconds that took. Work out what a list of a hundred million words would cost on a machine a thousand times faster than yours.
One member survives it. Look at their hash: there's nothing to see. What they did differently isn't in the database but in their head.
Crack them anyway. Their password is sitting there literally as an example in chapter 3. Go and fetch it, put it in the Your own words box and click again.

Your own words to add to the list (commas in between)

What went wrong here: a hash without salt

The club encrypted nothing and you decrypted nothing. You calculated forwards: took the hash of every word and checked whether it was in the list. That works because the same input always gives the same hash — and that's exactly the property that makes a hash useful. There is one thing that breaks this attack, and that's salt: then the site doesn't hash your password but a random piece of text plus your password, a different one for every member. One list no longer does the job; the attacker has to start all over again for each member. How that works is in chapter 3.

This isn't an invented scenario. In June 2012 a file with 6.5 million LinkedIn password hashes appeared on the internet: SHA-1, without salt. Within a few days most of it was cracked, in exactly the way you just carried out yourself. Later the leak turned out to be far bigger than those 6.5 million.

Three more words

Keystream: The long trail of random-looking bits that a secret writing makes out of the key and the IV. Your message is added to it with XOR, and the receiver subtracts the same trail again. You already saw it at the bottom of chapter 4.
Crib: A piece of text you suspect is in the message: Hi, the, the receiver's name. A guess, then, but a good one. Crib dragging is sliding that guess across every position in the message and seeing where it fits.
Token: The little proof a website leaves in your browser after you've logged in. With every next click your browser sends it along, and that's how the site recognises who you are. It says who you are and what you're allowed to do.

Puzzle 3 — two messages, one keystream

A chat app encrypts every message with XOR: message ⊕ keystream. Fine in itself — that's how AES works too. But the programmer wrote the IV down once and left it there. Same key, same IV, so with every message exactly the same keystream. Here are two messages the app sent, in hex the way you pluck them off the wire:

message 1: db344ac5f216ba14ddb19a695eaebb301c89a459daadaea1f3fd4936df8903eb612ea12371e275c2efef6d4514ab0016ddd91c
message 2: db344ac5f216ba14e0f99e241db5be3e5588a559daadaea1e0e143218b801ea87e61e02438e936c8f5f321040ef85551988f41

Look at the beginning: db344ac5f216ba14 is there twice. Sixteen hex characters, eight bytes, identical letter for letter. That can only happen if the messages start the same there and the keystream is the same there. One line of the app told you that.

Take the keystream away

Everything happens in your browser. Nothing is sent to the server. The two ciphertexts are read off this page; the plaintexts are nowhere in the code — they only come out if your guess is right.

Click XOR them onto each other. Because both messages were encrypted with the same keystream, that stream drops out. What's left is message 1 ⊕ message 2.
Count the zeros at the front. Where two messages have the same character, XOR gives zero. Eight zeros means: eight characters the same.
Type a guess for message 1 and click Lay my guess alongside. What you get back is message 2 — if your guess is right. Start with Hi Sam, and add a word at a time. If the other side reads as English you're on track; if rubbish comes out you're wrong.
Stuck? Click Crib dragging. The demo slides a list of everyday words across every position in the XOR and puts at the top whatever comes out looking most like English.

Your guess for message 1

What went wrong here: the same IV twice

The key was nowhere guessed and nowhere broken. It dropped out, because it was used twice in the same way. In chapter 4 it says the IV doesn't have to be secret, only new. This is why. One IV too few and you no longer have two encrypted messages, but two plaintexts lying on top of each other.

With AES-GCM, the mode your messaging app really uses, it's worse still. There, reusing the IV doesn't only give you this: an attacker can also forge the seal with it and so tamper with your messages unnoticed. And AES doesn't warn you. Everything keeps looking normal.

In October 2017 Mathy Vanhoef and Frank Piessens of KU Leuven showed that you can force a wifi device to reinstall its key, which makes the counter that supplies the IV jump back to zero and the same keystream start again. That attack is called KRACK, and it worked against WPA2 — the security protocol of just about every wifi network in the world at that moment. The name of their paper says exactly what it's about: Forcing Nonce Reuse in WPA2.

Puzzle 4 — the signature nobody checks

A school platform hands you a token when you log in. It says who you are and which role you have: pupil or administrator. The server signs that token with its private key, as in chapter 7.1, so that nobody can forge it. The math is right, the key pair is real, the signature is real. There's only one problem: the server doesn't look at it.

Become administrator

Everything happens in your browser. Nothing is sent to the server. The key pair is made fresh on every click and disappears when you close the tab.

Click Log in as a pupil. The demo makes a key pair (ECDSA on P-256, the curve from chapter 6.2) and signs a token. It appears in the box: three pieces in base64url, separated by dots. You know those from chapter 1.
Click Check it the way it should be. The public key says: fine, this comes from the server.
Click Tamper: make me administrator. The middle piece is changed and the header gets alg: none in it — "there is no signature". The third piece is emptied out.
Click Check like the leaky server. You're in as administrator.
Click Check it the way it should be again. Refused. Same token, same math, different answer — the difference lies entirely in what the server does with what it gets.

The token (you may also tamper with it by hand)

What went wrong here: `alg: none`

A signature you don't check isn't a signature but a decoration. Worse still: this server lets the attacker put in the token's own header how the checking should be done, and accepts the answer "don't". That's hanging your keyring on the door handle with a note beside it.

On 31 March 2015 Tim McLean published that a whole range of widely used libraries for this kind of token did precisely this: letting alg: none through as a valid choice. In chapter 6 you can read why that's so painful — the whole point of a public key is that everyone can check. Here everyone could have, and nobody did.

This is math: why using one key twice wrecks everything

Take puzzle 3 in symbols. Message a and message b both go through the same keystream k:

c₁ = a ⊕ k

c₂ = b ⊕ k

c₁ ⊕ c₂ = (a ⊕ k) ⊕ (b ⊕ k) = a ⊕ b

That last line is the whole puzzle. You may do XOR in any order you like, and k ⊕ k = 0 — that's the rule from chapter 4, applied twice here. The key drops out. What's left holds not a single secret bit any more: it's two messages covering each other up, and English covers English badly.

The odd thing is that XOR with a keystream is mathematically perfect as long as you use it once. Claude Shannon proved that in 1949: if the key is as long as the message, truly random and used only once, then there is nothing to get out of the ciphertext. Not "hard" — nothing. That's called a one-time pad, and it's the only secret writing proven to be unbreakable. The word one-time does all the work.

That didn't stay theory. In 1942 the Soviet printing works, under wartime pressure, made some 35,000 duplicate pages of such key booklets. American codebreakers noticed, and could read along with messages for years because of it — the VENONA project, which had its first breakthrough on 20 December 1946. Of hundreds of thousands of intercepted messages, fewer than 3,000 have been read in whole or in part, and that was enough to expose spy networks. One reused page at a time.

This is information theory: the field that measures how much information a message really holds, also founded by Shannon. It explains why a ⊕ b can be read and a ⊕ k cannot — not because one sum is harder, but because English text is predictable and randomness isn't.

Where this stops. What you did here, you do on your own stuff or in an environment built for it. Those environments exist: the CTF contests from About this site are exactly this, but for a whole weekend and with hundreds of others. On a system that isn't yours it's a criminal offence — in Belgium article 550bis of the Criminal Code, introduced by the act of 28 November 2000. You don't have to break anything or steal anything: getting in where you're not allowed is enough. The difference between the two isn't a matter of being able to, but of permission.