Onderzoekers van de Universiteit van Californië in San Diego hebben een geavanceerde aanvalstechniek op het RSA-algoritme ontwikkeld, waarmee digitale handtekeningen kunnen worden vervalst zonder factorisatie van de onderliggende priemgetallen van RSA en zonder de privé-sleutel te hoeven herstellen. De middelen die nodig zijn om een aanval uit te voeren op een RSA-sleutel van 1024 bits, zijn geschat op 1380 jaar rekentijd op één processor kern, wat het mogelijk maakte om in vijf maanden de parameters te bepalen die nodig zijn voor het genereren van valse RSA-handtekeningen op het universitaire cluster (in het experiment werden geen AI-versnellers en GPU's gebruikt, bij toepassing hiervan kan de rekentijd aanzienlijk worden verkort). Ter vergelijking vereist de klassieke factorisatiemethode om de privésleutel van RSA-1024 te recreëren tussen de 500.000 en een miljoen jaar rekentijd op één processor kern.
Voor het uitvoeren van de aanval is de mogelijkheid vereist om herhaaldelijk verzoeken te sturen voor het ondertekenen van door de aanvaller gegenereerde gegevens, bijvoorbeeld door contact op te nemen met een autorisatieservice of HSM-module. Om de parameters van RSA-1024 te bepalen, is het voldoende om 232 van dergelijke verzoeken te versturen, en voor een aanval op RSA-2048-sleutels die in het Privacy Pass-protocol worden gebruikt, 243. Na het verkrijgen van een reeks ondertekende gegevens, wordt een langdurig proces van parameterberekening gestart (voor RSA-1024 ongeveer 265 bewerkingen), waarna de aanvaller valse handtekeningen kan genereren voor alle gegevens, met een rekentijd van ongeveer 180 uur op één kern per handtekening.
De methode is alleen toepasbaar op RSA-handtekeningen waarbij geen opvulling en extra opvulling vóór de encryptie wordt gebruikt (padding). De aanval is kwetsbaar voor implementaties van blinde handtekening, waaronder die welke in het Privacy Pass-protocol worden gebruikt. De meeste gangbare implementaties van RSA, inclusief PKCS#1v1.5 en RSA-PSS (gebruikt in TLS en SSH), maken gebruik van extra opvulling en zijn niet kwetsbaar voor de aanval.
De basis van RSA-encryptie is de operatie van exponentiële machtsverheffing modulo een groot getal. De openbare sleutel bevat het modulus en de exponent. Het modulus wordt gevormd op basis van twee willekeurige priemgetallen die alleen bekend zijn bij de eigenaar van de privésleutel. De voorgestelde methode is gebaseerd op een onderzoek uit 2007, dat heeft aangetoond dat het extraheren van de wortel in de exponent zoals gespecificeerd in de openbare sleutel uit het versleutelde bericht, zonder informatie over de geheime factoren, een minder resource-intensieve operatie is dan het factoriseren van de factoren zelf.
Door gebruik te maken van een speciale methode genaamd sieving of numerieke velden (SNFS), hebben onderzoekers de complexiteit voor het compromitteren van RSA-1024 sleutels weten te reduceren tot 265 operaties, wat praktische aanvallen op moderne clusters mogelijk maakt. Voor 2048-bits RSA-sleutels wordt de aanvallingscomplexiteit geschat op 290, wat theoretisch uitvoerbaar is door grote bedrijven of inlichtingendiensten. Voor 4096-bits sleutels is de aanvallingscomplexiteit 2119 operaties, wat momenteel praktisch nog niet haalbaar is, maar onder de aanbevolen minimumwaarde van 2128 ligt, zoals vastgesteld door de NSA, het National Institute of Standards and Technology en het Europese Agentschap voor Netwerk- en Informatiebeveiliging.
Bron: opennet.ru
