En attackmetod som kraftigt minskar resurserna för förfalskning av RSA-digitala signaturer.

Forskare från University of California, San Diego har utvecklat en förbättrad attackteknik mot RSA-algoritmen, vilket möjliggör förfalskning av digitala signaturer utan att behöva faktorisera de primtalen som ligger till grund för RSA och utan att återställa den privata nyckeln. Resurserna som krävs för att utföra en attack på en 1024-bitars RSA-nyckel uppskattas till 1380 år av beräkningar på en processor kärna, vilket på det tillgängliga universitetsklustret har gjort det möjligt att under 5 månader bestämma de parametrar som krävs för att skapa falska RSA-signaturer (AI-acceleratorer och GPU användes inte i experimentet, och med deras användning kan beräkningstiden reduceras avsevärt). Jämfört med detta kräver den klassiska faktoriseringstekniken mellan 500 000 och en miljon år av beräkningar på en processor kärna för att återskapa den privata nyckeln för RSA-1024.

För att utföra attacken krävs möjlighet att upprepade gånger skicka förfrågningar för att signera de data som angriparen generar, till exempel genom att kontakta en autentiseringstjänst eller en HSM-modul. För att bestämma parametrarna för RSA-1024 räcker det med att skicka 232 sådana förfrågningar, och för att attackera RSA-2048-nycklarna som används i Privacy Pass-protokollet krävs 243. När en uppsättning signerade data har erhållits startar en lång beräkningsprocess (för RSA-1024 ungefär 265 operationer), varefter angriparen kan skapa falska signaturer för vilken data som helst, vilket tar cirka 180 timmar av beräkningar på en kärna för varje signatur.

Metoden är tillämplig endast för RSA-signaturer där formatering och ytterligare fyllnad före kryptering (padding) inte används. Attacken är sårbar för implementeringar av blind signatur, inklusive de som används i Privacy Pass-protokollet. De flesta allmänt använda RSA-implementationer, inklusive PKCS#1v1.5 och RSA-PSS (som används i TLS och SSH), tillämpar ytterligare fyllnad och är därför inte sårbara för attacken.

Grunden för RSA-kryptering är exponentiering modulo ett stort tal. Den offentliga nyckeln innehåller modul och exponent. Modulen bildas baserat på två slumpmässiga primtalsnummer, som endast ägs av innehavaren av den privata nyckeln. Den föreslagna metoden bygger på en forskning publicerad 2007, som bevisade att det är mindre resurskrävande att extrahera roten i den exponent som anges i den offentliga nyckeln från ett krypterat meddelande, än att faktorisera själva faktorerna.

Genom att använda en specialmetod för sållning av numeriska fält (SNFS) lyckades forskarna reducera komplexiteten för att kompromettera RSA-1024-nycklar till 265 operationer, vilket möjliggör praktiska attacker på moderna kluster. För 2048-bitars RSA-nycklar uppskattas angreppskomplexiteten till 290, vilket teoretiskt är genomförbart av stora företag eller underrättelsetjänster. För 4096-bitars nycklar uppgår angreppskomplexiteten till 2119 operationer, vilket i praktiken fortfarande är oåtkomligt, men under minimumen 2128, rekommenderat av NSA, National Institute of Standards and Technology och European Union Agency for Cybersecurity.

Källa: opennet.ru