Xbox key defended by more than just length

[This article was contributed by LWN reader Tom Owen]

On Monday, this story was up on ZDNet with a dateline of 3PM Pacific. The Neo Project, an open source distributed computing effort, had started work to factorize the Microsoft Xbox public key. Just a few hours later, a little before midnight in Ontario, administrator Mike Curry posted this message on the Neo discussion board:

The Neo Project had spent six months grinding away on the RSA 576-bit factoring challenge while waiting for something worthier to come up. "Something worthier" turned out to be the Xbox Challenge, once Michael Robertson (Lindows and mp3.com) extended his offer of $100,000 for a procedure to boot 386 Linux on a Microsoft Xbox games console.

The games console business model was invented by King Camp Gillette as "razors and blades," but a better analogy for technical folks might be "printers and cartridges." The initial unit — razor, printer or console — is priced attractively regardless of the actual cost, and the profits are made on surprisingly expensive consumables. It takes technical subtlety and legal protection — to stop free-riding competitors. In the case of the Xbox, Microsoft charges a fat fee — many dollars per copy — to sign a game with the private xbox key; the console knows the public key and won't boot games signed by anyone else. Owners can fit so-called mod chips to bypass the check, but MS knows that most people won't poke around in the hardware. The Neo Project set out to crack the Xbox key to allow Linux to boot on an unmodified Xbox.

If the key only allowed booting Linux on the Xbox, Microsoft would probably not be too concerned. But that key would also allow anybody to sign any game, and thus bypass Microsoft altogether. And that, of course, is a direct threat to Microsoft's Xbox business plan.

The Xbox hacker site has an "unofficial quote" from a Neo Project source

So is Microsoft releasing its vicious assault lawyers in a desperate attempt to preserve the endangered xbox business model? Well, probably not. There was never any practical danger. One of the largest keys ever factored in public was the RSA 512 bit challenge, it took a few months work on a few hundred sub-500MHz class machines and nine days on a Cray. The 2048 bit Xbox public key is obviously more difficult, but it's truly astonishing just how much more difficult. RSA doesn't publish an estimate beyond 1620 bits, which they list as requiring a year with over 1000 trillion (1,000,000,000,000,000) 500MHz Pentiums, each with 120TB memory. Even the dotcom bust has not freed up that sort of hardware, so they expect this sort of key to stand for decades.

Instead, the Neo Project was hoping to get lucky; they were trying random keys in the hope that they might happen to hit the right one. In the day they were running, a few thousand machines tested almost a billion potential keys. Which is good progress, except that the number of potential keys is counted in a number with hundreds of digits. Odds like that make winning the lottery twice, or death in a meteorite strike into everyday occurrences. If they were really looking for a result "today, tomorrow or never," the smart money would be on never.

Microsoft -- assuming it was Microsoft -- bets with the smart money, but they shut down the Neo Project's Xbox effort anyway. It must take a firm nerve to keep faith in RSA and statistics when you learn that thousands of machines are working away on a lock that defends a future billion-dollar revenue stream. Compared with a risk like that, lawyers are cheap, even when they have to work nights.