Duitse universiteit kraakt RSA-576 code

Door gebruik te maken van de General Number Field Sieve techniek is op de universiteit van Bonn de RSA-576 code gekraakt, zo meldt het Duitse Heise. Jens Franke van de universiteit van Bonn ontvangt $10.000 aan prijzengeld van RSA Security als resultaat van het kraken waar een 174-cijferig getal uit is gekomen. De volgende uitdaging ligt al te wachten: Het kraken van RSA-640 tot en met RSA-2048, waarbij er met laatstgenoemde $200.000 te verdienen is. RSA Security sponsort dit soort uitdagingen om het onderzoek in getaltheorie te promoten, en uiteindelijk tot betere encryptiemethoden te komen:

Die Firma RSA Security sponsert die Herausforderung, da sie sich davon Ermutigungen für die Forschung in der Zahlentheorie erhofft. Außerdem sollen die Bemühungen neue Erkenntnisse für die Kryptographie-Entwicklung und die die Eignung bestimmter Schlüssellängen für unterschiedliche Anforderungen bringen.

Reacties (45)

[Verwijderd]

Wat ik mis is de het gemak van RSA in relatie tot encryptie/decryptie t.o.v. het kraken.

Als je overstapt van 1024 bits sleutels naar b.v. 2048 bits sleutels betekent dat je computer 2 x zolang bezig is met de encryptie en decryptie.
Voor het kraken is het opeens zo dat je er miljarden meer computers tegen aan moet gooien om het te kraken.

[Verwijderd]

1-bit = 0 of 1 : 2 mogelijkheden
1024-bit: 2^1024 mogelijkheden
1025-bit: 2 x 2^1024 = 2^1025 mogelijkheden
2048-bit: 2^1024 x 2^1024 = 2^2048 mogelijkheden

(2^1024 = 1,80e+308)

dus niet 2x zoveel werk, maar een getal met 308 nullen keer zoveel werk.

[Verwijderd]

Wat doet RSA dan met die sleutel?
Ik heb eerlijk gezegt geen idee hoe RSA werkt, behalve dan dat je er sleutel van een x aantal bits voor nodig hebt.

[Verwijderd]

http://science.kennesaw.edu/~jdemaio/maa/RSAEncryptionAlgorithm.htm

Voila, het algoritme. Is ook niet eens zoo moeilijk

[apa]

Niet het dubbele, maar het kwadraat...

Een 1024-bits sleutel betekent dat er 2^1024 mogelijkheden zijn. Met een 2048-bits sleutel heb je 2^2048 mogelijkheden wat het kwadraat is van 2^1024...

[ILUsion]

Het nut van die encryptie? Het kraken van een bepaalde boodschap die door RSA-576 geëncrypteerd is, kan nog wel een tijdje duren (je denkt toch niet dat ze die boodschap op een paar minuten gekraakt hebben?)
Maar inderdaad, de veiligheid is afgenomen (omdat ze een algoritme kunnen bepalen om de boodschap te kraken)
voor de rest is het natuurlijk zeer stoer om te zeggen "ik ben een van de eersten die die encryptie gekraakt heeft", en natuurlijk is het een leuk studie-object...

[gumkop]

Maar inderdaad, de veiligheid is afgenomen (omdat ze een algoritme kunnen bepalen om de boodschap te kraken)

Als het algoritme zelf was gekraakt had je gelijk gehad. Het is nu niet onveiliger geworden, omdat bij een nieuw sleutelpaar (public/private) toch weer van voor af aan de sleutel moet worden geraden.

Het is hierdoor alleen maar veiliger geworden, want een de veiligheid van een encryptie techniek wordt niet bepaald door de sleutellengte, maar door de tijd dat het nodig is om het te kraken. Nu hebben ze dus een inschatting van de tijd.

[Verwijderd]

Tja ik vraag me wel af of iemand zich er ooit aan gaat wagen om 1024 bit's ecryptie te gaan kraken

Daar heb je heel wat operton'etjes voor nodig...

[dasiro]

klik eens op die methode en kijk hoe ze ertoe zijn gekomen. Waar jij op doelt is brute-force kraken door alle mogelijkheden af te gaan.

vanaf dat de encryptie gebruikt wordt zal men ook proberen ze te kraken, wees daar maar zeker van

[Verwijderd]

Op dit moment is brute kracht alles wat we hebben om RSA te kraken. Als er slimme truuks zouden zijn die de zoekruimte flink beperken, dan is de methode al half gekraakt; dat is namelijk precies de kracht waarop RSA berust.

[Qwerty-273]

Je kan bruteforce op twee manieren indelen. Inderdaad is er bruteforce nodig om een RSA getal te ontbinden in 2 priemgetallen (van gelijke grote)

Je hebt de methode om elk getal te bekijken of dit een priem getal is. En wanneer je het RSA getal deelt door priem getal je nog een priem getal overhoudt. Dit kan duizenden jaren duren. Maar met heel veel buitensporig geluk binnen 1 minuut.

Echter er is een andere mogelijkheid die hier ook gebruikt is. Dat is het gebruik maken van een GNFS (aangezien een RSA getal geen speciaal getal is wat mbv SNFS gepakt kan worden). Dit process vraagt op het moment dat er een grote matrix moet worden gemaakt van alle sieve gegevens ontiegelijk veel RAM geheugen. Waardoor grote getallen simpel ondoenlijk zijn om binnen een redelijke tijd aan te pakken. Zoals hier nu bewezen is kan een getal van 576-bits nu in de praktijk mits er voldoende resources aanwezig zijn aangevallen worden.

[D-Three]

Je bedoelt het goed maar je zegt het verkeers hoor!

Tja ik vraag me wel af of iemand zich er ooit aan gaat wagen om 1024 bit's ecryptie te gaan kraken

Ooit wel ja, maar waarschijnlijk dit jaar niet meer Het zal inderdaad heel wat rekenkracht vergen. Maar dat wil niet zeggen dat we nooit die rekenkracht ter onzer beschikking zullen hebben.

[Verwijderd]

Tja ik vraag me wel af of iemand zich er ooit aan gaat wagen om 1024 bit's ecryptie te gaan kraken

en het punt is dat dat soort verzuchtingen in het verleden altijd te niet gedaan zijn...

[wica]

xbox-linux.sf.net hebben geprobeert RSA 2048 te kraken. Om een vrij brute wijze. Is ze jammer genoeg niet gelukt

[ekx]

heel leuk dat dit kan...

Toch heb ik weer een vraagje:

éénmaal het gekraakt is, wat is dan het nut van zo'n encyptie?

Ik bedoel, als je kan kraken, kan je toch alles kraken (éénmaal je inzicht hebt?)

Voor mensen die geen inzicht hebben en hun bestanden/emails/info veilig willen overbrengen, gebruiken dan toch pgp? of ben ik hierin mis?

EDIT: typo: nu --> nut

[Verwijderd]

éénmaal het gekraakt is, wat is dan het nut van zo'n encyptie?

Ik bedoel, als je kan kraken, kan je toch alles kraken (éénmaal je inzicht hebt?)

Voor mensen die geen inzicht hebben en hun bestanden/emails/info veilig willen overbrengen, gebruiken dan toch pgp? of ben ik hierin mis?


PGP is een programma, RSA (en 3DES) is een encryotietechniek. PGP gebruikt RSA om een (ik dacht) 3DES sleutel te coderen; 3DES wordt gebruikt om het eigenlijke bericht te coderen. Dit omdat 3DES makkelijker & sneller te (de)coderen is dan RSA.

Op zich is het kraken van deze code van beperkt nut. Alleen als je oude, ge-encrypte, boodschappen hebt bewaard die nu met de gevonden sleutel gecodeerd bleken te zijn, weet je dus achteraf wat erin stond.

Het nut van dit geintje is, dat we nu weten wat er met de huidige technologie te kraken is aan sleutelgrootte; het is bv. handig om nu (en telkens) als minimale sleutellengte 2 keer de lengte van de laatste (grootste) gekraakte sleutel te nemen. Daarmee weet je zeker dat je berichten voorlopig veilig zullen zijn...

Als dit soort uitdagingen niet gehouden werden zouden we minder goed weten wat er op dit moment met alle nieuwe hardware, softwaretruuks en samenwerking maximaal mogelijk is. Op de NSA dan .

@Visionmaster:
Mijn commentaar was inderdaad vooral gericht op thuisgebruikers (de markt waar PGP volgens mij oorpspronkelijk op gericht was). Voor bedrijven gelden natuurlijk (zoals je beschrijft) nog veel strengere regels. Ik kan mij overigens voorstellen dat deze prestatie als effect heeft dat de normen voor die certificaten weer omhoog gaan...

[VisionMaster]

Ik gebruik op mijn werk ook wat security maatregelen gebaseerd op technieken van RSA met PKI en X509 certificaten.
Om de verbindingen, handelingen en werkwijzen zoveilig mogelijk te laten verlopen wordt er gebruik gemaakt van beveiligde verbindingen en authenticatie en autorisatie afhandelingstechnieken.
Leuk grapje vind ik het gebruik van de certificaten... Ieder heeft zijn eigen certificaat en voor je iets gaat doen dan zal je eerst een 'afstamming' van jou certificaat Moeten maken. Dit nieuwe certificaat heeft kan extra info bevatten dat alleen van toepassing is op de nog uit te voeren handelingen. Dit certificaat heeft een levensduur van 12 uur met een 512bits sleutelcombi.
Het is redelijk aannemelijk dat het blootleggen van de private key tegen de tijd van oncijfering nutteloos is geworden

Back @ Frankvde:
Ja, de afgeleide certificaten worden ivm performance redenen op 512 bits (standaard) gebakken. Je kan het aantal bits ook omhoog schroeven. Mijn eigen certificaat is gesigned met een 2048bits key en bevat een 1024bits key. Dus ja ... er is bekent dat dit te ontcijferen is, maar er wordt vertrouwd op de moeilijkheid van de ontcijfering omzo deze ontcijfering een nutteloze actie te maken.

[Verwijderd]

éénmaal het gekraakt is, wat is dan het nut van zo'n encyptie?
Ik bedoel, als je kan kraken, kan je toch alles kraken (éénmaal je inzicht hebt?)

Nee, dit geldt alleen voor dit ene bericht, voor ieder nieuw bericht worden 2 nieuwe RSA sleutels aangemaakt. Het betekend alleen dat het in de praktijk is aangetoond dat het mogelijk de RSA-576 te kraken.

[Verwijderd]

Ik dacht toch dat PGP iets ander werkt dan je nu beschrijft. Je maakt een key aan, met een publiek en een private deel. Daarna gebruik je die key zolang hij veilig lijkt te zijn; stel bv. dat je de hierboven genoemde gekraakte versie gebruikte, dan wordt het tijd voor een grotere sleutel .

Daarnaast wordt voor een bericht (als ik het mij goed herinner) gevraagd om een code (zin/woorden/whatever) om eea. te beschermen. En het kan zijn dat je die code bij elk bericht opnieuw moet opgeven (en dus kan veranderen) - maar dit is niet de sleutel die gekraakt is.

[score: 0??? Op dat moment was dat een relevante opmerking; nu zijn er veel meer mensen die net als ik graag hun encryptie-kennis spuien :)]

[Tootoo]

Wat sanctum al zei: het is ze gelukt om dit ene bericht te ontcijferen. Als de RSA encryptie methode was gekraakt dan had de hele beveiligings wereld nu op zijn kop gestaan

Hoe lang hebben ze nu gedaan over het kraken van het bericht?

[Olaf van der Spek]

PGP is zelf volgens mij geen encryptie/hash methode.
Verder is ook PGP te 'kraken'.

[bille]

dat klopt. PGP is een methode waarbij men gebruikt maakt van een publieke en geheime sleutel. De twee sleutels zijn mathematisch aan elkaar gekoppeld.
Een bestand geencrypt met een publieke sleutel kan alleen gedecrypt worden door gebruik te maken van de geheime sleutel. Het versleutelen van de data zelf wordt gedaan met bijv. het RSA of DES algoritme.
Als ik me niet vergis is bij RSA de sleutel een erg groot priemgetal dat slechts te factoriseren is in 2 priemgetallen (mersense priemgetallen heet dat geloof ik). Een van de priemgetallen wordt als publieke sleutel gebruikt en alleen als mén ook het geheime priemgetal heeft kan men het orginele priemgetal terug rekenen.

Opzich zijn er ook bruteforce manieren (factoriseren) om de geheime sleutel af te leiden van de publieke sleutel. Het factoriseren is echter een behoorlijk langdurig proces gezien het factoriseren van grote priemgetallen exponentieel moeilijker met het aantal cijfers. Het artikel geeft echter aan dat er steeds slimmere manieren bedacht worden om het factoriseren te versnellen. Maar goed, een factor 100 sneller oplossen betekend gewoon dat de priemgetallen een met enkele decimalen groter gemaakt dient te worden. Zolang als dat RSA ervoor kan zorgen dat ze altijd een stapje voorzijn is er eigenlijk niets te vrezen.

[edit] zie hier: RSA

[Woy]

Je verhaal klopt voor een groot deel wel maar er zijn toch wel een paar foutjes in je verhaal. Ten eerste is DES geen public/private ( a-symetrische encryptie ) key encryption maar werkt het maar met een key. Het decrypten wordt gewoon gedaan met de inverse van de key. Die is in het geval van DES makkelijk te berekenen en dus is er eigenlijk maar 1 private key ( symetrische encryptie )

Daarnaast zeg je dat RSA werkt met Grote priemgetallen die maar in 2 priemgetallen te factoriseren zijn. Dit is ook niet correct. Een priemgetal is natuurlijk niet te factoriseren want anders was het geen priemgetal.
Als uitgangspunt worden er inderdaad grote priemgetallen genomen maar de werkelijke sleutels hoeven geen priemgetallen te zijn. De RSA encryptie is inderdaad wel te breken door te factoriseren en dat is inderdaad een vrij lastig proces.

[Verwijderd]

Toch heb ik weer een vraagje:

éénmaal het gekraakt is, wat is dan het nut van zo'n encyptie?

RSA Security sponsort dit soort uitdagingen om het onderzoek in getaltheorie te promoten, en uiteindelijk tot betere encryptiemethoden te komen.

[Verwijderd]

Als je er een paar jaar mee bezig bent om het te kraken is het nu van het kraken naar mijn idee al weg omdat de versleutelde gegevens dan toch al outdated zijn....

[dmace]

Hoe lang duurde het om deze code te kraken??
(kan 't ff niet vinden).

[djexplo]

Kijk verder dan je neus lang is:

On Feb. 2, 1999, a group led by H. te Riele completed factorization of RSA-140 into two 70-digits primes. Primality of the factors was proved using two different methods. The factorization was found using the number field sieve factorization method, and beat the 130-digit record (for RSA-130) set on April 10, 1996. The amount of computer time spent on this factorization is estimated to be equivalent to 2000 MIPS years.

Wat trouwens opvalt is dat voornamelijk 5/10-tallen zijn gekraakt mathworld.wolfram.com/RSANumber.html Waarschijnlijk zijn andere getallen moeilijker.
Ook is het zo volgens dit artikel (url) dat 10 bits meer 2x zoveel processor kracht vraagt.

[VisionMaster]

Wel leuk dat in je artikeltje het CWI (Centrum voor Wiskunde en Informatica) en SARA (Stichting Academisch Rekencentrum Amsterdam) respectivelijk de filtering van de mogelijkheden en het proberen te vinden van een subset van de mogelijkheden op zich had genomen.

[Verwijderd]

Maaruh... Dus eigenlijk kan je elke bits-codering kraken, maar dan wel door een gigantische computer-kracht (echt wel gigantisch) achter te zetten???

Of is het makkelijker om een soort algoritme te vinden waardoor je deze (en dan ook alle andere codering met hetzelfde aantal bits, of ben ik daar ook weer mis ?) te kraken?

En RSA heeft er toch niet veel aan als deze code met brute force wordt gekraakt ??

Sorry voor mijn onwetentheid trouwens

[[Yellow]]

Yep, klopt. Alle beveiliging is te kraken. De vraag is alleen hoeveel het de tegenpartij gaat kosten om het te breken. Denk als voorbeeld aan een kluis in een bank. Ook die is te kraken met de juiste (lees: dure) middelen en een hoop denkwerk

Op dit moment is er maar 1 beveiliging die 'onkraakbaar' is (als zoiets al zou bestaan), nl. het XOR'en van alle bytes met een sleutel die net zolang is als het bericht. Daarbij komt dan nog dat je die sleutel ook nog maar 1 keer mag gebruiken, dus ook niet voor een ander bericht.

Maare, nu weet RSA tenminste *hoeveel* het de tegenpartij zou kosten om erdoorheen te komen

[Verwijderd]

Met 'hoeveel het zou kosten' bedoel je hoeveel manuren erin steken of hoeveel pc's nodig zouden hebben om die code te kraken ??

[Verwijderd]

Hoeveel bits zijn deze dan

RSA-640 tot en met RSA-2048?

64 en ???

[Olaf van der Spek]

640 en 2048

[Drogo]

64 en ???

204,8

[Verwijderd]

De rekentijd die de computer nodig heeft om een bericht te
encrypteren verdubbelt wel ongeveer (probeer eens een getal van 4 cijfers achtereenvolgens te vermenigvuldigen met een van twee en een ander van vier cijfers). Terwijl de tijd die je nodig hebt om de code te kraken exponentieel toeneemt (zodat daar zo veel meer tijd voor nodig is). Dit kan je ook proberen op dezelfde manier als hierboven, maar je moet wel op een "domme" manier te werk gaan door alle mogelijkheden af te lopen.

[Erycius]

En wat is het verschil met wat de doet?

Da's toch ook zo'n code, niet?

[Jack Flushell]

Ja! 72 bits

[Mizitras]

RSA-576, wil dit dus zeggen 576 bit?

Zoja, dan hoe slaagt zo'n unief er dan in (of hadden ze 'geluk') dat zo snel te vinden op slechts 4-jaar (1999) tijd terwijl wij bij }:O[img]http://www.tweakers.net/g/s/k.gif[/img] er ontiegelijk véél ruwe kracht moeten tegenaan gooien om zo'n miezerig kleine 72-bit sleutel te kraken????

Of heeft die unief soms 4-jaar aan een stuk een Linux cluster supercomputer met Itaniums ofzo zitten runnen???

[Seejay]

Een getal van 174 getallen? Dat is nog niets bij dat grote priemgetal dat laatst gevonden werd, laat ze dat maar eens kraken ;-)

[LiMy]

WTF valt er te kraken aan een priemgetal... tis louter een zoektocht naar de vindbare grootste...