Claude AI rozwiązał 25-letnią zagadkę klucza początkowego NSA

Przez dziesięciolecia niektórzy z najwybitniejszych kryptografów na świecie gonili za widmem. Pięć krzywych matematycznych wykorzystywanych do ochrony komunikacji internetowej zawierało tajemnicze liczby dostarczone przez Agencję Bezpieczeństwa Narodowego (NSA) i nikt nie potrafił w sposób zadowalający wyjaśnić, skąd te liczby się wzięły. Teorie wahały się od zapomnianych żartów po celowo zasiane słabe punkty. Wtedy sztuczna inteligencja Claude firmy Anthropic podjęła się rozwiązania tej zagadki i prześledziła pochodzenie tych liczb aż do starego programu komputerowego i znaczników czasu sprzed prawie trzech dekad.

25-letnia tajemnica z NSA w centrum

Historia zaczyna się pod koniec lat 90., kiedy to matematycy opracowywali standardy kryptografii opartej na krzywych eliptycznych – metody ochrony informacji cyfrowych wykorzystującej zaawansowaną matematykę. Pięć krzywych, znanych jako P-192, P-224, P-256, P-384 i P-521, ostatecznie stało się częścią standardów opublikowanych przez Narodowy Instytut Standardów i Technologii (NIST). Ich matematyczne podstawy pomogły zabezpieczyć strony internetowe, transakcje finansowe i komunikację rządową.

Ale tu pojawia się haczyk. Każda krzywa została skonstruowana przy użyciu tajemniczej 160-bitowej liczby początkowej, zwanej „ziarnem”. Każdy mógł zweryfikować procedurę matematyczną wykorzystaną do wygenerowania krzywych, ale nikt nie wiedział, w jaki sposób NSA wybrała te pierwotne liczby. To pytanie bez odpowiedzi podsycało spekulacje, że agencja mogła celowo dobrać liczby początkowe, aby ukryć słaby punkt, z którego mogliby skorzystać wyłącznie jej własni specjaliści.

Kryptolodzy Neal Koblitz i Alfred Menezes przeanalizowali tę kontrowersję w swojej pracy z 2015 roku zatytułowanej „A Riddle Wrapped in an Enigma” („Zagadka owinięta w enigmę”). Nigdy nie wykazano istnienia żadnego praktycznego „tylnego wejścia”, ale tajemnica ta nie chciała zniknąć.

Tajna fraza, która najwyraźniej nigdy nie istniała

Przez lata dominującym wyjaśnieniem była wersja dotycząca matematyka z NSA, Jerry’ego Solinasa, który rzekomo dostarczył pierwotne wartości początkowe. Solinas i inni wspominali, że liczby zostały wygenerowane poprzez haszowanie humorystycznych angielskich zwrotów, prawdopodobnie czegoś w rodzaju „Jerry zasługuje na podwyżkę”. Haszowanie przekształca informacje w matematyczny odcisk palca o stałej długości. Niestety nikt nie pamiętał dokładnych zwrotów, a oryginalny komputer został podobno wymieniony.

Sam Solinas próbował odtworzyć ten proces, ale bezskutecznie. Tajemnica ta w końcu zyskała swoją cenę. W październiku 2023 roku kryptograf Filippo Valsorda zaoferował nagrodę w wysokości 12 288 dolarów dla każdego, kto wyjaśni pochodzenie tych liczb początkowych. Dzięki charytatywnej umowie o podwojeniu kwoty potencjalna wypłata wzrosła do 36 864 dolarów. Przez trzy lata nikt nie zgłosił się po pieniądze. Wtedy na scenę wkroczył Claude.

Claude odkrywa odpowiedź ukrytą na widoku

Zgodnie z badaniami firmy Anthropic opublikowanymi 16 października jeden z pracowników poprosił wewnętrzny model badawczy Claude o zbadanie nasion, nie wspominając o utrwalonej teorii tajnej frazy. Model zaczął analizować wzorce związane ze starszymi programami komputerowymi. Jedna wskazówka od razu rzucała się w oczy. Kilka wartości początkowych zawierało grupy liczb, których najwyższe bity były konsekwentnie równe zero – wzór, którego losowe pojawienie się ma prawdopodobieństwo około 1 do 5 810.

Wskazywało to na lrand48, generator liczb pseudolosowych powszechnie dostępny w środowiskach programistycznych z epoki Unix. W przeciwieństwie do prawdziwie losowych procesów, generatory pseudolosowe wytwarzają przewidywalne sekwencje, gdy tylko znane są ich wartości początkowe. Claude prześledził matematyczne procesy wstecz, odtworzył wewnętrzne stany generatora i dokładnie odtworzył opublikowane wartości początkowe. Potem nastąpiła prawdziwa sensacja.

Wartości początkowe odpowiadały sygnaturom czasowym systemu Unix – zwykłym numerycznym reprezentacjom dat i godzin – z lat 1997 i 1998. Zapisane rozumowanie modelu odzwierciedlało jego własne, widoczne niedowierzanie. „To zdumiewające: rozwiązuje to 25-letnią zagadkę”. Cała operacja zajęła mniej niż 30 minut.

Pięć krzywych, pięć znaczników czasu i jedno niezwykłe dopasowanie

Odzyskane wartości początkowe pozwoliły przypisać pięć krzywych pola liczb pierwszych NIST do konkretnych dat między majem 1997 r. a kwietniem 1998 r. Krzywa P-192 pochodziła ze znacznika czasu odpowiadającego 18 maja 1997 r., natomiast krzywa P-521 – z 8 sierpnia tego samego roku. P-256 pojawiła się 16 sierpnia, P-384 – 30 sierpnia, a P-224 – 3 kwietnia 1998 r. Przepis na to wydawał się niemal komicznie prosty. Należy zainicjować zwykły generator liczb losowych za pomocą sygnatury czasowej, wygenerować potencjalne wartości początkowe, sprawdzić je pod kątem wymagań matematycznych i kontynuować poszukiwania, aż pojawi się akceptowalna krzywa.

W przypadku P-256 akceptowalna wartość początkowa pojawiła się jako kandydat nr 1842. W przypadku P-224 potrzeba było 7026 kandydatów. Dopasowania były dokładne — odtwarzały wszystkie 160 bitów opublikowanych wartości początkowych, a nie tylko generowały liczby o podobnym wyglądzie. Valsorda niezależnie odtworzył wyniki przy użyciu języka programowania Go, potwierdzając te ustalenia. Firma Anthropic udostępniła również kod, umożliwiający innym sprawdzenie tych obliczeń. Wyniki dostarczają mocnych dowodów matematycznych na poparcie tej metody generowania, choć nie wyjaśniają one dokładnie, kto obsługiwał oryginalne oprogramowanie ani dlaczego niektóre kandydatury zostały odrzucone.

Co to odkrycie oznacza dla bezpieczeństwa w Internecie

Konsekwencje tego odkrycia są uspokajające, choć nie stanowią one uniwersalnej gwarancji bezpieczeństwa. Jedną z długotrwałych obaw była możliwość, że NSA dysponowała wystarczającą swobodą przy wyborze liczb początkowych, by celowo wybierać krzywe podatne na ataki matematyczne. Odtworzony proces wydaje się oferować znacznie mniej możliwości wyboru niż wymagałyby tego niektóre hipotetyczne ataki. Badacze z firmy Anthropic oszacowali, przy dość optymistycznych założeniach, swobodę wyboru na około 30 bitów, co jest wartością znacznie mniejszą niż około 70 bitów przewidzianych w jednym z proponowanych scenariuszy wyboru słabych punktów.

To sprawia, że ta konkretna teoria dotycząca „tylnych drzwi” staje się znacznie mniej prawdopodobna. Co ważne, odkrycie to nie podważa kryptografii opartej na krzywych eliptycznych ani nie potwierdza, że wykluczono wszystkie możliwe słabe punkty. Nie ma ono również bezpośredniego wpływu na Bitcoin ani Ethereum, które wykorzystują inną krzywą eliptyczną o nazwie secp256k1.

Gregory Maxwell studzi entuzjazm związany z wielką chwilą Claude’a

Co ciekawe, programista Bitcoina Gregory Maxwell wyraził mniej entuzjastyczną opinię, twierdząc na Hackernews, że 20 września zasugerował zbadanie tej samej zagadki kryptograficznej przyjacielowi, którego kredyty w Anthropic AI wkrótce wygasną. Agent AI tego przyjaciela spędził nad tym problemem wiele godzin bez powodzenia, przez co Maxwell nie był pod wrażeniem jego zdolności rozumowania.

Maxwell, zagorzały krytyk podejścia firmy Anthropic do sztucznej inteligencji, zastanawiał się, czy firma nie ograniczyła możliwości modelu jego przyjaciela, i wyśmiewał rozgłos wokół odkrycia Claude’a. Nie posunął się jednak do przypisywania sobie zasług ani kwestionowania wyników, sugerując, że różnica w wynikach może po prostu odzwierciedlać sposób, w jaki sztuczna inteligencja została nakierowana.

„Nie mówię tego, by sugerować, że misantrop po raz kolejny przywłaszczył sobie cudzą pracę – jest to oczywiste pytanie, które z pewnością zadało sobie wiele osób, a sukces prawdopodobnie zależał od fachowego wykorzystania (czego absolutnie nie zastosowano w przypadku mojego przyjaciela)” – napisał Maxwell. „Zastanawiam się jednak, czy firma w niewidoczny sposób nie obniżyła wydajności modelu”.

Nagroda została wypłacona, ale pytania pozostają

To odkrycie ostatecznie rozstrzygnęło trwające od trzech lat wyzwanie Valsordy. Zespół Anthropic przekazał nagrodę w wysokości 36 864 dolarów organizacji Internet Security Research Group, która zarządza serwisem Let’s Encrypt. Valsorda opisał to odkrycie jako coś, co „pomaga uzupełnić kartę historii kryptografii i wzmacnia nasze zaufanie do tych kluczowych prymitywów kryptograficznych”. Pozostało jednak kilka niewyjaśnionych kwestii. Badacze nie wyjaśnili w pełni, dlaczego niektóre matematycznie dopuszczalne kandydatury zostały odrzucone, a pochodzenie nasionka innej krzywej, B-163, pozostaje nierozwiązane.

Niemniej jednak główna zagadka wydaje się rozwiązana. Po dziesięcioleciach podejrzeń, spekulacji i nieudanych prób odtworzenia rzekomo zapomnianej tajnej frazy, odpowiedź znajdowała się w zwykłej procedurze komputerowej z lat 90. Tajemnicze liczby NSA niekoniecznie kryły skomplikowaną tajemnicę. Być może po prostu służyły do pomiaru czasu.