Badacze z University of California San Diego i francuskiego INRIA podrobili podpisy RSA dla klucza 1 024-bitowego przechowywanego w sprzętowym module zabezpieczeń (HSM) — urządzeniu odpornym na manipulacje, którego instytucjonalni depozytariusze używają do ochrony kluczy kryptograficznych — bez jakiegokolwiek wyodrębnienia klucza.

Zespół szczegółowo opisał technikę w pracy przesłanej 20 września do archiwum IACR (International Association for Cryptologic Research) Cryptology ePrint Archive. Przeprowadzenie ataku wymagało około 2^32 żądań podpisu — około 4 miliardów — oraz około 1 380 lat-rdzeni obliczeń CPU. Autorzy zaznaczają, że metoda najprawdopodobniej nie stanowi bezpośredniego zagrożenia dla większości współczesnych wdrożeń RSA, które opierają się na dopełnieniu (paddingu).

Ten wynik nie jest złamaniem Bitcoina ani Ethereum. Bitcoin podpisuje transakcje algorytmem ECDSA (elliptic curve digital signature algorithm), a jego krzywa obsługuje również podpisy Schnorra. Ethereum i większość innych większych blockchainów stosuje to samo podejście oparte na krzywych eliptycznych. Badania dotyczą RSA — kryptografii Rivest-Shamir-Adleman — czyli zupełnieego schematu podpisu.

Badacze zademonstrowali technikę na sprzętowym module zabezpieczeń, urządzeniu odpornym na manipulacje, które przechowuje klucze prywatne i podpisuje dane na żądanie. Aby umożliwić atak, wyłączyli tryb FIPS modułu — konfigurację certyfikowaną według amerykańskich rządowych standardów Federal Information Processing Standards dla modułów kryptograficznych — tak aby podpisywał surowe, niesformatowane liczby, i użyli własnego klucza testowego. Następnie poprosili urządzenie o podpisanie około 4 miliardów wybranych przez siebie liczb i przeprowadzili analizę matematyczną odpowiedzi, aby skonstruować sfałszowane podpisy. Kryptografowie nazywają taki odpytywalny cel wyrocznią (oracle) — system, który odpowiada na dane wejściowe wybrane przez atakującego i którego odpowiedzi mogą ukrywać podatne na wykorzystanie wzorce. Innymi słowy, wynik nie pokazuje pokonania certyfikowanej konfiguracji; wymagane było jej wcześniejsze wyłączenie.

Konfiguracja przypomina sejf, który nigdy się nie otwiera, ale stempluje każdą czystą kartkę wsuniętą pod drzwi: po wystarczającej liczbie próśb można nauczyć się odtwarzać stempel samodzielnie.

To odkrycie jest testem odporności praktyk ochrony kluczy. Według BitGo instytucjonalni dostawcy usług powierniczych używają sprzętowych modułów zabezpieczeń właśnie po to, aby klucze prywatne nigdy nie istniały poza urządzeniem. W tej demonstracji klucz nigdy nie opuścił modułu — a mimo to podpisy zostały podrobione.

Do czego służy podpis cyfrowy

Za każdym razem, gdy użytkownik potwierdza transakcję, portfel podpisuje ją kluczem prywatnym posiadacza. Ten podpis cyfrowy jest dowodem, że posiadacz klucza zatwierdził transakcję i że nikt nie zmodyfikował komunikatu po drodze.

RSA, opracowany w 1977 roku przez Rona Rivesta, Leonarda Adlemana i Adiegoira — "S" w skrócie — to jeden ze sposobów konstruowania takiego dowodu. Jego kluczowa idea polega na tym, że mnożenie dwóch ogromnych liczb pierwszych jest łatwe, podczas gdy rozłożenie wyniku z powrotem na czynniki — zadanie zwane faktoryzacją — jest wyjątkowo trudne. Autorzy piszą, że bezpieczeństwo RSA jest powszechnie rozumiane jako oparte na tej trudności, choć nigdy nie udowodniono, że złamanie RSA jest równoważne faktoryzacji. Co istotne, ten zespół niczego nie sfaktoryzował.

Kogo dotyczy problem

Standardowe podpisywanie RSA stosuje dopełnienie (padding) — etap mieszania i formatowania, taki jak PKCS#1 v1.5 lub PSS, wykonywany przed obliczeniami — a podpisy z dopełnieniem nie tworzą podatnej na wykorzystanie wyroczni. Długość klucza dodaje kolejną warstwę dystansu: demonstracja użyła klucza 1 024-bitowego, podczas gdy aktualne wytyczne amerykańskich standardów (NIST) traktują 2 048 bitów jako minimum dla nowych kluczy RSA. Autorzy twierdzą, że atak najprawdopodobniej nie stanowi bezpośredniego zagrożenia operacyjnego dla większości współczesnych wdrożeń RSA. Praca pozostaje preprintem, a jej twierdzenia muszą jeszcze przejść formalną recenzję.

Niektóre systemy celowo udostępniają taką wyrocznię. Ślepe podpisy oparte na RSA — technika określona w standardzie Internet Engineering Task Force — pozwalają serwerowi podpisać komunikat bez jego oglądania, tak działa jedna z odmian Privacy Pass. Według Cloudflare Apple używa wersji Privacy Pass, aby użytkownicy mogli udowodnić, że przeszli weryfikację, taką jak CAPTCHA, bez ujawniania swojej tożsamości. Ślepe podpisy mają też głębokie korzenie w historii kryptografii: David Chaum zastosował tę technikę, zakładając DigiCash w 1989 roku.

Większym zagrożeniem wciąż jest komputer kwantowy

Nagłówki w stylu "RSA złamane" mają już swoją historię. W styczniu 2023 roku chińscy badacze ogłosili kwantową metodę zagrażającą RSA, ale sfaktoryzowali jedynie liczbę 48-bitową, a eksperci odrzucili to twierdzenie. Tym razem demonstracja dotyczy rzeczywego klucza 1 024-bitowego — choć z gwiazdką wielkości samej wyroczni.

Autorzy opisują swój wynik jako klasyczny argument za odejściem od RSA podczas przejścia na kryptografię postkwantową — czyli zmiany na szyfrowanie zaprojektowane tak, aby wytrzymać komputery kwantowe. To przejście ma już konkretne kamienie milowe: amerykańska organizacja normalizacyjna NIST sfinalizowała pierwsze standardy kryptografii postkwantowej w sierpniu 2024 roku, dając dostawcom i operatorom wspólny cel migracji.

W przypadku Bitcoina pytanie kwantowe dotyczy podpisów na krzywych eliptycznych. Badacze z Caltech oszacowali pod koniec marca, że 10 000–20 000 kubitów — kwantowego odpowiednika bitów — może wystarczyć do uruchomienia algorytmu Shora, metody zagrażającej tym podpisom. Z kolei Google wyznaczył rok 2029 jako termin zakończenia migracji własnych systemów do kryptografii postkwantowej.

Ta relacja została pierwotnie opublikowana przez Decrypt: Atak RSA bez kradzieży klucza: co to oznacza dla krypto.