Xbox Private Key Distributed Computing Project 579
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*.
Well... (Score:3, Interesting)
But... (Score:5, Interesting)
-Majestix-
Re:Relating.. (Score:2, Interesting)
How is this thing done anyhow? (Score:5, Interesting)
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 */
Re:Gee... (Score:3, Interesting)
Hello, earth calling Salimma, do you copy? We're talking about Microsoft here. Either the public key is crackable within a few weeks or months or someone ought to leak this out to the media so MS shareholders can question MS why the products they use themselves are so secure, in contrary to the products they sell, because I have yet to see a Windows shipped with SSH 2 or similiar encryption based remote terminal capabilities. Let alone with an encryption which uses a 2048 bits key.
Consider this possibility... (Score:5, Interesting)
Step 2: Setup nearly hopeless, but technically legitimate project to crack the key.
Step 3: By sheer luck, one of your members 'cracks' the key a few months later.
So, if someone did aquire knowledge of the key by other means, they could cover their tracks by this subterfuge.
-Nad
Waste of electricity. (Score:5, Interesting)
Maybe you could hire a couple of ex-CIA sneaker types to just break through all the security on the Microsoft campus and steal the code.
-end sarcasm-
Really, this seems like a waste of resources. Unless someone gets really, fantastically lucky, the chances of breaking this key before the Play Station 5 is released [theonion.com] are about the same as getting hit by lightning 20 times on the way home from collecting your multiple Lotto winnings.
-Peter
Re:Relating.. (Score:4, Interesting)
Given the demo was last year, give it another year or so, and they'll have the beast large and stable enough to do the breaking in no time flat.
As an aside, an earlier q-bit demo had 25 ops in 9 nanoseconds ... which scales to about 25 billion hertz, kinda leaving most Athlons and PIVs in the dust. That's 8 orders of magnitude faster, which, by the way Moore's law is going, would still take several years to achieve with mainstream processors...
Re:How to Compute Key Cracking? (Score:2, Interesting)
It's your hardware, enhance it as you like (Score:5, Interesting)
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.)
Re:Gee... (Score:1, Interesting)
Re:Relating.. (Score:5, Interesting)
RSA is currently providing monitary awards [rsasecurity.com] for groups who can crack a larger RSA key than has been cracked before. Here's a quote from the FAQ [rsasecurity.com] associated with that contest:
Re:Gee... (Score:2, Interesting)
The reason it may help Microsoft is in quality and number of games created for the XBox. Which will then fuel more platform sales and games bought. People always say that game platforms wars are won or lost through the games, right? If the better games are created for the Xbox - and consquently, the XBox2 - then it will be more of a success in terms of platforms sold and games sold. Which then helps Microsoft.
Re:Relating.. (Score:2, Interesting)
Re:Consider this possibility... (Score:2, Interesting)
And it just uses simple DES 56-bit, with 16 keys, of which 4 is used only to encrypt key update messages, and the remaining 12 to scramble programs.
Re:How will they know when they crack it? (Score:5, Interesting)
By finding the primes 'p' and 'q' such that
p * q = n
where 'n' is from the public key '(e,n)'.
They will then be able to determine the private key '(d,e)' by solving the congruence
e * d =(congruent) 1 (mod (p-1)*(q-1))
The difficulty in breaking RSA is in finding the prime factors 'p' and 'q' from a very large 'n'.
see:
RSA encryption [wolfram.com]
Prime Factorization [wolfram.com]
Who the hell does that? (Score:4, Interesting)
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
Getting the right key is like winning the lottery (Score:1, Interesting)
It appears to me that a key this large could best be solved with a non-iterative brute force approach, that is if your goal is short-term (needs to be solved before the XBox's successor (XBoxNext) hits the streets)...
On second thought, maybe the lottery analogy is a bad one, because it may be similar to winning a thousand lotteries, anyone here know the right probability?
Re:Gee... (Score:2, Interesting)
The more games and developers working on the xbox the better it will look in the market place. period.
-v
Re:How to Compute Key Cracking? (Score:5, Interesting)
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.
Re:Relating.. (Score:3, Interesting)
At least, that's how I'd do it if I were in their position, since the key is the linchpin that's allowing MSFT to stay competitive by preventing unauthorized games or copying.
Re:Why brute force? (Score:3, Interesting)
If the key to the survival of the Federal Govt. rested on cracking a paltry 2048bit encryption key the NSA/NCSA would have it done in time to recive a bonus and loads of poorly documented funding for more happy-fun projects after lunch the same day. Of course I'm probably being optimistic, but I deal the plausibility card based on the idea that if the government could not somehow deal with RSA algorithms, they would be outlawed. For a time they were, but that seems to have passed.
And on a personal note, I would love to see the classification for the XBox go from "Game Console" to "Personal Computer" and see every single game they have for it pulled out of Blockbuster and every other rental location. Why you ask?
Because there are laws in the United States for what qualifies as a product you can rent software for. Computers, like the kind used to submit this reply, are ineligible for software rentals. Due to the accessories, Secondary storage, and shared software libaries like DirectX, the Xbox should be considred a computer and maybe even an example of Palladium in action.
Re:Difficulty of breaking RSA. (Score:5, Interesting)
Close, but no cigar. Much more than half of the RSA-155 factorization was farmed out. The General Number Field Sieve algorithm falls naturally into several phases. The first phase, polynomial selection, was run over several weeks on a number of computers and used 100 MIPS-years. The sieving phase, which accounted for about 90% of the computation, was spread over close to three hundred machines and took 15 weeks. The sieving used about 8400 MIPS-years.
The final three stages were not widely distributed, though the last was run on four different machines concurrently. I don't have details of the filtering stage but, based on personal experience, I suspect it was done on one or two machines and used less than a week of cpu time.
The linear algebra was actually done on the Cray C916 (not a CM5) at SARA in Amsterdam. It took 224 cpu-hours and 2Gb of RAM. The last stage, extracting a square root in an algebraic number field, was run on four 300MHz SGI processors and each job ran for around 40 hours.
Incidentally, the matrix stage doesn't require a single supercomputer. A parallelized version is being developed which runs nicely on a Beowulf-type cluster. I'll be starting the matrix for a 506-bit GNFS factorization on just such a cluster later this week.
Paul
Engineering approach to cracking the PKey (Score:1, Interesting)