Claude rozwiązał zagadkę NSA nad którą kryptografowie głowili się przez 25 lat. Zajęło mu to 30 minut

Model Claude firmy Anthropic ustalił, skąd pochodzą liczby, które amerykańska Agencja Bezpieczeństwa Narodowego (NSA) przekazała pod koniec lat 90. do standardu podpisów cyfrowych. Nie były to skróty tajnego hasła ani starannie dobrane wartości. To wynik zwykłego generatora liczb pseudolosowych z biblioteki języka C, który za punkt wyjścia brał bieżącą datę i godzinę. Kryptografowie spierali się o nie przez ponad ćwierć wieku. Modelowi zajęło to, jak podaje Anthropic, niecałe pół godziny.

Dodaj nas do ulubionych źródeł w Google

Skąd wzięły się podejrzenia wobec NSA

Krzywe z rodziny P opublikował amerykański Narodowy Instytut Standaryzacji i Technologii (NIST) w 2000 r. w standardzie FIPS 186-2. Każda powstała z 20-bajtowego ziarna, które przepuszczano przez funkcję skrótu SHA-1. Z wyniku wyliczano jeden ze współczynników krzywej. Taka procedura miała dowodzić, że nikt nie dobrał parametrów pod siebie. Słaby punkt był jeden: ziarna dostarczyła NSA i nigdy nie wyjaśniła, skąd je wzięła.

Na P-256 i P-384 opierają się certyfikaty, które chronią dużą część ruchu w internecie. P-256 obsługują też klucze dostępu (passkeys), układy Secure Enclave w iPhone’ach i sprzętowe klucze bezpieczeństwa. Wątpliwości wokół tej krzywej nie były więc akademickim sporem.

W 2013 r. dokumenty ujawnione przez Edwarda Snowdena wzmocniły podejrzenia, że NSA umieściła furtkę w innym standardzie NIST, generatorze liczb losowych Dual_EC_DRBG. Instytut najpierw odradził jego używanie, a potem wykreślił go z zaleceń. Od tamtej pory każda niewyjaśniona liczba od agencji budziła nieufność.

Ziarna wygenerował w 1997 r. Jerry Solinas, matematyk NSA. W 2015 r. wspominał, że były skrótem żartobliwego zdania w rodzaju „dajcie Bobowi i Jerry’emu podwyżkę” z dopisanym licznikiem. Kod napisał jego kolega Bob Reiter, ale żaden z nich nie pamiętał szczegółów, a archiwów z tamtych lat nie odnaleziono.

Solinas zmarł na początku 2023 r. Kilka miesięcy później, 5 października 2023 r., kryptograf Filippo Valsorda ogłosił nagrodę za odnalezienie ziaren. Valsorda do 2022 r. odpowiadał za kryptografię w zespole języka Go w Google. Oferował 12 288 dolarów gotówką albo trzy razy tyle, jeśli zwycięzca przekaże pieniądze na cele dobroczynne. Do puli dorzuciło się jedenaście osób z branży, m.in. Matthew Green z Uniwersytetu Johnsa Hopkinsa. Przez trzy lata nikt nie zgłosił się po pieniądze.

Jak Claude znalazł ziarna P-256

Kilku pracowników Anthropica szukało wcześniej zdania o podwyżce, bez skutku. W październiku jeden z nich zapytał wewnętrzny, badawczy model Claude’a, jak powstały ziarna. Celowo nie podsunął mu wskazówki o zdaniu. Model poszedł inną drogą. Założył, że oprogramowanie z lat 90. korzystało ze standardowego generatora z bibliotek języka C, a takie generatory są na tyle słabe, że ich wynik da się rozpoznać.

Claude napisał program, który przesuwał się po każdym ziarnie bit po bicie i sprawdzał 34 kombinacje generatorów i sposobów cięcia ich wyników. Na trop naprowadziło go spostrzeżenie, że w czterech ziarnach najwyższy bit każdego 32-bitowego słowa wynosi zero. Przypadkiem zdarza się to raz na 5810 prób. To znak rozpoznawczy funkcji lrand48, która z 48-bitowego stanu oddaje tylko górne 31 bitów. Brakujące 17 bitów Claude ustalił metodą prób i błędów, sprawdzając wszystkie 131 tys. możliwości. Przy krzywych P generator zostawiał w ziarnie mniej bitów, więc Claude sięgnął po redukcję krat algorytmem LLL (Lenstry-Lenstry-Lovásza). To podręcznikowe narzędzie do odzyskiwania stanu takich generatorów.

Po cofnięciu generatora do punktu startowego za każdym razem wychodził uniksowy znacznik czasu, czyli liczba sekund, które upłynęły od 1 stycznia 1970 r. Model sprawdził dziesięć ziaren: pięć z NIST i pięć z amerykańskiego standardu bankowego ANSI X9.62. Wszystkie wskazały daty od maja 1997 r. do kwietnia 1998 r. Sama procedura była banalna. Program brał kolejne 20 bajtów jako kandydata na ziarno i odrzucał go, jeśli krzywa nie spełniała warunków. P-256 to 1842. kandydat z serii uruchomionej 16 sierpnia 1997 r. o 3:52:34 czasu polskiego. Odzyskany 48-bitowy stan odtwarza wszystkie 160 bitów opublikowanego ziarna, a przy dziesięciu takich trafieniach o przypadku nie ma mowy.

Model sam nie dowierzał wynikowi. W zapisie rozumowania zastanawiał się, czy nie trafił do symulowanego środowiska testowego i czy to w ogóle możliwe, by coś tak prostego umknęło ludziom przez 25 lat. Przekonała go dopiero zgodność co do bitu.

Dziesięcioosobowy zespół Anthropica zgłosił rozwiązanie 15 października o 3:07 czasu polskiego. Valsorda przepisał algorytm w języku Go i potwierdził wynik na swoim blogu. Firma opisała ustalenia w piątkowym wpisie badawczym. Dołączyła kod zwracający dokładnie te ziarna, które od 26 lat figurują w standardzie.

Przy okazji Claude wyjaśnił pochodzenie punktów bazowych sześciu krzywych z maja 1997 r., w tym P-192. Wylosował je generator z FreeLIP, biblioteki do obliczeń na dużych liczbach napisanej przez holenderskiego kryptologa Arjena Lenstrę. Według Anthropica nikt wcześniej nie wyjaśnił pochodzenia żadnego punktu bazowego NIST.

Furtki nie było, ale nie wszystko wiadomo

Anthropic zastrzega, że nie chodzi o złamanie zabezpieczeń ani nowy atak. Wynik działa w drugą stronę i podcina teorię o furtce. Jej najpoważniejszą wersję opisali w 2017 r. kryptolodzy Daniel Bernstein i Tanja Lange. Ich technika wymagałaby około 70 bitów swobody w wyborze ziarna, żeby trafić w hipotetyczną klasę słabych krzywych.

Valsorda policzył, ile swobody NSA mogła mieć naprawdę. Agencja mogła wybrać dowolną sekundę z lat 1997–1998 i dowolnego z pierwszych 16 poprawnych kandydatów. Nawet wtedy miałaby ledwie około 30 bitów swobody. Każdy bit mniej to dwa razy mniej wariantów, więc 40 bitów różnicy oznacza około biliona razy mniej możliwości. Za mało, by celowo cokolwiek ukryć.

Valsorda poszedł dalej. Napisał, że dziś osobiście poleciłby krzywe NIST zamiast Curve25519, konkurencyjnej konstrukcji autorstwa Bernsteina. Dodał też z przekąsem, że rehabilitacja przyszła w samą porę, by krzywe mogły odejść na emeryturę na rzecz podpisów postkwantowych.

Kilka pytań zostało bez odpowiedzi. Program z lat 90. pomijał część kandydatów, z których dało się zbudować poprawną krzywą. Przy P-256 taki był już kandydat nr 876, a do standardu trafił 1842. Według Valsordy prawidłowych ziaren było mniej więcej dwa razy więcej, niż opublikowano, i żadne wyjaśnienie dobrze do tego nie pasuje. Może błąd tkwił w obliczeniach, które w 1997 r. były jeszcze szczytem możliwości. Może też generator zużywał liczby na inne rachunki. Anthropic ocenia, że pominięć jest za mało, by ktoś mógł w ten sposób wybrać słabszą krzywą. Nie udało się też odtworzyć ziarna krzywej binarnej B-163 ani punktów bazowych P-224, P-256, P-384 i P-521.

Czy Bitcoin i Ethereum są zagrożone?

Bitcoina ta historia nie dotyczy bezpośrednio. Satoshi Nakamoto wybrał krzywą secp256k1 ze standardu konsorcjum SECG. Jej parametry nie pochodzą z żadnego ziarna, a współczynniki równania to po prostu 0 i 7. W czasach, gdy krzywe NIST budziły podejrzenia, właśnie za to ją chwalono. Na secp256k1 opierają się także klucze zwykłych kont w Ethereum.

Pośrednio sprawa dotyka jednak kryptowalut coraz mocniej. Od aktualizacji Fusaka z grudnia 2025 r. Ethereum ma wbudowaną obsługę P-256 (propozycja EIP-7951). Portfele mogą dzięki temu zatwierdzać transakcje kluczem dostępu, odciskiem palca albo Face ID. Używają do tego tych samych układów w telefonach, które chronią logowanie do banku. Pytanie o pochodzenie ziarna P-256 regularnie wracało w dyskusjach o takich portfelach. W 2023 r. część społeczności Ethereum zbierała nawet dodatkowe pieniądze do puli Valsordy. Teraz ten argument odpada.

Tego samego dnia Anthropic opublikował też wiadomość mniej kojącą dla posiadaczy kryptowalut. Claude zaprojektował wydajniejsze obwody kwantowe, w niektórych przypadkach o rząd wielkości lepsze od najlepszych znanych. Firma pisze, że praktyczne komputery kwantowe mogą przez to nadejść szybciej, niż zakładano. A wystarczająco duży komputer kwantowy złamie zarówno P-256, jak i secp256k1, na której stoi Bitcoin.

Redakcja BitHub.pl poleca również: