Agenty AI pracujące pod nadzorem człowieka pomogły Google DeepMind zidentyfikować dwa sposoby na obniżenie kosztu ataku na systemy kryptograficzne RSA 1024-bitowe. Prace te, prowadzone z kryptografami z UC San Diego i Inria, wskazują, że ataki na przestarzały RSA-1024 wymagają mniej mocy obliczeniowej niż dotąd zakładano.
RSA to system szyfrowania z kluczem publicznym, którego siła opiera się na trudności rozkładu dużej liczby na czynniki pierwsze. Pushmeet Kohli, wiceprezes Google DeepMind i dyrektor naukowy Google Cloud, uspokaja jednak co do znaczenia tych wyników: „W praktyce te wyniki dotyczą tylko przestarzałych systemów RSA 1024-bitowych, a nowoczesne protokoły szyfrowania, które niemal powszechnie używają kluczy 2048-bitowych lub większych, pozostają bezpieczne ».
Podpisy cyfrowe i dopełnienie
Pierwsze odkrycie dotyczy podpisów cyfrowych i dopełnienia, czyli wstępnie ustalonych danych, które wiele standardów podpisu dodaje do wiadomości, aby doprowadzić ją do stałego rozmiaru bloku. Mechanizm ten był znany z utrudniania fałszowania, ale jego skuteczność wobec atakującego mogącego wybrać, co jest podpisywane, pozostawała niejasna. DeepMind ustalił, że wszystko zależy od części podpisywanego bloku, którą kontroluje atakujący. Jak wyjaśnia Pushmeet Kohli, „gdy kontrolują około połowy bloku lub więcej, dopełnienie nie zapewnia już żadnej ochrony ».
Zgodnie z artykułem naukowym towarzyszącym tym pracom, dotyczy to formatu PKCS#1 v1.5, używanego przez interfejs podpisu PKCS#11 urządzeń kryptograficznych, takich jak sprzętowe moduły bezpieczeństwa (HSM).
W teście przeprowadzonym w odizolowanym środowisku agenty ponownie uruchomiły opublikowany już w pracy naukowej atak przez fałszowanie, na tym samym kluczu 1024-bitowym. Czas obliczeń procesora został skrócony 3,5-krotnie. Pierwsze sfałszowanie wymagało 391 lat-rdzeni procesora, wobec 1380 w oryginalnym badaniu.
Dwa agenty AI zaprojektowały, wykonały i poprawiły obliczenia fałszowania w mniej niż cztery dni, przy około 20 komunikatach od ludzkiego badacza, głównie zatwierdzeniach. Klucz nie został rozłożony na czynniki – operację, którą źródło szacuje na 500 000 do 1 miliona lat-rdzeni procesora. Gdy atakujący kontroluje mniejszą część bloku, na przykład 32-bajtowy skrót (hash), fałszowanie jest trudniejsze. DeepMind twierdzi jednak, że znalazł algorytm, który według jego teoretycznych szacunków jest około 1600 razy lepszy od poprzedniej najskuteczniejszej metody przeciw kluczom 1024-bitowym.
Faktoryzacja wielu kluczy
Drugie odkrycie dotyczy faktoryzacji wielu kluczy RSA o tej samej wielkości. Atakujący może wtedy rozłożyć koszt jednego dużego wstępnego obliczenia na cały zestaw tych kluczy. Agenty DeepMind opracowały algorytm, który średnio czyni faktoryzację każdego dodatkowego klucza 1024-bitowego około 30 razy tańszą niż najlepsze wcześniejsze podejście. To teoretyczne oszacowanie zakłada jednak wstępne obliczenie równie kosztowne jak faktoryzacja pojedynczego klucza, a metoda nie została wdrożona.
Badacze podkreślają, że atak na podpisy nie pozwala odzyskać klucza prywatnego. Wymaga on wcześniej około 4 miliardów żądań podpisu i nie działa przeciwko urządzeniom, które wewnętrznie haszują wiadomości. „Razem te wyniki pokazują, że w nowej erze matematyki i obliczeń wspomaganych przez AI, nie możemy traktować trudności kryptograficznej jako stałego założenia » – podsumowuje Pushmeet Kohli. Dodaje: „Używanie AI do rygorystycznego testowania naszych wcześniejszych założeń pozwoli zapewnić, że nowoczesne szyfrowanie pozostanie bezpieczne ».
