Distributed computing-project poogt Xbox te kraken

News.com meldt dat het distributed computing-grid van The Neo Project bezig is met het kraken van de Xbox-encryptiecode. Met deze code in de juiste handen zou het een heel stuk makkelijker zijn om Linux te laten draaien op het apparaat, iets wat $100.000 kan opleveren. De kans dat de code op deze manier gekraakt wordt is echter miniem. Het RC5-72 project van Distributed.net probeert een 72-bit lange sleutel te kraken door bruutweg alle mogelijke combinaties te proberen, en met de huidige snelheid zou dat nog zo'n 3000 jaar duren. De Xbox-bootrom is echter met 2048-bits gecodeerd, en zal volgens de kansberekening pas gekraakt zal worden als de zon de aarde allang heeft verzwolgen. De starter van het project is iets positiever:

More than 3,500 Neo users were working on the Xbox project as of Monday morning, according to the project's Web site, and had already eliminated 776 million possibilities for the encryption key. [...] "The Xbox public key is 2,048 bits and nearly impossible to crack with today's methods in a reasonable time," project founder Mike Curry said via e-mail. "So, with that said, we decided to use a random method...that could send a result today, tomorrow or never."

Reacties (114)

Het is nu wel duidelijk dat brute-force-cracking weinig nut meer heeft.
Men kan beter, vind ik, een andere kraakmethode zoeken.

Ik dacht aan een ramkraak

Maar even serieus, voor $100K is toch wel iemand om te kopen die de code kan leveren?
Want MS heeft de code waarschijnlijk gewoon op een machine staan, ze moeten toch af en toe die codes maken. Dan moet er ook iemand toegang tot hebben.

* 786562 TheGhostInc

Wat zou dan anders kunnen gebruiken? Heuristiek zou te veel op reverse enginering lijken...

Ach, mensen kopen ook nog steeds loten voor loterijen en ik denk dat de kans om daar $100.000 mee te winnen vaak net zo klein is...

* 786562 PowerFlower

In de Staatsloterij is de kans op de jackpot, die aanzienlijk hoger ligt dan $100.000, ongeveer 1 op 10 miljoen (bron: Volkskrant.nl). De kans dat je een key vind in een space van 2048 bits is 1 op 3,2 E+616. Natuurlijk kan je wel vaker dan eens per maand meespelen. Stel dat je met je P4 2GHz elke klok een key controleert Dan haal je 5 E+15 keys per maand. Dat mag je dan van mij ook nog vermenigvuldigen met de 3500 deelnemers aan het project.

edit:

Bronvermelding, ik had het immers ook wel uit mijn duim kunnen zuigen.

Tja, hoe dan ook blijft de kans groot dat het erg lang duurt voordat de sleutel gekraakt is. Bij zo'n RC5 project is dat niet zo erg, maar in dit geval zal de XBox waarschijnlijk allang dood en vergeten zijn voordat de BIOS gekraakt is. En dan heeft het niet echt bepaald veel nut meer

De aarde is dan al aan zijn einde gekomen, ik weet niet hoelang deze actie nog duurt, maar ik denk dat het al vergeten is als je dan met een XBox met linux aan komt. Dan krijg je meer dan $100.000, voor het vinden van bewijs dat er vroeger op een planeet 'aarde' (200 miljoen jaar geleden) intelligente wezens hebben bestaan die zich in holen vermaakten met groene dozen . En dan krijgen we op tekeningen hoe we eruit zagen allemaal klauwen van 10 cm lang omdat de controller zo groot was .

\[typo's]

nou hoeveel powercows hebben niet aan andere numbercrunchers meegedaan, kijk maar naar de
distributed kracht van:

www.setiathome.ssl.berkeley.edu

Als er een paar duizend screensavers draaien kan je wel wat keys proberen lijkt mij.

ach het is altijd effe leuk om ome bill op deze manier te plagen

#### DUBBEL POST ### sorry te snel geklikt

Hoe lang zou het duren als je met elke pc op de wereld mee zou doen om die code te kraken?

laten we er vanuit gaan dat (miljardje meer of minder maakt dan niet uit) er 6 miljard pc's zijn, 6 miljard pc's, wie vult me ff aan? want hoeveel key's kan 1 pc per dag controleren?

6 miljard x <aantal key's per dag> = <aantal dagen dat het duurt voordat key gekraakt is>

is wel leuk om uit te rekenen.

in het stukje staat dat 3500 users nodig waren om 776 miljoen mogelijkheden af te gaan, dit deden zij vanaf vanmorgen, dus laten we zeggen 8:00 uur tot 23:00 = 15 uur

in 15 uur 800 miljoen keys met 3500 users

dus 6.000.000.000 miljard users in 15 uur hebben dan 1.330.285.714.285.714 keys

1.330.285 miljard keys in 15 uur, is 2.128.457.142.857.142 keys per dag (24 uur)

totaal aantal keys wat afgegaan moet worden = (2,048 bits hoeveel mogelijkheden zijn dat?)

Aantal dagen dat ze er over doen = (2.128.457.142.857.142 delen door (2,048 bits in volledig getal)

linux bc:
2^2048
32317006071311007300714876688669951960444102669715484032130345427524\
65513886789089319720141152291346368871796092189801949411955915049092\
10950881523864482831206308773673009960917501977503896521067960576383\
84067568276792218642619756161838094338476170470581645852036305042887\
57589154106580860755239912393038552191433338966834242068497478656456\
94948561760353263220580778056593310261927084603141502585928641771167\
25943603718461857357598351152301645904403697613233287231227125684710\
82020972515710172693132346967854258065669793504599726835299863821552\
51663894373355436021354332296046453184786049521481935558536110595962\
30656

2^2048/2128457142857142
15183301284577503638102169531633342215429412887139019598460973799048\
95408732804650894712023792817385688778278669300549446651881121713939\
31740284290123964391386779300868329712138793965615975923555594778950\
71051219851060188252097924686828566161732261749991173442723410333927\
57245900783023421979843487226951899726224007629888722335664205455832\
03530287236628279620770837774231562530774554178168338081831612530082\
10555210584949679501882783489327516418836368345799205570554120663405\
36168336555520727680811436983149826254316369565557587907090074641349\
5395063529574056163104677435806586652801147008198914820786

dat zijn aardig wat dagen lijkt me.

maar als iedereen al zijn PC's/computers/mainframes inzet kan het wellicht een factor 1000-1000000 sneller. wat betekent dat je er 3 to 6 getallen mag afhalen....

1000-1000000 sneller. wat betekent dat je er 3 to 6 getallen mag afhalen....

En dan kun je de versnelling van de hardware in de komende 200 jaar erbij kwakken, dat zal gemiddeld misschien een keer of 1.000.000.000.000.000X zijn, en dan nog.

Over 10 jaar (dan zitten hun op 0,0000000000000000
0000000000025 % van de keys ofzo) zal microsoft die key zo aan hun geven....

Ze vinden het gewoon leuk, dan kun je zeggen; mijn pc werkt mee aan de xbox-linux crack.

\[devil-modus]
wat mooi lullig zou zijn, dat de microsoft in het geniep hun key nu gaat gebruiken om linux op de xbox te laten draaien. Dan kapen ze mooi dat geld weg........weg actie,weg irritatie voor microsoft, maar dat doen ze toch niet ......
\[/devil-modus]

Iedere processor verschilt weer op snelheid en dus de snelheid waarmee 1 key wordt getest . En aangezien de snelheid steeds meer wrodt , kan er dus steeds meer keys worden verwerkt en dus hogere scores. Het is gewoon een kwestisch van een paar jaar .

snelheid is niet echt van belang, als je pc hebt met paar gig ram dan gaat het sneller

eh mis ik nou iets? het aantal keys per minuut dat op je pc kan worden berekend is puur cpu afhankelijk hoor. sinds wanneer voert je geheugen berekeningen uit?

Ja, maar mr0 heeft een 3×86 met 10GB EDO-RAM en daar wil hij graag mee opscheppen

Inderdaad: dit is geheel cpu afhankelijk. Een beetje meer geheugen helpt wel omdat je pc dan minder hoeft te swappen (2048 bits neemt nog wel een beetje in). Boven de 512MB zul je het verschil echter niet meer merken denk ik...

Je gaat er automatisch vanuit dat iedereen op deze aarde een pc heeft

Je moet ook niet vergeten dat bijhoorlijk wat mensen meerdere pc's hebben.
En als het even kan kunnen ze de pc's op hun werkt ook nog gebruiken

Je hebt toch een computer?

////Edit: never mind

... totaal aantal keys wat afgegaan moet worden = (2,048 bits hoeveel mogelijkheden zijn dat?)
...

wel dat zijn er dus 2 tot de 2048 macht of 2 x 2 x 2 ... enz 2048 keer. = [admin knipje] om precies te zijn (nagerekend met Mathematica 4.2)

die jongen is echt wel optimistisch hoor

Als iedereen op aarde mee doet, zou microsoft dan niet ingrijpen?

Aantal dagen dat ze er over doen = (2.128.457.142.857.142 delen door (2,048 bits in volledig getal)

Dat lijkt me 1 gedeeld door het aantal dagen. En het lijkt me nog steeds heel veel daagjes. Er moet een veel betere methode zijn, ergens, somehow.

Wacht: Als we nu eens alle XBOX computers op distributed.net aansloten?
Of beter nog, aangezien er veel meer PS2 machines zijn (en Sony M$ best een ha(c)k wil zetten): laat alle PlayStation2 dingen eraan meerekenen.

Ik vraag me af of de maker heeft nagedacht over het volgende. Random number generatoren op een computer zijn altijd een pseudo random number generatoren, dwz de cyclus van zogenaamd random getallen die door de generator worden geleverd zal zich na een tijdje gaan herhalen. Oftewel je kan met random number generatoren op een computer nooit elk willekeurig getal van oneindige grootte genereren. RNG zijn beperkt in hun bereik waarin alle getallen ooit een keer gegenereerd zullen worden, en ik vermoed dat 2048 bits buiten dat bereik ligt.

Oftewel, het kan dus heel goed dat hun software nooit en te nimmer de key zal genereren omdat de key niet tot de hele grote verzameling van getallen ligt die de rng uberhaupt kan genereren.

<edit>

Wat netter geschreven.

Het blijven een rijtje enen en nullen, dus je hoeft alleen 2048 keer een 1 of een 0 pseudo random te genereren. Per key uiteraard.

En natuurlijk kan het sneller door het in grotere segmenten dan bitje op te delen.

edit:

Reactie op Skull26

Je redenering loopt stuk op 1 punt: Er wordt niet gebruik gemaakt van 1 random generator maar van een heleboel (distributed).
Bij een pseudo-random generator is de "seed" (zeg maar de beginsituatie) ervan de bepalende factor voor de gegenereerde getallen. Ik neem aan dat de bedenker van deze aanval wel ervoor heeft gezorgd dat niet honderden mensen met dezelfde reeks aan de slag gaan.
En ik denk niet dat er ook maar 1 computer zal zijn die zijn reeks volledig zal doorlopen als het gaat om een pseudorandom reeks met 2048 bits.

Er is de volgende conspiracy theory:

Men probeert momenteel op een illegale manier aan een key te komen (hacken, omkopen etc.). Als dat gelukt is kan men vanaf nu zeggen dat de key waar het mee lukt niet illegaal verkregen is maar dmv een toevalstreffer met dit project.

Best wel slim want als de key dmv een hack of diefstal bekend zou worden krijgt dit project waarschijnlijk een heleboel advocaten achter zich aan.

De kans dat je toevallig binnen relatief korte tijd met dit project de juiste code vind is zó klein, dat de rechter nóg met 'aan zekerheid grenzende waarschijnlijkheid' kan stellen dat de code niet uit dit project komt.

Dat is dan aan de rechter of advocaten... om dat te bewijzen dus..

zeer intersessante bedenking man :-) dat is iets voor de advokaten om weer in het stof te bijten ;-)

Is dit niet strafbaar onder de DMCA?

/quote van site
Everything done on this project is for the sole purpose of writing interoperable software under Sect. 1201 (f) Reverse Engineering exception of the DMCA.

Ramkraken vallen niet onder de DMCA

Tsjah, tenzij je mazzel hebt en de key toevallig na 1% berekenen al hebt gevonden/gekraakt dan is het leuk dat je de X-Box hebt kunnen kraken zo snel.

Maar kan ook zijn dat je pas bij 99% de key vindt...en dan heb je er dus al heel wat eeuwen op zitten (alhoewel natuurlijk ook de rekensnelheid per jaar verdubbelt in theorie, maar goed, dan moet je ook weer rekening houden met het feit dat niet elk jaar alle PC's die al bestaan verdubbelen kwa rekensnelheid )

Als je hem na 1% gevonden hebt, denk ik niet dat er nog Xboksen bestaan hoor

"The Xbox public key is 2,048 bits and nearly impossible to crack with today's methods in a reasonable time," project founder Mike Curry said via e-mail. "So, with that said, we decided to use a random method...that could send a result today, tomorrow or never."

Wat een briljant staaltje logica zeg, de beste methoden zijn niet snel genoeg, dus laten we dan maar de slechtste methode proberen. Als ze nou gewoon een goede Block Lanczos implementatie in elkaar zouden zetten met een efficiente siever zouden ze bij een groot aantal deelnemers nog een redelijke kans op succes hebben. Als ze slim zijn lopen ze eerst nog even wat testjes na voor de speciale getallen die wel makkelijker te factoriseren zijn.

Bij RSA verdubbelt het aantal mogelijkheden per 10bit, bij RC5 per bit

Dit zal je toch even moeten uitleggen dan;
Elke bit die je aan de sleutel toevoegt verdubbelt het aantal mogelijke sleutels, ongeacht de codeerwijze.
Het aantal "zwakke" sleutels is verwaarloosbaar, maar 10 bits geven dan nog steeds 1024 keer zoveel mogelijkheden en niet slechts een verdubbeling.

RSA encryptie werkt met priemgetallen, dit betekend dat een heleboel van die 2^2048 getallen niet geschikt zijn als key, en die hoef je dus ook niet te testen, je hoeft alleen de priemgetallen te checken.
10 extra bits geven dus niet 1024 keer zo veel mogelijkheden, omdat je een groot deel van de nieuwe mogelijkheden niet hoeft te proberen.

De kennis dat de sleutel een priemgetal is geeft geen enkel extra voordeel voor de kraker, het uitproberen van de sleutel gaat sneller dan het testen of een getal van 2048 bits een priemgetal is.

Bof , ik dacht dat de key steeds een vermenigvuldiging was van 2 priemgetallen ....

Het RC5-72 project van Distributed.net probeert een 72-bit lange sleutel te kraken door bruutweg alle mogelijke combinaties te proberen, en met de huidige snelheid zou dat nog zo'n 3000 jaar duren. De Xbox-bootrom is echter met 2048-bits gecodeerd, en zal volgens de kansberekening pas gekraakt zal worden als de zon de aarde allang heeft verzwolgen. De starter van het project is iets positiever:

Dat is niet met alle toekomstige technieken meegeteld neem ik aan he?
Zo van, dadelijk alles 64-bits en daarna quantum-technologie, dat gaat alles toch wel ff sneller laten verlopen

Good point. De ontwikkelingen in quantum computing schijnen sneller te gaan dan men verwachtte. Zie bv. Grote vooruitgang in quantum computing:

De verwachting is dat in 2007 quantum computing de eerste uitvoerende taken zal voltooien, zoals Grover's algoritme - een op kwantumtechniek gebaseerd zoekalgoritme.

Maar aan de andere kant: het lijkt me dat, tegen de tijd we quantumcomputers hebben, er ook nieuwe beveiligingstechnieken zullen verschijnen, met als doel dat ook een quantumcomputer er een eeuwigheid over moet doen om de boel te kraken...

-EDIT- Nieuwe beveiligingstechnieken 'tegen' quantum computing zijn misschien juist knap lastig te verzinnen, indien dat een linear kraakalgoritme op zou leveren. Het 'leuke' aan de complexiteit van dit probleem is juist dat je de grootte van je key maar een klein stukje op hoeft te hogen om het kraken stukken moeilijker te maken. Dat voordeel ben je met quantum computing kwijt, dus ik ben benieuwd welke kant het dan met de beveiliging op moet.

Tja, maar dit behoud je bij alles in de computerwereld.
Er wordt iets uitgevonden, en er wordt iets tegen uitgevonden.
Voorbeeld: UT. Men dacht dat de laatste UTPure gewoon niet te omzeilen was. Zo zag het er ook naar uit een half jaar of zo. Maar tóch is het nu gelukt om een aimbot te maken, door héél lang te proberen.
Zo zal het straks ook zijn als de quantum techieken gebruikt zullen worden.
Maarja, van de andere kant, 2007 staat idd op de schatting, maar da's een schatting van wanneer de eerste quantumcomputers komen. Dus IMHO duurt het dan nog wel een jaar of 10 voordat ze ook voor thuisgebruik beschikbaar zijn...