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*.
Could anyone of you tell how much time/processnig power this will need in comparisson to things like the RSA challenge?
Thank you.
Ok this may be a stupid question, but doesn't this violate that DMCA thingy that everyone is all concerned about? Just a thought.
-Majestix-
--- I was far from home, and the spell of the Eastern sea was upon me. -Lovecraft-
1. Provided Microsoft uses a proper public key infrastructure, brute-forcing this thing could potentially take forever
2. This so that you can feel good subverting an X-Box by making it run Linux
3. By that time the hardware would be definitely obsolete, or X-Box 2 would be out with programs signed with a different key
4. And in any case, buying the X-Box already helps Microsoft. The more units sold, the more games developed.
5. There are tons of other worthwhile distributed computing projects to do out there - Folding@Home, SETI@Home, Mersenne Prime Search etc.
Grow up folks! Running Linux on a hacked X-Box is cool, yes, but this might be going too far...
Michel
Fedora Project Contribut
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.
All we need now is an xbox version of this distributed computing client. I'd love to see the xbox key cracked by a modchipped xbox.
The question is -- would one really need to crack that key to fool the Xbox? I mean, reading all the data on the disc would be way too slow, so it could only check a part of it. Would it be possible to re-use some already signed code from an existing game? What kind of code is signed, really? (All of it, just not the data?) And of course, how many buffer overflows are there in the signature verification code? =)
/* Steinar */
(This comment is of course GPLed.)
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.
nothing drives innovation like porn and piracy. bring on the flames.
Cracking keys is a very hands-off approach to improving your Xbox or any other device. You bought the hardware, it's yours, so enhance it to your heart's content by installing a hardware mod that makes it general purpose, or get it done for you by a supplier. Voiding the warranty is no issue if you value the extended specification.
It's no different in concept to any other kind of DIY improvements that you carry out at home --- absolutely everything that you buy has patents, trademarks, or other legal constraints, but in no other industry do they see fit to limit what you can do with items that you have purchased, simply because they can. It's your equipment, do with it what you wish. (If you were merely leasing the hardware then it would cost much less and they might have a case, but here they're trying to have their cake and eat it too, take your money for an outright purchase and still lay claim to controlling your possessions. That's simply not right.)
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
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.
By the time you finish this: There will be an XBOX 4
By the time they finish this, XBoxes will have evolved into higher life forms and be enslaving us all.
And I for one welcome our new X-shaped overlords. I'd like to remind them that as a trusted Slashdot personality, I can be helpful in rounding up others to toil in their underground deathmatch sessions.
Sometimes it's best to just let stupid people be stupid.
"Therefore, people buying the X-box then not buying any games is pretty devestating."
.001 percent. Somehow I don't think MS will be hurt by the 10-20 people who buy Xbox's but never buy any games for them. Let's not be silly in estimating how many people would actually consider doing this, its just not realistic. Although I guess its possible Larry Ellison has a stack of them in his closet out of spite.
Wealthy idiots who hate Microsoft? I'd venture the amount of people who 1) really want to run linux on Xbox and 2) Are never going to buy game for it, is on the order of
If you wanna get rich, you know that payback is a bitch
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.
Let's assume we want to find the key in about one year.
6 79812491847 0034501286984934080\2 6173015536181603483336 1032784430099655323\9 9902489291405217648393 6232454940842516362\0 4019484459166088424059 6873702316740293441\3 7127342032430926831573 9828884343009334529\5 9628831104499868523479 9854643717630057264\2 4010974519290044145762 9590988748658836010\6 1834647652719112497108 8586363327032331220\5 68862609019439636890
2 0574938 1512491823325275367\2 3437132028369300928737 2136090488973662885\3 5281529166119647272954 3623272112620364581\0 6188703489047492973236 7903825810597884676\9 6494498088117693882712 8484532375726579806\4 8375737098966810233408 2736619960338101994\9 8321364177283871960956 9923672820142531423\8 3247750938845967420404 6551928328834053889\8 7565463644
:)
The keyspace is 2^2048. This means that to find it on average in one year, we need to search (2^2048)/2 keys.
There are 365 * 24 * 60 * 60 = 31536000 seconds in a year. A current machine, say 2 GHz, will not be able to check keys any faster than 2 billion per second (in practice the number would be much lower than this, but it cannot be any higher, ignoring chips which can parallelise operations). This means we can check 63072000000000000 keys per machine per second.
This means we need:
( (2048^2)/2 divided by 63072000000000000 ) machines to participate.
That's:
25619138501483231307644340348070421074
536045058749470424288206517
242390857959540549852794245
788307622972306591036879771
555215196986044143194475602
237823719925815402062766832
742821393465861224879124664
631953178327398239073428324
171673195729764659671523380
That's a lot of machines. In fact, every person in the world would need to have:
408818288091685305913758191399560859893800
003998376109373765758136618
074952085782319420248781372
917102669618547672588166152
008706652644606806303666902
892981235565930906683499598
519114104392953160204053596
115413517917473248413544519
032527313815387159252508549
machines.
Good luck
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/
Correction: Apparently (according to another poster), you need to add 10 bits to an RSA key to double the strength of the encryption. It would actually only take a little over 10^53 times the age of our universe to crack. So, never mind about having Duke Nukem Forever by then.
Ok so I havent passed the discrete matchs exam yet, but doesn't numbers that are divisible by 5 end in either 0 or 5 (thus beeing eliminated already)?
Yes, that was also what was said.
Why not numbers that end in 0,2,4,6,8 AND numbers where the total sum of the individual digits is divisible by 3?
You can do almost that. In fact you wouldn't be looking on a decimal representation, but rather a binary representation. So computing the last digit of a decimal representation would take som computation time. Unless you are smart and keep the last digit in a seperate variable. Just adding one to a byte and starting from zero every time you reach ten would be a lot faster than computing the last digit every time.
But in fact we can be even smarter than that. Why keep the last digit of a base 10 representation? It would be smarter to save the last digit of the number in a higher base, because there will be a larger fraction of digits that can be ruled out immediately. For example the case of divisibility by three would be trivial if we kept the last digit of a base 30 representation rather than base 10. I'd even go as far as base 210, which happens to be the product of the first four primes. Only 48 of the 210 possibilities would have to be tested. That has cut the number of cases down to 23%
But we can be even smarter. Why even add only one each time, given the last digit we already know how many times we will have to add one before reaching the next candidate. So rather just keep an array telling us how much to add each time, then we don't even have to remember the last digit, but just an index in an array with 48 bytes.
But why stop at base 210. Take another two primes and make the base 30030, only 5760 of those would have to be tested. So we would be down to 19% of the original search space. But here we notice that increasing the array by a factor 120 only saved us a few percent. And in fact each time we add another prime the size of the array grows faster and faster while the gain in reduction of search space gets smaller. So as soon as we hit the size of the L1 cache, we will probably gain no more. All in all we might have cut the search space by a factor four, maybe five or six, but no more.
But for a problem of exponential complexity cutting the time usage by a constant factor doesn't really help. All our efforts to avoid candidates that are obviously not prime can be defeated by just using a key five bits larger. Those five bits would be enough to make the problem harder than before we used those tricks. And the price for those five bits in normal use of the key is close to nothing. In fact they already did add another five bits and then again some more.
But we can be even smarter, first of all we obviously only have to verify divisors up to the square root of the number. Of course we'd already just do that, because we would be starting from zero and going upwards.
But we can be even smarter, because trial and error is absolutely not the fastest way to factorize products of large primes. Other techniques like quadratic sieve would be a lot faster. And then all our smart ways to avoid obviously nonprimes is not usefull at all. The way to actually factorize is completely different.
Do you care about the security of your wireless mouse?
If it did, that'd be great, but it never will. The point however, would be moot if a genuine attempt was not made.
The point is thus: to resist technologies that limit what consumers can do with what they legally own.
Microsoft is a very visible example of an entity trying to tell consumers "you may not do this or that with what you have purchased." In no other industry (save the closely related entertainment industry in this case) do there exist similar shenanigan. If I purchase a computer, I should be damn well permitted to run any type of software on that computer I see fit. The XBox, amongst consoles, is the closest device to a personal computer you can get. And yet, the manufacturer is trying to make it impossible for you to use it how you see fit.
This project is a protest of such consumer-unfriendly tactics. They will never crack the key, but they are still trying and Microsoft as well as many others will be well aware that they are trying. This is resistance. Microsoft, we will put forth the same effort against DRM technologies like Palladium. We'll never stop.
Of course, we could all just not buy XBoxes, Windows, Office, and switch to unencumbered/open technologies, but... I digress.
Why bother.