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*.
they can borrow my CPU power... an Athlon 1600... that should take care of... let's see... one trillionth of a bit?
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-
I don't remember just how large the key was for the last RSA challenge, but it certainly wasn't more than a kilobyte. If we assume it was a kilobyte, the difference in processing power required is a factor of 2^2048/2^1024 = 2^1024 ~= 1.8x10^308. So unless they've reduced the effective key size by a lot, there probably isn't enough matter in the universe to make the computers that would be required to break that key.
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.)
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.
Hate me!
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...
This is assuming the key has 2^2048 entropy. If that is so, it is hopeless, however if the entropy of the key is lower, which it is for many microsoft products, then it can be cracked in smaller amount of time. See Bruce Schreider's writings about this topic.
ato
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
Yeah, just remember Sega. Dreamcast was a great machine, but as soon as people were releasing cracked games that can be written to disc and run without a boot disc or mod chip, I'm pretty sure their income went through the floor. Too bad, it was an excellent system.
RSA is currently providing monitary awards for groups who can crack a larger RSA key than has been cracked before. Here's a quote from the FAQ associated with that contest:
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.
By the time it's brute forced no one will care about it anymore. I think there's a better chance with getting it leaked by some disgruntled MS programmer.
"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
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?
wrong, every xbox sold is another number than can add to their tally. The more than can say they have sold, the better their system looks to game developers. Whether or not any of these xbox owners actually buy any games or just hack it is irrelevant.
The more games and developers working on the xbox the better it will look in the market place. period.
-v
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?
You can be sure that nobody at MSFT will actually have the private key. They'll have a black box there with the key in tamper-proof silicon. You get authorization to see the box, you put in a finished XBE with no signature, you get back out a signed executable, you're escorted from the room.
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.
Straight up, we need to leave the Von-Neuman crap serving webpages and go straight to using a DNA matricies and a highly paralleled quantum system to work through solution sets instead of pushing a brute-force asymmetric namespace around. If we can use simple DNA we can manipulate massive datasets in realtime. Ackerman has probably danced around such ideas (he's the "A" in RSA) and avoided them in to avoid showing up on spook-radar and being forced to live in another country.
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.
Every new form of media has it's own Requirimento
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
Lasciate ogne speranza, voi ch'intrate
Why not connect the XBox processor to a state monitor and slow the CPU down to single clock steps, then probe the state of the CPU registers and memory buffers after the public key is read from the DVD-ROM when the primes calculation is made in the CPU to compare the public key against the private key ?