Forskerne fra Universitetet i Californien, San Diego, har udviklet en avanceret angrebsteknik mod RSA-algoritmen, der muliggør forfalskning af digitale signaturer uden at faktorisere de underliggende primtal i RSA og uden behov for at genoprette den private nøgle. De ressourcer, der kræves for at udføre angrebet på en RSA-nøgle på 1024 bits, er vurderet til 1380 års beregninger på en enkelt CPU-kerne, hvilket gjorde det muligt at bestemme de nødvendige parametre for at danne falske RSA-signaturer på den tilgængelige universitetskluster i løbet af 5 måneder (AI-acceleratorer og GPU'er blev ikke brugt i eksperimentet, men ved deres anvendelse kan beregningstiden forkortes betydeligt). Til sammenligning kræver den klassiske faktorisering metode mellem 500.000 og en million års beregninger på en enkelt CPU-kerne for at genskabe RSA-1024's private nøgle.
For at gennemføre angrebet kræves der, at der er mulighed for gentagne gange at sende forespørgsler om at signere de data, der genereres af angriberen, for eksempel ved at henvende sig til en autoriseringstjeneste eller en HSM-modul. For at bestemme parametrene for RSA-1024 er det tilstrækkeligt at sende 232 sådanne forespørgsler, mens angrebet på RSA-2048 nøgler, der anvendes i Privacy Pass-protokollen, kræver 243. Når et array af signerede data er opnået, startes en langvarig beregningsproces for at bestemme parametrene (for RSA-1024 cirka 265 operationer), hvorefter angriberen kan skabe falske signaturer for enhver data og bruge omkring 180 timers beregninger på en kerne pr. signatur.
Metoden er kun anvendelig for RSA-signaturer, hvor der ikke anvendes formatering og ekstra padding før kryptering. Angrebet er sårbart over for implementeringer af blind signatur, herunder dem der anvendes i Privacy Pass-protokollen. De fleste almindeligt anvendte RSA-implementeringer, herunder PKCS#1v1.5 og RSA-PSS (der anvendes i TLS og SSH), benytter ekstra padding og er ikke sårbare over for angrebet.
I kernen af RSA-kryptering ligger operationen med at hæve til en potens modulo et stort tal. Den offentlige nøgle indeholder modulus og eksponent. Modulus dannes ud fra to tilfældige primtal, som kun ejeren af den private nøgle kender. Den foreslåede metode er baseret på en forskning offentliggjort i 2007, der viste, at det at udtrække roden til den eksponent, der er angivet i den offentlige nøgle, fra den krypterede meddelelse uden information om de hemmelige faktorer er en mindre ressourcekrævende operation end faktoriseringen af selve faktorerne.
Ved at bruge en speciel metode til numeriske felt-sieves (SNFS) er forskerne lykkedes med at reducere kompleksiteten ved at kompromittere RSA-1024 nøgler til 265 operationer, hvilket muliggør praktiske angreb på moderne klynger. For 2048-bits RSA nøgler vurderes angrebscomplexiteten til 290, hvilket teoretisk set er gennemførligt af store virksomheder eller efterretningstjenester. For 4096-bits nøgler er attack complexity 2119 operationer, hvilket i praksis stadig er uopnåeligt, men under minimum 2128, som anbefalet af NSA, National Institute of Standards and Technology og Det Europæiske Agentur for Net- og Informationssikkerhed.
Kilde: opennet.ru
