Algorytm HAWK wycofany po ataku AI Mythos Anthropic

Algorytm HAWK, kandydat na oficjalny standard kryptografii postkwantowej w USA, został wycofany z dalszych testów. Decyzja ta zapadła po tym, jak model bezpieczeństwa oparty na sztucznej inteligencji, Mythos firmy Anthropic, pomógł odkryć w nim poważną lukę, która czyniła go podatnym na ataki.

HAWK to schemat podpisu cyfrowego zaprojektowany w celu ochrony przed przyszłymi atakami ze strony komputerów kwantowych. Algorytm przeszedł już dwie rundy rygorystycznych testów prowadzonych przez NIST (National Institute of Standards and Technology) i znajdował się w trzeciej fazie, której celem było właśnie wykrycie tego typu niedoskonałości, jakie ujawnił Mythos. Po ogłoszeniu wyników przez Anthropic, twórca HAWK-a podjął decyzję o jego wycofaniu.

Przełom w kryptoanalizie wspomaganej AI

Anthropic już wcześniej podkreślał możliwości swojego modelu Mythos, który został poddany dwóm problemom kryptograficznym. Model wykrył słabości w matematycznych podstawach HAWK-a, a także, niezależnie, w powszechnie używanym szyfrze AES. Choć wycofanie HAWK-a jest znaczące, firma podkreśla, że odkrycia te mogą sygnalizować istotny postęp w dziedzinie łamania kryptografii, kluczowej dla prywatności i bezpieczeństwa.

Należy jednak zaznaczyć kilka ważnych zastrzeżeń:

• Wyniki są przyrostowe: Nie łamią one żadnego z kryptosystemów, na których opieramy się na co dzień. Zamiast tego, ujawniają metody umiarkowanego zmniejszenia wysiłku potrzebnego do pokonania tych systemów.
• Osłabione wersje: Testowane kryptosystemy były osłabionymi wersjami tych zdefiniowanych w formalnych specyfikacjach. Jest to standardowa praktyka w testach, ale rzeczywiste implementacje są znacznie bardziej odporne.
• Podstawowe prymitywy bezpieczne: Nawet z usprawnieniami, podstawowe problemy matematyczne (tzw. prymitywy), które stanowią budulec kryptosystemów, pozostają bezpieczne – przynajmniej na razie.
• Niewykonalność poza laboratorium: Obie metody ataku prawdopodobnie byłyby niewykonalne poza środowiskami testowymi.

Jak Mythos złamał HAWK-a?

Model Mythos, dostępny obecnie tylko dla wybranej grupy użytkowników, był w stanie usprawnić ataki na dwa kryptosystemy. W przypadku HAWK-a, schematu podpisu cyfrowego odpornego na komputery kwantowe, badacz Anthropic, bez specjalistycznej wiedzy kryptograficznej, wykorzystał Mythos do poprawy istniejącego ataku. Wymagało to około 60 godzin pracy i kosztów obliczeniowych rzędu 100 000 dolarów.

Bezpieczeństwo HAWK-a opiera się na trudności problemu izomorfizmu kratowego (Lattice Isomorphism Problem), który, w przeciwieństwie do obecnie używanych schematów, jest uważany za bezpieczny przed atakami kwantowymi. Najlepszy znany atak klasyczny na ten problem polega na znajdowaniu tzw. symetrii automorficznych. Mythos opracował wcześniej nieznaną metodę znajdowania takich symetrii, co z definicji złamało algorytm. Chociaż lukę można by załagodzić poprzez podwojenie rozmiaru klucza, dodatkowe obliczenia sprawiają, że HAWK staje się mniej atrakcyjny niż inne dostępne algorytmy podpisu cyfrowego PQC, takie jak ML-DSA i FN-DSA.

Matthew Green, profesor z Johns Hopkins i ekspert w dziedzinie kryptografii, podkreślił, że imponujące w tym odkryciu jest wykorzystanie kilku istniejących metod, których nikt wcześniej nie pomyślał połączyć. „Atak nie wymyśla fundamentalnie nowej matematyki” – napisał Green. „Po prostu rozszerza szereg dostępnych i dobrze znanych narzędzi, uzyskując dobry wynik”.

Mythos działał półautonomicznie, z okazjonalnym nadzorem człowieka. Po przeprowadzeniu obszernego przeglądu literatury, rozumowania matematycznego i eksperymentów obliczeniowych, model znalazł atak i samodzielnie zweryfikował jego poprawność. Co ciekawe, w procesie tym brały udział dwa niezależne agenty AI, z których jeden początkowo odrzucił metodę jako niewykonalną, a drugi znalazł sposób na jej zastosowanie, ostatecznie pracując w unisonie.

Mniej dramatyczne wyniki dla AES

Atak na szyfr AES przyniósł mniej dramatyczne rezultaty. Opiera się on na usprawnieniu ataku typu „meet-in-the-middle”, który służy do wyprowadzania klucza w modelu zagrożenia z wybranym tekstem jawnym. Technika ta polega na wprowadzaniu dużej liczby znanych tekstów jawnych do systemu kryptograficznego i analizowaniu zaszyfrowanych danych wyjściowych w poszukiwaniu wskazówek, które ostatecznie ujawnią nieznany klucz. Wcześniej najlepszy atak „meet-in-the-middle” na AES wymagał około 2^105 danych wejściowych, co czyniło go niewykonalnym.

Mythos pomógł znaleźć nową technikę „meet-in-the-middle”, która opiera się na Möbius Bridge, bardziej zaawansowanym algorytmie odcisków palców. Dzięki temu kod wygenerowany przez Mythos był w stanie zredukować liczbę wymaganych danych wejściowych do 2^89. Anthropic twierdzi, że to oszczędność może skrócić czas potrzebny na takie ataki od 200 do 800 razy. Mimo to, taka liczba danych wejściowych nadal sprawia, że atak jest poza zasięgiem poza warunkami laboratoryjnymi, a testy przeprowadzono na osłabionej wersji AES (7 rund zamiast 10, 12 lub 14).

Przyszłość kryptoanalizy z AI

Anthropic podkreśla, że choć wyniki mają swoje ograniczenia, są one znaczące i mogą fundamentalnie zmienić proces kryptoanalizy. Firma uważa, że modele językowe są w stanie odkrywać tak wiele błędów, że standardowe procesy ludzkie (takie jak triaż, weryfikacja i naprawa luk) mają trudności z nadążaniem. Przewiduje się, że to samo wkrótce będzie dotyczyć akademickich badań kryptograficznych, gdzie autonomiczne generowanie nowych wyników przez modele językowe może sprawić, że badacze ludzcy staną się wąskim gardłem w weryfikacji tych odkryć.

Chociaż raport Anthropic nie wspomina o atakach na bardziej ugruntowane kryptosystemy, takie jak kryptografia krzywych eliptycznych czy RSA, to zdolność AI do znajdowania luk w algorytmach na wczesnym etapie rozwoju, jak HAWK, jest godna uwagi. Badania te jasno pokazują, że kryptoanaliza wspomagana przez AI, choć wciąż w początkowej fazie, ma potencjał do znaczącego wpływu na bezpieczeństwo cyfrowe. Warto obserwować, jak rozwój dużych modeli językowych (LLM) będzie kształtował wyścig między zabezpieczaniem a kompromitowaniem naszych najważniejszych zasobów cyfrowych w przyszłości.

Źródło: arstechnica.com