Claude odhaľuje pôvod ECDSA Curve seeds

Výskumníci z Anthropic konečne vyriešili desaťročia starú záhadu okolo pôvodu jedného z najpoužívanejších kryptografických štandardov, Elliptic Curve Digital Signature Algorithm (ECDSA). Claude, interný výskumný model, zistil, že základy piatich NIST kriviek a štyroch štandardných kriviek ANSI X9.62 boli generované pomocou jednoduchého generátora pseudonáhodných čísel inicializovaného Unixovými časovými pečiatkami.

Krivka ECDSA je jedným z najpoužívanejších kryptografických štandardov na svete, prijatý NIST v roku 2000 ako súčasť štandardu FIPS 186-2 Digital Signature Standard. Avšak výskumníci už roky pochybujú o pôvode semien poskytnutých Národnou bezpečnostnou agentúrou (NSA) bez akéhokoľvek vysvetlenia či odôvodnenia.

Neal Koblitz a Alfred Menezes napísali vynikajúce zhrnutie tejto kontroverzie vo svojom článku ‘A Riddle Wrapped in an Enigma’, ktorý rozoberá históriu a obavy týkajúce sa hodnôt semien. Táto záhada viedla k amatérskemu vyšetrovaniu pôvodu semien, pričom bola vyhlásená odmena pre každého, kto ich nájde.

Jerry Solinas, dlhoročný zamestnanec NSA, prezradil, že semienka generoval pomocou vtipnej heslovej frázy: ‘Dajte Bobovi a Jerrymu zvýšenie platu’ alebo niečoho podobného. Bohužiaľ, Jerry však zomrel v roku 2023, čo ponechalo otvorenú otázku, ako tieto semienka pôvodne vznikli.

Zvedavý zamestnanec Anthropic požiadal Clauda, aby zistil, ako sa tie semená generujú, bez toho, aby ukázal na akékoľvek stopy. Za menej ako pol hodiny Claude zistil, že žiadne zo semien nebolo výsledkom hashovacieho algoritmu, ale skôr výstup generátora náhodných čísel lrand48 v knižnici C s časovou pečiatkou Unixu!

Použitý algoritmus by vzorkoval bajty z generátora náhodných čísel inicializovaných Unixovým časovým pečiatkom (t) pre určitý počet iterácií (n). Každá iterácia by vykreslila 20 bajtov ako kandidátsky seed. Napríklad P-256 vyžadoval 1842 iterácií na výstup štandardizovaného semena.

Nejde o kryptografický zlom ani nový útok na ECDSA krivky, ale skôr nás to posilňuje v presvedčení, že krivky boli vybrané bez zadných vrátok alebo zámerných slabostí. Semená boli generované veľmi jednoduchým spôsobom: bežným pseudonáhodným generátorom čísel inicializovaným z hodín, ktorý teraz môže ktokoľvek reprodukovať.

Claudeova vnútorná myšlienka vtedy spočívala v overení, či ide naozaj o reálny svet a nie o nejaké simulované/testovacie prostredie. Skontroloval, že horné bity sú čisté pre všetkých 20 slov zo štyroch semien, s pravdepodobnosťou 1/5810 náhodou. To potvrdilo, že ide o skutočný objav.

Avšak vyvstáva ďalšia otázka: ako boli tieto základné body generované? Pri kontrole semien Claude tiež zistil, odkiaľ niektoré základné body pochádzajú. Základné body šiestich kriviek generovaných v máji 1997 pochádzajú z generátora náhodných čísel vo FreeLIP, aritmetickom balíku Arjena Lenstru.

Recept na generovanie základných bodov je jednoduchý: použiť Unixovú časovú pečiatku ako inicializačný seed a potom ju spustiť cez funkciu lrand48() s určitými špecifickými parametrami. Claude zistil, že táto metóda generuje správne základné body pre šesť kriviek, ale nie pre iné.

Nie každý 20-bajtový kandidátsky seed dokázal vygenerovať životaschopnú krivku a pozorovali sme, že niektoré potenciálne životaschopné krivky boli preskočené. Pre P-256 je publikovaný seed kandidát 1842, ale kandidát 876 z toho istého behu tiež poskytuje krivku prvočíselného rádu s parametrami zvolenými rovnakým spôsobom ako na publikovanej krivke.

Počet preskočených kandidátov je malý, takže nie je pravdepodobné predpokladať, že boli vybrané oslabené krivky. Napriek tomu zostáva možné, že tieto krivky boli vybrané tak, aby mali špecifické vlastnosti vyhľadávaním cez časové pečiatky v generátore náhodných čísel. Nič neukazuje, koľko behov tam bolo.

Existuje aj jedno semeno, ktoré sa nám nepodarilo obnoviť: B-163 nezodpovedá ničomu, čo Claude skúšal, a zostáva nevysvetlený. Nakoniec nevieme, ako boli generované základné body pre P-224, P-256, P-384 a P-521 ani pre binárne krivky NIST.

Odmena vo výške 36 864 dolárov bude venovaná Internet Security Research Group na znak uznania tohto úspechu. Táto práca bola vykonaná v Anthropic tímom vedeným Johnom Woodom, Henrym de Valence, Avou Howell, Zackom Voasom, Lucy Sweet, Amirom Omidim, Paulom Crowleym, Iainom McGinnissom, Nicholasom Carlinim a Stevom Weisom.

Radi by sme posmrtne ocenili Jerryho Solinasa za jeho dobrý humor, keď bol označený za ‘zlý internetový meme’ a ‘Yo La Tengo strašiakov NSA’. Ďakujem tiež Filippovi Valsordovi za organizáciu odmeny za semienka eliptických kriviek NIST.

Claudeov objav je významným míľnikom v kryptografii, ktorý poskytuje väčšiu istotu, že ECDSA krivky boli zvolené bez zadných vrátok alebo zámerných slabín. Semená a základné body generované pomocou unixových časových značiek sú teraz reprodukovateľné kýmkoľvek.

Výskumný tím v Anthropic tiež pracuje na zlepšovaní kvantových obvodov pre praktické použitie. Claude dostal špecifikácie v jednoduchom jazyku pre osem kvantových obvodov spolu s automatizovaným hodnotiteľom na kontrolu a hodnotenie ich návrhov, čo viedlo v niektorých prípadoch k zlepšeniu obvodov o rád alebo viac.

Tento úspech nás približuje bližšie, než sa predtým očakávalo, k vývoju praktických kvantových počítačov. Práca tímu na zlepšení kvantových obvodov je významným príspevkom do tejto oblasti.