Slashdot Mirror
Xbox Private Key Distributed Computing Project
aeiz writes "The Neo Project has added "The Xbox Public Key Challenge" to it's distributed computing client. The aim is to compute the 2048 bit private key that Microsoft uses to sign Xbox media. If it is a success, modchips wouldn't be necessary. Now many Xbox hacking and scene sites have started groups in order to compete with one another." gee, only 2048 bits? No problem *cough cough*.
The story that dealt with this (as an add-on) isn't even off the main page yet. This is as much a dupe as this comment probably is by the time I press submit. sigh
Switch back to Slashdot's D1 system.
if you just try all possible keys, it would take 2^2048 attempts to try them all. it could be the first key you try but it could also be the last. on average you need (2^2048)/2 tries. you can measure how long it takes on average to try 1 key. multiply that by the number of tries, divide by the number of machines trying codes. and you'de get an estimate.
> 4. And in any case, buying the X-Box already helps Microsoft. The more units sold, the more games developed.
Nope. Remember the big story last month? Micros~1 is losing their ass on everything except Windows and Office. Obviously, Micros~1 makes money on each game license sold because all the cost is up-front with development. However, they're not going to be making money on the hardware any time in the near future. Therefore, people buying the X-box then not buying any games is pretty devestating.
"Isn't reverse engineering a company's hardware/cracking encryption a violation of the DMCA? I am not saying I support the DMCA but it would be a shame if unsuspecting people jumped on this project and had the FBI raid their house and throw them in jail."
Ah, here we go... US Code, Title 17 (copyrights), Section 1201 (part of the DMCA)
(reads it. reads it again.)
OK, I don't feel so smart anymore... But, the first part (a-1-A) of the section says:
"No person shall circumvent a technological measure that effectively controls access to a work protected under this title. The prohibition contained in the preceding sentence shall take effect at the end of the 2-year period beginning on the date of the enactment of this chapter."(This should be in effect now, since it was signed into law by Clinton in 1998)
but later in (f-1):
"Notwithstanding the provisions of subsection (a)(1)(A), a person who has lawfully obtained the right to use a copy of a computer program may circumvent a technological measure that effectively controls access to a particular portion of that program for the sole purpose of identifying and analyzing those elements of the program that are necessary to achieve interoperability of an independently created computer program with other programs, and that have not previously been readily available to the person engaging in the circumvention, to the extent any such acts of identification and analysis do not constitute infringement under this title."
Go read the whole thing (well, maybe it isn't recommended) but this *should* be legal... or... not. There is always the saying that if you cannot exercise a right, you don't have it. That was the tactic used with DVDs, even though you were allowed to make fair use copies, the use of CSS and Macrovision did not allow it to happen as easily. (No, I am not a lawyer.)
fair.org counterpunch.com truthout.com indymedia.org salon.com
eff.org guerrilla.net debian.org gentoo.org
That is slightly incorrect. For normal symmetric key ciphers (DES, AES, IDEA, Blowfish, etc.) that is how you do it. This, though, is RSA, which is a asymmetric key cipher. This means that you have access to the public key, and you know that the public key is the product (as in multiplication) of the two parts of the private key, N=p*q. So, when bruteforcing, you only need to try 2^1024 keys, which is a lot better, but still infeasible. There are nice ways of doing better, though. The largest effort I know of is when the RSA-155 (512 bit) challenge was factored in 1999, using more than 35 cpu years. This would take about 2^512 times as long...
-- Free speech is only free if your time is worth nothing.
I'm all for this effort, but as a pragmatist, I don't think that it's going to be very successful.
Check out these stats from a "similar" project
[paraphrased from the website...]
The RC5-64 project was able to brute force a key in 1757 days using 58,747,597,657 work units tested the winning key was found!
They completed 86,950,894 workunits on the best day. This is 0.12% of the total keyspace meaning that at the peak rate they could expect to exhaust the keyspace in 790 days.
The peak rate of 270,147,024 kkeys/sec is equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP machines or (to use some rc5-56 numbers) nearly a half million Pentium Pro 200s.
Over the course of the RC5-64 project, 331,252 individuals participated. They tested a toal of 15,769,938,165,961,326,592 keys.
So the real question is did MS make the key length long enough? Given the example of approx 5 years, seems like it's close.
later...
chad
I can't check it right now (the website is /.-ed), but the 2048 suggests we're talking about an asymmetric key in which case you're wrong. For an RSA key, about 10 additional bits double the strength of the encryption (instead of 1 bit for a symmetric key).
I think you made the same mistake than this other poster:
RSA != RC5
RSA is asymmetric, RC5 is symmetric.
Of course, it's still some 5*10^30 harder than a 1024 key...
I wouldn't say all numbers... You can obviouly eliminate numbers that end in 0,2,4,5,6, and 8, since they are even, and/or divisible by 5. So already, you've reduced the set by 60%.
Slashdot is like Playboy: I read it for the articles
OK. First, obviously this story is a duplicate... but don't mod me redundant just yet. The story is still on the front page, too. In any case, the same questions get asked here and are not being answered to the extent they were in the other discussion. So here:
1. Could anyone of you tell how much time/processnig power this will need in comparisson to things like the RSA challenge?
Thank you.
Answer: Somewhat more complicated.
2. Doesn't this violate that DMCA thingy?
Answer: RE: DMCA Anyone?
3. How is this done anyhow?
Answer: RE: Buffer Overflow...
I found these comments to be most helpful in the other discussion... certainly surpassing what I've seen here. Who can blame them: who wants to keep posting the same stuff over and over again, even if it is smart writing? Anyway, sorry for the whoring. I'll stop now.
Which, however, does not mean it's easy. RSA has been running the RSA Challenge for a few years now, the lowest prize being $10,000 for a 576-bit key and up to a whopping $200,000 for a 2048-bit key -- like the one in the Xbox. There have been no takers yet, and the largest RSA key cracked to date remains 512 bits. RSA's own estimate is that you would need 320 million 520 MHz Pentium-class machines to crack a 1024-bit key in one year, and we're talking 2^100 times that for a 2048-bit key!
Cheers,
-j.
Many comments here assume that the time to factor a composite integer N is proprotional to N, which is, happily, quite incorrect. Even by trial division, you only have to test prime divisors <=sqrt(N), and there are many far more efficient factoring methods.
RSA Security Inc. has quite informative FAQs on this subject, for example The RSA Factoring Challenge FAQ or What are the best factoring methods in use today?
A good paper, "A Survey of Modern Integer Factorization Algorithms" by P.L.Montgomery, can be found at Crypto World. It is slightly math-inclined but definitvely a worthwhile read for anyone interested in the topic.
Now for the bad news: 2048 bits can't be done today. Even GNFS, the best algo in town, has only managed to factor a 512 bits RSA key (and a 158 decimal digit number, with a 576 bits RSA coming soon, though) but 2048 bits will be million times harder. Right now there's no way to factor that, if Microsoft has chosen the primes for the key even remotely securely. I'm sorry to say that but with present technology, this project is a waste of time.
Alex
Heisenberg may have been here
Think again. The XB2 encryption key wouldn't be "in place of" the XB1 key, it would be "in addition to" the XB1 key. The XBox2 would 1)check if it's an XB1 or XB2 game, then 2) use the appropriate key. These are computers. We can do things like that with computers.
If a job's not worth doing, it's not worth doing right.
What part of that is so hard to understand?
It's hard to be religious when certain people are never incinerated by bolts of lightning.
RSA encryption works like this:
You pick two large primes, p and q; multiply them together to get N.
Then, arbitrarily pick an encryption key e (1 < e < N) and calculate the corresponding decryption key d (1 < d < N, d != e).
Make the set {e, N} public but keep d private.
Now, to encrypt a message M you calculate cyphertext C as follows:
C = M ^ e (mod N)
To decrypt, you calculate M' = C ^ d (mod N). The claim is, of course, that M' == M. (Notice that M' = (M ^ e) ^ d (mod N) = (M ^ d) ^ e (mod N), so it's really irrelevant which of {e,d} you make public.)
Anyway, from the public key, you know N and e and you want to figure out d. To do that you need to factor N into p and q (see above), then you can make an easy calculation to get d. Since p and q are primes, those are the only factors of N (other than 1 and N). Further, since we are talking about 2048 bit encryption (N >= 2^2048), the factors p and q can be up to 1024 bits long (2^1024). To brute-force the private key you need to go through 2^1024 (*) possible factors of N until you find one that works.
Now, suppose we have a computer that can check the divisibility of N 1000 times per second. It will need 10 ^ 298 years to go through all possible combinations (though of course it can get lucky and pick the right factor early on). If we have 1,000,000 of these computers, we'll still need 10 ^ 292 years, so don't hold your breath...
(*) It's actually less than 2^2048 because you only need to consider prime numbers, but it's still staggeringly large. Also, given a number x, it's not so easy to tell if it's prime (unless it's even). You need to use an algorithm to determine that, which takes time.
___
If you think big enough, you'll never have to do it.
No they can't. Each CD you pop in has to be signed by the private key (that only MS knows). The public key built-into every xbox is used to verify weather the CD should run or not. Which means there's only 1 public key, and only 1 private key. All CDs are signed by the same private key, and all xboxes are fitted with the same public key.
It's not possible to re-use a signature because any change in the code will change the signature. That's the whole point of a signature. Mod chips get around this by replacing the kernel (compressed in the bios) with a patched version of the kernel that skips the signature check. If we knew Microsoft's private key, we could sign our own software. This would allow people to install linux (or pirate games) without using a mod chip.
It might be possible to exploit a bug in the kernel or third party software that would allow us to transfer program control to our unsigned code, but nobody's found one yet. Given Microsoft's track record, I'm sure such a bug exists and will be found soon. With $100,000 up for grabs, there's a heck of a lot of people looking for it.
It's not Slander, it's Libel becuase the poster wrote it rather than spoke it in open forums.
The difficulty of breaking RSA keys depends on the assumptions you build into the model. Unlike DES cracking factoring does not neatly decompose with trivial parallelism. There are parallel algorithms but there is a tradeoff between the part you do on a loosely coupled parallel box and the part that requires a tightly coupled processor.
The rough equation that is generally used is 512 bits RSA is roughly equivalent to a 56 bit symmetric cipher. 1024 bit RSA is roughly equivalent to a 76 to 80 bit symmetric cipher and 2048 bit RSA is roughly equivalent to a 112 to 128 bit symmetric cipher.
This is on the basis that the breaks of 56 bit DES and 512 bit RSA came at arround the same time and used roughly equivalent amounts of processing. In fact there is a slight discontinuity since only half of the RSA calculation could be farmed out. The farming stage results in a heck of a big matrix that you have to invert which was done on a CM5 I seem to recall.
Unlike the DES challenge there is no chance that you just 'get lucky' after a very small number of trials.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
Therefore, people buying the X-box then not buying any games is pretty devestating.
Not really. Even given that MS is selling the unit for less than it costs them to make it, you're still giving them money.
Say it costs MS $250 to produce an XBox. They then sell it for $200. If you buy it, MS loses $50. If you *don't* buy it, MS loses $250.
If you don't like MS, it would be much more devastating if you just didn't bother with the XBox and instead invested in a PS2 or GameCube.
"Nine times out of ten, starting a fire is not the best way to solve the problem." - my wife