Výskumníci z Kalifornskej univerzity v San Diegu vyvinuli vylepšenú techniku útoku proti algoritmu RSA, ktorá umožňuje falšovanie digitálnych podpisov bez faktorizácie podkladových prvočísel RSA a bez nutnosti obnovenia súkromného kľúča. Zdroje potrebné na útok na 1024-bitový kľúč RSA sa odhadujú na 1 380 rokov výpočtov na jednom jadre procesora. Použitím existujúceho klastra univerzity im to umožnilo určiť parametre potrebné na generovanie falošných podpisov RSA za päť mesiacov (experiment nepoužíval akcelerátory umelej inteligencie ani grafické procesory, ale ich použitie mohlo výrazne skrátiť čas výpočtu). Pre porovnanie, klasická metóda faktorizácie vyžaduje 500 000 až milión rokov výpočtov na jednom jadre procesora na rekonštrukciu súkromného kľúča RSA-1024.
Vykonanie útoku vyžaduje možnosť opakovane odosielať požiadavky na podpísanie údajov generovaných útočníkom, napríklad prístupom k autorizačnej službe alebo modulu HSM. Na určenie parametrov RSA-1024 stačí odoslať 232 takýchto požiadaviek a na útok na kľúče RSA-2048 používané v protokole Privacy Pass stačí 243. Po prijatí poľa podpísaných údajov sa začína zdĺhavý proces výpočtu parametrov (približne 265 operácií pre RSA-1024). Po výpočte týchto parametrov môže útočník vytvoriť falošné podpisy pre akékoľvek údaje, pričom na jeden podpis strávi približne 180 hodín výpočtu na jednom jadre.
Táto metóda je použiteľná iba pre podpisy RSA, ktoré nepoužívajú formátovanie ani doplnenie pred šifrovaním. Implementácie slepých podpisov, vrátane tých, ktoré sa používajú v protokole Privacy Pass, sú zraniteľné voči útoku. Najbežnejšie používané implementácie RSA, vrátane PKCS#1v1.5 a RSA-PSS (používané v TLS a SSH), používajú doplnenie a nie sú zraniteľné voči útoku.
Šifrovanie RSA je založené na operácii umocnenia veľkého čísla modulom veľkého čísla. Verejný kľúč obsahuje modul a umocnenú hodnotu. Modul sa generuje pomocou dvoch náhodných prvočísel, ktoré pozná iba vlastník súkromného kľúča. Navrhovaná metóda je založená na štúdii publikovanej v roku 2007, ktorá preukázala, že extrahovanie koreňa šifrovanej správy na umocnenú hodnotu špecifikovanú vo verejnom kľúči bez znalosti tajných faktorov je menej náročná operácia na zdroje ako faktorizácia samotných faktorov.
Pomocou špecializovanej metódy číselných polí založenej na site (SNFS) sa výskumníkom podarilo znížiť zložitosť kompromitácie kľúčov RSA-1024 na 265 operácií, čo umožnilo praktické útoky na moderné klastre. Pre 2048-bitové kľúče RSA sa zložitosť odhaduje na 290, čo je teoreticky uskutočniteľné pre veľké korporácie alebo spravodajské agentúry. Pre 4096-bitové kľúče je zložitosť 2119 operácií, čo je v súčasnosti v praxi nedosiahnuteľné, ale nižšie ako minimum 2128 odporúčané NSA, Národným inštitútom pre štandardy a technológie a Európskou agentúrou pre sieťovú a informačnú bezpečnosť.
Zdroj: opennet.ru
