The thief from Chapter 2 is back at the PIN pad, but this time the machine does not swallow the card. This time he can try as often as he likes — a thousand tries, a million, a billion — and he is in no hurry. His question is no longer "what are my chances on one try?" It is the question every patient attacker asks: how long until I win?
That question has an arithmetic of its own, and it is the arithmetic that prices every attack in this book. It runs on two ideas. The first is expected value — the average outcome, computed before anything happens. The second is the long run — the fact that averages, over enough trials, stop wandering and settle. Between them sits one honest surprise that most people get wrong: run exactly enough tries to "expect one win," and the win is still not certain. It is not even close to certain.
Chapter 2's raffle answers one-try questions. But nobody robs a raffle by buying one ticket and going home; the serious adversary buys tickets every day. The questions that matter for security are all about accumulation:
These are the questions this chapter answers, and they answer with two tools: the expected value, and the behavior of averages over long runs.
Roll a die once. What do you expect? Not 3 or 4 — those are just faces. Here is the way to compute what a single roll is worth on average. Imagine 6,000 rolls. Fairness means each face shows up about 1,000 times, so the total of all rolls is about
\[ 1{,}000 \times 1 \;+\; 1{,}000 \times 2 \;+\; 1{,}000 \times 3 \;+\; 1{,}000 \times 4 \;+\; 1{,}000 \times 5 \;+\; 1{,}000 \times 6 \;=\; 21{,}000, \]and the average per roll is \(21{,}000 / 6{,}000 = 3.5\). No die shows 3.5, yet 3.5 is the average — the value each roll contributes to the long-run total. Factoring out the 1,000s shows the shape: each face weighted by its share of the rolls, which is its probability:
\[ 1 \times \tfrac{1}{6} \,+\, 2 \times \tfrac{1}{6} \,+\, 3 \times \tfrac{1}{6} \,+\, 4 \times \tfrac{1}{6} \,+\, 5 \times \tfrac{1}{6} \,+\, 6 \times \tfrac{1}{6} \;=\; \tfrac{21}{6} \;=\; 3.5. \]The expected value of a numerical outcome is each possible value multiplied by its probability, all added together: multiply each value by its chance, then sum. It is the long-run average, computed in advance. It need not be a value that can actually occur — the die expects 3.5 and shows it never.
One property makes expected value the workhorse of this book: expectations add, always. The expected total of two dice is \(3.5 + 3.5 = 7\); of a hundred dice, \(350\). No independence required, no fine print — expected values simply add across trials. The thief's arithmetic is one line away.
Watch the thief work. Each try at the PIN is a tiny lottery ticket worth 1 win with probability \(1/10{,}000\) and 0 wins otherwise, so its expected yield is \(1/10{,}000\) of a win. Expectations add: over \(k\) tries, the expected number of wins is
\[ k \times \frac{1}{10{,}000} \;=\; \frac{k}{10{,}000}. \]A hundred tries: expected wins \(100/10{,}000 = 0.01\). Ten thousand tries: \(10{,}000/10{,}000 = 1\) — one expected win. That is the entire pricing formula for brute force: expected wins equal tries times chance-per-try.
For a thief guessing distinct possibilities — never repeating himself, the way any competent key-search works — something even cleaner happens. His \(k\) distinct guesses cover \(k\) of the \(N\) possibilities, so his chance of having won is exactly \(k\) in \(N\): 100 distinct tries at the PIN is exactly a \(100/10{,}000 = 1/100\) chance, no approximation. Expected value and exact chance coincide here, because at most one guess can be right.
Hold both facts for Part III, where \(N = 2^{256}\): an attacker's success chance after \(k\) well-chosen guesses is at most \(k\) in \(N\) — and his expected wins are exactly \(k/N\). Pricing an attack means dividing the attacker's budget by this arithmetic.
So how long does the thief wait, on average? Two models, two answers — and the difference matters.
The systematic thief — distinct guesses, no repeats, the way any competent search runs — finds the target somewhere in his search order, and it is equally likely to be found on try 1, try 2, …, try \(N\). The average of those is about \(N/2\): he expects to be done halfway through the space, and he is certain to be done by the end of it. For the 4-digit PIN: about 5,000 tries on average, 10,000 at worst. For a 6-digit PIN: half a million on average, a million at worst — at one guess per second, about 5.8 days on average, 11.6 days to be sure. That is the sense in which six digits are a hundred times stronger than four: the wait stretches by a hundred.
The independent-guess thief — each try a fresh 1-in-\(N\) shot, repeats allowed — waits exactly \(N\) tries on average, and here comes the honest surprise that nearly everyone gets wrong. Averaging \(N\) tries per win does not mean winning within \(N\) tries. Run \(N\) independent tries at a 1-in-\(N\) chance and the chance of never winning is:
\[ \left(1 - \frac{1}{N}\right)^{N} \approx 0.368 \quad\text{when $N$ is large}, \]That 0.368 is the one formula this book imports without proof — its exact name is \(1/e\), and deriving it is calculus, not arithmetic; checking it is arithmetic, so check it. So the chance of at least one win is only about \(0.632\) — roughly 63 in 100, not 100 in 100. (Compute it: 1 - (1 - 1/10**6)**(10**6) prints 0.6321207427789335.) Ten thousand PIN tries "expect" a win, yet more than a third of the time no win has happened at all. And the symmetric gift to the thief: some of the time the win lands early. Expectation is an average, not a schedule.
Two thousand simulated thieves, each guessing a random 4-digit PIN: the average wait is 10,089.9 tries — the theory's ten thousand — while one thief hits at try 2 and another is still guessing at try 79,791. Same game, same odds, wildly different fates. The average is real; the spread is real too.
Keep the two models straight, because they answer different questions with different numbers. Systematic search: exact chance \(k/N\) after covering \(k\) of \(N\) possibilities, an average wait of about \(N/2\), certainty at \(N\). Independent tries: an average wait of exactly \(N\), no certainty at all, and the \(\approx 0.368\) never-win chance after \(N\) tries. The first model governs brute force on one key; the second fits things like a botnet hammering thousands of different wallets, where each wallet is its own raffle. Both appear in Part IV's case files.
Why trust expected value at all, given that spread? Because of what averages do over long runs: they settle. Roll a die ten times and the average might be 3.1; keep rolling and the wandering dies down:
The running average creeps toward 3.5 — the expected value from §3.2 — and it does not leave again. Mathematicians call this the law of large numbers: over enough independent trials, the average of what happened closes in on the average of what could happen. This book treats it the way you just saw it: not as a theorem to admire but as an experiment you can rerun with any seed.
The long run is why the thief's arithmetic matters in practice. A single attack is luck; a campaign of attacks is a business, and businesses run on averages. When Part III prices brute force against a 256-bit key, the pricing works because the attacker cannot argue with the long run: at cosmic \(N\), the expected cost is the whole story, and no lucky early hit is coming to anyone's rescue. (Why the early-hit caveat stops mattering at cosmic scale is Chapter 8's job to make you feel.)
Everything so far shares one quiet assumption: the outcomes are equally likely. The fair coin, the fair die, the thief facing the full 10,000 PINs. But secrets chosen by people are not like that. Ask a million humans for a four-digit code and 1234 shows up far more than its fair \(1/10{,}000\) share; ask for a password and password beats xj9#q2 every time. When outcomes are not uniform, the good guesses come first — and a thief who guesses in popularity order does far better than \(k/N\).
So Part II needs a way to measure how unfair a choice process is: how much surprise does the answer actually contain, and how many guesses does the smartest thief need? Those are the two entropy questions, and they are Chapters 4 and 5.
Exercise 3.1 ★ The die's center. Compute the expected value of one fair die roll from the definition — each face times its chance, summed. You should get exactly \(3.5\).
Exercise 3.2 ★ Coverage. A thief makes 500 distinct tries at a 4-digit PIN. What is his exact chance of success? You should get \(500/10{,}000 = 1/20\), a 5% chance.
Exercise 3.3 ★★ The patient machine. A computer makes one guess per second at a 6-digit PIN, working through the space without repeating itself. About how many seconds to cover the whole space — the point of certainty? And about how long does the search take on average? You should get about \(1{,}000{,}000\) seconds \(\approx\) 11.6 days for the full space, and about half that — 5.8 days — on average (a day holds 86,400 seconds).
Exercise 3.4 ★★ Rerun the experiment. Run the PIN simulation from §3.4 exactly as printed, seed and all. Confirm the average wait is \(10{,}089.9145\) tries, the luckiest thief hit at try \(2\), and the unluckiest needed \(79{,}791\).
Exercise 3.5 ★★ The 63% fact. In Python, compute 1 - (1 - 1/10**6)**(10**6) and confirm 0.6321207427789335. Then explain in one sentence why a million independent tries at a one-in-a-million game do not make the win certain.
Exercise 3.6 ★★★ "The expected value is not the value you should expect." Defend that sentence in a short paragraph, using two exhibits from the chapter: the die that never shows 3.5, and the simulated thieves whose actual waits ranged from 2 to 79,791 around an average of about ten thousand.
Sketches, not model answers — enough to check your reasoning against. The computational exercises embed their expected outputs in the exercise text.
Exercise 3.5. Each try misses with chance \(1 - 1/N\), independent misses multiply (Chapter 2), so \(N\) tries all miss with chance \((1 - 1/N)^N \approx 0.368\) — and "at least one win" is the complement, about \(0.632\). Certainty would need the never-chance to be 0, and independent tries never drive it there; each try faces the same full \(N\) again.
Exercise 3.6. The expected value is a property of the average over many trials, not of any one trial. The die's 3.5 never appears on a face, because it lives one level up: in the total of thousands of rolls, where the wandering cancels. The simulated thieves make the same point in attacker's clothing — the average wait of 10,089.9 describes no one thief; the shortest wait was 2 tries and the longest nearly eighty thousand. Expectation prices the campaign, not the attempt. Confusing the two is how "a 1-in-a-million chance" gets misread as either "impossible" (too pessimistic about the thief who hits at try 2) or "safe to ignore for a million tries" (too optimistic about the same thief).