Onderzoekers vinden ruim 200.000 rsa-privésleutels door analyse grote dataset

Onderzoekers van het beveiligingsbedrijf Kudelski Security hebben ongeveer 210.000 rsa-privésleutels weten te achterhalen door een grote dataset met publieke sleutels te analyseren. Daarbij gebruikten ze bekende methodes, die al eerder voor hetzelfde doeleinde zijn toegepast.

De onderzoekers maakten gebruik van een techniek die bekendstaat als batch gcd, waarbij die laatste afkorting staat voor greatest common denominator, oftewel de grootste gemene deler. Omdat een rsa-sleutel aan de hand van twee of meer grote priemgetallen wordt gegenereerd, zijn er soms sleutels die eenzelfde factor delen. Batch gcd maakt hiervan gebruik om de privésleutel te achterhalen. De onderzoekers legden uit dat deze methode sneller werkt met een grotere dataset aan sleutels. Hun bedrijf is niet het eerste dat deze aanpak gebruikt, zo deed Cryptosense ongeveer hetzelfde in 2015.

Ze verzamelden allerlei verschillende sleutels, in totaal meer dan 340 miljoen in een groeiende collectie. Daarvan waren bijna 70 procent sleutels uit X.509-certificaten, die gebruikt worden voor het beveiligen van https-verbindingen. Die vonden ze door een eigen scanner te gebruiken. Iets minder dan een derde van de verzameling bestaat uit ssh-sleutels, waarvan de ruime meerderheid afkomstig is uit de bestaande CroCS-dataset en een kleiner aantal uit eigen scans. Een klein restpercentage, ongeveer drie procent, betrof pgp-sleutels. Die hadden ze in veruit de meeste gevallen verzameld via sleutelservers. Het verzamelproces strekte zich uit over de periode van een jaar.

De 210.000 met behulp van batch gcd achterhaalde sleutels waren in 207.000 gevallen sleutels van digitale certificaten, waarvan er meer dan 1400 nog in gebruik waren in het afgelopen jaar. In de meeste gevallen ging het om routers. Verder achterhaalden ze meer dan 3100 ssh-sleutels en bijna 300 pgp-sleutels. De onderzoekers keken niet alleen of de sleutels kwetsbaar waren voor batch gcd, maar ook voor een aanval die bekendstaat als Roca.

Deze maakt het mogelijk de privésleutel aan de hand van de publieke sleutel te achterhalen bij paren die gegenereerd zijn met bepaalde Infineon-chips. Ze vonden 4000 sleutels die hiervoor kwetsbaar waren, waarvan ongeveer een derde ook daadwerkelijk gevaar liep doordat een sleutel van 2048bit was gebruikt. De rest gebruikte 4096bit, waartegen een aanval niet interessant zou zijn.

Tijdens hun analyse kwamen de onderzoekers er ook achter dat in minstens 3400 gevallen gegenereerde sleutels voor zowel X.509-certificaten als voor pgp of ssh werd gebruikt.

Reacties (26)

[GateKeaper]

Dus van de 340.000.000 public keys die ze hebben, waren er 210.000 waarvan de private key te bepalen is. Dat is 0,06%. Een veiligheid van 99.94% dus.

Enerzijds zorgwekkend artikel. Aan de andere kant klinkt het nog behoorlijk veilig.

Lesson learned; gebruik niet langer 2048bit, maar gebruik 4096bit keys. En ook dan, upgrade naar hogere bits wanneer systemen daar sneller mee kunnen werken.

Het protocol is niet lek, het is de enorme dataset die ze hebben die dit mogelijk maakt. Hadden ze geen 340 miljoen sleutels, maar slechts die 210.000 gekraakte, dan waren die naar alle waarschijnlijkheid niet gekraakt.

Zo is het weer eens benadrukt dat er gevolgen hangen aan big data.

[robvanwijk]

Hadden ze geen 340 miljoen sleutels, maar slechts die 210.000 gekraakte, dan waren die naar alle waarschijnlijkheid niet gekraakt.

Als ik de uitleg van batch gcd goed begrijp, dan is dat niet zo. Als ze op de één of andere (volkomen onverklaarbare) manier precies de 210.000 kwetsbare sleutels hadden gehad, maar geen enkele niet-kwetsbare, dan zouden ze nog steeds allemaal gekraakt zijn.

Dus van de 340.000.000 public keys die ze hebben, waren er 210.000 waarvan de private key te bepalen is. Dat is 0,06%. Een veiligheid van 99.94% dus.

Mooi getal, maar wat betekent het in de praktijk? Het is wat mij betreft niet duidelijk hoe je als eigenaar van een key kunt nagaan of jouw key bij 0,06% of juist bij de 99.94% hoort. Als er een database van password hashes uitlekt waarvan 0,06% gekraakt kan worden, dan heb je wel degelijk een grote mate van controle of jouw password te kraken is. In dit geval lijkt het puur en alleen gebaseerd te zijn om stomme pech; als iemand jouw sleutel probeert te kraken en toevallig een andere sleutel heeft met daarin dezelfde priemfactor, dan ben je de sjaak, maar er is niets wat je kunt doen (nou ja, een sleutel baseren op twee, in plaats van meer dan twee, factoren) om je daartegen te verdedigen. Dat lijkt me niet bepaald een acceptabel resultaat voor sleutels die zeer gevoelige data(verbindingen) beveiligen.

Lesson learned; gebruik niet langer 2048bit, maar gebruik 4096bit keys.

Dat vraag ik me af. Als RSA keys uit meer dan twee priemfactoren bestaan omdat we simpelweg niet (snel genoeg) priemfactoren kunnen genereren die groot genoeg zijn om aan twee factoren genoeg te hebben (en ik heb geen flauw idee of dat ook echt de reden is; het is echter de enige reden die ik kan verzinnen), dan zullen 4096 bit keys uit twee keer zoveel factoren bestaan dan 2048 bit keys. Dan maak je het probleem dus alleen maar groter.

Als mijn redenatie hierboven klopt, dan is één 4096 bit key moeilijker net zo makkelijk ^*) om te kraken dan als één 2048 bit key, maar zou een verzameling van een miljoen 4096 bit keys makkelijker te kraken zijn dan een verzameling van een miljoen 2048 bit keys...!? Is er iemand in de zaal die echt weet waar ie het over heeft en hier een second opinion over kan geven?

<edit>
*) De lengte van de priemfactoren blijft hetzelfde, het zijn er alleen twee keer zoveel. In dat geval duurt kraken van één factor ruwweg net zo lang voor beide key lengths. Ik heb nog niet uitgezocht of je één factor of alle factoren moet kraken om een sleutel te achterhalen. Maar zelfs als je alle factoren moet hebben duurt het kraken van 4096 bits dan echter twee keer zo lang (lineaire schaling) als het kraken van 2048 bits, terwijl het eigenlijk "bijna oneindig" keer zo lang (exponentiële schaling) zou moeten duren. Zie de disclaimer hieronder; ik moet nog uitzoeken hoe een sleutel met meer dan twee factoren precies werkt.
</edit>

Disclaimer:
Toen ik het artikel las dat ik in eerste instantie dat de auteur een fout had gemaakt met "twee of meer grote priemgetallen" en dat het "precies twee grote priemgetallen" had moeten zijn. Maar, in dat geval zou deze aanval niet kunnen werken, dus daar moet ik me in vergissen. Als ik dat verkeerd begrepen heb, dan is er een kans dat mijn verdere redenatie ook foutief zou kunnen zijn.

[Reactie gewijzigd door robvanwijk op 23 juli 2024 04:24]

[uiltje]

OK, I'll bite.

Multi-prime RSA bestaat wel, maar wordt nog weinig ingezet. Dit helpt niet alleen met het vinden van de priemgetallen; RSA is erg langzaam met het genereren van sleutelparen, maar 4096 bits sleutels zijn snel genoeg gegenereerd. Het is vooral handig om de operaties van de private sleutel zelf te versnellen. Dit kan door gebruik te maken van de Chinese Remainder Theorem (CRT). De CRT parameters bevatten namelijk de priemgetallen.

Bijna alle RSA sleutel paren worden gegenereerd uit twee priemgetallen. Vanwege specifieke aanvallen zijn die beide (ongeveer) de helft van het aantal bits van de sleutel. Dus bij RSA met 2048 bits key heb je twee priemgetallen van 1024 bits en RSA met 4096 bits heb je twee priemgetallen van 2048 bits. Het aantal priemgetallen blijft sterk groeien als het aantal bits groter wordt. Dus er zijn veel meer priemgetallen mogelijk bij 4096 bits dan bij 2048 bits. De dichtheid neemt wel af, maar niet genoeg om de groei van het aantal mogelijkheden bij te houden (het algoritme is wel te vinden, maar is nogal stevig, dus ik zal het je onthouden).

Het feit dat er botsingen zijn met de priemgetallen komt niet door toevallige botsingen. Er zijn zoveel mogelijkheden dat zelfs de birthday paradox er geen invloed op zou moeten hebben. Het probleem is dat of de random nummer generator of de RSA (key pair) generator niet goed functioneerde. Hierdoor kunnen de botsingen ontstaan. Over het algemeen maakt bij dit soort problemen de sleutel grootte niet al te veel uit. Tevens zal het gebruik van multi-prime niet veel invloed hebben (behalve dat halve oplossingen zoals die van Gemalto minder noodzakelijk zijn bij multi-prime RSA).

Ik sta in de top 10 bij https://crypto.stackexchange.com voel je vrij om daar vervolgvragen te stellen.

[Reactie gewijzigd door uiltje op 23 juli 2024 04:24]

[robvanwijk]

In het Wikipedia artikel over RSA kon ik geen uitleg over multi-prima RSA vinden, maar op Stack Exchange (goede tip, dankjewel!) kwam ik deze vraag en dit antwoord (op een andere vraag) tegen. Het lijkt erop dat de wiskunde simpelweg blijft werken (daarvan was ik in eerste instantie niet meteen overtuigd) en dat het beoogde voordeel is dat een aantal bewerkingen sneller worden (waarom dat zo interessant is ontgaat me; voor zover ik weet is public key crypto sowieso te traag om er volledige berichten mee te versleutelen, dus het wordt alleen maar gebruikt voor het versleutelen (en veilig uitwisselen) van symmetrische sleutels).

[uiltje]

Nou ja, elke keer dat een HTTPS connectie gemaakt wordt heb je toch een RSA private key operatie nodig op de server (mits een RSA eind-certificaat gebruikt wordt, natuurlijk). Dat kan bij elkaar nog lekker optellen, zeker als je bedenkt dat - vergeleken met AES bijvoorbeeld - RSA inderdaad erg traag is. Het verlaagt ook de latency van het opzetten van een verbinding. Niet voor niets wordt er in TLS 1.3 gebruik gemaakt van session-resumption met 0-RTT.

RSA wordt ook gebruikt voor smart cards en ander embedded systemen, waarbij de vertraging nog veel groter is dan op high end server systemen.

Dat het genereren van een private key ook sneller is maakt minder uit; meestal worden private keys niet gemaakt voor kort gebruik (en waar dat wel het geval is schakelt men meestal over naar (EC)DH. Maar zelfs dan: probeer eens een 16K key te maken met openssl; vergeet niet eerst een bakkie te zetten (merk op dat de tijd dat het kost om een priemgetal te vinden niet deterministisch is: soms gaat het snel, soms heeeel traag). Dat geld dus ook voor de generatie van het sleutelpaar met twee priemgetallen.

[xorpd]

Het probleem is niet de sleutellengte (ook 1024-bit RSA is nog steeds veilig hoor) maar de entropie van de gebruikte random generator, die is nogal laag bij stand-alone devices zoals routers, waardoor dezelfde keys gegenereerd worden.

Simpel voorbeeld: als de entropie slechts 30 bit is, is er een kans van 1 op een miljard dat 2 devices dezelfde key genereren. Meerdere devices verhogen die kans aanzienlijk.

[Reactie gewijzigd door xorpd op 23 juli 2024 04:24]

[Roani52]

Zojuist 'even' uitgerekend voor het 2048 bit scenario:
Als een willekeurig priemgetal tussen de 1 en 2^2048 zou liggen zijn er bij benadering 2^2048/(log(2^2048)-1) priemgetallen te vinden. De kans dat er van de (minimaal) 680 miljoen getallen er 2 of meer gelijk zijn komt dan op ('afgerond') 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002984881% uit.
Nemen we nu in plaats daarvan een entropie van die 30 bit (dus daadwerkelijk 2^30 mogelijke priemgetallen) is de kans dat er 2 of meer gelijk zijn ineens 46.9%. Dat betekent dus niet dat ~47% van de sleutels op deze manier gekraakt kan worden, het is dat er 47% kans is dat er minimaal 2 gelijke priemgetallen zitten in die 680 miljoen. Ofwel, er is 47% kans dat er 2 sleutels uit de 340 miljoen op deze manier gekraakt kan worden. Ik zou zeggen dat dat toch wel significant minder is dan de 0,06% genoemd door @GateKeaper, ook al neem je aan dat er 30 bit aan entropie is.
Er is dus iets flink mis met hoe deze getallen gegenereerd worden als blijkt dat er 'zo veel' priemgetallen met deze methode te achterhalen zijn. Nu ben ik redelijk onbekend op dit gebied, maar ik kan me voorstellen dat wanneer er vooral gebruik gemaakt word van mersennepriemgetallen (priemgetal in de vorm 2^n-1) je het aantal mogelijke priemgetallen flink vermindert.

[xorpd]

Ik heb het even nagerekend, en je berekening klopt. 1 - (1 - 1 / 2^30) ^ 680M. Maar de berekende kans is dat er minimaal 2 dezelfde sleutels inzitten, niet exact 2.

P.S. Mersenne priemgetallen zijn onwenselijk, daar zijn er veel te weinig van.

[Reactie gewijzigd door xorpd op 23 juli 2024 04:24]

[Roani52]

Maar de berekende kans is dat er minimaal 2 dezelfde sleutels inzitten, niet exact 2.

Klopt inderdaad, maar gegeven dat er minimaal 2 dezelfde priemgetallen inzitten is het meest aannemelijke 2. De kans op meer neemt snel vrij snel af. Voor de conclusie maakt het niet zo veel uit, maar misschien had ik het iets anders moeten opschrijven.

Ik had voornamelijk mersennepriemgetallen genoemd juist omdat het er niet zoveel zijn en dat ze vrij gemakkelijk gevonden kunnen worden in een binair systeem als een computer, op zoek naar een verklaring voor het relatief grote aantal gevonden sleutels. Blijkt alleen dat er nog minder van zijn dan ik had verwacht
Ik had aangenomen als 2^n-1 dan en slechts dan is n priem, in plaats als 2^n-1 dan is n priem. Scheelt toch zo'n factor 20 in het aantal beschikbare onder 2^2048 (15 in plaats van ~300)

[rewolff3]

Het "verjaardagparadox" zegt dat je er behoorlijk naast zit. Redeneer even als volgt.

Stel je bent die 0.68 miljard getallen met 30 bits entropy aan je verzameling aan het toevoegen. Maar druk even op "pauze" zo'n 100 getallen voor het eind. Als we voor het gemak even aannemen dat we nog geen doublures hebben, dan is zo'n 68% van de mogelijke 1 miljard getallen bezet. Pakken we nu nog 1 getal, dan heeft die een 68% kans om gelijk te zijn aan 1 van de eerdere getallen. 34% kans op weer een unieke. Doen we dit 100x, dan is de kans 0.34^100 dat we nog steeds geen doublures hebben. Dit is ongeveer 10^-47. De kans dat je met een 30-bit space en 680 miljoen getallen doublures hebt is 100% (afgerond op 40 cijfers achter de comma).

Die 46% die jij hebt uitgerekend is de kans dat de laatste twee alletwee geen doublure zijn. Zoiets.

[Roani52]

Ai, ja je hebt volledig gelijk. In dat geval is de kans op 640 miljoen unieke getallen (bij 30 bits) 2.89e-82835099. Daar laat ik het maar bij, de getallen worden nu te groot om überhaupt nog mee te kunnen rekenen.

[uiltje]

RSA 1024 biedt een sterkte van ongeveer 80 bit en zou eigenlijk niet meer gebruikt moeten worden. RSA-2048 is met 112 bit nog steeds een stuk minder sterk dan bijvoorbeeld AES-128. Pas vanaf 3072 bits ben je echt toekomstbestendig - tenminste als Quantum Computing niet plotseling op komt.

Een curve van 256 bits biedt ook 128 bits aan veiligheid; daarom is Elliptic Curve Cryptography momenteel veelgebruikt. Post Quantum Cryptography is in opkomst, maar dat gaat heel langzaam.

Als je sleutellengtes wilt vergelijken: https://keylength.com

[Reactie gewijzigd door uiltje op 23 juli 2024 04:24]

[GarBaGe]

En met regelmaat je sleutels vernieuwen / vervangen.
Bijvoorbeeld jaarlijks.

[rbr320]

Voor SSH gebruik ik al jaren ED25519 sleutels. Volgens de bronnen die ik er over heb gelezen bied dit type sleutel betere beveiling en performance dan RSA. Het enige nadeel is dat er nog oudere sytemen in gebruik zijn die het niet ondersteunen.

https://ed25519.cr.yp.to/
https://risan.io/upgrade-ssh-key-to-ed25519.html
https://security.stackexc...tication-keys/46781#46781

[GekkePrutser]

En dat deze zich nog niet zo lang bewezen hebben. Voor hetzelfde geld wordt er weer een slimmigheidje bedacht. RSA heeft al veel langer onder vuur gelegen. Het grote voordeel van elliptic curve technieken als ES25519 is wel dat ze bestand zijn tegen quantum computing maar dat is nu nog steeds geen ding (niet voor deze sleutelgroottes).

Overigens, in het geval van SSH private key login hou je normaal gezien je publieke EN je prive gedeeltes geheim. Tenzij je het mixt en je publieke PGP key ook voor SSH gebruikt, maar dat lijkt me sowieso niet zo wijs. Dus deze techniek levert hier geen voordeel op.

Het publieke deel staat wel op de server maar als die gecompromitteerd wordt dan heb je de sleutel ook niet meer nodig.

Dus ja op zich is het een mooie techniek maar ik zou er ook niet echt haast me emaken.

[Reactie gewijzigd door GekkePrutser op 23 juli 2024 04:24]

[twizzle]

Dat helpt misschien bij logins maar als je geheime gegevens verstuurdt ben je nog steeds de pineut wanneer je sleutel gekraakt is

[Cerberus_tm]

Nu vraag ik me af of het totaal onvoorspelbaar is welke sleutels ze konden kraken, dan wel bepaalde sleutels kwetsbaar waren om specifieke redenen. Wat zijn die redenen dan? En hoe kan het dat dit soort sleutels zo onveilig zijn? Is dit te vermijden?

Update:

De volgende tekst komt van bovenstaand artikel van Cryptosense uit 2015:

While there are valid reasons to use an RSA modulus consisting of the product of several large primes, in this case we found several small prime factors and one large one. Taken in context, this seems to indicate either a flawed key generator that is being used by a tiny number of people, or a corner-case flaw in a more widely used key generator that only exhibits itself very very rarely. It could also be something more banal like a corrupted single character somewhere in the base-64 encoding of the key. However, it’s impossible to identify how SSH keys were generated from the resulting public key, so for the moment we are in the dark. We have asked GitHub to help us contact the users to investigate this further. We will continue to update this post with further information.

Helaas hebben ze die pagina nooit geüpdate. Ik ben heel benieuwd wat het nou uiteindelijk was dat deze zwakte veroorzaakte, en ook wat de zwakte heeft veroorzaakt in deze nieuwe set sleutels.

[Reactie gewijzigd door Cerberus_tm op 23 juli 2024 04:24]

[ToolBee]

Ook de snellere hardware van nu helpt mee dit soort "klusjes" in een voor mensen overzichtbare termijn te klaren.

[dasiro]

dus als ik het goed begrij kan je hierdoor potentiëel een dns opzetten die aan de hand van de gevonden private keys een phishing-site als legitiem laat doorgaan en misschien ook transacties onderscheppen?

edit: misschien ook zelfs rechtstreeks in routers ?

[Reactie gewijzigd door dasiro op 23 juli 2024 04:24]

[M.l.]

Ja, en nee. Mocht toevallig de privesleutel van hotmail.com er tussen zitten, dan kan jij verbindingen met precies die website onderscheppen. Verder niet. Wel kan je, als je toevallig al heel erg veel versleutelde verbindingen hebt afgeluiserd , een deel daarvan decoderen, maar dan ook alleen van verbindingen waar een van de gekraakte sleutels is gebruikt (en waar verder ook geen extra veiligheidsmaatregelen zijn getroffen).

[uiltje]

Je kan je voordoen als de website inderdaad, of een MitM doen.

Tegenwoordig maken veel verbindingen gebruik van ephemeral-ephemeral ECDH key agreement. Daarbij worden de master sleutel (die gebruikt wordt om de sessie sleutels af te leiden) niet versleuteld door de RSA sleutel, en is het het dus onmogelijk om een sessie te ontsleutelen met behulp van de RSA private key. Dit wordt forward security genoemd; bij TLS 1.3 worden alle verbindingen zo opgezet.

[Reactie gewijzigd door uiltje op 23 juli 2024 04:24]

[blissard]

Pff, dat is niets. Ik ken iemand die alle pincodes van alle Nederlanders kent. https://youtu.be/p54CXA2eilk

[dasiro]

getallen van 0001 tot 9999 "kennen" is geen verdienste, zeker niet als als je maar een paar keer mag gokken vooraleer ze geblokkeerd is, dat noemen ze bruteforcen.

[WhiteDog]

Het is dan ook een grapje...