ESR on Quake 1 Open Source Troubles

ESR as chimed in to say his bit on the recent quake problems that popped up following the source release. Its definitely a problem that will happen again and something that needs to be handled. Read what he has to say about it.

The following was written by ESR. You know who he is already ;)

The case of quake cheats The open-source community got a lump of coal in its Yule 1999 stocking from renowned hacker John Carmack, the genius behind id Software and such games as Castle Wolfenstein, Doom, and the Quake series. Carmack's .plan file noted a problem that has swiftly emerged since the Quake 1 source was released under GPL; it seems that some people have used their ability to modify the Quake client as a mechanism for cheating.

This may at first sight seem a trivial issue -- who cares if a few testoterone-pumped teenagers cheat at a shoot-em-up game? But in today's internetworked world, countermeasures against Quake cheating arguably provide an important laboratory model for cases that are decidedly not trivial, such as electronic commerce, securities trading, and banking.

The Quake model is made particularly relevant by its open-source connection. Open source advocates (including me) have been making a strong argument over the last two years that open-source software such as Linux and Apache is fundamentally more secure than its closed-source competitors. Cryptographers have long understood that no encryption system can really be considered well-tested until it has been energetically and repeatedly attacked by experts who have full knowledge of the algorithms it uses. Open-source advocates argue that there is nothing special about cryptography but its high stakes -- that, in general, open peer review is the only road to systems which are not merely accidentally secure by obscurity, but robustly secure by design.

Carmack, therefore, caused a bit of a flutter on Slashdot when he went on to to suggest that only a pair of closed-source encryption programs could solve the Quake-cheating problem. The problem, as he correctly pointed out, is that asking the open-source client to verify its own correctness won't work; a sufficiently clever cracker could always write a client that would simulate the right kinds of responses and then cheat.

A debate ensued, with several people pointing out that trusting the client half of a client-server pair is bad security policy whether the client code is open or closed. Fundamentally, there's no way for the server to be sure it isn't talking to a clever simulation of `correct' behavior. Thus, opening the source to Quake 1 didn't create security problems, it merely exposed one that was already present (and exploitable, and for all anyone knew already secretly exploited) in the design of the game.

Carmack weighed in to make clear that the Quake-cheating problem is subtler than many of the debators were assuming. It's not possible for a cheating client to give a player infinite ammunition or life points; the server does not in fact trust the client about these things, and manages them itself. This is correct design; whether or not it's open-source, a bank should not depend on a customer's client software to tell the bank what the cutomer's balance is!

Carmack observes that "the [cheating] clients/proxies focus on two main areas -- giving the player more information than they should have, and performing actions more skillfully."

The serious "more information" cheats depend on a performance hack. In order to hold down the number of updates of the Quake world it has to pass to the client, the server gives the client information about the location of objects and opponents that the player can't yet see, but might be able to see before the next update. The server then counts on the client not to make those things visible until they "should" be (e.g, until the user gets to a particular location in the maze the client is simulating). A cheating client can reveal an opponent seconds before the player would turn the corner and expose himself to fire.

The "more skillfully" cheats substitute the computer's speed and accuracy for tasks that the server and other players expect the player's hands and brain to be performing. Carmack talks about "aim bots" which automatically lock the player's gun onto visible opponents and fire it with inhuman accuracy.

And indeed it's hard to see how either of these sorts of cheats can be prevented given an open-source client and no way independent of the client itself to check that the client is honest. Thus Carmack's suggestion of a closed-source Quake-launcher program that would take a checksum of the client binary, communicate with the server to make sure the binary is on an approved list, and then handle communication with the server over a cryptographically-secured channel.

Carmack's argument seems watertight. What's wrong with this picture? Are we really looking at a demonstration that closed source is necessary for security? And if not, what can we learn about securing our systems from the Quake case?

I think one major lesson is simple. It's this: if you want a really secure system, you can't trade away security to get performance. Quake makes this trade by sending anticipatory information for the client to cache in order to lower its update rate. Carmack read this essay in draft and commented "With a sub-100 msec ping and extremely steady latency, it would be possible to force a synchronous update with no extra information at all, but in the world of 200-400 msec latency [and] low bandwidth modems, it just plain wouldn't work." So it may have been a necessary choice under the constraints for which Quake was designed, but it violates the first rule of good security design: minimum disclosure.

When you do that, you should expect to get cracked, whether your client is open or closed -- and, indeed, Carmack himself points out that the see-around-corners cheat can be implemented by a scanner proxy sitting between a closed client and the server and filtering communicatiuons from server to client.

Closing the source of the client may obscure the protocol between client and server, but that won't stop a clever cracker with a packet sniffer and too much time on his hands. Carmack confirms that even without the packet sniffer or access to source there are a variety of ways to flush out anticipatory information, ranging from tweaking the gamma and brightness on your screen to banish shadows to hacking your graphics card's device drivers to do transforms of the world model (such as making walls transparent).

We're back in familiar territory here; the history of computer security is littered with the metaphorical (and in some cases maybe literal) corpses of people who thought security through obscurity was sufficient. Crackers love that kind of naivete and prey on it ruthlessly.

The aim-bot cheat is trickier to prevent. The difference between human and aim-bot actions is measured only in milliseconds of timing. Changing the protocol to stop it from leaking information won't banish aim-bots; it would take the server doing statistical analysis of player action timings to even detect them, and (as Carmack points out) "that is an arms race that will end with skilled human players eventually getting identified as subtle bots."

Fortunately, the aim-bot cheat is also much less interesting from a general security point of view. It's hard to imagine anything but a twitch game in which the client user can cheat effectively by altering the millisecond-level timing of command packets. So the real lesson of both cheats may be that a closed-source program like Carmack's hypothetical secured program launcher is indeed a good idea for security -- but only if you're a hyperadrenalized space marine on a shooting spree.

(Any computer game at which computers are better than most humans has analogous cheats, some of which aren't even detectable in principle. Carmack observes "correspondence chess has been subverted from its original intent by players using computers." This isn't something security design can fix.)

If Quake had been designed to be open-source from the beginning, the performance hack that makes see-around-corners possible could never have been considered -- and either the design wouldn't have depended on millisecond packet timing at all, or aim-bot recognition would have been built in to the server from the beginning. This teaches our most important lesson -- that open source is the key to security because it changes the behavior of developers.

Open source keeps designers honest. By depriving them of the crutch of obscurity, it forces them towards using methods that are provably secure not only against known attacks but against all possible attacks by an intruder with full knowledge of the system and its source code. This is real security, the kind cryptographers and other professional paranoids respect.

It's the kind of security the Linux kernel and the Apache webserver have, and the kind people victimized by the Melissa and Chernobyl viruses and Back Orifice and the latest Microsoft-crack-of-the-week don't have. If you're betting your personal privacy or your business's critical functions on the integrity of software, it's the kind of security you want, too.

To recap, the real lessons of the Quake cheats are (a) never trust a client program to be honest, (b) you can't have real security if you trade it away to get performance, (c) real security comes not from obscurity but from minimum disclosure, and most importantly (d) only open source can force designers to use provably secure methods.

So, far from being a telling strike against open source, the case of the Quake cheats actually highlights the kinds of biases and subtle design errors that creep into software when it's designed for closed-source distribution and performance at the expense of security. These may be something we can live with in a shoot-em-up, but they're not tolerable in the running gears of the information economy. Avoiding them is, in fact, a good reason for software consumers to demand open source for anything more mission-critical than a Quake game.

Eric S. Raymond

Comments

Nitpicks

[CrusadeR]

Some issues with this article:

A) This is the Quake 1 source Rob, not Quake 3 :)
B) ESR states:

If Quake had been designed to be open-source from the beginning, the performance hack that makes see-around-corners possible could never have been considered -- and either the design wouldn't have depended on millisecond packet timing at all, or aim-bot recognition would have been built in to the server from the beginning. This teaches our most important lesson -- that open source is the key to security because it changes the behavior of developers.

I fail to see how if Quake had been open source software from the beginning, how the situation would be any different. Quake is a fast action game that is often played over connections with high latency, the dependency on "millisecond packet timing" is inherent to the game itself due to how quickly entities manuever in the game world. Similarly, trying to build aim bot detection into the server from the beginning, as you suggested, would run into the same wall its hitting now: some players have enough skill that some form of statistical analysis would conclude they are using an aiming proxy.

Re:Nitpicks

[WNight]

Designing Quake in open source wouldn't solve the problem of writing aim bots. Aim bots take that knowledge the play has, or could easily have (by looking behind them) and acting upon it.

But, designing Quake as open source, and seeing how easy a hack like making players show through walls, for instance, would be could be expected to lead to different design choices.

Quake uses the PVS and PHS (potentially visible/hearable sets. The PVS is the list of all 'areas' visible from the player's location, and the PHS is the PVS and all PVSes...) for knowing when to send information about one player to the next. In some fairly connected levels, the PHS is *huge* and the client knows where the other players are far in advance. This could be changed to use an algorithm to determine the quickest route for both entities to take before being visible to each other, and if that's under the update delay (ie, likely to happen before the next upate) then the information would be sent. Otherwise, it wouldn't. Thus, cheaters would have a much smaller window of opportunity.

One other 'bug' is that if the player models are replaces with a big pointy model, where each axis has a big arrow, you can see these arrows far ahead of the actual player, even through walls and floors (in the other player is in your PHS). Writing the code, in many spots, to generate errors if the models were above a certain maximum reasonable size, and if they passed through world brushes, would make this a non-trivial hack, unlike now where you load the models into an editor, add a couple of points, and boom, can see people through walls.

The skin, the image that wraps around the wireframe, can be altered. A white skin naturally shows up better in shadows than a dark one. In Quake some colors are 'full bright', meaning that they 'emit light'... A skin made up on these literally is visible in complete darkness. If they changed the renderer to not use these drawing modes for characters skins, this would eliminate this easy for of cheating. A skilled programmer could add this in, but it would take a lot more work than simply opening up MS Paint and flood-filling a PCX...

Also, the design of the basic game could change a little. Quake 1 had few instant-hit weapons. The shotgun and the lightning gun are the only ones. Bots of course favor instant-hit weapons because they don't have to predict the enemy's movements, they simply line up the crosshairs and fire. The shotgun isn't a big deal because it's fairly low damage and the spread makes it less effective at medium or long range. The lightning gun is a Quake1 bot's favorite weapon. Knowing this, they could have designed the game to reduce the effectiveness of the lightning gun in such a way.

Perhaps it's heavy and induces some movement lag on the character, preventing instant-turn shot... These are many ways the game could have been changed to prevent there from being a perfect weapon for the bots. And really, the lightning gun, and later the railgun, are no-brainer guns. All it takes are reflexes and a fast computer/vid card. Other weapons take thought, to predict the enemy movements, something a bot isn't good at.

There are *many* design changes they could have, and pretty well, would have to have made, if Quake 1 was designed with open source in mind.

Nice handwave

[Tim Behrendsen]

Fortunately, the aim-bot cheat is also much less interesting from a general security point of view. It's hard to imagine anything but a twitch game in which the client user can cheat effectively by altering the millisecond-level timing of command packets. So the real lesson of both cheats may be that a closed-source program like Carmack's hypothetical secured program launcher is indeed a good idea for security -- but only if you're a hyperadrenalized space marine on a shooting spree.

Uh, with all due respect, THAT IS THE MAJOR PROBLEM!! You in essense admit that this problem is unsolvable, then go on to say that it's really not a problem that anyone that's important (to you) cares about. Well, trivializing the problem by mocking quake fans doesn't make the problem go away, and it doesn't change the fact that open source has made the problem infinitely worse.

Then, of course, you go on to conclude that open source is the ultimate answer (while giving no evidence).

ESR, normally I'm with you, but this essay was major smoke and mirrors.

---

Here's a similar problem from the vlsi cad world

[taniwha]

People want to be able to distribute encrypted IP (chip designs) to customers for simulation. There are a couple of reasons for this - IP providers want to protect their product - and they want to protect themselves from liability should the customer change the source and then blow a lot of money on building a bogus chip.

Traditionally this problem has been handled in a closed source world with a public key/private key sort of setup with the private key (for decryption) and encryption algorithm embedded in the compiler binary somewhere.

This leaves the IP provider's product at the mercy of the vendor of the CAD tool

A few years back this all fell apart for Verilog, a popular simulation compiler, for various reasons the language runtime is extensible, it was also interpreted - this left a version of the compiler which contained symbols. An anonymous poster to comp.lang.verilog pointed out how to write a gdb script that set a breakpoint in 'yylex' and extracted the decrypted token from IP.

All hell broke loose .... eveyone who'd ever sent encrypted IP to customers was now open to the world...

So - back to the topic - does anyone have any idea how one can do this sort of thing in an Open Source world - send people secret stuff to be used by an OS program without giving away the secret? Given that the only schemes I've seen to do this rely on security-by-obscurity (as above) I suspect it just can't be done.

This argument has been hashed out before

[jd]

And the conclusions were much the same. That time, it was with cheating on Netrek. (Script Kiddies seem more interested in big numbers than learning skills.)

The solution there was to distribue the source as Open Source, but only allow "blessed" binaries to connect to "blessed" servers.

This hasn't been fool-proof. Plenty of people have cracked Netrek's security, and whilst it's good at keeping the drearier riff-raff out, all that really does is give you a better class of riff-raff. It doesn't solve anything.

How, then, to prevent cheating? That depends on how much the client does, and what counts as cheating. The server can always prevent cheating, with anything under it's direct management, by simply controlling throughput. No more than N operations per unit of time effectively prevents souped-up clients with super-human reflexed, for example.

Controlled throughput also gives you much better Quality Control, as you can effectively ensure that no connection suffers undue lag at your end.

As for anything else, this calls for the ability to access points in the code by address. If you can do that, then the server can call routines to check for validity in a way that can't easily be bypassed by simply rigging the checks.

Stopping AimBots - a possible solution.

[SuperKendall]

I think ESR has got it wrong, the AimBot is by far a much worse problem than a player being able to see around corners - a good player essentially can tell where people are anyway based on sound cues or knowing how far behind him someone was. It might give a slight advantage, but not the godlike ability to clean out a room that an AimBot gives.

However, I thought of a possible solution - one way to stop AimBots might be for the server to send a few "fake" players to the client with either transparent skins, or embedded in the walls, or perhaps randomly "clone" the user just behind himself every now and then. A real player would never see these "shadows" but an AimBot would fire at these pahntom targets and that could trigger the server to shut him down.

As an added bonus, an AimBot set to use the rocket launcher firing at a fake target a foot away would bring a little justice to the bot user.

Security through obfuscation...

[David A. Madore]

...is just something that has never worked, will never work, and cannot work. Every now and then someone tries to use it (the DVD Consortium for example), arguing that ``yes, in general security through obfuscation is bad, but in this particular case it will work''; wrongo: it always fails.

This is made abundantly clear in Bruce Schneier's famous book on cryptography.

This is not an open source vs. proprietary software problem, it is a disclosed source vs. obfuscation problem. This is not an ethical issue, it is a completely practical one, and it seems that the lesson needs to be learned one more time.

Carmack's suggested closed-source binary loader can be spoofed much more easily than by using a proxy. Indeed, it contains an obvious race condition: how is the loader to check that the program hasn't been altered between the time it is checksumed and the time it is run? A simple ptrace() should do the trick for that, and, in fact, anything invented along similar lines.

As another poster pointed out, what we need is to have Quake clients act as simple 2D rendering clients. But that means the server would have to perform all the 3D calculations and that is hopeless. We want the client to perform the calculations without being able to spoof them; so the problem amounts to the following:

(``Computing in `hostile environment' ''). You are given a powerful computer and you want to use it to perform a computation. However, you cannot trust the computer. You want to perform the computation in such a way that the computer should be (a) unable to fool you (i.e. give a wrong answer and make you think it is the right answer), and (b) unable to learn anything from the computation (in the Quake case, learn more than the final, 2D, result). The computer can refuse to carry out the computation, of course, and you cannot prevent this, but it cannot make you think it carried out the computation whereas in fact it is fooling you.

This is a purely theoretical problem, and it has been studied. A cryptologist told me (but was unable to give a reference, unfortunately) that the problem is solved in the theoretical sense: computation in hostile environment is possible (using strong crypto). This makes it theoretically possible to have a solution to the problem using just one secret key, stored on the server and everything else being disclosed (basically: the server sends the encrypted computation to the client, the client performs the computation without knowing what it is calculating, sends it back to the server, the server verifies that the computation was correctly carried out, and sends the decrypted result to the client). Unfortunately, this solution is completely unpractical (the bandwidth required is simply too large).

So, the Right Thing fails. IMHO, this is not, however, an excuse to do the Wrong Thing. If the problem has no solution, then the problem is not a problem!

And you people wanted to open the Windows source?

[Tony Hammitt]

Guess what would happen if the windows source code suddenly became open? All kinds of cracks would appear. We've just proven it.

They open the source for Quake1, and within days, there's people out there playing cheat clients. It wouldn't take even hours for the world's windoze boxes to all be cracked if they opened the source code. Anyone depending on windoze would simply be out of business.

You can't go from 'security' through obscurity to open source. That is the main problem. All of this other stuff about the details of how people cheat when it happens are not the core issue. The core issue is that the development model cannot change from closed to open source without exposing all of the security flaws. Suddenly there are thousands of eyes looking at the code for weaknesses where before there were only dozens (who were mainly interested in functionality, not security. Why should they care; it's closed source?)

So, how do we fix it? We could develop games entirely open source. Who's going to pay for that? People don't buy support contracts for games; they rarely buy the manuals.

We could try to convince Carmack to release the code in stages. Release the server code first to get all of the bugs and cracks worked out. Then release the clients after most of the hacks have been anticipated. This is still suboptimal, with optimality being the unlikely open-source case. Anyone have any better ideas?

Yes, I know, there are plenty of open source projects. They usually only have a dozen developers at most. I doubt they would pass a security audit. I know most open source net games are crackable, I've done it myself.

Maybe in the future they will give the code a security audit before they release it. They're doing this as a publicity stunt anyway, they might as well get the most out of it.