Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Microsoft

Xbox Private Key Distributed Computing Project 579

Posted by CmdrTaco 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*.
This discussion has been archived. No new comments can be posted.

Xbox Private Key Distributed Computing Project More

Xbox Private Key Distributed Computing Project

Comments Filter:

  • Relating.. (Score:5, Insightful)

    by Karamchand ( 607798 ) on Sunday January 05, 2003 @01:46PM (#5020190)
    Could anyone of you tell how much time/processnig power this will need in comparisson to things like the RSA challenge?
    Thank you.

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

      by Jimmy_B ( 129296 )
      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.

      • Re:Relating.. (Score:4, Interesting)

        by lrichardson ( 220639 ) on Sunday January 05, 2003 @02:10PM (#5020358) Homepage
        I'd like to point out that IBM's demo of the 7 q-bit machine last year involved factoring a number ... which seemed to me to be pretty explicit about one intended use.

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

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

            by fwr ( 69372 )
            Faster than a 3GHz processor, I assume, which would make it about 8 times faster, not 8 orders of magnitude. Plus, it's not taking into account how many ops a P IV or Athlon could do in one cycle...
        • No, it is about 8 times faster. That is a LOT less than 8 orders of magnitude.

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

        by szakacs ( 259230 ) on Sunday January 05, 2003 @02:21PM (#5020431)
        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.

        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:

        If the RSA crack took x^56 time, this one will need approx. x^2048.

        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)

        by Zeinfeld ( 263942 ) on Sunday January 05, 2003 @03:54PM (#5020896) Homepage
        RSA is a public key algorithm and so there are faster attacks than brute force. The difficulty of breaking an n+1 bit key is not twice the difficulty of breaking an n bit key.

        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)

          by Xilman ( 191715 ) on Monday January 06, 2003 @05:29AM (#5024181) Homepage Journal
          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

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

        by weave ( 48069 ) on Sunday January 05, 2003 @04:16PM (#5020985) Journal
        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.

        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, Informative)

      by cschieke ( 308178 ) on Sunday January 05, 2003 @02:18PM (#5020411)
      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

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

        by KilerCris ( 637493 )
        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.

        • Re:Relating.. (Score:3, Interesting)

          by Uller-RM ( 65231 )
          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.

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

        by Temporal ( 96070 ) on Sunday January 05, 2003 @04:26PM (#5021016) Journal
        So, for a 64-bit key, it took five years? Correct me if I'm wrong, but at that rate, won't the 2048-bit key only take about 5 * 2^(2048 - 64), or a little over 2^1986 years to compute? I think that's somewhere around 10^587 times the age of our universe.

        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)

          by Temporal ( 96070 ) on Sunday January 05, 2003 @04:38PM (#5021074) Journal
          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.

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

        by DarkZero ( 516460 ) on Sunday January 05, 2003 @05:20PM (#5021270)
        I know only a little bit about encryption, so I may be completely talking out of my ass here (and feel free to educate me if I am), but I noticed this one point that you mentioned:

        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)

      by interiot ( 50685 ) on Sunday January 05, 2003 @02:29PM (#5020481) Homepage
      Well, the 2048-bit key is an RSA key (see here [ph-freiburg.de]).

      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:

      • To date, the largest number of this type to be factored is 512 bits. It was factored in 1999 as part of the previous RSA Factoring Challenge, which this challenge replaces. See the announcement for information about this factorization. The 576-bit value is likely to be factored in the next year or so,
      • while RSA-2048 should stand for decades.

    • Re:Relating.. (Score:3, Funny)

      by pangur ( 95072 )
      It will take approximately 5 libraries of Congress.

      Oh, wait...

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

    by moonbender ( 547943 )
    The story that dealt with this [slashdot.org] (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

  • This one is simple (Score:2, Funny)

    by Anonymous Coward
    --- Begin Microsoft Private Key --- 666666666666666666666666666666666666666666 666666666666666666666666666666666666666666 666666666666666666666666666666666666666666 666666666666666666666666666666666666666666 ... ... 666666666666666666666666666666666666666665 --- End Microsoft Private Key ---

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

    by silvaran ( 214334 ) on Sunday January 05, 2003 @01:48PM (#5020213)
    they can borrow my CPU power... an Athlon 1600... that should take care of... let's see... one trillionth of a bit?

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

    by Majestix ( 41486 ) on Sunday January 05, 2003 @01:48PM (#5020214)
    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-

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

      by Tom7 ( 102298 ) on Sunday January 05, 2003 @01:56PM (#5020266) Homepage Journal
      Why would it? The relevant section of the DMCA only bans the circumvention of mechanisms that control access to a copyrighted work. The private key itself isn't such a mechanism, as far as I know, though programs that use it probably would be. The DMCA is a bit vague, but it isn't so vague that it outlaws every possible kind of "hacking."

      It's a good idea to read the DMCA (http://www4.law.cornell.edu/uscode/17/1201.html), because in fact Microsoft or someone probably would make DMCA threats against this kind of activity. In that case it's good to understand the law, because such a letter often sounds pretty convincing and scary!

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

        by anthony_dipierro ( 543308 ) on Sunday January 05, 2003 @02:02PM (#5020304) Journal

        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 not the private key qualify? I doubt it.

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

          • If they're smart they'll promote it. Getting anti-Microsoft fanatics wasting CPU cycles on a project which isn't likely to come up with anything useful for the next decade is a good thing for Microsoft.

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

        by 91degrees ( 207121 )
        You're quite right on the DMCA. They may try an attack based on something along the lines of trade secrets if this attack is actually succesful, but all things considered, it's a pretty secure mechanism, so hopefully MS sees it this way.
  • I've always wondered how one computes how long it would take to crack a key? For example, how long would it take an top of the line Athlon to crack that 2048 bit key?
    • It all depends - you could get it on the first try, or it could take trillions and trillions of calculations.

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

      by BorgDrone ( 64343 ) on Sunday January 05, 2003 @01:54PM (#5020256) Homepage
      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.
      • This is a usefull task for 64Bit machines....
        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.
      • 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.

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

        by bo-eric ( 263735 ) on Sunday January 05, 2003 @02:12PM (#5020371)
        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 [rsasecurity.com], using more than 35 cpu years. This would take about 2^512 times as long...
      • <irresistable> It is guaranteed to be the last assuming the search stops on success... </irrestable extAttr="grin">

      • not quite (Score:5, Informative)

        by RelliK ( 4466 ) on Sunday January 05, 2003 @03:12PM (#5020695)
        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.

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

    by stevens ( 84346 ) on Sunday January 05, 2003 @01:50PM (#5020229) Homepage
    #include "duplicate_story.h"
    #define DUPE

    ...

    #ifdef DUPE
    # include "standard_rant.h"
    bitch();
    #endif /* DUPE */
    • [drew@localhost drew]$ cat > bitch.c

      #include "duplicate_story.h"
      #define DUPE

      ...

      #ifdef DUPE
      # include "standard_rant.h"
      bitch();
      #endif /* DUPE */

      [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
  • There will be an XBOX 4. I'd stick with the modchips, kids. That said, good luck and way to stick it to them.
  • I just recieved my Matrix [xodus-chip.com] no-solder modchip and 120GB drive. The state of the Xbox scene is 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)

    by salimma ( 115327 ) on Sunday January 05, 2003 @01:52PM (#5020241) Homepage Journal
    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 [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)

      by archnerd ( 450052 ) <nonce+slashdot,org&dfranke,us> on Sunday January 05, 2003 @01:59PM (#5020288) Homepage
      > 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.

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

        by MrWa ( 144753 )
        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)

        by bogie ( 31020 ) on Sunday January 05, 2003 @03:12PM (#5020693) Journal
        "Therefore, people buying the X-box then not buying any games is pretty devestating."

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

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

        by Trogre ( 513942 ) on Sunday January 05, 2003 @06:13PM (#5021586) Homepage
        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)

      by Dark Lord Seth ( 584963 )
      1. Provided Microsoft uses a proper public key infrastructure, brute-forcing this thing could potentially take forever

      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.

      • Comment removed based on user account deletion
      • Actually, Windows 2000 Terminal Server has pretty decent 128 bit encryption - perfect for remote administration. And yet, Microsoft's "Remote Desktop" is still far more responsive than either VNC or pcAnywhere, both running with their default of zero encryption.

        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)

        by CaptainSuperBoy ( 17170 )
        Windows 2000 server ships with a strong encryption library including SSL and filesystem encryption. It also has terminal server which does remote access securely. Windows XP also comes with a VPN client. I'm sorry, what version of Windows have you 'yet to see' ship with encryption?
  • Apparently, this was suggested [ph-freiburg.de] last may on the Xbox-linux mailing list.

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

    by BitwizeGHC ( 145393 ) on Sunday January 05, 2003 @01:57PM (#5020271) Homepage
    Maybe with enough encouragement from a topless HAlle Berry, Stanley Jobson would be able to crack that 2048-bit encryption with a multi-headed worm!

  • Xbox client (Score:4, Funny)

    by BorgDrone ( 64343 ) on Sunday January 05, 2003 @01:58PM (#5020286) Homepage
    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.
  • If there's a computing project to distribe XBox's private key, then is it really private?

    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 ;x

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

    by Sesse ( 5616 ) <sgunderson@big[ ]t.com ['foo' in gap]> on Sunday January 05, 2003 @02:02PM (#5020311) Homepage

    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:How is this thing done anyhow? (Score:5, Insightful)

      by exhilaration ( 587191 ) on Sunday January 05, 2003 @02:25PM (#5020462)
      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)

      by greenrom ( 576281 ) on Sunday January 05, 2003 @03:35PM (#5020800)
      Here's how it works. Not all the data on the DVDs have signatures. Only executable code. Basically, there's a 256 byte field in the program header of executables that contain the signature. The kernel is designed so that when a program is loaded into memory, the signature is verified before control is passed to the application. If the kernel determines the executable doesn't have a valid signature, it won't allow the program to execute.

      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.

  • If the keys are distributed sequentially, then all Microsoft has to do is sign up with a bunch of rogue clients right around the time that it is about to get broken. If the keys are distributed psudorandomly, and the algorithm isn't public, then it's a bit harder, but Microsoft still could set up lots of rogue clients which wait 5 minutes (or whatever time it takes) and then return "failed".
    • Excellent point. I'd say the only solution to such a problem would be to send each possibility to be processed by 10, 20, or 100 different nodes, to guarantee that a small number of "rogue" clients don't discard the valid key.

      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)

    by Nad Maximus ( 234442 ) on Sunday January 05, 2003 @02:07PM (#5020336)
    Step 1: Aquire 2048-bit key by non-cracking means (hacking, leak from inside, etc)

    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
    • Apart from the cracking project, this is how D2Mac sattelite TV was "cracked" by the people who produces pirate cards. Money + leaks.

      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.

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

    by pschmied ( 5648 ) on Sunday January 05, 2003 @02:09PM (#5020349) Homepage
    Not that I'm condoning illegal methods, but wouldn't it be easier to start an account to bribe an MS worker to give the code?

    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

  • lol (Score:2)

    by LHN ( 599122 )
    The Neo Project cant even handle the slashdot effect, how are they going to crack a 2048 bit private key. Good luck fellas.
  • or otherwise does anyone think RSA would offer $200,000 [rsasecurity.com] to anyone able to crack a 2048-bit RSA key generated by them (exactly the same kind of key)?

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

    by Mulletproof ( 513805 ) on Sunday January 05, 2003 @02:18PM (#5020419) Homepage Journal
    Don't forget, there is always a number of people with more than enough time on their hands to pull this crap off... never underestimate the power of the bored stiff.

  • It's your hardware, enhance it as you like (Score:5, Interesting)

    by Morgaine ( 4316 ) on Sunday January 05, 2003 @02:22PM (#5020444)
    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.)

  • 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 actually duped himself!

    Ah Slashdot: there's still hope.

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

    by FosterSJC ( 466265 ) on Sunday January 05, 2003 @02:39PM (#5020531)
    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? [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.
  • ...to simply look for a bug of weakness in the key verification software that exists in every xbox?

    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)

    by jpatokal ( 96361 ) on Sunday January 05, 2003 @02:45PM (#5020567) Homepage
    First up, since many posters seem to be rather confused, RC5 is a symmetric algorithm while RSA is asymmetric, which are very different beasts. Asymmetric keys need about 10 bits more length to double their security, compared to only one for symmetric keys. Cracking a 2048-bit asymmetric key isn't thus quite as 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 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.

  • This is the first time that I've seen a distributed cracking project that actually tackles an interesting problem with practical real-world implications. All the RSA cracking contests are neat and all, but they don't really have a lot of practical impact on the world. This, if it succeeds would be huge.

    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.
  • How about we apply for a national foundation of the arts grant to purchase 10,000 XBoxes which will then be welded together into a giant Tux the Penguin sculpture and put on permanent display in Redmond, WA? A completely legal way to poke Billy Borg in the eye, if in fact Microsoft does sell the XBox at a loss...

  • How long (Score:3, Informative)

    by akruppa ( 300316 ) on Sunday January 05, 2003 @02:56PM (#5020618) Homepage
    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 [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)

    by TerryAtWork ( 598364 ) <research@aceretail.com> on Sunday January 05, 2003 @03:32PM (#5020784)
    Looks like they smartened up after DVDs lame 40 bit key was cracked.

    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)

    by jvl001 ( 229079 ) on Sunday January 05, 2003 @03:44PM (#5020843) Homepage
    Two-step key solution:
    1. Break into Bill G.'s office.
    2. Copy key from Post-It note on corner of monitor.

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

    by markbthomas ( 123470 ) on Sunday January 05, 2003 @03:47PM (#5020860)
    Let's assume we want to find the key in about one year.

    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:
    256191385014832313076443403480704210746 79812491847 0034501286984934080\
    5360450587494704242882065172 6173015536181603483336 1032784430099655323\
    2423908579595405498527942459 9902489291405217648393 6232454940842516362\
    7883076229723065910368797710 4019484459166088424059 6873702316740293441\
    5552151969860441431944756023 7127342032430926831573 9828884343009334529\
    2378237199258154020627668325 9628831104499868523479 9854643717630057264\
    7428213934658612248791246642 4010974519290044145762 9590988748658836010\
    6319531783273982390734283246 1834647652719112497108 8586363327032331220\
    1716731957297646596715233805 68862609019439636890

    That's a lot of machines. In fact, every person in the world would need to have:
    4088182880916853059137581913995608598938002 0574938 1512491823325275367\
    0039983761093737657581366182 3437132028369300928737 2136090488973662885\
    0749520857823194202487813723 5281529166119647272954 3623272112620364581\
    9171026696185476725881661520 6188703489047492973236 7903825810597884676\
    0087066526446068063036669029 6494498088117693882712 8484532375726579806\
    8929812355659309066834995984 8375737098966810233408 2736619960338101994\
    5191141043929531602040535969 8321364177283871960956 9923672820142531423\
    1154135179174732484135445198 3247750938845967420404 6551928328834053889\
    0325273138153871592525085498 7565463644
    machines.

    Good luck :)

  • The Code (Score:3, Funny)

    by sdjunky ( 586961 ) on Sunday January 05, 2003 @03:48PM (#5020868)
    Duh, Same as Bill's luggage... 12345

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

    by Lethyos ( 408045 ) on Monday January 06, 2003 @12:57AM (#5023466) Journal
    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.

Slashdot Top Deals

Two can Live as Cheaply as One for Half as Long. -- Howard Kandel

Close