Onderzoekers factoriseren RSA-768-getal

Onderzoekers uit verschillende landen hebben een 768bit-getal met 232 decimale cijfers afkomstig van RSA Security, ontbonden in zijn priemgetallen. RSA-768 is daarmee onveilig verklaard, maar RSA-1024 houdt nog jaren stand.

Het team van onderzoekers uit Nederland, Frankrijk, Duitsland, Zwitserland, de Verenigde Staten en Japan had tweeëneenhalf jaar nodig om het ontbinden te voltooien. De Nederlandse inbreng kwam van het Centrum voor Wiskunde en Informatica. De RSA-encryptiemethode voor datacommunicatie is gebaseerd op een groot getal dat het product is van twee priemgetallen. In 1991 begon RSA Security de RSA Factoring Challenge, een competitie voor het ontbinden in priemgetallen van een lijst semipriemgetallen, RSA-getallen genoemd. Zijn die priemgetallen eenmaal gevonden, dan zijn RSA-sleutels van die grootte niet meer als veilig te beschouwen. Van het RSA-getal van 768 bits, ofwel 232 cijfertekens in het decimale stelsel, kortweg RSA-768, zijn de samenstellende priemgetallen nu bekend.

De eerste stap van de kraak, de selectie van polynomen, duurde een half jaar op een computercluster van tachtig pc's. Voor de tweede stap, het ontbinden in factoren via number field sieve, duurde aanzienlijk langer: tweeënhalfjaar. Hiervoor gebruikten de onderzoekers naar eigen zeggen 'honderden machines'. Op een systeem met een singlecore Opteron-processor met een kloksnelheid van 2,2GHz en 2GB werkgeheugen zou deze rekenklus 1500 jaar duren, schatten de wetenschappers. De 768bit-encryptie wordt als onveilig beschouwd ook al duurt het dus jaren en vereist het heel wat rekenkracht om de priemgetallen van een 768bit-sleutel te vinden. De wetenschappers houden echter rekening met de voortschrijdende technologische vooruitgang en andere factoren die een 'kraak' kunnen versnellen.

RSA-512 is in 1999 gekraakt en de onderzoekers schatten dat de priemgetallen van RSA-1024-getal binnen tien jaar gevonden worden. Vanwege het belang van 1024bit-RSA-encryptie menen zij wel dat deze beveiliging in de komende drie tot vier jaar met pensioen moet. Overigens wonnen de onderzoekers geen geldbedrag, zoals voorheen, aangezien RSA Security de Factoring Challenge-wedstrijd na de overname door EMC heeft geschrapt.

Reacties (122)

[ciro-bonano]

Wat nou gekraakt? Ze hebben laten zien dat een brute-force aanval te doen is in 2.5 jaar tijd; ze hebben geen fundamentele fout in het algoritme gevonden.

[PiepPiep]

Het is zeker geen bruteforce aanval!
Als je dat zou doen op een 768 bits key moet je dus 2^(768/2) = 2^384 berekeningen doen. Stel je doet er 1.000.000.000 per seconde (wat de huidige cpu's niet halen met zulke getallen) dan blijft er nog ongeveer 2^354 seconde over. Als iedereen op deze aarde (ik reken even voor het gemak 8 biljoen mensen) die reken kracht eraan zou besteden blijft er nog 2^321 seconde over.
Kortom, brute force is het niet.

[stresstak]

Ik hoop toch dat je miljard bedoelt ipv biljoen. Het is al vol genoeg

[Soldaatje]

Inderdaad, met zo'n resultaat is deze codering juist uitermate veilig te noemen.
Waar wordt deze versleuteling voor gebruikt vraag ik me af.

[Reactie gewijzigd door Soldaatje op 22 juli 2024 18:09]

[Verwijderd]

Nee het is dus juist niet uitermate veilig. Dat is het gehele punt. 2.5 jaar is in de encryptie wereld namelijk helemaal niks. Er zijn zat berichten waarvan je niet wilt dat ze ooit in jouw levensloop openbaar komen. Denk aan militaire documenten, bank geheimen e.d. Dit soort berichten mogen nooit binnen 2.5 jaar gekraakt worden (ja ik weet dat je dit soort dingen met een symmetrische encryptie doet en dat RSA asymmetrisch is, het gaat even om het punt). Daarom is dus ook het advies om over te stappen naar bijvoorbeeld 1024 bits.

[Orion84]

Zelfs al gebruik je symmetrische encryptie voor grote hoeveelheden data, vaak wordt die symmetrische sleutel dan wel met RSA versleuteld verstuurd/opgeslagen. Dus ook in die gevallen zit je met een beperkte veiligheid van je data.

[Apoca]

Wil het zeggen dat nu men weet hoe je een "hack" op een RSA-768-versleuteling moet toepassen dat men dit thuis zelf ook zou kunnen doen ff kort door de bocht genomen? Of heb je daar zoveel CPU power voor nodig dat dit voor de hacker op de hoek niet te doen is?

[Jiriki]

Ja, ze hebben nu de sleutel achter de sleutels gevonden. Zeg maar de master key, de loper voor alle andere RSA-768 sleutels.

Dit is dus een waarschuwing voor iedereen die nog 768 bit encryptie gebruikt dat het nu toch echt tijd is om te gaan opwaarderen.

Edit: dit heb ik wel erg slecht opgeschreven... Er is nu een lijst met keys, waar de challenge key dus bijzit. Elke willekeurige andere key kan er dus ook bijzitten.

[Reactie gewijzigd door Jiriki op 22 juli 2024 18:09]

[Dannr]

Ehm, nee. Dat is pertinent niet waar.

Ze hebben een sleutel, die als challenge gepost was, gekraakt. Dat is indrukwekkend, maar heeft geen enkel gevolg voor alle andere sleutels die in gebruik zijn, en ieder gewoon mens kan met een gerust hart RSA-768 blijven gebruiken.

[Verwijderd]

Uh nee, zo werkt RSA niet.

Zie voor het (openbare) algoritme: http://en.wikipedia.org/wiki/RSA

Ze hebben van 1 RSA key van 768-bit length dus de bijhorende twee priemgetallen gevonden. Ze hebben dus 2,5 jaar nodig gehad om 1 key te breken, wat volgens mij aangeeft dat de keys nog redelijk veilig zijn. (Als je een andere key wilt doen, kost dat je ook zo rond de 2,5 jaar dan.)

Er bestaat niet zoiets als een 'master sleutel' voor alle RSA sleutels. Dat zou het algoritme nogal kwetsbaar maken, laat staan onbetrouwbaar, aangezien je nooit kan weten of zo'n sleutel nou echt nog geheim is of niet.

[Reactie gewijzigd door Verwijderd op 22 juli 2024 18:09]

[robvanwijk]

Ja, ze hebben nu de sleutel achter de sleutels gevonden. Zeg maar de master key, de loper voor alle andere RSA-768 sleutels.

Uhm. sorry? Ik wist niet dat er zo'n master key was. Voor de zekerheid heb ik nog even nagelezen hoe RSA ook alweer precies werkt, maar over een master key kan ik niks vinden. Heb je een bron?
Voor zover ik kan bepalen betekent dit alleen dat er één specifieke RSA-sleutel is gekraakt. Behalve dat we nu weten hoeveel compute power je ongeveer nodig hebt om 768 bit RSA te kraken verandert dit niks aan de veiligheid van andere sleutels; die zijn nog steeds even veilig als gisteren.

[dmantione]

Inderdaad, er is geen mastersleutel, ze hebben één specifieke sleutel gevonden.

[Rob Coops]

Als dat zo was dan zouden er maar heel erg weinig mensen nog RSA gebruiken. Het idee is juist dat is aangetoont dat een key te achterhalen is maar dat wil niet zeggen dat men alle keys heeft of even met een paar regels code een scriptje kan produceren dat een key in enkele seconden weet te kraken. Alles dat berijkt is is dat men heeft bewezen dat als je echt wil en genoeg geld, tijd en horsepower hebt je deze beveiliging zou kunnen kraken.

Het zal nog wel een paar jaar duren voor men met een huis thuin en keuken PC'tje even een RSA-768 sleutel achter halen kan. Maar dat het in in de praktijk mogenlijk zou kunnen zijn is nu bewezen.

Realistisch gezien kun je makkelijk nog een jaar of 10 gebruik maken van de RSA-786 encryptie tenzij je echt met materiaal bezig bent dat onder geen beding in de handen van een erg kapitaal krachtige andere partij mag vallen. (Overheden zijn de voornaamste groep in deze).

[cdwave]

Thuis niet te doen, ook niet met hulp van je broertje z'n PC. Wel in grote clusters, en een paar jaar tijd.

Overigens gebruikt vrijwel iedereen RSA-1024. Uitgaande van een beetje gelijkmatige spreiding van priemgetallen, kun je stellen dat:

als RSA-768 in 2,5 jaar te kraken is dan, uitgaande van dezelfde hardware, ...

duurt RSA-769 ongeveer 5 jaar
duurt RSA-770 ongeveer 10 jaar
duurt RSA-771 ongeveer 20 jaar
...
duurt RSA-1024 ongeveer... eh 2,5 * 2^256... jaar. 2^256 is best wel een groot getal. Zoiets als "het aantal atomen van alle sterren die we kunnen zien".

[deadinspace]

Overigens gebruikt vrijwel iedereen RSA-1024. Uitgaande van een beetje gelijkmatige spreiding van priemgetallen, kun je stellen dat:

als RSA-768 in 2,5 jaar te kraken is dan, uitgaande van dezelfde hardware, ...

duurt RSA-769 ongeveer 5 jaar
duurt RSA-770 ongeveer 10 jaar
duurt RSA-771 ongeveer 20 jaar
...
duurt RSA-1024 ongeveer... eh 2,5 * 2^256... jaar.

Nee, zo werkt dat niet; één bit toevoegen aan de key betekent niet dat het aantal berekeningen om de key te kraken verdubbelt, dat is alleen (ongeveer) zo voor bepaalde symmetrische ciphers.

Van Wikipedia:

In cryptography, key size or key length is the size (usually measured in bits or bytes) of the key used in a cryptographic algorithm (such as a cipher). An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits. The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. For example, Triple DES has a key size of 168 bits but provides at most 112 bits of security, since an attack of complexity 2¹¹² is known.

Door één bit aan een RSA key toe te voegen gaat de key length met één omhoog, maar de cryptographic security gaat met een stuk minder omhoog, zoals ik wat verderop zal laten zien.

Het Wikipedia artikel gaat als volgt verder:

This property of Triple DES is not a weakness provided 112 bits of security is sufficient for an application. Most symmetric-key algorithms in common use are designed to have security equal to their key length. No asymmetric-key algorithms with this property are known; elliptic curve cryptography comes the closest with an effective security of roughly half its key length.

Wat al suggereert dat één bit extra key length minder dan één bit cryptographic security genereert (RSA is een asymmetric-key cipher).

De cryptographic security van RSA is ongeveer sqrt(ln(2^k)*ln(ln(2^k)))/ln(2) bits, voor RSA sleutels van k bits. (bron: Fundamentals of Cryptology - het boek gebruikt overigens niet alle truukjes om de rekentijd te verkorten, dus dit geeft nog een optimistische schatting van de cryptographic security; deze RSA pagina geeft een paar waarden van ongeveer 25% bits minder. Maar dat is geen ramp voor deze uitleg)

Uitgaand van bovenstaande formule heeft een 768-bit RSA key een cryptographic security van 83.40 bits, en 769-bit RSA 83.46 bits. Dat betekent dus dat het toevoegen van één bit aan een 768-bit RSA key slechts 2^0.06 - 1 = 0.04 = 4% extra benodigde rekentijd toevoegt. Om de benodigde rekentijd te verdubbelen moet je van een 768-bit key naar een 784-bit key gaan.

1024-bit keys hebben een cryptographic security van 98.48, wat een vooruitgang is van 98.48 - 83.40 = 15.08 bits. Het kost dus ongeveer 2¹⁵ = 32768 keer zoveel rekenkracht om een 1024-bit key te kraken t.o.v. een 768-bit key.

Hier begin je trouwens wel te merken dat mijn formule voor de cryptographic security niet 100% nauwkeurig is; In het artikel staat dat ze verwachten RSA-1024 binnen 10 jaar te kraken. In 10 jaar tijd is de rekenkracht ongeveer een factor 1024 toegenomen (uitgaande van een verdubbeling per jaar), geen factor 32768. Maar om duidelijk te maken dat de relatie tussen key length en cryptographic security voor RSA niet lineair is, is het goed zat

edit:
Ah, tweaker ProfPi heeft verderop in deze discussie een link gepost naar de paper die beschrijft wat ze gedaan hebben om de RSA-768 modulus te factoriseren.

Uit de paper:

The number RSA-768 was taken from the now obsolete RSA Challenge
list [37] as a representative 768-bit RSA modulus (cf. [36]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder [...]

Dat maakt mijn schatting van "een factor 1024 meer" aardig in de buurt, en bevestigt nog meer dat mijn formule voor de cryptographic security van RSA niet 100% toereikend is.

[Reactie gewijzigd door deadinspace op 22 juli 2024 14:01]

[CornéM]

Lees even het artikel door tot onderaan ... RSA-1024 verwacht men binnen 10 jaar te hebben gevonden.

[DjDuivert]

[quote]Op een systeem met een singlecore Opteron-processor met een kloksnelheid van 2,2GHz en 2GB werkgeheugen zou deze rekenklus 1500 jaar duren, schatten de wetenschappers.[/qoute]

Met een i7 op 4,5GHz zal het heel wat sneller gaan en als je het op je videokaart laat draaien kan het nog heel wat sneller, maar voorlopig is dit wel iets dat alleen hackers met goede apparatuur voor elkaar krijgen.

In principe zal elke beveiliging te kraken zijn, met als uitzondering hooguit quantumencryptie, als je maar lang genoeg probeert. Maar als je ervoor kunt zorgen dat het kraken zolang duurt en zoveel geld kost kun, zorg je ervoor dat hackers interesse verliezen. Als je data steelt wil je dat meteen kunnen gebruiken, als je nog eens 3 jaar met een supercomputer moet gaan zitten rekenen is het voor de hacker niet rendabel lijkt me

[badnews.nl]

als jij nu op je i7 begint, kan je net zo goed over 5 jaar (minimale tijd, denk dat een i7 er zo'n 200 jaar over doet) met een nog snellere processor werken, doe je er nog 100 jaar over (dus 95 jaar winst).

zo blijf je bezig

Later starten met snellere hardware is op dit moment eerder klaar zijn dan met huidige top spul.

[KiLLerS]

beetje gevalletje hacker, heeft toch minimaal 100 pc's in een botnetje, dus tja dan wordt het in een keer niet zo heel moeilijk meer....

[bbob]

of zoals gezegd optimaliseer het geheel voor een gpu berekening en het loopt heel veel sneller. Pak een cluster aan gpu's en de tijd gaat nog korter worden.

[dtech]

En wie zegt dat dit type berekeningen goed&snel op GPU's uit te voeren is...

Bovendien gaat een bezitter van zo'n botnet echt geen moeilijke software schrijven om een sleutel te kraken: dan is verhuren als spamverstuurder makkelijker en levert evenveel op...

[tes_shavon]

een getal in priemfactoren opdelen is niet echt state-of-the-art wiskunde... dat kan heel simpel op elke chip uitgeprogrammeerd worden.

[Reactie gewijzigd door tes_shavon op 22 juli 2024 18:09]

[Verwijderd]

Als het geen state-of-the-art wiskunde zou zijn, waarom houdt het Centrum voor Wiskunde en Informatica zich er dan mee bezig?

Niet dat ik erg geloof in argumentatie per autoriteit, maar volgens mij heb je geen idee waar je over praat.

De kunst is niet om iets te laten werken, de kunst is om iets zo snel mogelijk te laten werken.

Ik neem aan dat je zelf geen wiskunde hebt gestudeerd.

[Verwijderd]

@gang-ster

Het is miljoenen keren simpele wiskunde, wat het in totaal toch wel vrij state-of-the-art maakt, de basis ligt uiteindelijk bij het vinden van priemgetallen, wat niet heel spectaculair is.

@dtech

GPU's zijn heel parallel opgebouwd, en kunnen honderden vrij simpele taken tegelijk uitvoeren, terwijl een CPU er slechts een paar doet, die dan wel weer complexer kunnen zijn.
In mijn opzicht (Onthoud: ik ben geen professional.) moet dit prima op GPU's te doen zijn, omdat het factoriseren een parallelle taak is, zoals op wikipedia ook te lezen is: "Finding the large primes p and q is usually done by testing random numbers"

[Reactie gewijzigd door Verwijderd op 22 juli 2024 18:09]

[dragonfly28]

ja maar de state of de art is dat het niet ontzettend lang duurt.
Je kan wel gewoon beginnen met is het getal deelbaar door 2, door 3, door 4 etc maar dan haal deze tijd echt niet hoor.

[mickvdv]

Gewoon ff wat wilde voorbeelden:

Als die huurder van het botnet nou een al qaida terrorist was. Die informatie van de NSA nodig heeft. Hij huurt een botnet in en laat de RSA encryptie van de NSA kraken. Als dat botnet groot genoeg is (1 miljoen pc's):

1 Opteron Single core is waarschijnlijk 0.5x de gemiddelde hedendaagse pc (tegenwoordig is bijna alles dual-core), daarmee duurt het:

1500 / 2 = 750 jaar voor 1 pc
750 / 1x10^6 = 0.00075 jaar met 1 miljoen pc's
0.00075 * 365 = 0.27375 dagen
0.27375 * 24 = 6.57 uur om de encryptie te kraken.

Voor een al qaida terrorist heeft die RSA key meer waarde, een hele grote meerwaarde. En dus is de kans best reëel dat dit gebeurt. Het is dus maar goed dat die onderzoekers dit onderzoek hebben gedaan.

P.S. Dit was een reactie op dtech

[Sir Isaac]

GPU's zijn vooral goed in grote hoeveelheden floating point berekeningen. Dit zijn integer berekeningen. Ik betwijfel daarom of een GPU hier meerwaarde heeft.
Als je iets wilt kun je misschien beter een FPGA programmeren om dit te doen. Dan heb je code die je nodig hebt in hardware gebakken.

[mBull]

dit zijn geen integer berekening, aangezien een integer een geheel getal...
er staat letterlijk in de text:

het RSA-getal van 768-bit met 232 decimalen, oftewel RSA-768, zijn de samenstellende priemgetallen nu bekend.

232 decimalen zijn dus getallen achter de komma... waardoor het of een float, of een double wordt...

[EdwinG]

De tekst '232 decimalen' is hier niet bedoeld als 'een getal met 232 cijfers achter de komma'. Het gaat hier om een getal dat is samengesteld uit twee priemgetallen. Aangezien priemgetallen natuurlijke getallen zijn, is een product van twee priemgetallen dat ook.

[Toolskyn]

GPU's zijn vooral goed in niet-branchende berekeningen. Dus wanneer elke keer precies dezelfde stapjes uitgevoerd kunnen worden om tot het antwoord te komen, en wanneer die berekening heel erg vaak uitgevoerd moet worden (met verschillende invoer) dan zal je GPU daar om smullen.

De GPU is wat minder blij met dingen als het bewegen van een muis (om eens een simpel voorbeeld te noemen). Daar is niets aan te voorspellen wat er moet gaan gebeuren, en daar kan je GPU totaal niet mee overweg.

[cdwave]

GPUs zijn ook verrekte goed in integers hoor. Daarom zijn ze ook zo goed in pixelkleurtjes.

[joppe.s]

er zijn botnets geweest met > miljoen computers, ik denk dat georganiseerde hackers dit klusje sneller kunnen dan in 2,5 jaar. zeker nu er een techniek bekend is over de methode om het te doen.

[Arnoud Engelfriet]

Deze "hack" is voor iedere RSA-768 sleutel bruikbaar, maar duurt elke keer gemiddeld precies even lang (tenzij je snellere hardware neemt).

[MMaI]

juist, de enige optimalisatie is dat je de selectie van de polynmomen kan overslaan. De totale tijd voor het kraken is nu dus 2.5 jaar voor een enkele key.

[i-chat]

of minder als je de hardware dubbelt ...

maar aan de andere kant, - botnets draaien doorgaans niet op I7's ...

[PiepPiep]

Die selectie van polynomen is afhankelijk van je key.
Ze moeten geloof ik relatief priem zijn met een bepaalde waarde afhankelijk van je key.
Bron heb ik hier niet echt van, ik weet alleen dat ik zoiets ooit gelezen heb. Het is ook erg ingewikkelde materie dus een bron zou ook niet veel zeggen

[HerrPino]

Wat ik nou nooit begrijp is, waarom gebruikt men niet gewoon iets als RSA-4096 of weet ik veel hoeveel bits. Of laat het aantal bits varieren, da's misschien nog lastiger. Encrypten wordt dan misschien iets trager is, maar kan me niet voorstellen dat dat veeeele malen trager is om mee te werken en uiteindelijk gaat het er bij encryptie om dat het veilig is, niet dat het ongelooflijk snel is.

[Orion84]

Voor encyptie om praktisch toepasbaar te zijn is performance wel degelijk heel belangrijk
Als mensen merken dat ze met encryptie hun werk niet meer vlot kunnen doen, dan hebben ze de neiging om het uit te zetten of te omzeilen op de een of andere manier. En op die manier is je beveiliging dus waardeloos.

Tuurlijk, voor super top secret shizzle kan je de afweging maken dat een beetje performance verlies geen kwaad kan, maar voor heel veel toepassingen weegt performance best zwaar en is het echt niet zomaar een optie om naar het zwaarste middel te grijpen.

En elke verdubbeling van de key size heeft nogal dramatische gevolgen voor de performance van de decryptie stap. Zoals hier te lezen valt: http://stackoverflow.com/...e-of-rsa-based-on-keysize

[Reactie gewijzigd door Orion84 op 22 juli 2024 18:09]

[dreku88000]

Best mooi om te lezen hoe de hele encryptie - decryptie - processor kracht samenhang zich ontwikkeld. Zoals Orion84 hierboven aangaf (in de link), kost het ongeveer een seconde met een Pentium 2Ghz processor om een 4096 bits RSA code te decrypten.

Hoe lang zou het dan nog duren met een Core 2 Duo of vergelijkbare processor? Dat zal dan toch wel minder dan een seconde moeten zijn? Zou dit echt zo'n probleem zijn dan? Als het aan de gebruikservaring van de persoon achter de pc ligt, lijkt het me wel overkombaar. Als dit echter inhoud dat je dan al die tijd (die nodig is voor en of de-crypten) kwetsbaar bent, moet dit idd tot een minimum beperkt worden.

Als rode draad zou ik het houden op stilstand is achteruitgang. Wel interessant bericht overigens.

[Orion84]

Uhm, bedenk je even dat er talloze webservers zijn die een of meer RSA decrypties moeten uitvoeren voor elke bezoeker die een HTTPS verbinding opent.

Als je voor elke bezoeker een seconde extra bezig bent, dan kan dat voor een drukbezochte webserver echt wel voor problemen gaan zorgen.

[paella]

Snelheid is wel degelijk een issue bij allerlei toepassingen.

[remcio]

wie gebruikt er eigenlijk zulke wachtwoorden ? of welke instantie's

[Luqq]

Iedereen, SSL gebruikt vaak RSA encryptie afaik.

[MMaI]

SSL zoals het origineel bedacht was, is inmiddels overal vervangen door TSL (Transport Layer Security), en deze maakt gebruik van 1024bit of 2048 bit RSA keys welke momenteel respectievelijk 15 miljoen en 225 miljoen jaar om te kraken met behulp van een enkele pc

1024 bits zit in je client certificaat, 2048 is voornamelijk voor certificate authorities (CA's)

[Orion84]

Niet voor datatransport hoor. Enkel voor het signeren van certificaten en wat encryptie tijdens het opstartprotocol waar de uiteindelijke symmetrische sleutel wordt afgesproken. Verder gebruikt SSL over het algemeen AES, aangezien dat nu eenmaal veel sneller is dan RSA.

Maar inderdaad, RSA is een van de crypto systemen die gebruikt wordt als onderdeel van SSL.

[Reactie gewijzigd door Orion84 op 22 juli 2024 18:09]

[DjDuivert]

Overheden bijvoorbeeld, instanties als CIA willen informatie over topcriminelen wel geheim houden.

ZIekenhuizen hebben ook beveiliging, je wilt niet dat iemand alle patientendossiers zomaar in kan of nog erger, ze kan wijzigen.

Grote bedrijven als Intel gebruiken ook dit soort beveiliging lijkt me, USB sticks zijn vatbaar voor verlies als je het nieuws over verloren sticks bij elkaar zoekt... Ik snap zelf niet hoe er zoveel telefoons en sticks verloren kunnen gaan, maar goed. Er zijn in ieder geval een hoop bedrijven en instanties die prive gegevens beheren of geheim onderzoek verrichten en sommige data wil men dan koste wat het kost uit handen van anderen houden.

[Verwijderd]

RSA is gewoon gebaseerd op het feit dat computers niet snel grote getallen kunnen ontbinden in priemfactoren, zeker niet als het gaat om het product van 2 priemgetallen met meer dan 100 cijfers.

[Reactie gewijzigd door Verwijderd op 22 juli 2024 18:09]

[NitSuA]

daarom vind ik dit dus ook nogal zonde van de tijd. Men weet gewoon dat het systeem te kraken is. Lekker nutteloos dus allemaal. Laten ze die computertijd maar besteden aan medisch onderzoek, daar worden mensen echt beter van..

[FireDrunk]

Nee, want stel dat er een of andere wiskundeknobbel een manier vind om deze te kraken en NIET verteld... Dan zijn we verder van huis...

Liever openbaar gecontroleerd en zonde van de tijd dan niet openbaar en geen verspliling..

Lijkt ons drugsbeleid wel...

[NESFreak]

Volgens mij is het berekenen meer proof of concept dan dat men hier ook daadwerkelijk iets mee heeft bereikt verder.

Aangezien er algemeen beschikbare methodes zijn om getallen te factoriseren is het dus meer dan bekend dat dit te kraken is. Deze beveiligingsmethodes berusten dus vooral op de enorme rekentijd die het kost om ze te kraken. Ik weet niet wat voor een oplossingsmethode er hier gebruikt is, maar voor de meeste algoritmes is het gewoon mogelijk om een behoorlijk reële schatting te geven van de rekentijd. (Als ik het artikel zo lees kon dat ook hier, ze geven immers ook een schatting van de tijd die het op een normale operton-bak kost.)

Hadden ze dan niet beter gewoon deze methode al van te voren kunnen afschrijven, in plaats van er ook nog eens 2.5 jaar rekentijd op een enorm cluster aan te besteden?

-edit-
zie http://en.wikipedia.org/w...Difficulty_and_complexity voor een stukje over de runningtime.

[Reactie gewijzigd door NESFreak op 22 juli 2024 18:09]

[NitSuA]

exact!!

[MaartenC]

Men zegt dat een encryptie "veilig" is als de kost en inspanningen om het te kraken groter is dan de waarde van de inhoud van de versleutelde data.

Iemand die het wil kraken moet dus een meerwaarde krijgen tenzij het om prestige gaat,
'veilig' kan dus gerust als subjectief beschouwd worden.

NSA gegevens zijn iets anders dan de versleuteling van m'n weave account

[StefanTs]

Lekker nutteloos dat medisch onderzoek, we gaan toch wel een keer dood.

En volgens jouw redenatie kan ik een hoop meer nutteloos verklaren.

[Verwijderd]

Ze doen dit om dezelfde reden dat er gevechtsvliegtuigen ontwikkeld worden. Cryptografie is een onderdeel van je militaire communicatie infrastructuur in beginsel. Consumententoepassingen zijn er later pas gekomen.

Dus ze hebben niet zomaar een of ander dom algoritme laten draaien. Ze hebben er tijd in gestopt om de algoritmes zelf efficiënter te maken. Althans, dat hoop ik, want als ze dat niet gedaan hebben, dan mogen ze van mij allemaal ontslagen worden

Je kunt er wel vanuit gaan dat ze iets nieuwswaardig te melden hebben, meer dan "oh, kijk eens wat voor computers we hebben", maar dat zetten ze dan weer niet in dit tweakers bericht, omdat ze waarschijnlijk niemand in dienst hebben die dit soort dingen op waarde kan schatten of daar de tijd niet voor hebben.

[bonus]

Ik vind het ook een beetje van de gekke dit. Voor wie moet je dan bang zijn die het kan kraken. Die moet toch al een mega park aan krachtige (of een hele) pc's hebben. Iets is nooit 100% veilig dus ja zo kun je alles als onvelig bestempelen. Die 1024 variant is uiteindelijk ook te doen, kwestie van tijd.

[Verwijderd]

Het is daarom belangrijk dat dit soort kraak mogelijkheden worden gedaan door instanties die hopelijk meer rekenkracht hebben dan de criminelen.

En dat het gebruikers aanzet om versneld omhoog te gaan, dus inplaats van RSA-2048, waarom niet meteen naar RSA-4096.

Een crypto vriend van mij gebruikt zelf 16k en 32k keys, het duurt hem soms dagen om de sleutels te genereren, maar het daadwerkelijk gebruik ervan gaat redelijk snel met de rekenkracht die CPUs tegenwoordig bezitten.

Het is daarom ook mooi dat Intel extra instructies heeft toegevoegt aan de SSE standaard die daarbij kunnen helpen, zodat het gebruik van RSA-4096, RSA-8192, AES-256, of SHA-512 amper vertraging bied.

[maceddy2004]

Ik snap het bericht niet volledig.. Hebben ze nou de encryptiemethode gekraakt (ja, want ze hebben gevonden hoe het werkt?) maar betekent dit nu dat geen een key meer veilig is of duurt het 2,5 jaar om elke individuele RSA-768 key te kraken?

[Dannr]

Het algoritme is openbaar, dus die hoefden ze niet te kraken.

Het enige wat dit resultaat betekent is dat ze 1 bepaalde key (die officieel als "challenge" gezet is door dit RSA Security/ECM) hebben gekraakt, wat natuurlijk toch al met al wel indrukwekkend is. Het zegt technisch gezien niet zo ontzettend veel over andere, willekeurig gekozen, sleutels, al kun je verwachten dat je daar ook iets in de orde van deze rekentijd voor nodig zal hebben.

[Reactie gewijzigd door Dannr op 22 juli 2024 18:09]

[MaxxMark]

Je kunt nu met redelijke zekerheid vast stellen wat de periode is die nodig is om deze encryptie te kraken.

Aangezien techniek niet stil staat en alles steeds sneller wordt is dus ook te voorspellen dat het steeds korter zal duren om de encryptie te kraken.

Zodra er een tijdsspanne aan een het brute-force kraken van een encryptie gehangen kan worden kan je dus ook zeggen dat vanaf dat moment met het verstrijken van de tijd deze steeds onveiliger wordt.

En om die reden is deze informatie nuttig.

[Reactie gewijzigd door MaxxMark op 22 juli 2024 18:09]

[Gehakt]

De definitie van encryptie kraken is in deze denk ik ongeveer als volgt: "de mogelijkheid hebben om binnen afzienbare tijd een versleuteld bericht te kunnen lezen". Dit klinkt natuurlijk nog erg vaag maar ik denk dat we wel kunnen stellen dat voor een enkele persoon met een desktop computer 1500 jaar decrypten niet binnen afzienbare tijd is.

[Verwijderd]

Waarom zou dit 1500 jaar duren?
Ze kunnen ook alle berichten die versleuteld zijn met deze SLEUTEL meteen lezen, daar hoeven ze echter geen 1500 jaar over te doen.
Uiteraard voor elke andere sleutel moeten ze wel weer opnieuw gaan rekenen...
Al hoewel ze wel een klein voorsprongetje nu hebben want ze hebben al een gedeelte berekend....
Ik weet uiteraard niet of ze dan ook de andere sleutels al hebben opgeslagen
(ik neem aan dat ze nog steeds grootte priem getallen met elkaar hebben lopen te vermenigvuldigen om zo tot public/private key uit te komen

[Bacchus]

De algemeen geaccepteerde betekenis van een encryptie kraken is het vinden van een methode sneller dan alle sleutels uitproberen. Dat is in dit geval niet gebeurd. Dit bericht moet je ook niet lezen als "RSA is onveilig" maar als "je moet geen 768-bits sleutels meer gebruiken voor RSA", dat laatste deden we toch al niet, wel?

[dmantione]

RSA is dus cryptografisch helemaal niet gekraakt, het is gewoon zo dat door toenemende rekenkracht van computers grotere priemgetallen wenselijk worden. Zelfs het kraken van een 768 bits sleutel kost nog héél erg veel geld en is dus voorlopig nog veilig in de meeste toepassingen, alleen zeer rijke instanties, zoals regeringen zouden met veel moeite de sleutel kunnen achterhalen.

[zeroxcool]

Ai, daar maak je een grote denkfout. Denk even aan grote criminele organisaties met een bijna ongelimiteerd budget, zoals de mafia. Voor zo'n 'instanties' kun je met enkele miljoenen redelijk gemakkelijk een RSA-768, of zelfs een RSA-1024 private key achterhalen. Dat lijkt een heel groot bedrag (is het natuurlijk ook), maar als je bedenkt wat je met zo'n achterhaalde key zou kunnen doen: phishing, zonder dat het op phishing lijkt (vanwege SSL-certificaten); banktransacties ondertekenen (signen), zonder dat de tegenpartij doorheeft dat de partij niet de Rabobank is; onderscheppen van digitale communicatie tussen Justitiële partijen, advocaten etc. etc.

De mogelijkheden zijn eindeloos...

[Reactie gewijzigd door zeroxcool op 22 juli 2024 18:09]

[YopY]

Ja, maar om nu twee+ jaar te gaan rekenen om één SSL certificaat voor één bank te krijgen en gedurende een paar dagen te gaan phishen... kan dat uit? Moeten ze wel een grote gok nemen.

[Arnoud Engelfriet]

Wat kost twee jaar een botnet?

[Verwijderd]

Ik denk dat je voor een paar euro per machine wel klaar bent op een schaal van honderdduizenden machines.

Niemand gaat je in deze thread een aanbieding doen

[dmantione]

Nee, dat kan niet. SSL-certificaten moeten doorgaans jaarlijks vernieuwd worden, de browser van het potentieel slachtoffer zal melden dat het certificaat niet langer geldig is. Alleen als de rekentijd minder dan een jaar wordt zou dit kunnen.

Hoe dan ook, gewoon een grotere sleutel nemen, probleem opgelost, cryptografisch is met RSA nog altijd niets mis, en naar ik lees is ook geen voortgang geboekt om het RSA-algoritme cryptografisch te breken.

[Reactie gewijzigd door dmantione op 22 juli 2024 18:09]

[Jaap-Jan]

Het enige wat dit wil zeggen is dat RSA-768 niet meer gebruikt moet worden als je wilt dat je informatie niet gelezen kan worden door instanties met grote rekenclusters. De wetenschappers hebben aangetoond dat het binnen een redelijke termijn mogelijk is om een bericht te ontcijferen. Dat wil niet zeggen dat nu iedereen vanuit zijn luie stoel hetzelfde kan doen, er is nog steeds een immense hoeveelheid rekenkracht voor nodig.

RSA wordt toegepast in SSL en TLS als asymmetrische encryptie om een sessiesleutel over te sturen voor symmetrische encryptie (bijvoorbeeld AES) die de daadwerkelijke data voor de sessie versleuteld.

[dmantione]

In veel protocollen wordt gewoon de sleutel regelmatig veranderd. Bij betaaltelevisie wordt bijvooorbeeld het Common Scrambling Algorithm gebruikt als symmetrisch algoritme, en de sleutel kan wel iedere 20 seconden anders zijn...

Als je met een cluster 3 jaar moet rekenen om 20 seconden televisie te kunnen kijken heb niet veel bereikt.

[Orion84]

Maar als je de RSA sleutel eenmaal gekraakt hebt, kan je daarna elke keer dat er in het vervolg een nieuwe SSL verbinding wordt opgezet vrolijk meelezen (of jezelf voordoen als een vertrouwde partij) en dus de session keys te weten komen.
En als je netwerkverkeer uit het verleden hebt onderschept en opgeslagen kan je daar ook de met RSA versleutelde session key achterhalen en vervolgens al het verkeer decrypten.

[dmantione]

Als het goed geïmplementeerd is kan dat niet, je kunt zo via Diffie-Hellman nieuwe sleutels afspreken en dan moet een nieuwe combinatie priemgetallen gevonden worden.

Bij betaaltelevisie wordt bij de meeste systemen (er is maar 1 CSA, maar er zijn vele systemen voor het asymetrische deel) de assymetrische cryptografisch vercijferde gegevens om de symmetrische CSA-sleutel te vinden elke x seconden uitgezonden. Die gegevens zijn zelf ook weer asymetrisch vercijferd, de sleutel om dat te ontcijferen wordt met een periode van doorgaans eens per maand verzonden aan iedere kijker afzonderlijk (iedereen heeft daarvoor een aparte sleutel in zijn chipkaart), zodat mocht er een sleutel gevonden worden de kaart gewoon dichtgezet wordt.

Kortom, vind je de CSA-sleutel dan heb je 20 seconden beeld en heb je geen gegevens om aan de sleutel van de volgende 20 seconden komen. Vind je de sleutel om de CSA-sleutels te ontcijferen dan heb je een maand beeld. Vind je de sleutel in een chipkaart dan heb je permanent beeld, maar kan men je kaart dichtzetten door geen sleutelupdates voor je kaart meer te sturen.

[Orion84]

Niet elk key-negotiation schema is 100% afhankelijk van RSA nee. Maar RSA wordt wel vaak onderliggend gebruikt voor enige vorm van authenticatie. Als jij een RSA sleutel bemachtigt wordt het in allerlei protocollen mogelijk om man-in-the-middle attacks uit te voeren.

Diffie-Hellman biedt ook geen zekerheid, als de identiteit van de deelnemers niet gewaarborgd is.

Wat betreft CSA: ik ken dat protocol verder niet en uit jouw omschrijving kan ik niet direct helemaal helder voor de geest krijgen hoe het in elkaar steekt, maar inderdaad je kan protocollen best zo opzetten dat ze niet meteen helemaal nutteloos zijn als er een RSA sleutel gevonden wordt. Zeker met dergelijke verversingen, meerdere lagen en de mogelijkheid om clients te blokkeren bij ongeregeldheden kan je wel wat extra zekerheid inbouwen ja

[Lisadr]

Als het 2,5 jaar duur om elke een individuele RSA-768 key te kraken dan noem ik dit zeer veilig!

Pas als ze het binnen 1 week kunnen kraken, maak ik mij zorgen.

[Verwijderd]

Nou, dan zou ik me wel een beetje zorgen maken want deze kraak werd uitgevoerd door; 80 machines voor het eerste deel, en enkele 100den voor het tweede deel.

Volgens mij als je een botnet van enkele 100duizenden pc bestuurd, kan het binnen een halve dag!

[ProfPi]

Dat is een interessant punt. Is het algoritme van deze factorisatie eenvoudig te paralleliseren? Dus kan je het rekenwerk net zo eenvoudig over honderden als honderdduizenden computers verdelen?

Als dit niet het geval is, dan is er nog niet zo heel veel aan de hand. Als dit wél het geval is, zijn er dan crypto systemen die minder makkelijk zijn te paralelliseren?

[Arnoud Engelfriet]

Het is niet eenvoudig maar met enige moeite kun je dit kraakalgoritme wel parallelliseren.

[Sir Isaac]

Volgens mijn is het kraken van priemgetallen min of meer trial and error, en dus 100% efficiënt te paralleliseren.

[Bacchus]

Ja, dit parallelliseert als een trein, het is nl puur sleutel uitproberen.

[Strike_2]

Als een stel jongeren het met een paar honderd oude PC's kunnen doen in 2.5 jaar, hoe lang denk je dat overheidsinstanties met duizenden moderne computers erover doen?

[redfox314]

Als het 2,5 jaar duur om elke een individuele RSA-768 key te kraken dan noem ik dit zeer veilig!

Pas als ze het binnen 1 week kunnen kraken, maak ik mij zorgen.

Hangt er vanaf hoe lang je data interessant blijven. Stel jij stuurt een met RSA-768 geëncrypteerde email met informatie waaruit af te leiden valt dat je - verzin eens iets geks - de Russische maffia aan het oplichten bent.
Dat lijkt me informatie die je TENMINSTE tijdens jou leven niet aan het licht wil laten komen. Dan is 2,5 jaar ineens kort, of niet?