The training range

In the last chapter we assembled cryptography that can’t be broken head-on: factoring an RSA key would take longer than the age of the universe. And yet systems built on this mathematics get broken every day. Passwords leak out of a bank because a programmer glued a SQL query together from strings. A site with flawless TLS hands out other people’s passwords because one function didn’t check a length. In both cases the cipher is intact. The lock holds, but the door is lifted out frame and all, or the owner is talked into opening it. This chapter is about the frame.

The only place to learn to attack without harming anyone is a training range. Ours is the chapter itself: a vulnerable function in a live cell, a mock login form in a widget, a tiny database that lives for a second in the sandbox’s memory and vanishes. You break these targets and patch them on the spot, and the task tests check that after the patch the attack that just worked no longer does. We don’t touch anyone else’s systems: courtesy demands that, and so does the law, which we come to at the end of the chapter.

The range and the threat model

Before building any defense you answer three questions: what are we protecting, from whom, and at what cost? The answers together are called a threat model. Without one, talk of security turns into hand-waving: “we have to encrypt everything”—but why, from whom, and what happens if we don’t? The schoolkid fooling around in the next tab is stopped by one thing; someone studying your server for weeks for money, by something else entirely; and if you dictated your password over the phone yourself, nothing on that list will save you.

A weak spot through which an attacker gets something you didn’t plan for is called a vulnerability, and a ready way to make use of it is an exploit. Knowing about a bug in a program and being able to turn it into an attack are far from the same. On the range we learn both, so that later we notice such bugs in our own code before anyone else does.

Under the range lies the sandbox that runs every cell in the course. It runs your code with no access to the network, as a user with no rights, in memory that it wipes after every run. A vulnerable program in such a cell is safe to write and run: it has nowhere to do harm and nothing to do it with. We’ll take apart what the sandbox itself is built from near the end, when we get to least privilege.

The night of November 2, 1988

We start with the buffer overflow: it is the oldest attack in the chapter and shows most clearly how data becomes code. For it we’ll need the C of Chapter 33, where Python under the microscope turned out to be a C program, and writing past the end of an array quietly damaged the memory next to it.

Past the end of the buffer

Chapter 33 boiled the difference between Python and C down to one line. Before every indexed write Python checks the bound and raises an IndexError if you run off the edge. C checks nothing: a write past the end of an array is undefined behavior, and whatever lay next in memory changes silently. If it’s your own data next door, you get quiet corruption. If it’s the address the program will return to from the function, then whoever writes past the edge chooses where it jumps. Here is a vulnerable teaching program. It takes a “username” and puts it into a structure where, right after the name, sits a balance field, the money left in an account.

A short name goes through without incident: the balance stays what it was, a hundred. But the name field is eight bytes, and strcpy copies as much as it was sent. Thirteen letters (thirteen bytes and a terminating zero) don’t fit into eight, and the extra five land straight on balance. Nobody touched the account, yet the balance became a huge number assembled from the codes of the letter “A”: data from stdin overwrote a variable it had nothing to do with.

A buffer overflow is a write past the end of a buffer that damages whatever lies beyond it. While what lies beyond is a neighboring variable, the damage is a wrong number. But in Chapter 33 we saw the layout of a stack frame: right after the local variables sit the saved frame pointer and the return address. Send a longer name and pick the bytes, and a number chosen by the attacker lands on the return address, and ret jumps wherever they want. That is how the Morris worm got in through fingerd. We won’t carry this attack all the way through. Past the end of the structure the program fails in different ways on different machines (in the sandbox, with a signal), and the exact addresses depend on the processor and the compiler flags. What we’ve seen is enough: the extra data overwrites the neighboring memory, and whoever sent it chooses what to overwrite.

The patch is obvious and dull, which is why it gets forgotten: copy no more than fits, and leave room for the terminating zero. C has snprintf for this; it truncates the extra for you.

Now a long name is truncated to seven letters, and the balance holds at a hundred for any length of input: there’s nowhere for the extra bytes to go. In the bounds-check task you’ll fix a similar program yourself, where two hundred numbers are written into an array of a hundred.

Production systems don’t stop at one check. On top of it stand three more layers, in case the check was forgotten after all. A stack canary: the compiler puts a random number before the return address and checks it before returning; an overflow overwrites the canary, the mismatch is noticed, the program is halted. Non-executable memory (the “execute as code” permission in the page table from Chapter 38, known as the NX bit): pages for the stack and the heap are marked “not executable,” so the data put there can’t be run as code. Address space layout randomization (ASLR): the addresses of libraries and the stack are different on every run, and the attacker has nothing to aim at. That is why, as you saw in Chapter 33, the addresses in a C program change from run to run. No single layer is perfect, but together they turn “quietly rewrote the return address” into “most likely crashed.” We’ll come back to this layered defense.

A boy named Bobby Tables

Buffer overflow lives in languages with no bounds checking. But the same trouble, data that became a command, happens where no buffers are in sight. In Chapter 45 we queried a database with SQL and made a vow in passing: pass values from a visitor through a ?, and never paste them into the text of a query. Now we’ll break the vow on purpose. In xkcd comic #327 (2007), the school calls a mother: the database has lost the year’s student records, because she named her son Robert'); DROP TABLE Students;--. Names like that have been called “Bobby Tables” ever since.

Here is a mock login form. The database is a tiny table of users that lives in the sandbox’s memory for one run. The check function glues a SQL query together from strings, the way beginners often write it.

The first two lines behave as they should: with the right password, user; with the wrong one, None. The third gets in with no password at all, as whichever user happens to come first. The answer is in the printed query: the name ' OR 1=1 -- was pasted into the text, and the condition came to read name = '' OR 1=1 --' AND pw = '…'. The single quote closed the empty name, OR 1=1 made the condition true for every row, and two dashes start a comment in SQL, so the database never even saw the password check. This is a SQL injection: the string sent in stopped being data and became part of the command. The “Bobby Tables” name works the same way, only with DROP TABLE in place of OR 1=1.

The patch is the vow from Chapter 45. We hand the database the text of the query with ? in place of the values, separately from the values themselves. Each question mark holds a place where the database itself will put the data, as the contents of a cell, and the data can no longer become part of the command. The same query, the same attacks, and not one gets through.

All four attacks returned None: the database looked for a user named ' OR 1=1 --, didn’t find one and turned them away. Even “Bobby Tables” with its DROP TABLE is harmless; the last line shows the table is intact. What protects here isn’t a clever check or a blacklist of dangerous words (always bypassable), but a wall between command and data, drawn once and for good. On the range below, watch the text of the query: with gluing, the attack rewrites the command itself, while with parameters the command doesn’t change by a single letter, and the string sent in goes into the database separately, as a value.

In the sqli-fix task you’ll fix the vulnerable login yourself. The tests check two things: that an ordinary login still works, including for a person with a quote in their name (d'Anthès), and that no injection gets in or drops the table. That is how you check any patch: the feature still works, the attack no longer does.

Someone else’s script on your page

SQL injection pastes data into a command for the database. Paste it into a page that someone else will see, and you get cross-site scripting. In Chapter 43 we worked out that a page is text with tags: the browser builds a DOM tree from it and runs everything that lands inside a <script> tag. Picture a forum. You write a comment, the server saves it and shows it to everyone who opens the page. What if, instead of text, you send a <script> tag?

In the first case the tag sent in lands in the page’s tree as ordinary markup. Every forum reader’s browser will try to load the image from the nonexistent address x, the load will fail, and the onerror handler fires: a small script that runs as that reader, on this site. It can read cookies, send them to another server, click buttons on the visitor’s behalf. This is cross-site scripting (XSS). In the second case html.escape replaced < with < and > with >, and the browser shows the text of the tag as letters instead of running it. The principle is the same as with SQL: where data enters another language (here, HTML), you escape it, and the special characters stay letters.

The defense comes in two layers. The first is escaping output, as above. The second we met in Chapter 43: the HttpOnly flag on the session cookie. It forbids a page’s scripts to read that cookie at all, so even a script that gets through can’t carry off the session key through document.cookie. If the first layer was forgotten, the second limits the damage.

In 2005 Samy Kamkar showed what XSS looks like in practice. His worm for MySpace, hidden in a profile, crawled from profile to profile and added the line “but most of all, samy is my hero”; in less than a day it added its author as a friend to more than a million users. The worm stole no data and erased nothing, but MySpace had to take the site down for a while to clean it out. The author pleaded guilty to a computer break-in and got probation, community service, and a ban on going online. MySpace closed the hole, while XSS has stayed in the lists of the most common vulnerabilities for years, right next to injection.

A weak password

The Morris worm’s third route was the most primitive and the most reliable: guessing passwords from a short list of common words. Little has changed since. The one that still turns up most often in leaks is 123456, and right beside it at the top of the lists are 123456789, qwerty and password. Why try every combination when millions of people pick the same hundred? Suppose the defense is set up properly: passwords, as we agreed in the last chapter, are stored as salted slow hashes, and a stolen database won’t hand over the password directly; it has to be guessed. How many guesses will that take?

A six-digit numeric password falls instantly: a million choices at ten billion checks a second. Eight lowercase letters with digits already hold out for minutes. What decides is length: every added character multiplies the number of choices by the size of the alphabet. A phrase of four simple words (the famous xkcd example, “correct horse battery staple”) can’t be found by a character-by-character search at all, and it is easier to remember than Tr0ub32. That is why a long passphrase is safer than a short password bristling with special characters.

But all of this is about blind search. A live attacker starts with a dictionary: leaked passwords, names, dates, keyboard rows. Against a dictionary, length doesn’t help if the phrase itself is common. Even random words are searched whole, not letter by letter: if the attacker knows the password is four words from a list of 2048 (as xkcd assumed too), the number of choices is no longer $10^{49}$ but $2048^4 \approx 1.8 \cdot 10^{13}$, and at ten billion checks a second that is half an hour. Here a slow hash and an extra word or two come to the rescue: each word multiplies the search by 2048. So password defense adds things that don’t depend on the password’s strength: a limit on login attempts, a second factor (a code from an app), a check of the new password against lists of ones already leaked. On the storage side, what we assembled in Chapter 60 does the work: a salt, so that identical passwords give different hashes, and a slow hash, so that each guess costs the attacker dearly. In the password-strength task you’ll build an estimator that looks in the dictionary first and only then counts the brute-force search, and you’ll see a long but common password fail first.

When the server says too much

Until now the attacker made a system do too much. But you can also make it say too much: hand over a piece of memory meant for no one. The most famous case is Heartbleed, 2014.

Heartbleed is the mirror image of a buffer overflow: instead of an extra write there is an extra read past the end of a buffer, and what’s read goes out into the world. The root is the same: trusting a number sent by someone else. We’ll build a teaching model: the “server’s memory” is a string where a secret lies right next to a harmless answer. The client sends a word and a length; the vulnerable server returns a slice of the requested length, while the safe one checks the length against what was sent and doesn’t answer an inflated request at all.

A request with the right length returns “bird”. The same request with an inflated length pulls out the secret that lay in memory right after the word: the server read out what it wasn’t asked for. The fixed server sees that the length is more than the word it was sent and doesn’t answer at all (None): that is what version 1.0.1g did. On the simulator below, watch the moment the length crosses the end of the word: from that byte on, the server is handing out what belongs to others.

A call from “support”

Every hole so far sat in the code. The widest one sits in the person who maintains that code. Fooling a person is often cheaper than finding a vulnerability: no overflow, no injection, just a convincing message. Such deception is called social engineering, and one special case of it, a fake email or page that fishes for a password, is phishing.

On July 15, 2020, dozens of the most prominent Twitter accounts were taken over at once—Obama, Musk, Gates, major companies—and all of them posted, in their owners’ names, a promise to double any bitcoin sent in. The accounts’ technical defenses were not broken at all. The attackers called Twitter employees, posed as the company’s own support team, and coaxed out of them a way into an internal control panel from which any account could be taken over. The attack hit 130 accounts. In a couple of hours the fraudsters collected more than a hundred thousand dollars in bitcoin from trusting people, and not a line of exploit code was needed. The chief organizer turned out to be a seventeen-year-old.

No algorithm helps here: the target is a person. Rules and habits help. Support never asks for a password or an app code. An email with the word “urgent” and a link is checked by the sender’s address, not by the button in the email itself. Access to anything important is granted under a “two pairs of eyes” rule. All of this is dull and doesn’t look like programming, which is why people are the most common way in. A system is only as strong as its weakest link, and that is often a tired person at the end of a shift.

Least privilege and layers

We never found a perfect defense: a check can be forgotten, a person fooled, and a hole will turn up in someone else’s library. Since a break-in will happen sooner or later, the question has to be asked differently: how much can the attacker do once they’re in? That question is answered by a rule Jerome Saltzer stated in 1974 and a year later, with Michael Schroeder, included in his famous list of protection principles. It is the principle of least privilege: every program and every user runs with the minimum of rights that is enough for their task, and nothing beyond it. Then a captured part of the system does harm only within its meager rights, and the whole machine is spared.

The range where you have been running this chapter’s cells rests on this principle. Around the untrusted code there stand several independent walls: if one doesn’t hold, the next is behind it. This approach is called defense in depth, and the environment built this way around untrusted code is a sandbox. Below are the walls around your cell and the attacks each one stops.

The layers are described at the level of ideas, with no settings: with someone else’s defenses it’s useful to understand why each layer is there, and how to get past one is not something we discuss. The idea carries over to any system. Keep code you don’t trust (and by definition you don’t trust someone else’s code) where it has no network, no access to your files, no extra rights, and no more time or memory than you’ve allotted. Then even a malicious program can do only what those crumbs allow, which is next to nothing.

A poisoned well: backdoors

So far we’ve been fixing our own code and teaching our own people. But a program consists of more than your code: under it are the compiler, the libraries, the build tools, dozens of other people’s packages. What if the well everyone drinks from is poisoned?

This question was raised back in Chapter 52. Ken Thompson, in his 1983 Turing Award lecture, showed that a backdoor can be built into a compiler so that it inserts itself into every program compiled, and reproduces itself even in a compiler built from clean source. A backdoor is a deliberately left secret entrance, whereas a vulnerability appears by mistake. Thompson’s conclusion was harsh: checking the source isn’t enough if you don’t trust the whole chain of tools that built it.

In March 2024 this stopped being a thought experiment. The engineer Andres Freund was trying to work out why logging in over SSH on his test machine had started taking a little more processor time, a fraction of a second that he noticed all the same, and he dug up a backdoor in xz, a tiny and ubiquitous compression library. The supply-chain attack had been prepared for years. A person going by the name “Jia Tan” had helped develop the project since 2021, earned trust, became a maintainer, and then hid the backdoor in pieces. The payload itself went into the repository disguised as binary test files, while the altered build script that extracted it and wove it into the library was only in the release archives. Reading the source in the repository, you couldn’t spot the backdoor. The backdoor aimed at SSH and would have opened a secret entrance on a vast number of servers, had the infected versions reached the stable releases.

The defense against a poisoned well is the same one we talked about in Chapter 52: double compilation with independent compilers, and reproducible builds, where anyone can build the same bytes from the same source and compare. To them is added what worked in the xz case: open code that anyone can read, and an attentive person who trusts their own surprise. The xz story is also about social engineering, only stretched over years: trust in the new maintainer was built up patiently, while in the Twitter case a few phone calls were enough.

The law, ethics, responsible disclosure

Everything you did in this chapter is legal, because it happened on the course’s training range. Beyond its walls the rules are different. Testing someone else’s system without the owner’s explicit permission is a crime almost everywhere, even if you broke nothing and meant well. In the United States it is prosecuted under the Computer Fraud and Abuse Act, the law Morris was convicted under. Many countries’ laws also have separate offenses: unauthorized access to computer information, creating and spreading malware, interfering with critical infrastructure. “I only looked to see whether it was vulnerable” is no excuse: entering without permission is itself the offense.

For the second rule there is an accepted procedure, responsible disclosure, also called coordinated disclosure. Whoever finds a vulnerability first tells the owner quietly and gives them time for a patch, and only then goes public. The industry has settled on about 90 days; that is what Google’s Project Zero gives, for instance. That is how the stories you’ve met in the course were disclosed: language developers were warned before the talk about the attack on hash tables; Heartbleed was fixed on the day it went public, because it was known about in advance. Large companies pay for holes found (bug bounty programs), and so that the finder has somewhere to write, a site keeps a file at /.well-known/security.txt with a security contact. An ethical researcher works with permission, hits teaching targets and their own setups, and hands what they find to whoever can fix it.

From its first line the chapter has been about defense: how not to write a hole, and how a defense is built. Now you recognize in your own code the places where someone else’s data tries to become a command, and you know what to close them with: parameters, bounds checks, escaping, least privilege.

The range: tasks

Three targets: two vulnerable starters that pass simple checks and fall to an attack, and a password estimator to build from scratch. Fix them so that the useful part works and the attack stops; the tests check both.

What next

Take stock of the whole part. We taught the machine to keep secrets (Chapters 59–60) and to defend them against attack. But every defense in this chapter—the bounds check, the escaping, the parameters, the layers of rights, the rules for people—was thought up and written down by a human. The machine carried out our instructions to the last comma, fast and thoughtlessly. It has been that way all through the book: to count, to sort, to lay out routes, to encrypt, to recognize an injection in a string, we taught it with exact recipes.

But can the machine derive a rule by itself, from examples, a rule we couldn’t have written down? We’ll start with a simpler and more exciting question: can a machine be taught to play, that is, to choose a move when across the board sits an opponent who also thinks and wants you to lose? That question opens the last part of the book and the next chapter, a tournament of bots.