Výzkumníci z Kalifornské univerzity v San Diegu vyvinuli zlepšenou techniku útoku na algoritmus RSA, která umožňuje falšování digitálních podpisů bez faktorizace základních prvočísel RSA a bez nutnosti obnovit soukromý klíč. Zdroje potřebné k provedení útoku na 1024bitový klíč RSA jsou odhadovány na 1380 let výpočtů na jednom procesorovém jádře, což na dostupném univerzitním clusteru umožnilo za 5 měsíců určit parametry potřebné pro vytvoření falešného RSA podpisu (v experimentu nebyly použity urychlovače AI a GPU, jejichž použitím by se výpočetní čas mohl výrazně zkrátit). Pro srovnání, klasická metoda faktorizace vyžaduje pro obnovu soukromého klíče RSA-1024 mezi 500 tisíci až milionem let výpočtů na jednom procesorovém jádře.
Pro provedení útoku je nutné mít možnost opakovaně odesílat žádosti o podepsání dat vytvářených útočníkem, například prostřednictvím autentizační služby nebo HSM modulu. K určení parametrů RSA-1024 stačí odeslat 232 takových žádostí, a pro útok na klíče RSA-2048 používané v protokolu Privacy Pass je potřeba 243. Po získání pole podepsaných dat začíná dlouhý proces výpočtu parametrů (pro RSA-1024 přibližně 265 operací), po jejichž obtížném získání může útočník vytvářet falešné podpisy pro jakákoli data, přičemž každému podpisu věnuje přibližně 180 hodin výpočtů na jednom jádře.
Metoda je aplikovatelná pouze pro RSA podpisy, ve kterých se nepoužívá formátování a dodatečné vyplnění před šifrováním (padding). Útoku podléhají implementace slepé signatury, včetně těch používaných v protokolu Privacy Pass. Většina běžně používaných implementací RSA, včetně PKCS#1v1.5 a RSA-PSS (používané v TLS a SSH), používají dodatečné vyplnění a nejsou útoku podrobeny.
Základem šifrování RSA je operace umocňování modulo velkého čísla. Ve veřejném klíči se nachází modul a exponent. Modul je vytvořen na základě dvou náhodných prvočísel, která zná pouze majitel soukromého klíče. Navrhovaná metoda vychází z výzkumu zveřejněného v roce 2007, který prokázal, že extrakce kořene v exponentu uvedeném ve veřejném klíči ze zašifrované zprávy bez informací o tajných faktorech je méně náročná operace než faktorizace samotných faktorů.
Použitím speciální metody síta číselného pole (SNFS) se výzkumníkům podařilo snížit složitost kompromitace klíčů RSA-1024 na 265 operací, což umožňuje provádění praktických útoků na moderních klastrech. U 2048bitových klíčů RSA je složitost útoku odhadována na 290, což je teoreticky proveditelné velkými korporacemi nebo tajnými službami. U 4096bitových klíčů je složitost útoku 2119 operací, což je prozatím prakticky nedosažitelné, ale je to pod minimem 2128 doporučovaným NSA, Národním úřadem pro normy a technologie a Evropskou agenturou pro kybernetickou bezpečnost.
Zdroj: opennet.ru
