Slashdot Mirror
Lindows CEO Funds XBox Hacking Contest
Kai writes "PCWorld.com recently posted an article on how Lindows CEO Michael Robertson is funding the 'Linux on XBox Hacking Challenge'. He was previously annonymous donor who donated $200,000 to the project. His donation will be split in to two prizes, one to who completes part A of the challenge, and the other to the who completes part B. Part A, running Linux on the XBox, has already been completed, but Part B, running Linux on XBox with no hardware modifications has yet to be completed. Part A of the challenge can be downloaded from Sourceforge." Without a bios change, it seems like part B might be a bit tricky. T. adds: Tricky, but not hopeless. Eric C. writes "The Neo Project recently updated its client so users can use free processor cycles to try and crack the private key that Microsoft uses to sign Xbox software."
somebody correct the SF link
lol. The article points to sourceforget.net, not sourceforge. Might want to fix that :)
Let me try to answer some of your questions. I might be wrong.. but lets see.
The reason why this key needs to be cracked instead of found on some chip in the xbox is...
There are two keys. Public and private.
The Private key is used to sign or encrypt something. And this key is kept somewhere with MS.
The Public key on the otherhand would be in the xbox. This key is use to checked that the correct private key would have been used to sign the software.
The public and private keys are related by some math fuction that's suppose to tbe one way. So with the private key you can generate the public key. But with the public key you can't easily tell what the private key was. This has to do with the difficulty of factoring prime numbers.
So to find the private key what you can do is use a random guess of the private key to sign a piece of data like "hello world" then check with the public key to see if the signature is correct.
This guess and check method is quite time consuming as you can imagine. There are other ways but I am haven't learn about those yet.
hope this answers your questiosn.
The key that Bunnie found was an RC4 key that was stored in ROM. He snooped it being read by the CPU. It was this key that allowed the current generation of hacked MS BIOSes found in modchips.
The key being discussed here is a 2048 bit RSA key used to encrypt a hash of executable contents. The executable file will not be run by the Xbox unless the decrypted hash matches that of the file being run. The effect of this is that only people who hold the correct encryption key can 'sign' executables so that the Xbox will run them. If you take a signed executable and change even one bit, the decrypted hash will not match and it will not run.
The public key for the RSA encryption has been recovered from the MS code and is available in the Documentation section of the Xbox Linux site. The bruteforce attack on this will involve trying to decompose this 2048-bit number into two prime factors which were originally multiplied together to form the public key.
If these numbers can be recovered then the owner of the numbers will be able to sign their own executables and the evil 'Microsoft Code Only' Xbox will have been definitively broken.
Catch: Get a running task into the system. Your best bet to do this without modchipping would, IMO, be to emulate XBox Live or another download system for a game. You can open the box and plug the drive into a normal IDE system - but it uses the ATA protocol's password mode - meaning you either have to crack the key or hotswap the drive after powering it up in an XBox.
... hah.
Catch: Get the task running. The XBox is essentially a single-process OS due to its use of unified memory addresses for all hardware.
Having looked at the problem for some time my suspicion for the best way to go about it would be a buffer overflow or other flaw in the saved game system, since you can put those on a memory card easily enough and copy it to the HDD. Tada, backdoor without requiring modchipping.
In the XBox, once you've got control of the CPU, everything becomes possible. The catch is doing that, since the kernel will not allow you to load an unsigned executable. At the same time, I'm sure that MSFT has quite thoroughly checked the Dashboard XBE on the drive for exploitable bugs...
He has said in interviews recently that he doesn't care which version of Linux is used to achive the goal. It just has to be repeatable. The idea is to prevent Microsoft from jumping ship from the PC to a closed MS hardware platform for PCs which would truely exclude other OSs from the marketplace.
http://www.forbes.com/newswire/2003/01/03/rtr83678 5.html
"There is no business justification; that's not why I did it," Robertson told News.com of his rationale behind the contest. "I did it because I thought people should have the choice to run the software they want on the hardware of their choice."
Robertson said that Xbox is designed much like a PC with a closed operating system run on Intel microprocessors. He argues that as it has done with PCs, Microsoft is trying to make its software the defacto operating system in gaming consoles.
"I think Xbox sets a dangerous precedent," he told CNET News.com.
That's my understanding too: if you can make your edits to an already-signed executable, and then twiddle unused bits until the hash matches the original again then your modified executable will be accepted.
Franz Lehner did have a look at this a while back, with a view to getting some guidence from the hash algorithm as to which bits to change where. The problem was that by design, the hash algorithm loses information in the form of arithmetic carries. It quickly becomes hopeless trying to keep track of what bits are known and what bits are Xs because of carry losses; very quickly the whole thing becomes Xs.
Even so, it seems likely that even randomly twiddling bits looking for a hash collision is massively more likely to give results than the direct factoring method.
When the XBOX starts up, it loads the hash of the header into memory and decrypts a 2048 bit RSA signature and compares this to the header hash. If it matches, the program proceeds and it loads another section and does the same thing. There is no way to get around this either than knowing the private key or a hardware modification.
The RSA signature used to sign/for comparison purposes used with Xbox execuatables is 2048 bits long.
Common secure internet traffic, carrying thousands of credit card numbers as we speak, uses 128 bit keys (almost always).
It's virturally impossible with today's computational power and methods to break a 2048 bit key. Even if you somehow had all the processing power of all the current distributed systems, it would still take many thousands of years to break using classical methods. You either need several thousand years or an optical/DNA computer whose concept hasn't been refined yet.
In case some of your forget: it gets exponetionally harder as the length of the key increases. It's not like you just have to search a 128 bit key space 16 times. There are fancy methods where by you can get away with knowing some of the key like differential analysis, but when you increase the size of the key the performance of those tend to fall off also where you have no increase over brute force and man in the middle attacks.
So don't even think about joining that futile brute force effort, because it will just waste your time. What Lindows should have done is hire a hit man/career criminal to break into Microsoft or a 3rd party who has the key and steal it. Or optionally pay off an Xbox developer or employee who has similar access. Either way, it would be both cheaper and actually give the real key, unlike all of this nonsense.
"I'll just chip in a bit for RedHat: I actually have that installed on my university machine." - Linus, '95
God, where to start....
"RSA requires that you have two true primes to generate they key but the problem is there is no known way to generate a 2048 bit true prime that can't be factored in the same about of time it takes to generate it."
Wrong. Entirely wrong in fact. You should read the Handbook of Applied Cryptography (kindly made available online here). See e.g. section 4.3. Proving a 2048-bit number is prime (I think you mean 2x 1,024-bit numbers, but....) should take a minute or two - not excessive for a one-off operation!
"forget it however there are several publications that indicate that the number of solid pseudo-primes that are 512 bits long is about 2^40 so its key strength is about the same as 40 bits."
Erm, where do you get this stuff from? What's a "solid pseudo-prime"?"Since we are talking about a 4x as many bits, a good guess of the strenght of a 2048 bit pseudo-prime would be about as hard as guessing a 160 bit DES like key".
Hardly - Certicom reckon that a 128-bit symmetric key is equiv. to a 3072-bit RSA key. Don't forget that, with symmetric keys, the strength usually doubles with each added bit of key material - the same isn't true for RSA or DH keys as there is now a sub-exponential algorithm for solving these problems....
The rest of your post doesn't get much better, but I'm off to eat sunday lunch now....Seriously, read HAC - it's good for you.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
We proved that the validation algorithm is fully known, by reverse engineering it and testing it on known good files.
The C app incorporating the test can be had from CVS at:
http://sourceforge.net/cvs/?group_id=54192
The module name is xbedump. This was work from Franz Lehner and Asterisk, based on the dump app by Michael Steil.