'Rsa-1024 niet meer veilig voor moderne pc's'

De nog altijd onkraakbaar geachte rsa-1024-encryptie wordt in hoog tempo minder veilig, beweren onderzoekers. Een nieuw factorisatierecord laat zien dat er geen duizenden jaren meer nodig zijn om dergelijke versleutelingen te breken.

Onderzoekers van het Japanse NTT DoCoMo en de universiteiten van Lausanne en Bonn slaagden erin om een getal van 307 decimale cijfers in priemfactoren te ontbinden. De wetenschappers hadden elf maanden nodig om het rekenwerk door ruim honderd computers te laten uitvoeren, wat een flinke verbetering van het vorige record van hetzelfde team is. Het in priemfactoren ontbinden van een getal van 200 cijfers kostte ze indertijd bijna achttien maanden. De rekentijd werd in beide gevallen gemaximaliseerd door getallen te kiezen die extra 'lastig' te ontbinden zijn, maar dankzij steeds snellere computers en steeds betere code wordt het factoriseren van grote getallen toch steeds eenvoudiger.

De onderzoeksresultaten betekenen in feite dat rsa-1024 langzamerhand als onveilig beschouwd moet worden. Dergelijke sleutels hebben ongeveer evenveel decimale posities als het getal dat nu gekraakt is, en kwaadwillenden met een botnetje zouden binnen afzienbare tijd gehakt van de encryptie kunnen maken. Desgevraagd zei wiskundige Arjen Lenstra, die tegenwoordig voor de universiteit van Lausanne werkt, dat rsa-1024 'zonder voorbehoud doodverklaard kan worden'. Omdat onder andere banken en webwinkels deze encryptievariant gebruiken om hun financiële transacties te beveiligen, is het dan ook zinvol om alvast aan een opvolger te gaan denken, zei Lenstra: 'Ik zal geen voorspellingen over de toekomst van rsa-1024 doen, maar je kan wel zeggen dat het verstandig is om de ontwikkelingen op de voet te volgen.' Overigens heeft RSA Laboratories de prijzen voor het ontbinden van een specifieke rsa-1024-sleutel onlangs gedeactiveerd.

Reacties (36)

[Ernie]

Is het niet zo dat elke beveiliging op den duur onveilig wordt, ofwel door modernere explosieven of gereedschappen of door krachtigere computers en betere code. Dus zo bijzonder is het nieuws eigenlijk niet, nu is het wachten op een nieuwe encryptiemethode die nog moeilijker te kraken is. Uiteraard is die na een aantal jaren ook weer te kraken. Zo blijft het elkaar opvolgen.

[Who Am I?]

Ik zat het zelfde te denken.
De wet van Moore gaat ook nog steeds op, dus het word ook nog eens steeds moeilijker om betere encryptiemethode te ontwikkelen.
Het enige wat ze kunnen doen is het hackers heel erg moeilijk maken

[Kaasje123]

Moeilijker?

Het lijkt mij een kwestie van langere sleutels dat is niet toch niet heel veel moeilijker of zie ik dat verkeerd?

[miw]

De wet van Moore verzwakt een sleutel met ongeveer 1 bit per 18 maanden. Dat komt overeen met 1 decimaal van een sleutel in 5 jaar. Het nieuws is dat er nu in een vergelijkbare periode een verzwakking van 100 decimalen is opgetreden. Ruim 99 decimalen zijn te danken aan betere wiskunde. Dat is zeker een nieuwswaardig resultaat.
Als kluiskrakers eenzelfde progressie zouden kunnen realiseren, zou een dergelijke scepsis volledig ontbreken in de nieuwsreacties.

[dasiro]

moore heeft zelf al gezegd dat zijn wet niet meer geldig is.

[Verwijderd]

Intern gebruiken wij 8192bits, en het is ook gemakkelijk door te voeren, echter de rekentijd om zo'n key te genereren en te gebruiken lopen snel op.

Een oude Pentium3 computer heeft er een aardige kluif aan en is soms vele minuten zoet bij het decoderen en uren (soms dagen) bij het genereren. Zelfs een server met 2x X5355 Xeons die wij gebruiken doet er soms enkele minuten over als we met sterke keys werken. Dat is dus ondoenelijk om dat voor banken online te gebruiken, waarbij de key in real-time gedecodeerd moet worden door de client voordat de pagina getoont wordt. Dus er moet helaas voor een gulde middenweg gekozen worden.

RSA-2048 zal dus langzaam eventueel ingevoerd worden, moet op zich niet zo'n heel groot probleem zijn.

[n4m3l355]

Hoezo is het ondoenelijk voor banken om dit te doen? Zij hebben ons als klant, en zij zouden garant moeten staan voor ons geld. Daar komen de lusten mee (het trekken van rente over ons geld) en de lasten (het veilig houden van ons geld).
Daarnaast sleutels worden onveilig naarmate computers sneller worden, omgekeerd betekend het dus ook dat we steeds zwaarder verhoudingsgewijs kunnen versleutelen.

[ppl]

Ondoenlijk omdat de klant vrijwel niet in staat is om die sleutel te ontcijferen. Zoals Ron.IT al zegt is het voor een P3 een flinke kluit en niet bepaald werkbaar meer. Als jij als klant eerst een minuut moet wachten voordat je kunt internetbankieren dan ga je vrij rap op zoek naar iets anders (andere bankiermethode of andere bank).

[Olaf van der Spek]

Intern gebruiken wij 8192bits,

Wie zijn wij dan, dat er zo'n extreem lange sleutel gebruikt wordt?

[elmuerte]

Nee. Onderandere de one-time-pad zal altijd veilig blijven.

[M-Opensource]

Is die techniek niet zo dat je bij elke zending aan beide kanten (zender/ontvanger) een nieuwe "code" of de-codering gebruikt?

Dan praat je in principe over een heel ander systeem toch? De Rsa-1024 code die wordt gemaakt is zo ingewikkeld dat het lang duurt om die ene code te breken...

OTP is in principe steeds een andere de-codeer sleutel gebruiken, dus de variabele factor bij een encryptie wordt extreem verhoogd...

Bij Rsa-1024 is er geen variabele sleutel.... Pin me er niet op vast... maar in mijn herinnering zit dit zo...

desalniettemin maakt dat de OTP extreem veilig natuurlijk...

[elmuerte]

One-time-pad is niets anders dan een simpele XOR met een unieke sleutel met dezelfde lengte als het bericht. Het word veiliger naar mate het bericht groter wordt.
Maar, omdat de sleutel zo groot is en uniek heb je er niet veel aan

[StefSybo]

Wat wil je zeggen met het "wordt veiliger naarmate het bericht groter wordt"?

Een one-time pad is altijd absoluut veilig in die zin dat het onmogelijk is om het oorspronkelijke bericht af te leiden, omdat elk bericht van dezelfde lengte als de onderschepte data een mogelijkheid is voor het originele bericht.

Als ik zeg dat ik een one-time pad heb toegepast op een enkele bit en het resultaat hiervan is 1 dan is het voor jou onmogelijk om te zeggen of de oorspronkelijke bit een 1 of een 0 was. Dus zelfs bij een bericht dat uit een enkele bit bestaat is de one-time pad al perfect veilig.
Die veiligheid gaat pas verloren op het moment dat je de key gaat hergebruiken, maar dan is het natuurlijk geen one-time pad meer.

Het probleem met de one-time pad is het overdragen van de key naar de ontvanger, dit moet natuurlijk absoluut veilig gebeuren. In het verleden leverde dat altijd grote problemen op, maar met de ontwikkeling van quantumcryptografie wordt het perfect mogelijk om een key veilig en gemakkelijk over te dragen. Op het moment dat quantumcryptografie algemeen beschikbaar komt wordt de one-time pad dus een praktisch bruikbare en absuluut onkraakbare vorm van encryptie.

[ILUsion]

Er bestaan al perfect veilige transmissieprotocollen (want dat is het beste woord om het te omschrijven in feite). Momenteel heb je zoals hieronder al aangehaald, de OTP (Vernam cipher/One Time Pad). Deze komt er in feite op neer dat je een sleutel neemt die even lang is als het bericht, en compleet willekeurig (dus bij elke transmissie ook verschillend), waardoor iemand die het versleutelde bericht afluistert (maar niet de sleutel) er geen brute force-aanval op kan loslaten, want door de willekeurigheid van de sleutel, heeft het versleutelde bericht een stukje van die willekeurigheid overgekregen. Het sleutelde bericht kan voor de hacker dus elke mogelijke boodschap zijn van die bepaalde lengte. Met sleutels die korter zijn dan het bericht, kan men via cryptoanalytische technieken patronen ontdekken in het versleutelde bericht en zo meer te weten komen over het bericht/de sleutel. Met OTP heeft dat geen enkele zin, vermits de sleutel willekeurig is.

RSA is in tegenstelling tot OTP geen encryptie die steunt op wiskundige veiligheid. RSA behoort tot de familie Public Key-encrypties, die eigenlijk steunen op het feit dat de huidige computers moeilijk kunnen priemontbinden. En dat is hetgene dat er nu gebeurt: we vinden steeds betere technieken en algoritmes die die veronderstelling onderuit halen. In dat opzicht heb je gelijk dat wat betreft Public Key, het een kwestie van kat-en-muis-spelletje is. Want daarna valt de keuze op langere keys (en dus ook langere rekentijd, maar die langere rekentijd gaat net zo goed op bij het encrypteren/decrypteren van het bericht, dus: wordt minder handig). Het gekende PGP/GPG (Pretty Good Privacy) heeft een tussenweg die een combinatie van gewone cryptografie en public key gebruikt. Het ontbinden in priemfactoren is trouwens iets dat met quantumcomputers vrij makkelijk te doen zou moeten zijn.

Maar de nieuwe aankomende oplossing is quantum-cryptografie. Hiermee kan men (met de huidige kennis van zaken) met een zekerheid van 100% een sleutel doorsturen die niet afgeluisterd kan worden. En eenmaal je sleutel veilig overgebracht is, kan het bericht natuurlijk met bv. een klassieke OTP doorgestuurd worden. Vermits OTP perfect veilig is (als de sleutel veilig overeengekomen is, tenminste), is het bericht ook onkraakbaar beveiligd. Hier hangen enkele veronderstelling aan, op quantumfysisch niveau; dat het volgens mij nogal onwaarschijnlijk is dat men de eerste honderd jaar daar omwegen voor zou vinden (ik heb het dan onder andere over het niet exact kunnen dupliceren van een foton, niet kunnen waarnemen van een foton zonder de golfvergelijking van dat foton te wijzigen (wat volgende de huidige kennis gewoon een vaststaand feit is)).

[Olaf van der Spek]

Het gekende PGP/GPG (Pretty Good Privacy) heeft een tussenweg die een combinatie van gewone cryptografie en public key gebruikt.

SSH, SSL/TLS toch ook?

RSA is in tegenstelling tot OTP geen encryptie die steunt op wiskundige veiligheid.

Zijn er dan nog andere wiskundig veilige protocollen?

Maar de nieuwe aankomende oplossing

Nou ja, oplossing?
Volgens mij werkt dat totaal niet over bijvoorbeeld het huidige internet.

[halfgaar]

GPG kan met RSA werken, maar de meesten hebben een DSA key. Ik weet alleen niet hoeveel veiliger dat is. Gelukkig is mijn key 2048 bits.

SSH gebruikt RSA nog vrij intensief. Mijn users heeft een RSA private key, en dat zou dus kunnen betekeken dat mensen dat relatief makkelijk kunnen kraken. Ik weet alleen niet hoeveel bits hij is.

edit: ik zie dat ssh-keygen default 2048 doet, dus dat zal eerst wel goed zitten.

[cdwave]

Je bent al de tweede die hier beweert dat je een OTP key veilig wil kunnen oversturen, en dat dan alle problemen verdwijnen.

De OTP key is echter net zo groot als de data die je verstuurd. Het is dus efficienter om meteen de data via het veilige pad te versturen.

[Verwijderd]

houd dit misschien verband met het feit dat RSA een paar dagen terug de stekker uit het door hen gesponsorde RC5-72 project hebben getrokken?

zie:
http://n0cgi.distributed....ine&plan=2007-05-21.04:34

[deathz0rz]

Om precies te zijn, een getal met 307 decimale cijfers is 1019 of 1020 bits.

[Qwerty-273]

de snfs dificulty was anders wel 1039 bits - en dus stapte net over het randje van een kilobit snfs heen.

[.oisyn]

Ze kunnen ook niet rekenen

Uit de bron:

The 307-digit number itself was not an RSA key—the number was 2¹⁰³⁹-1

In mijn boekje heeft 2¹⁰³⁹-1 nog altijd 313 decimale digits. Iets klopt er dus niet in het bericht.

[Qwerty-273]

Als je een beetje door had gelezen (of andere juiste bron opgezocht) dan wist je dat er al een factor van 7 digits bekend was.

[.oisyn]

Ik denk dat jij zelf in de war bent met een andere bron hieromtrend, want zowel het t.net artikel als de bron voor het t.net artikel zegt niets over dat er al een factor bekend was. Ook de vele andere nieuwberichten hierover die op het internet te vinden zijn zeggen daar iets over.

Dus in plaats van mij betichten dat ik niet het hele artikel doorgelezen zou hebben of niet zou zoeken, zou je zelf ook behulpzaam kunnen zijn en jouw bron hier gewoon vermelden waar dat dan wél in staat

.edit: found it:
http://www.ddj.com/blog/p...7/05/world_record_fo.html

The experimental results show the completion of integer factorization for a world record of a 1017-bit composite number, a substantial increase over the special number field sieve method world record (911 bits). The results go on to show the factorization for (2^1039-1)/5080711, a special-type composite number.

[Qwerty-273]

Zoiets als dit wordt vaak aangekondigd op de NMBRTHRY list.

In dit geval:
http://listserv.nodak.edu...705&L=nmbrthry&T=0&P=1019

Of de press release bij NTT:
http://www.ntt.co.jp/news/news07e/0705/070521a.html

[Niemand_Anders]

Het belangrijkste mis ik, namelijk of bij het encrypten gebruik is gemaakt van PKCS1 of OAEP (Optimal Asymmetric Encryption Padding). Padding voorkomt dat het resultaat priemgetallen uit het private exponent bevat.


Overigens zijn deze bezoekers er slechts in geslaagd om priem getallen uit een lang getal te halen. Welke daarvan worden gebruikt voor de betreffende RSA private key weten ze dus nog niet. Ik vind het dus nogal ver gaan om RSA als onveilig te verklaren...

Ter vergelijking ze zeggen eigenlijk dat ze weten dat je pincode bestaan uit 4 cijfers in de range 1, 2, 3, 4, 5, 6, 7, 8, 9 of 0. Welke ook daadwerkelijk worden gebruikt en in welke volgorde kunnen ze nog niet zeggen.


Daarnaast, in de meeste gevallen waar RSA encryptie wordt gebruikt is de data 'vluchtig'. Dus tenzij ze er in realtime inslagen om RSA te decrypten kun je er nuttige dingen mee doen zoals een 'Middle of the man' attack in een SSL conversatie of militaire data wijzigen.

[Jefrey Lijffijt]

Dat klopt niet, als je de factorisatie hebt kun je zowel de sleutel vinden als berichten veel sneller decoderen.

Zoals het artikel is opgezet beweren de onderzoekers dat ze iedere sleutel in eenzelfde tijd kunnen kraken (slimme bruteforcing dus) en niet dat ze truukjes hebben om misbruik te maken van slecht gekozen sleutels.

[ronny]

De onderzoeksresultaten betekenen in feite dat rsa-1024 langzamerhand als onveilig beschouwd moet worden.

Het enige wat hier dus beweerd wordt is dat het moment van kraken nu dusdanig dicht bij komt dat er gewerkt moet worden aan een opvolger.
Je moet met zullke dingen niet wachten tot jan en alleman het kraken kan want dan ben je telaat.

Je voorbeeld is in zoverre goed dat je van de pincode van 4 karakters nu weten dat het 4 cijfers zijn en geen letters.
Dat betekent dat het aantal mogelijkheden drastisch is beperkt.

[Mitsuko]

Het is trouwens well 'man in the middle'.. dit doet me een beetje denken aan 'mond-op-mond reclame' (ipv mond-tot-mond)

[Olaf van der Spek]

Welke ook daadwerkelijk worden gebruikt en in welke volgorde kunnen ze nog niet zeggen.

De getallen zijn toch zo priem mogelijk? Zoveel factoren zullen er dus niet zijn.

En als je eenmaal de private key hebt, lijkt het me dat je SSL realtime kunt decrypten.

[IStealYourGun]

Als men een botnetwerk voor zo een doelen gaan gebruiken zal het volgens mij geen lang leven meer hebben.

Ik merk van support forums dat de meeste mensen 'pas' spyware/virus vermoeden als hun PC 'trager' loopt.

[Wilke]

Als men een botnetwerk voor zo een doelen gaan gebruiken zal het volgens mij geen lang leven meer hebben.

Ik merk van support forums dat de meeste mensen 'pas' spyware/virus vermoeden als hun PC 'trager' loopt.

Dus schrijf je bot zo dat hij alleen idle time gebruikt. Of maar 10-20% CPU-tijd gebruikt en de rest van de tijd yield aan andere processen.

Of iets in die geest. Anyway, dat zal geen onoverkomelijk probleem zijn.

Je kunt dergelijke processen ook wel weghouden uit de proceslijst (anders zou het wellicht ook wat gaan opvallen), als je maar een rootkit hebt.

[dj_raoul]

Als het echt zo 'makkelijk' te kraken was zou die 100.000 dollar toch al lang opgeeist zijn?

[Verwijderd]

Hmm..
Ik weet niet of ik mijn botnetje zou prijsgeven als ik de sleutel te pakken kreeg. Geef mij maar de account-inhoud van de KBC (of ABN of Rabo ofzo), ipv die 'schemiele' 100.000. toch?

[mind_]

De eerste die de sleutel zal kraken (of al gekraakt heeft) zal de NSA zijn en ik weet niet of die de 100.000 dollar gaan claimen.

[Verwijderd]

Dit was een probleem met een specifiekere algebraïsche structuur dan een willekeurig RSA-1024 probleem. M.a.w. het was simpeler. Om daaruit dan meteen te generaliseren dat dan heel RSA-1024 onveilig zou zijn is voorbarig. Tot nu toe is nl. niemand er publiekelijk in geslaagd om een willekeurige instantie van RSA-1024 op te lossen.

[DaaNMageDDoN]

Nu hoor ik een paar mensen zeggen dat de wet van Moore opgaat. Los ervan of dat zo is:

Als ik mijn sleutel lengte verdubbel, is het dan niet zo dat het kraken ervan 4 maal zo lang zal duren (in theorie)?

Dus iedere 2 jaar de lengte van de sleutel verdubbelen is meer dan genoeg?