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 faktorisera de underliggande RSA-primtalen och utan behov av att återställa den privata nyckeln. De resurser som krävs för att attackera en 1024-bitars RSA-nyckel uppskattas till 1 380 års beräkning på en enda processorkärna. Med hjälp av universitetets befintliga kluster kunde de bestämma de parametrar som krävs för att generera falska RSA-signaturer på fem månader (experimentet använde inte AI-acceleratorer eller GPU:er, men deras användning skulle kunna minska beräkningstiden avsevärt). Som jämförelse kräver den klassiska faktoriseringsmetoden mellan 500 000 och en miljon års beräkning på en enda processorkärna för att rekonstruera en RSA-1024 privat nyckel.
Att utföra en attack kräver möjligheten att upprepade gånger skicka förfrågningar för att signera angriparens genererade data, till exempel genom att använda en auktoriseringstjänst eller en HSM-modul. För att bestämma RSA-1024-parametrar räcker det att skicka 232 sådana förfrågningar, och för att attackera RSA-2048-nycklar som används i Privacy Pass-protokollet räcker det med 243. Efter att ha mottagit en array med signerade data påbörjas en lång process för parameterberäkning (cirka 265 operationer för RSA-1024). När dessa parametrar har beräknats kan angriparen skapa falska signaturer för vilken data som helst och spendera cirka 180 timmars beräkning på en enda kärna per signatur.
Metoden är endast tillämplig på RSA-signaturer som inte använder formatering eller utfyllnad före kryptering. Implementeringar av blinda signaturer, inklusive de som används i Privacy Pass-protokollet, är sårbara för attacken. De vanligaste RSA-implementeringarna, inklusive PKCS#1v1.5 och RSA-PSS (används i TLS och SSH), använder utfyllnad och är inte sårbara för attacken.
RSA-kryptering baseras på operationen att upphöja ett stort tal till en potensmodulo. Den publika nyckeln innehåller modulen och potensen. Modulen genereras med hjälp av två slumpmässiga primtal som endast är kända för ägaren av den privata nyckeln. Den föreslagna metoden är baserad på en studie publicerad 2007 som visade att det är en mindre resurskrävande operation att extrahera roten från ett krypterat meddelande till en potens specificerad i den publika nyckeln utan kännedom om de hemliga faktorerna än att faktorisera själva faktorerna.
Med hjälp av en specialiserad siktbaserad talfältmetod (SNFS) kunde forskare minska komplexiteten i att kompromettera RSA-1024-nycklar till 265 operationer, vilket möjliggör praktiska attacker mot moderna kluster. För 2048-bitars RSA-nycklar uppskattas komplexiteten till 290, vilket är teoretiskt genomförbart för stora företag eller underrättelsetjänster. För 4096-bitarsnycklar är komplexiteten 2119 operationer, vilket för närvarande är ouppnåeligt i praktiken, men lägre än minimumvärdet på 2128 som rekommenderas av NSA, National Institute of Standards and Technology och European Network and Information Security Agency.
Källa: opennet.ru
