Raziskovalci z Univerze v Kaliforniji v San Diegu so razvili naprednejšo tehniko napada na algoritem RSA, ki omogoča ponarejanje digitalnih podpisov brez faktoriranja osnovnih praštevil in brez potrebe po obnovitvi skrivnega ključa. Viri potrebni za izvedbo napada na 1024-bitni RSA ključ so ocenjeni na 1380 let izračunov na enem procesorskem jedru, kar je na voljo na univerzitetnem klastru omogočilo, da so v 5 mesecih določili parametre, potrebne za oblikovanje lažnih RSA podpisov (pri eksperimentu niso bili uporabljeni AI pospeševalci in GPU, pri njihovi uporabi se lahko izračunani čas znatno skrajša). Za primerjavo, klasična metoda faktoriranja zahteva za obnovitev skrivnega ključa RSA-1024 od 500.000 do enega milijona let izračunov na enem procesorskem jedru.
Za izvedbo napada je potrebno imeti možnost večkratnega pošiljanja zahtevkov za podpis ustvarjenih podatkov s strani napadalca, na primer, da se obrne na storitev avtentikacije ali HSM modul. Za določitev parametrov RSA-1024 zadostuje, da se pošlje 232 takšnih zahtevkov, za napad na ključe RSA-2048, uporabljene v protokolu Privacy Pass, pa 243. Po pridobitvi množice podpisanih podatkov se sproži dolgotrajen postopek izračuna parametrov (za RSA-1024 približno 265 operacij), po katerih lahko napadalec ustvari lažne podpise za katere koli podatke, pri čemer porabi za vsak podpis približno 180 ur izračunov na enem jedru.
Metoda je uporabna le za RSA podpise, pri katerih se ne uporablja oblikovanje in dodatno polnjenje pred šifriranjem (padding). Napadu so podvržene izvedbe slepega podpisa, vključno s tistimi, ki se uporabljajo v protokolu Privacy Pass. Večina običajnih izvedb RSA, vključno s PKCS#1v1.5 in RSA-PSS (ki se uporabljajo v TLS in SSH), uporablja dodatno polnjenje in napadu niso podvržene.
Osnova RSA šifriranja temelji se na operaciji potenciranja po modulu velikog broja. U javnom ključu se nalaze modul i eksponent. Modul se formira na osnovu dva nasumična prosta broja, koja su poznata samo vlasniku privatnog ključa. Predložena metoda temelji se na istraživanju objavljenom 2007. godine, koje je dokazalo da je izvlačenje korena u eksponentu navedenom u javnom ključu iz enkriptovane poruke bez informacija o tajnim faktorima manje zahtevna operacija nego faktoracija samih faktora.
Korišćenjem specijalne metode rešeta numeričkog polja (SNFS), istraživačima je uspelo da smanje složenost kompromitacije RSA-1024 ključeva na 265 operacija, što omogućava praktične napade na savremenim klasterima. Za ključeve dužine 2048 bita, složenost napada procenjuje se na 290, što je teoretski izvodljivo velikim korporacijama ili obaveštajnim agencijama. Za ključeve od 4096 bita, složenost napada iznosi 2119 operacija, što je za sada praktično nedostižno, ali ispod minimuma od 2128, koji preporučuju NSA, Nacionalni institut za standarde i tehnologiju i Evropska agencija za mrežnu i informacijsku sigurnost.
Izvor: opennet.ru
