Claude megfejtette a NIST-görbék 25 éves rejtélyét

Mi volt a rejtély?

Az ECDSA a legelterjedtebb elliptikus görbés aláírási szabvány, a NIST 2000-ben vette fel a FIPS 186-2-be. A szabványos görbékhez közzétettek egy seed nevű paramétert, ennek hash-éből jön a görbe b együtthatója. A seedeket az NSA adta, magyarázat nélkül. Emiatt évekig téma volt, hogy nincs-e szándékos gyengeség a görbékben, Filippo Valsorda pedig díjat is kitűzött annak, aki megtalálja az eredetüket.

A legismertebb magyarázat Jerry Solinastól, az NSA egykori munkatársától jött: szerinte egy vicces mondat hash-éből készültek, valami olyasmiből, hogy „Give Bob and Jerry a raise”. Solinas 2023-ban meghalt, az ügy nyitva maradt (Anthropic).

Mit talált Claude?

Az Anthropic több munkatársa is próbálkozott a mondatos nyomon, eredmény nélkül. Októberben egy kolléga tipp nélkül kérdezte meg egy belső kutatási modellt. Claude kevesebb mint fél óra alatt megtalálta a P-192, P-224, P-256, P-384 és P-521 seedjeinek eredetét. Egyik sem hash: mind az lrand48 kimenete, amelyet egy Unix-időbélyeggel indítottak. A program 20 bájtos jelölteket húzott egymás után, a P-256 seedje az 1842. jelölt volt egy 1997. augusztus 16-i (UTC) futásból.

A módszer lényege: Claude abból indult ki, hogy a 90-es évek C-könyvtáraiban lévő gyenge generátorok kimenete felismerhető. Írt egy szkennert, amely 34 generátor- és kimenetkombinációt próbált végig. Feltűnt neki, hogy tíz seedből négynél minden 32 bites szó legfelső bitje nulla, ennek véletlen esélye 1:5810. Ez az lrand48 ujjlenyomata, mert csak 31 bitet ad vissza a 48 bites állapotából. A prímgörbéknél a kimenet csonkolt volt, ott LLL-rácsredukcióval állította vissza a generátor állapotát. Minden visszafejtett indítás 1997 májusa és 1998 áprilisa közé eső időbélyegnek bizonyult.

Mellékesen hat görbe bázispontjának eredetét is megtalálta: ezek Arjen Lenstra FreeLIP könyvtárának generátorából jöttek, kis egész seedekkel (a P-192-nél 20000). Nyitva maradt viszont a B-163 seedje, illetve a P-224, P-256, P-384 és P-521 bázispontja.

Claude saját gondolatmenete is bekerült a posztba. Először azt mérlegelte, nincs-e tesztkörnyezetben, aztán így zárta: „Wow, it's a real discovery.”

Mit jelent ez a biztonságra?

Az Anthropic hangsúlyozza: ez nem törés és nem új támadás, senkinek nincs teendője. Inkább megnyugtató, mert a seedek egy egyszerű, bárki által reprodukálható folyamatból jöttek, így kevés tér marad a manipulációra. A reprodukáló kódot CC0 licenccel közzétették.

Egy furcsaság azért maradt. Néhány használható jelöltet a generálás átugrott, a P-256-nál például a 876. jelölt is megfelelő görbét adott volna. Hogy miért, azt nem tudni. Az Anthropic szerint az átugrott jelöltek kis száma miatt nem valószínű, hogy szándékosan gyengített görbét választottak.

Mit mond a díj kitűzője?

Filippo Valsorda megerősítette, hogy az Anthropic csapata október 15-én hajnalban bejelentkezett a teljes díjért. Ellenőrzésképp ő maga Go-ban újraírta az algoritmust. Szerinte az eredmény teljesen kizárja azt a Bernstein és Lange által 2017-ben leírt technikát, amellyel egy szándékosan gyenge görbét lehetett volna kiválasztani. Ha az NSA bármelyik 1997-es vagy 1998-as időbélyeget és az első 16 jelölt bármelyikét választhatta volna, akkor is alig 30 bitnyi mozgástere lett volna, ez kevés egy hátsó ajtóhoz (Filippo Valsorda).

Valsorda szerint ezzel a NIST-görbék „rehabilitációja” teljes, ő maga már ezeket ajánlaná a Curve25519 helyett. Azt is hozzáteszi: éppen akkor, amikor a poszt-kvantum aláírások miatt nyugdíjazni kezdik őket.

A 36 864 dolláros díjat az Anthropic az Internet Security Research Groupnak, a Let's Encrypt fenntartójának adományozta.