Claude odtworzył proces generowania parametrów NIST-owych krzywych eliptycznych. Odkrycie zostało nagrodzone w ramach programu bounty.

Implementując algorytmy kryptograficzne często korzystamy z oficjalnych standardów (opublikowanych m.in. przez NIST, czy NSA), nie zastanawiając się przy tym, w jaki sposób wygenerowano zawarte w nich  kluczowe dane. W przypadku algorytmów symetrycznych (np. AES) sprawa jest względnie prosta.  Prymitywy kryptograficzne (takie jak S-boxy, czy macierze MDS) muszą spełnić jawne kryteria matematyczne i przejść szereg testów statystycznych oraz kryptograficznych (odporność na kryptoanalizę liniową i różnicową, wysoka nieliniowość, odpowiednie właściwości dyfuzyjne, itp.).

Nieco inna sytuacja jest w przypadku kryptografii asymetrycznej, a zwłaszcza bazującej na krzywych eliptycznych (ECC). Standaryzacja narzuca nam przyjęcie konkretnych, odgórnie ustalonych parametrów. Ich użycie jest kluczowe, ponieważ z jednej strony “gwarantują” odpowiedni poziom bezpieczeństwa, z drugiej zaś są niezbędne do poprawnego nawiązania połączenia między stronami. 

W 2000 roku NIST opublikował standard FIPS 186-2, w którym zostały umieszczone specyfikacje krzywych eliptycznych (P-256, P-384, P-521). Do utworzenia parametrów krzywych wykorzystano 160-bitowe ziarno (SEED), które podane na wejście funkcji skrótu SHA-1 służyło do wygenerowania parametru b równania krzywej. Pochodzenie tych ziaren od dawna budziło pytanie, ponieważ zostały dostarczone przez NSA bez żadnego wyjaśnienia ani uzasadnienia. 

Przez lata temat generacji ziaren wracał. Jedni uważali, że parametry te zostały dobrane w taki sposób, aby NSA było w stanie zapewnić sobie backdoora, a co za tym idzie podsłuchiwać komunikację. Inni uważali, że najprawdopodobniej jest to skrót jakiejś żartobliwej frazy.  

Tak czy inaczej, za odnalezienie sposobu generacji ziaren wyznaczono nagrodę (bounty) wynoszącą ponad 36 000 USD. Mimo, że znajomość metody ich tworzenia najpewniej nie wpływa bezpośrednio na bezpieczeństwo krzywej, a stanowi swojego rodzaju zagadkę.

Na odpowiedź trzeba było poczekać do 2026 r. Badacz z Anthropic wykorzystał model Claude do odtworzenia sposobu generacji parametrów. Od początku model założył, że do utworzenia danych wykorzystano tradycyjny, systemowy generator lrand48 zainicjowany znacznikiem czasu (Unix timestamp) pod koniec lat 90 i miał rację.

Claude przeprowadził symulację i przeszukał przestrzeń potencjalnych czasów systemowych z przedziału 1997-1998. Następnie zastosował zaawansowane narzędzia matematyczne (w tym metodę redukcji krat i algorytm LLL) do odtworzenia stanu wewnętrznego generatora. Brzmi skomplikowanie, jednak Claude doskonale sobie z tym radzi i praktycznie wszystkie operacje przeprowadza samodzielnie w tle.

Wynik przerósł oczekiwania. Udało się odtworzyć ziarna do większości krzywych umieszczonych w standardzie. Tym samym spekulacje o backdoorze w parametrach krzywych zostały jednoznacznie wykluczone. Do wygenerowania danych użyto zwykłego systemowego generatora lrand48 zainicjalizowanego znacznikiem czasu.

W odtworzonym algorytmie parametr t oznacza znacznik czasu Unix, n określoną liczbę iteracji, a Seed ziarno. Każda iteracja pobierała z generatora 20 bajtów jako potencjalnego kandydata. Dla przykładu wygenerowanie ziarna dla krzywej P-256 wymagało 1842 iteracji algorytmu. 

Co ciekawe, podczas iteracji 876 otrzymano krzywą o rzędzie pierwszym, odpowiednim rozmiarze i parametrach dobranych w ten sam sposób jak w krzywej P-256. Mimo wszystko, z nieznanych powodów krzywa ta została odrzucona. Być może nie spełniała innych warunków bezpieczeństwa lub została pominięta bez powodu.

Wyznaczona nagroda wynosząca $36,864 trafiła ostatecznie do organizacji Internet Security Research Group (ISRG) rozwijającej m.in. projekt Let’s Encrypt.

Osoby zainteresowane szczegółami technicznymi wraz z przykładowym kodem pozwalającym na odtworzenie tych danych odsyłamy do źródeł.

Źródło: anthropic.com

~secmike