Nowa metoda ataku na RSA. Badacze obeszli faktoryzację i podważyli dotychczasowe zasady kryptografii

Naukowcy z Uniwersytetu Kalifornijskiego w San Diego opracowali nową metodę ataku na szyfrowanie RSA, która nie wymaga rozkładania dużych liczb na czynniki pierwsze. Zaprezentowana technika opiera się na fałszowaniu podpisów cyfrowych i redukuje ilość mocy obliczeniowej potrzebnej do naruszenia bezpieczeństwa o kilka rzędów wielkości. Choć bezpośrednie ryzyko dla większości obecnych systemów sieciowych pozostaje niewielkie, ustalenia badaczy obalają dotychczasowe założenia kryptografii.

Ominięcie tradycyjnego łamania klucza prywatnego

Zespół badaczy pod kierunkiem Laury Shea oraz prof. Nadii Heninger z University of California w San Diego wykazał, że do wygenerowania prawidłowego podpisu cyfrowego RSA nie jest konieczne wcześniejsze poznanie klucza prywatnego. Dotychczas specjaliści zakładały, że jedynym sposobem na złamanie tego systemu jest faktoryzacja, co w przypadku kluczy 1024-bitowych wymagało nakładów finansowych rzędu dziesiątek milionów dolarów lub zasobów dostępnych wyłącznie dla agencji rządowych. Nowa metoda wykorzystuje wariant algorytmu sita ciała liczbowego z 2007 roku połączony z wyrocznią kryptograficzną (ang. cryptographic oracle), zmniejszając wymagany nakład pracy z 2^80 operacji i 500 tysięcy lat pracy rdzenia procesora do 2^65 operacji i 1380 lat pracy rdzenia. Pozwoliło to na przeprowadzenie udanego ataku na klucz 1024-bitowy w ciągu kilku miesięcy na akademickim klastrze CPU i to bez użycia akceleratorów GPU czy algorytmów sztucznej inteligencji. Karsten Nohl, ekspert do spraw kryptografii oraz szef do spraw innowacji w firmie Allurity, ocenił te wyniki w następujący sposób:

Jeśli ten wynik utrzyma się w procesie recenzji naukowej, będzie to rzeczywiście przełom. RSA jest tak trudne do złamania, jak faktoryzacja dużych liczb całkowitych, a przynajmniej tak sądziliśmy. 

Zastosowanie metody ogranicza się do wybranych protokołów

Nowy atak nie zagraża przeważającej większości wdrożeń RSA stosowanych w internecie, które wykorzystują mechanizmy dopełnienia PKCS lub PSS zapobiegające powtarzalności szyfrogramów. Podatność dotyczy wyłącznie systemów opartych na tak zwanych ślepych podpisach, znanych jako podręcznikowe RSA. Najbardziej znanym przykładem wykorzystania tego rozwiązania jest protokół Privacy Pass, służący do uwierzytelniania użytkowników bez ujawniania ich tożsamości, z którego korzystają między innymi Apple oraz Cloudflare. Przeprowadzenie udanego ataku na ten protokół wymagałoby jednak wysłania zapytania o tokeny około 2^43 razy, co stanowi wartość zbliżoną do całodobowego ruchu sieciowego obsługiwanego przez Cloudflare. Prof. Nadia Heninger wyjaśniła dotychczasowy stan wiedzy w tym zakresie:

Kryptografowie sądzili, że jedyną drogą do wygenerowania prawidłowych podpisów cyfrowych RSA jest wcześniejsze obliczenie klucza prywatnego poprzez faktoryzację. W przypadku kluczy 1024-bitowych uważano to za bardzo kosztowne, choć prawdopodobnie możliwe do zrealizowania przy zasobach dużych firm technologicznych lub NSA – rzędu dziesiątek milionów dolarów czasu obliczeniowego dla pojedynczego klucza. Dla kluczy 2048-bitowych uznawano to za całkowicie nieosiągalne.

Obniżenie poziomu ochrony przyspieszy zmiany w branży IT

Standardy wyznaczone przez amerykańską Agencję Bezpieczeństwa Narodowego (NSA), Narodowy Instytut Standardów i Technologii (NIST) oraz Europejską Agencję do spraw Cyberbezpieczeństwa (ENISA) wymagają, aby systemy kryptograficzne zapewniały poziom ochrony wynoszący co najmniej 128 bitów, co odpowiada konieczności wykonania ponad 2^128 operacji. Opracowana metoda obniża ten poziom do 2^65 dla kluczy 1024-bitowych, 2^90 dla kluczy 2048-bitowych oraz 2^119 dla kluczy 4096-bitowych. Autorzy badania zwracają uwagę, że przygotowany przez nich kod nie był zoptymalizowany pod kątem dedykowanych układów scalonych, co oznacza, że dalsze prace mogą jeszcze bardziej obniżyć te progi. Chociaż bezpośrednie zagrożenie operacyjne dla firm jest obecnie ograniczone, publikacja ta wymusza rewidowanie dotychczasowych modeli zagrożeń i zwiększa presję na szybkie wdrażanie nowych algorytmów szyfrujących.