Badacze z University of California San Diego oraz francuskiego INRIA sfałszowali podpisy RSA dla klucza 1 024-bitowego przechowywanego w module bezpieczeństwa sprzętowego — odpornego na manipulacje urządzenia, na którym instytucjonalni powiernicy polegają przy ochronie kluczy kryptograficznych — bez wyodrębniania samego klucza.

Badacze skutecznie podszyli się pod moduł bezpieczeństwa sprzętowego, czyli urządzenie przechowujące klucze prywatne i podpisujące na żądanie, uzyskując z niego prawidłowe podpisy, podczas gdy klucz pozostawał w środku. Opisali atak w pracy przesłanej do IACR Cryptology ePrint Archive 20 września.

Dla posiadaczy kryptowalut odkrycie to nie oznacza złamania Bitcoina ani Ethereum. Bitcoin podpisuje transakcje za pomocą algorytmu podpisu cyfrowego opartego na krzywej eliptycznej, czyli ECDSA, a jego krzywa obsługuje także podpisy Schnorra. Ethereum oraz większość innych dużych blockchainów również korzysta z podpisów opartych na krzywych eliptycznych. Praca dotyczy kryptografii Rivesta-Shamira-Adlemana, czyli RSA — innego schematu podpisu.

Wynik stanowi jednak test odporności sposobów ochrony kluczy. Dostawcy usług powiernictwa instytucjonalnego, według BitGo, korzystają z modułów bezpieczeństwa sprzętowego — odpornych na manipulacje urządzeń zaprojektowanych tak, aby klucze nigdy nie istniały poza sprzętem, a osoby z zewnątrz mogły jedynie żądać podpisów. W tym przypadku klucz nigdy nie opuścił urządzenia, a mimo to badacze sfałszowali podpisy.

Wyłączyli tryb FIPS modułu, czyli certyfikowane ustawienie bezpieczeństwa, aby urządzenie podpisywało niesformatowane liczby, i użyli własnego klucza testowego. Następnie polecili urządzeniu podpisać około 4 miliardów wybranych przez siebie liczb — około 2^32 żądań podpisu — po czym wykonali obliczenia na uzyskanych odpowiedziach. Obliczenia wymagały łącznie szacunkowo 1 380 lat pracy rdzeni CPU. Można to porównać do skarbca, który nigdy się nie otwiera, ale stempluje każdą pustą kartkę wsuniętą pod drzwi: po wystarczającej liczbie prób można nauczyć się samodzielnie odtworzyć stempel.

Czym jest podpis?

Za każdym razem, gdy użytkownik zatwierdza transakcję, jego portfel podpisuje ją kluczem prywatnym. Taki podpis cyfrowy potwierdza, że posiadacz klucza zaakceptował transakcję i że nikt nie zmienił wiadomości podczas jej przesyłania, dlatego podpisy są podstawą każdego transferu wartości w blockchainie.

RSA jest jednym ze sposobów tworzenia takiego potwierdzenia. Schemat powstał w 1977 roku za sprawą Rona Rivesta, Leonarda Adlemana i Adiego Shamira — „S” w nazwie pochodzi od jego nazwiska. Kluczowa idea polega na tym, że pomnożenie dwóch ogromnych liczb pierwszych jest łatwe, ale rozłożenie wyniku z powrotem — proces zwany faktoryzacją — jest niezwykle trudne. Autorzy piszą, że bezpieczeństwo RSA powszechnie uważa się za oparte na tej trudności, choć nigdy nie dowiedziono, że złamanie RSA jest równoważne faktoryzacji. Ten zespół niczego nie rozkładał na czynniki.

Kogo to dotyczy

Standardowe podpisy RSA wykorzystują padding — etap szyfrowania i formatowania, taki jak PKCS#1 v1.5 lub PSS, wykonywany przed właściwymi obliczeniami — a podpisy z paddingiem nie tworzą podatnego na wykorzystanie wyroczni. W praktyce atak działa wyłącznie przeciwko urządzeniu skonfigurowanemu do podpisywania surowych, niesformatowanych liczb. Zgłoszone zagrożenie zależy więc od interfejsu podpisywania i jego konfiguracji, a nie tylko od tego, czy klucz jest przechowywany w HSM. Autorzy twierdzą, że atak prawdopodobnie nie stanowi bezpośredniego zagrożenia operacyjnego dla większości współczesnych wdrożeń RSA. Praca jest preprintem.

Niektóre systemy celowo udostępniają wyrocznię. Oparte na RSA ślepe podpisy pozwalają serwerowi podpisać coś bez oglądania podpisywanej treści, na czym opiera się jeden z wariantów Privacy Pass. Cloudflare twierdzi, że Apple korzysta z wersji Privacy Pass, aby użytkownicy mogli potwierdzić przejście kontroli, takiej jak CAPTCHA, bez ujawniania swojej tożsamości.

Ślepe podpisy mają korzenie w kryptografii. Kryptograf David Chaum wykorzystał tę technikę, gdy w 1989 roku założył DigiCash.

Większym zagrożeniem nadal pozostaje technologia kwantowa

Nagłówki głoszące, że „RSA zostało złamane”, mają już swoją historię. W styczniu 2023 roku chińscy badacze twierdzili, że opracowali kwantową metodę zagrażającą RSA, ale udało im się rozłożyć na czynniki jedynie liczbę 48-bitową, a eksperci odrzucili te twierdzenia. Tym razem demonstracja dotyczy rzeczywistego klucza 1 024-bitowego — z zastrzeżeniem wielkości wyroczni.

Autorzy opisują swój wynik jako klasyczny argument za odchodzeniem od RSA w ramach transformacji postkwantowej, czyli przejścia na szyfrowanie zaprojektowane tak, aby przetrwać działanie komputerów kwantowych.

W przypadku Bitcoina kwestia kwantowa dotyczy podpisów opartych na krzywych eliptycznych. Badacze z Caltech oszacowali pod koniec marca, że do uruchomienia algorytmu Shora — metody zagrażającej tym podpisom — może wystarczyć od 10 000 do 20 000 kubitów, czyli kwantowych odpowiedników bitów.

Google wyznaczył rok 2029 jako termin zakończenia migracji własnych systemów do kryptografii postkwantowej.