Claude ujawnia pochodzenie krzywych ECDSA
Wyjaśniono pochodzenie jednego z najpopularniejszych standardów kryptograficznych. Zbadaliśmy to długotrwałe otwarte pytanie społeczności kryptograficznej, aby rozstrzygnąć obawy dotyczące ECDSA, jednego z najszerzej stosowanych standardów kryptograficznych.
ECDSA jest najszerzej stosowanym standardem kryptografii krzywych eliptycznych. Został przyjęty przez NIST w 2000 roku jako część standardu FIPS 186-2 Digital Signature Standard, który wymienia zestaw standardowych krzywych eliptycznych o różnych rozmiarach i poziomach bezpieczeństwa. Dla krzywych nad ciałami pierwszymi i binarnymi specyfikacje publikowały parametr „seed”, którego wartość skrótu jest używana do zdefiniowania współczynnika b krzywej. Pochodzenie tych ziaren było długotrwałym pytaniem, ponieważ zostały dostarczone przez NSA bez wyjaśnienia ani uzasadnienia. Na przykład ziarno krzywej NIST P-256 to SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 bez informacji, skąd pochodzi.
Neal Koblitz i Alfred Menezes napisali podsumowanie tej kontrowersji, „A Riddle Wrapped in an Enigma”, które omawia historię i obawy wokół wartości ziaren. Ta zagadka doprowadziła do amatorskiego śledztwa w sprawie pochodzenia ziaren i nagrody dla każdego, kto mógłby je znaleźć.
Najlepsza historia głosiła, że Jerry Solinas, wieloletni pracownik NSA, wygenerował ziarna za pomocą skrótu humorystycznej frazy. Niestety, Jerry zmarł w 2023 roku, a inni ówcześni koledzy nie odpowiadali, pozostawiając otwartym pytanie, w jaki sposób te ziarna zostały pierwotnie wyprowadzone.
Claude znalazł ziarna
Kilku pracowników Anthropic bezskutecznie ścigało ziarna po wskazówce, że jest to skrót humorystycznej frazy. To okazało się błędne. W październiku 2026 roku pracownik Anthropic zapytał wewnętrzny model badawczy, czy potrafi ustalić, jak te ziarna zostały wygenerowane, bez wskazywania wskazówki.
W niecałe pół godziny Claude odkrył pochodzenie ziaren NIST P-192, P-224, P-256, P-384 i P-521. Żadne z nich nie było wynikiem żadnego algorytmu haszującego, lecz wynikiem generatora liczb losowych lrand48 z biblioteki C, zainicjowanego znacznikiem czasu Unix!
Algorytm pobierał bajty z generatora liczb losowych (RNG) zainicjowanego znacznikiem czasu Unix (t) dla pewnej liczby iteracji (n). Każda iteracja pobierała 20 bajtów jako ziarno kandydujące. Pierwsze 20 bajtów to kandydat 1, kolejne 20 bajtów to kandydat 2 i tak dalej. Na przykład P-256 wymagało 1842 iteracji, aby wygenerować ustandaryzowane ziarno.
Co to oznacza
To nie jest przełamanie kryptograficzne, nowy atak ani słabość krzywych ECDSA. W rzeczywistości daje to większą pewność, że krzywe zostały wybrane bez żadnych tylnych furtek ani celowych słabości. Przez wiele lat ludzie byli podejrzliwi wobec pochodzenia parametrów krzywych NIST. Zostały one przedstawione NIST bez wzmianki o tym, jak zostały wybrane, co sprawiało, że ludzie zastanawiali się, czy mogły zostać wybrane tak, aby miały w sobie celowe tylne furtki. Te odkrycia sprawiają, że jest to znacznie mniej prawdopodobne. Ziarna zostały wygenerowane w bardzo prosty sposób: za pomocą powszechnego generatora liczb pseudolosowych zainicjowanego zegarem, co każdy może teraz odtworzyć.
Jak to zostało znalezione
Wyszukiwania frazy oparte na plotkach nie przyniosły rezultatów. Claude spróbował innego kąta: przewidując, jak musiało działać oprogramowanie, które wygenerowało krzywe. Claude zgadł, że oprogramowanie używało generatora liczb pseudolosowych (PRNG), który był dostarczany z bibliotekami C z lat 90. Te stare PRNG są wystarczająco słabe, aby ich wynik można było rozpoznać. Rozpoznanie tego wyniku ujawniłoby, który PRNG został użyty i prawdopodobnie pozwoliłoby na odzyskanie jego stanu inicjalizacji.
Claude napisał skaner, który przesuwał się wzdłuż każdego opublikowanego ziarna bit po bicie i testował, czy sąsiednie fragmenty były kolejnymi wynikami generatora z lat 90. Skan obejmował 34 kombinacje generatora i wycinków wyjściowych. W tym momencie Claude zauważył wzorzec w górnych bitach dla niektórych ziaren: wszystkie były zerami. Zapisane jako pięć 32-bitowych słów, cztery z dziesięciu ziaren mają 0 w górnym bicie dla wszystkich 20 słów. To zdarzyłoby się przypadkiem z prawdopodobieństwem 1/5810. To była sygnatura generatora liniowego kongruencyjnego lrand48, który zwraca tylko górne 31 bitów 48-bitowego stanu. Wzorzec jest widoczny gołym okiem, gdy już wiesz, żeby go szukać. Aby odzyskać stan, Claude wziął pierwsze słowo, wypróbował wszystkie 2¹⁷ wartości 17 ukrytych bitów i sprawdził, czy kolejne cztery słowa pasują. To zadziałało dla wszystkich czterech ziaren pod dyskusją.
Ziarna krzywych pierwszych pochodziły z tego samego generatora lrand48, ale zachowywały mniej bitów każdego wyniku. Claude musiał odzyskać wewnętrzny stan PRNG z tych bitów. Okazuje się, że odzyskanie stanu uciętego generatora liniowego kongruencyjnego jest podręcznikowym problemem sieciowym, rozwiązywanym za pomocą algorytmu redukcji bazy Lenstra–Lenstra–Lovász (LLL). Claude nie wiedział, które bity stanu ziarna mogą pokazywać, więc uruchomił solver dla każdego okna. Pięć ziaren krzywych pierwszych NIST plus pięć kolejnych ze standardu ANSI X9.62 miało ten sam wzorzec: lrand48() >> 23. Każdy odzyskany 48-bitowy stan regeneruje wszystkie 160 bitów swojego ziarna, co nie dzieje się przypadkiem.
Ten generator liniowy kongruencyjny działa wstecz tak samo łatwo jak do przodu, więc dla każdego ziarna Claude cofał stan, aż osiągnął formę, w której zostałby zainicjowany przez srand48, z dolnymi 16 bitami równymi 0x330E. Wewnętrzny stan PRNG w tej formie pojawiałby się raz na 65 536 kroków, więc osiągnięcie go nie jest dowodem samym w sobie.
Jednak dla dziesięciu ziaren krzywych pierwszych każda inicjalizacja srand48 była znacznikiem czasu Unix reprezentującym datę między majem 1997 a kwietniem 1998 roku. Używali słabego PRNG zainicjowanego znacznikiem czasu Unix. Cztery inicjalizacje krzywych binarnych odczytano jako luty 1984. Przy podwojonych znacznikach czasu mapują się one na 17 kwietnia 1998 roku, dwa tygodnie po uruchomieniu P-224. Więc program mógł podzielić zegar na pół.
Claude znalazł również punkty bazowe
Każda krzywa ma również punkt bazowy, G, stały punkt, którego wielokrotnością jest każdy klucz publiczny ECDSA. Znalezione ziarno nie określa tego G, więc pojawia się kolejne pytanie: jak wygenerowano te punkty bazowe?
Podczas sprawdzania ziaren Claude znalazł również, skąd pochodzą niektóre punkty bazowe. Punkty bazowe sześciu krzywych wygenerowanych w maju 1997 roku (P-192 i pięć przykładowych krzywych ANSI X9.62 prime192v2, prime192v3 oraz prime239v1 do v3) pochodzą z generatora liczb losowych w FreeLIP, pakiecie arytmetyki długich liczb całkowitych Arjena Lenstry. Wczesne wersje biblioteki NTL Victora Shoupa zawierały ten sam kod.
Przepis jest prosty: zainicjuj generator małą liczbą całkowitą, odrzuć siedem wyników, generuj kandydatów współrzędnych x z 26-bitowych wyników zredukowanych mod p, powtarzaj krok 3, aż x znajdzie się na krzywej. Claude odkrył, że ziarna generatora to 20000 dla P-192, 20420, 20507 i 20509 dla prime239v1 do v3 oraz 20512 i 20517 dla prime192v2 i v3. O ile nam wiadomo, żaden punkt bazowy NIST nie został wcześniej wyjaśniony. Punkty bazowe P-224, P-256, P-384 i P-521 nie pasują do tego przepisu; nie byliśmy w stanie wyjaśnić, jak zostały wybrane.
Otwarte pytania
Nie każde 20-bajtowe ziarno kandydujące mogło wygenerować wykonalną krzywą i zaobserwowaliśmy, że niektóre potencjalnie wykonalne krzywe zostały pominięte. Dla P-256 opublikowane ziarno to kandydat 1842, ale kandydat 876 z tego samego przebiegu również daje krzywą rzędu pierwszego o odpowiednim rozmiarze i parametrach wybranych w ten sam sposób, co na opublikowanej krzywej. Przebieg P-224 pominął trzy takie krzywe, a dwa przebiegi za przykładowymi krzywymi ANSI X9.62 pominęły siedem kolejnych. Nie wiemy, jakie kryteria mogły zostać użyte ani czy był to niezamierzony artefakt.
Ponieważ liczba pominiętych kandydatów jest mała, nie uważamy za prawdopodobne, aby wybrano osłabione krzywe. To sugerowałoby, że osłabione krzywe są powszechne i łatwe do znalezienia. Nadal można sobie wyobrazić, że te krzywe zostały wybrane tak, aby miały określoną właściwość w zasadzie poprzez przeszukiwanie znaczników czasu dla generatora liczb losowych. Jednak musiałbyś to zrobić tylko wtedy, gdybyś miał ujawnić znacznik czasu jako dowód, że ziarno zostało wygenerowane w sposób nieszkodliwy. Nic w liczbach nie pokazuje, ile było przebiegów.
Jest też jedno ziarno, którego nie udało nam się odzyskać. Piąte ziarno binarne, B-163, nie pasuje do niczego, czego próbował Claude i pozostaje niewyjaśnione. Wreszcie, nie wiemy, jak wygenerowano punkty bazowe dla P-224, P-256, P-384 i P-521. To samo dotyczy krzywych binarnych NIST.
Nagroda
36 864 USD za znalezienie ziaren zostanie przekazane Internet Security Research Group.
Kim jesteśmy
Praca ta została przeprowadzona w Anthropic przez Johna Wooda, Henry'ego de Valence, Avę Howell, Zacka Voase'a, Lucy Sweet, Amira Omidi, Paula Crowleya, Iaina McGinnissa, Nicholasa Carliniego i Steve'a Weisa.
Podziękowania
Chcielibyśmy pośmiertnie uhonorować Jerry'ego Solinasa, który z humorem przyjął bycie nazwanym „złym memem internetowym” i „Yo La Tengo straszydeł NSA”. Podziękowania również dla Filippo Valsordy za zorganizowanie nagrody NIST Elliptic Curves Seeds Bounty.