Badacze z Uniwersytetu Kalifornijskiego w San Diego opracowali zaawansowaną technikę ataku na algorytm RSA, umożliwiającą oszustwo podpisów cyfrowych bez faktoryzacji podstawowych liczb pierwszych RSA i bez potrzeby odzyskiwania klucza prywatnego. Zasoby potrzebne do przeprowadzenia ataku na klucz RSA o długości 1024 bitów szacowane są na 1380 lat obliczeń na jednym rdzeniu procesora, co pozwoliło na uniwersyteckim klastrze w ciągu 5 miesięcy określić parametry niezbędne do generowania fałszywych podpisów RSA (w eksperymencie nie zastosowano akceleratorów AI ani GPU, a ich użycie mogłoby znacznie skrócić czas obliczeń). Dla porównania, klasyczna metoda faktoryzacji wymaga od 500 tysięcy do miliona lat obliczeń na jednym rdzeniu procesora do odtworzenia klucza prywatnego RSA-1024.
Aby przeprowadzić atak, konieczne jest posiadanie możliwości wielokrotnego wysyłania żądań podpisania danych tworzonych przez atakującego, na przykład poprzez kontakt z serwisem autoryzacyjnym lub modułem HSM. Do określenia parametrów RSA-1024 wystarczy wysłać 232 takich żądań, a do ataku na klucze RSA-2048 używane w protokole Privacy Pass — 243. Po uzyskaniu zbioru podpisanych danych rozpoczyna się długi proces obliczania parametrów (dla RSA-1024 to około 265 operacji), po których atakujący może tworzyć fałszywe podpisy dla dowolnych danych, wydatkując na każdy podpis około 180 godzin obliczeń na jednym rdzeniu.
Metoda jest stosowana tylko w przypadku podpisów RSA, w których nie zastosowano formatowania i dodatkowego wypełnienia przed szyfrowaniem (padding). Atak jest podatny na realizacje ślepego podpisu, w tym wykorzystywane w protokole Privacy Pass. Większość powszechnie stosowanych realizacji RSA, w tym PKCS#1v1.5 i RSA-PSS (używane w TLS i SSH), stosuje dodatkowe wypełnienie i są odporne na atak.
Podstawą szyfrowania RSA jest operacja podnoszenia do potęgi modulo dużej liczby. W kluczu publicznym zawarty jest moduł i wykładnik. Moduł jest formowany na podstawie dwóch losowych liczb pierwszych, które są znane tylko właścicielowi klucza prywatnego. Proponowana metoda opiera się na badaniu opublikowanym w 2007 roku, które wykazało, że wydobycie pierwiastka w wykładniku określonym w kluczu publicznym z zaszyfrowanej wiadomości bez informacji o sekretach mnożnikowych jest operacją mniej zasobożerną niż faktoryzacja samych mnożników.
Dzięki zastosowaniu specjalnej metody sitkowania pola liczb (SNFS) badaczom udało się zredukować złożoność kompromitacji kluczy RSA-1024 do 265 operacji, co umożliwia przeprowadzanie praktycznych ataków na nowoczesnych klastrach. W przypadku kluczy RSA o długości 2048 bitów złożoność ataku szacuje się na 290, co teoretycznie jest wykonalne dla dużych korporacji lub służb specjalnych. Dla kluczy o długości 4096 bitów złożoność ataku wynosi 2119 operacji, co na razie pozostaje poza zasięgiem, ale jest poniżej minimalnej wartości 2128, zalecanej przez NSA, Narodowy Instytut Standaryzacji i Technologii oraz Europejską Agencję ds. Bezpieczeństwa Sieci i Informacji.
Źródło: opennet.ru
