## Xbox Private Key Distributed Computing Project 579

Posted
by
CmdrTaco

from the yeah-thats-gonna-work dept.

from the yeah-thats-gonna-work dept.

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*.
## Relating.. (Score:5, Insightful)

Thank you.

## Re:Relating.. (Score:2, Interesting)

## 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:Relating.. (Score:2)

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.I'm sorry, faster than what? Your post is unclear.

A billion hertz is one gigahertz.

## Re:Relating.. (Score:3, Insightful)

## Re:Relating.. (Score:2)

## Re:Relating.. (Score:5, Informative)

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...

## Difficulty of breaking RSA. (Score:5, Informative)

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.

## Re:Difficulty of breaking RSA. (Score:5, Interesting)

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.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

## Here are some clues. (Score:3, Funny)

bit 0 of p is a 1

bit 1023 of p is also a 1

OK that is 2 bits out of 1024, thats 1/512th of the total

## Re:Relating.. (Score:5, Funny)

Yeah, but there's always the chance you get lucky and happen upon it early, plus it's more likely that you'll crack this one than there is finding aliens in white noise (*ducks*)

## Re:Relating.. (Score:5, Funny)

er, i don't have a calculator on me...And you typed this post into a computer?

## Re:He's not using Linux, I guess... (Score:3, Insightful)

since I don't know of a calculator with a "How many digits, you reckon?" button.My calculator has one of those buttons... it's an Hewlett-Packard 11C, and the button is labelled "LOG".

## Re:Relating.. (Score:5, Informative)

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

## Re:Relating.. (Score:2, Interesting)

## 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:Relating.. (Score:5, Funny)

By that time, we'll all be playing Duke Nukem Forever on our Itanium-based systems running GNU/HURD and the Fesco windowing system. Open source software will have gone mainstream, giving us no reason to care about hacking the X-Box. Right?

## Oops (Score:5, Funny)

## Re:Relating.. (Score:5, Insightful)

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!1,757 days is nearly 5 years, meaning that the project would have had to have started five years ago in order to have already been finished. My memory of where, exactly, computers were in 1997-1998 (depending on when the project finished, I'm not sure) is a little fuzzy, but I remember that in mid-1999, a 700mhz Pentium 3 was considered "high end" and the average Dell/Gateway type of computer was running a low-end processor like a Cyrix at roughly 200-300mhz. By comparison, it isn't out of the ordinary to find a 1.6-2ghz processor in a consumer PC right now and the sort of geeks that would make up a decent portion of this project probably have much faster processors than that and a lot more RAM. In addition to that, if Moore's Law were to hold, processors would be improving by at least 2ghz per year from now on instead of the 500-700mhz that they were in 1999.

So really, doesn't the RC5-64 project essentially just show us the length of the race track without giving us any data about the speed of the cars that will be driving on it?

## 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:

while RSA-2048 should stand for decades.## Re:Relating.. (Score:3, Funny)

Oh, wait...

## Dupe ... (Score:2, Informative)

sigh## This one is simple (Score:2, Funny)

## Well... (Score:3, Interesting)

## But... (Score:5, Interesting)

-Majestix-

## Re:But... (Score:5, Insightful)

It's a good idea to read the DMCA (http://www4.law.cornell.edu/uscode/17/1201.html)

## Re:But... (Score:5, Insightful)

The private key isn't a mechanism? Isn't that the essence of DeCSS?

I think certainly distribution of the actual private key would violate the DMCA. But does distribution of keys which are

notthe private key qualify? I doubt it.## Re:But... (Score:2)

I think certainly distribution of the actual private key would violate the DMCA. But does distribution of keys which are not the private key qualify? I doubt it.Lol. So the effort to crack the key would be legal right up to the moment it succeeds.

No matter what the DMCA says, MS is likely to try and squelch this anyway.

## Re:But... (Score:2)

## Re:But... (Score:2, Insightful)

## How to Compute Key Cracking? (Score:2)

## Re:How to Compute Key Cracking? (Score:2)

## Re:How to Compute Key Cracking? (Score:4, Informative)

## 64Bits (Score:2)

Each key check should take about half the time, because SFAIK the main overhead is the 32bit -> 2048Bit math conversion.

Or am I talking out of my ass.

## Re:How to Compute Key Cracking? (Score:2, Interesting)

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.## Re:How to Compute Key Cracking? (Score:4, Informative)

publickey, 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 [rsasecurity.com], using more than 35 cpu years. This would take about 2^512 times as long...## Re:How to Compute Key Cracking? (Score:2, Insightful)

lastassuming the search stops on success... </irrestable extAttr="grin">## not quite (Score:5, Informative)

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.

## Re:How to Compute Key Cracking? (Score:2)

You mean all numbers between 0 and 2^2048 are prime?No, but is there a list of all prime numbers between 0 and 2^2048 ?

The computer doesn't know which numbers are prime, so it has to at least check 2^2048 numbers to see if they are prime and if they are it takes a bit longer to check if it's the right prime. you'll still end up checking all numbers.

## Re:How to Compute Key Cracking? (Score:2, Informative)

## Re:How to Compute Key Cracking? (Score:5, Interesting)

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.

## Re:How to Compute Key Cracking? (Score:2)

## Oh my, here we go again... (Score:4, Funny)

## That's not valid C! (Score:2, Funny)

[drew@localhost drew]$ cat > bitch.c

/* DUPE */

#include "duplicate_story.h"

#define DUPE

...

#ifdef DUPE

# include "standard_rant.h"

bitch();

#endif

[drew@localhost drew]$ gcc -ansi --pedantic -Wall bitch.c

bitch.c:1:29: duplicate_story.h: No such file or directory

bitch.c:4: parse error before '...' token

bitch.c.7:27: standard_rant.h: No such file or directory

## By the time you finish this: (Score:2)

## Re:By the time you finish this: (Score:2)

## Re:By the time you finish this: (Score:5, Funny)

By the time you finish this: There will be an XBOX 4By 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.

## In other news... (Score:2)

sceneis white hot. Nifty programs to manage your backups, play your media files, and even run linux are being updated daily, not to mention the activity in alt.binaries.cd.image.xbox The XBox was one hell of a gift this year.Woo Hoo

## Gee... (Score:5, Insightful)

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 [stanford.edu], SETI@Home [berkeley.edu], Mersenne Prime Search [mersenne.org] etc.

Grow up folks! Running Linux on a hacked X-Box is cool, yes, but this might be going too far...

## Re:Gee... (Score:5, Informative)

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.

## Re:Gee... (Score:2, Interesting)

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.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.## 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

## Re:Gee... (Score:5, Informative)

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.

## 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.

## Re:Gee... (Score:2)

because I have yet to see a Windows shipped with SSH 2 or similiar encryption based remote terminal capabilitiesRDP uses some nifty 128-bit encryption, couple that with a L2TP session with a big ass key, and you're probably doing pretty well. Throw on IPSEC and I'd say the packet is pretty secure.

You can keep increasing the key size forever if you want, but the main effect is more encrpy/decrypt overhead - not greater security.

## Re:Gee... (Score:2)

I'm sure Windows XP also has encryption turned on by default for its remote desktop. You just have to manually up it from 56 bit to 128, as long as both PC's can handle it.

## Re:Gee... (Score:3, Insightful)

## Re:Gee... (Score:2)

Like the one used by PGP and GnuPG: on Linux it would take input from

## Re:Gee... (Score:3, Funny)

Don't worry, the key's probably something like "Sony engineers suck donkey balls" written backwards ;)I'm imagining something more like, "one key to rule them all" :)

## Re:Gee... (Score:3, Informative)

I don't think that M$ could do this - this'd mean you cannot play old games on X-Box 2.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.## Some thoughts (Score:2)

## Hmmm... (Score:3, Funny)

## Xbox client (Score:4, Funny)

## I don't get it (Score:2, Funny)

In either case, you don't need the original key. Just get a good locksmithing set. I've never heard of a lock that big though.

All kidding aside however, I've seen a photo of an XBox with the cover off (don't arrest me.) It wasn't gruesome, but it is possible to get inside. What's this hoopla

## How is this thing done anyhow? (Score:5, Interesting)

The question is -- would one really

needto crack that key to fool the Xbox? I mean, readingallthe 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:How is this thing done anyhow? (Score:5, Insightful)

Would it be possible to re-use some already signed code from an existing game?You'd run into copyright infringement issues - the signed code would be property of the copyright owner, and redistributing it would almost definitely be illegal. No need to take chances; I'm sure Microsoft's IP lawyers are looking for any excuse they can to take this project down.

## Re:How is this thing done anyhow? (Score:4, Informative)

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.

## Interesting... (Score:2)

## Re:Interesting... (Score:2)

Going one step further and making sure that data is distributed to IP's from different regions of the world would also greatly reduce the chances of sabotage by a single entity.

But your point is still valid - reverse-engineering the protocol and poisoning the results wouldn't be difficult for a highly motivated and well-funded organization. At the same time, fighting through redundant processing would be very expensive in terms of CPU time.

## 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

## 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:Consider this possibility... (Score:3, Insightful)

If step 1 were accomplished by a leak from the inside, it would be a criminal trade secret violation: at least the leaker would go to jail if caught, and possibly any outsiders who were found to have "conspired" with the leaker. But you propose to do this and then try to cover the tracks. Well, let's see ...

Direct cracking of the key is hopeless, and your notion that it might be found by "sheer luck" is hopeless as well. Finding one key out of 2**2048 possibilities is not going to happen by sheer luck. After all, if you have one billion people working on the problem in parallel, and each person can try a billion keys per second, it will still take you 1e591 years to try all keys, and the expected time to find the key will be the time to try half the keys.

Sure, it's theoretically possible; it's also theoretically possible to suffocate because all the oxygen molecules randomly happen to find themselves on the other side of your room! (though the odds of this happening is a far bigger number).

Making a claim in court that you found the key in this way, if you didn't, will easily be discovered, and then you add perjury to criminal trade secret violation, plus conspiracy. Prepare to be in jail for a long time. And for what? So you can run Linux on an Xbox? Who the hell cares?

## 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:Waste of electricity. (Score:2)

Really, this seems like a waste of resources.Not if they manage to steal Janick's little black box on the way out.

## Theft is illegal (Score:2)

This would be under trade secret law.

## lol (Score:2)

## It's beyond hopeless... (Score:2)

## Only 2048 bits... (Score:3, Funny)

## 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.)

## "There's still hope" (Score:2)

What cracks me up about this dupe is that in the space of a few hours we've gone from "There's still hope: distributed computing can factor the public key" to "Only 2048 bits *cough*. Yeah, that's gonna work."

Pretty impressive flip, especially considering...wait for it...

these comments were both in articles posted by CmdrTaco.Yes, our beloved Cmdr actuallyduped himself!Ah Slashdot: there's still hope.

## Sigh... (Score:5, Informative)

1.Could anyone of you tell how much time/processnig power this will need in comparisson to things like the RSA challenge? [slashdot.org]Thank you.

Answer: Somewhat more complicated. [slashdot.org]

2.Doesn't this violate that DMCA thingy? [slashdot.org]Answer: RE: DMCA Anyone? [slashdot.org]

3.How is this done anyhow? [slashdot.org]Answer: RE: Buffer Overflow... [slashdot.org]

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.

## Wouldn't it be easier... (Score:2)

The object code for this must be readable somehow, and knowing microsoft it probably has some vulnerability, such as taking a few extra clock cycles to reject a key if it's partially correct, increasing as you get closer to the key.

Oh, btw, the legality of reverse engineering software for compatibility purposes is one of the very few rights that are actually enshrined in British law, so those of us who live in this jusridiction can find they key without falling foul of the law.

## RSA != RC5 (Score:5, Informative)

quiteas difficult as you might think.Which, however, does not mean it's easy. RSA has been running the RSA Challenge [rsasecurity.com] 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 [rsasecurity.com] is that you would need

320 million 520 MHz Pentium-class machinesto crack a 1024-bit key in one year, and we're talking 2^100 times that for a 2048-bit key!Cheers,

-j.

## Unlikely but an interesting idea... (Score:2)

Having said that though, that key is enormous, and the odds that they find this key before it becomes irrelevant are extrordinarily slim. Still, it would be interesting to see the nature of the shit that hit the fan if they did indeed get the key.

## I've Got a Better Idea (Score:2)

## How long (Score:3, Informative)

RSA Security Inc. has quite informative FAQs on this subject, for example The RSA Factoring Challenge FAQ [rsasecurity.com] or What are the best factoring methods in use today? [rsasecurity.com]

A good paper, "A Survey of Modern Integer Factorization Algorithms" by P.L.Montgomery, can be found at Crypto World [crypto-world.com]. 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

## Never happen (Score:3, Insightful)

If the encryption on the xbox is not broken (and it might be...) you will NEVER crack a 2048 bit key. If it took d.net 4 years to do a 64 bit key I argue that it will take 2^(2048/64) or 4 BILLION times as long to do the 2048 bit key.

Find another path, this one won't work.

## Two-step key solution... (Score:4, Funny)

## Lets try a little calculation... (Score:5, Insightful)

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

## Re:Lets try a little calculation... (Score:4, Funny)

003998376109373765758136618

074952085782319420248781372

917102669618547672588166152

008706652644606806303666902

892981235565930906683499598

519114104392953160204053596

115413517917473248413544519

032527313815387159252508549

cu ft, or

152753523670238916267372392021974920508126439

cubic miles.

13600000000 light years for the observed universe: 186000 mps * 3600 sph = 669600000mph * 24hpd * 365.25dpy = 5869713600000 miles per light year.

Thus, the farthest observed object is 79828104960000000000000 miles away.

The volume of a sphere extending from the Sun to this object 13.6b light years away is approximately 2034826806600032443575507615744000000000000000000

Therefore, your garage is

750695455626874385717573171328582959724588996

times larger than the observable universe. Damn, you own a LOT of land

## The Code (Score:3, Funny)

## The point really isn't to crack the key... (Score:4, Insightful)

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'llneverstop.Of course, we could all just not buy XBoxes, Windows, Office, and switch to unencumbered/open technologies, but... I digress.

## Re:hey (Score:3, Funny)

## Re:sounds illegal to me (Score:3, Informative)

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.)

## Re:sounds illegal to me (Score:3, Informative)

## calling all quantum computers (Score:5, Funny)

## 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]

## Re:How will they know when they crack it? (Score:2, Insightful)

## Re:Sigh. (Score:2)

These are just kids messing around with a stupid console - what you're suggesting would bring down our entire e-commerce infrastructure.

## 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.