Metoda napada koja značajno smanjuje resurse za falsificiranje RSA digitalnih potpisа.

Istraživači sa Univerziteta u Kaliforniji u San Diegu razvili su naprednu tehniku napada na RSA algoritam koja omogućava falsificiranje digitalnih potpisa bez faktoriranja osnovnih prostih brojeva RSA-a i bez potrebe za obnovom privatnog ključa. Resursi potrebni za izvođenje napada na RSA ključ od 1024 bita procijenjeni su na 1380 godina proračuna na jednom procesorskomjezgru, što je na postojećem univerzitetskom klasteru omogućilo da se u 5 meseci odrede parametri potrebni za stvaranje falsifikovanih RSA potpisa (u eksperimentu nisu korišćeni AI akceleratori i GPU-ovi; kada bi se oni primijenili, vreme proračuna bi se značajno smanjilo). Za poređenje, klasična metoda faktoriranja zahtijeva od 500.000 do milion godina proračuna na jednom procesorskom jezgru za rekonstrukciju RSA-1024 privatnog ključa.

Za izvođenje napada potrebna je mogućnost višekratnog slanja zahteva za potpisivanje podataka koje napadač formira, na primer, putem servisa za autorizaciju ili HSM modula. Za određivanje parametara RSA-1024 dovoljno je poslati 232 takva zahteva, dok je za napad na RSA-2048 ključeve, koji se koriste u protokolu Privacy Pass, potrebno 243. Nakon što se dobije niz potpisanih podataka, započinje dugotrajan proces proračuna parametara (za RSA-1024 otprilike 265 operacija), nakon čega napadač može stvarati falsifikovane potpise za bilo koje podatke, trošeći na svaki potpis otprilike 180 sati proračuna na jednom jezgru.

Metoda se može primeniti samo na RSA potpise u kojima se ne koristi formatiranje i dodatno punjenje pre šifrovanja (padding). Napadu su podložne implementacije slepog potpisivanja, uključujući one koje se koriste u protokolu Privacy Pass. Većina trenutno u upotrebi RSA implementacija, uključujući PKCS#1v1.5 i RSA-PSS (koje se koriste u TLS i SSH), primenjuju dodatno punjenje i nisu podložne napadu.

Temelj RSA šifriranja je operacija potenciranja modulo velikog broja. Javni ključ sadrži modul i eksponent. Modul se formira na osnovu dva nasumična prosta broja, koja su poznata samo vlasniku privatnog ključa. Predložena metoda se oslanja na istraživanje objavljeno 2007. godine, koje je dokazalo da je vađenje korena u eksponentu navedenom u javnom ključu iz šifrovanih poruka bez informacija o tajnim faktorima manje resursno intenzivna operacija od faktorizacije samih faktora.

Koristeći posebnu metodu kibernetske rešetke (SNFS), istraživačima je uspelo da smanje složenost kompromitacije RSA-1024 ključeva na 265 operacija, što omogućava izvođenje praktičnih napada na savremenim klasterima. Za 2048-bitne RSA ključeve, složenost napada se procenjuje na 290, što je teoretski ostvarivo od strane velikih korporacija ili obaveštajnih agencija. Za 4096-bitne ključeve, složenost napada iznosi 2119 operacija, što je u praksi trenutno nedostižno, ali ispod minimuma 2128, koji preporučuju NSA, Nacionalni institut za standarde i tehnologiju i Evropska agencija za mrežnu i informacionu sigurnost.

Izvor: opennet.ru