RSA, een veelgebruikt systeem voor asymmetrische cryptografie, blijkt kwetsbaarder dan gedacht. Onderzoekers kunnen onder bepaalde omstandigheden geldige digitale handtekeningen maken zonder de privésleutel te achterhalen. Daarmee blijkt een belangrijke aanname over de beveiliging van RSA niet altijd op te gaan.
Dit meldt Ars Technica. Het onderzoek betekent niet dat RSA-beveiliging op grote schaal kan worden gekraakt. De aanval werkt alleen bij specifieke implementaties die gebruikmaken van zogeheten blinde handtekeningen. Systemen met de tegenwoordig gebruikelijke PKCS- of PSS-padding zijn er niet vatbaar voor.
De ontdekking is vooral interessant omdat cryptografen lang aannamen dat een aanvaller voor het vervalsen van een RSA-handtekening eerst de privésleutel moest achterhalen. Dat vereist het ontbinden van zeer grote getallen in priemfactoren. Juist de enorme hoeveelheid rekenwerk die daarvoor nodig is, vormt de basis van de beveiliging van RSA.
De onderzoekers, onder wie Nadia Heninger van de University of California San Diego, hebben nu een andere route gevonden. Met een variant van het number field sieve-algoritme kunnen zij rechtstreeks een geldige handtekening construeren. Factorisatie van de RSA-sleutel is daarbij niet nodig.
Fors minder rekenkracht
Het verschil in benodigde rekenkracht is groot. Voor het factoriseren van een verouderde 1024-bits RSA-sleutel wordt gerekend op 500.000 tot een miljoen CPU-corejaren. De onderzoekers hadden voor hun aanval 1.380 corejaren nodig. Uitgevoerd op een academisch computercluster nam dat enkele maanden in beslag.
Ook bij grotere sleutels verandert de rekensom. Het geschatte beveiligingsniveau komt volgens de onderzoekers uit op 2 tot de macht 90 (2^90) bewerkingen voor 2048-bits RSA en 2 tot de macht 119 (2^119) voor 4096-bits RSA. Beide waarden liggen onder het niveau van 128 bits dat tegenwoordig als uitgangspunt voor sterke cryptografie wordt gebruikt.
Daarbij is de methode nog nauwelijks geoptimaliseerd. Het team gebruikte bijvoorbeeld geen GPU’s. Verdere technische verbeteringen zouden de hoeveelheid benodigde rekenkracht dus nog kunnen verminderen, aldus Ars Technica.
Geen probleem voor regulier RSA
Voor organisaties is er vooralsnog weinig reden tot ongerustheid. Moderne RSA-implementaties voegen met PKCS of PSS extra gegevens toe aan de cryptografische verwerking. De nieuwe techniek werkt daar niet tegen.
Een toepassing waar de onderzoekers wel naar kijken is Privacy Pass. Dit protocol laat gebruikers bewijzen dat zij geautoriseerd zijn zonder hun identiteit bekend te maken. Onder meer Apple en Cloudflare gebruiken het. Voor een aanval zouden ongeveer 2^43 aanvragen bij één organisatie nodig zijn. Regelmatige vervanging van cryptografische sleutels maakt misbruik bovendien aanzienlijk lastiger.
De belangrijkste consequentie van het onderzoek ligt daarom niet bij een onmiddellijk beveiligingslek, maar bij de theorie achter RSA. Het blijkt mogelijk de beveiliging ervan aan te vallen zonder het wiskundige probleem op te lossen waarop RSA traditioneel steunt.
Dat is relevant nu organisaties toch al voorbereidingen treffen om klassieke cryptografie te vervangen door algoritmen die bestand zijn tegen toekomstige quantumcomputers. De nieuwe methode maakt die migratie niet plotseling urgent, maar laat wel zien dat ook met gewone computers nog nieuwe manieren kunnen worden gevonden om de veiligheidsmarges van RSA te verkleinen.