Az internet titkosításának jelentős része a NIST elliptikus görbéire épül, de a görbék kiindulóértékeinek eredete negyedszázadon át rejtély maradt. Most kiderült, hogy egyszerű 1990-es évekbeli véletlenszám-generátorral, a gép órájáról indítva készültek. A megoldást az Anthropic egyik belső kutatási modellje, a Claude találta meg kevesebb mint fél óra alatt. A részleteket a cég Frontier Red Team csapata október 16-án tette közzé.
Miért volt gyanús 25 évig?
Az ECDSA a legelterjedtebb elliptikus görbés aláírási szabvány. A NIST 2000-ben, a FIPS 186-2 szabványban fogadta el, a hozzá tartozó P-192, P-224, P-256, P-384 és P-521 görbékkel. Ezek a weben használt tanúsítványok jelentős részét is védik. Minden görbéhez tartozik egy 160 bites „seed”, vagyis kiindulóérték, amelynek hash-éből a görbe egyik együtthatója származik. A seedeket az NSA adta át magyarázat nélkül. A P-256 seedje például ez: C49D3608 86E70493 6A6678E1 139D26B7 819F7E90.
Mivel senki nem tudta, honnan származnak, sokan gyanították, hogy az NSA szándékosan gyenge görbéket választhatott. A legismertebb magyarázat szerint Jerry Solinas, az NSA munkatársa egy tréfás mondat hash-éből állította elő őket, de a pontos mondatra már ő sem emlékezett. Solinas 2023-ban meghalt. Ugyanabban az évben Filippo Valsorda kriptográfus díjat tűzött ki a seedek megfejtésére: 12 288 dollárt, amely jótékony célra fordítva 36 864 dollárra nő.
Nem hash, hanem óraidő
Az Anthropic több munkatársa is a tréfás mondat nyomán kereste a megoldást, sikertelenül. Októberben egy kolléga a kiinduló tipp nélkül kérdezte meg a belső modellt. A Claude más irányból indult: azt feltételezte, hogy a görbéket generáló program egy 1990-es évekbeli C-könyvtár álvéletlenszám-generátorát (PRNG) használta. Ezek a generátorok annyira gyengék, hogy a kimenetük felismerhető.
A modell írt egy keresőprogramot, amely 34 generátor- és kimenetkombinációt vizsgált végig. Észrevette, hogy négy seedben mind a 20 darab 32 bites szó legfelső bitje nulla. Ennek véletlen esélye 1:5810, viszont pontosan erre számítani a C-könyvtár lrand48 függvényénél, amely 48 bites belső állapotának csak a felső 31 bitjét adja ki. A prímgörbék seedjeinél kevesebb bit maradt meg, ott a belső állapotot rácsredukciós módszerrel, az LLL-algoritmussal állította vissza. Az lrand48 visszafelé is ugyanolyan könnyen léptethető, mint előre, így a modell eljutott az indítóértékig. Ez mind a tíz prímgörbénél egy 1997 májusa és 1998 áprilisa közötti Unix-időbélyeg volt.
A generátor minden lépésben 20 bájtot adott, ez egy-egy jelölt seed. A P-256 a 1842. jelölt volt, egy 1997. augusztus 16-i, 01:52:34-es (UTC) időbélyegből. A négy bináris görbe indítóértéke 1984 februárjára esne, de az időt kétszerezve 1998. április 17. jön ki, két héttel a P-224 futása után. Az Anthropic szerint ezért a program valószínűleg megfelezte az óra értékét. A modell belső gondolatmenetében ez állt: „Ez elképesztő: megoldja a 25 éves rejtélyt.” Utána szkeptikusan azt is megvizsgálta, nem tesztkörnyezetben van-e, végül arra jutott, hogy a 160 bites egyezés nem lehet véletlen.
Mit jelent ez a biztonságra nézve?
Az Anthropic hangsúlyozza: „Ez nem kriptográfiai törés, nem új támadás és nem az ECDSA-görbék gyengesége. Sőt, ez még biztosabbá tesz minket abban, hogy a görbéket hátsó kapuk és szándékos gyengeségek nélkül választották ki.” Egy órával indított, bárki által reprodukálható generátor sokkal kevesebb mozgásteret hagy a manipulációra, mint egy ismeretlen eredetű érték. A témának az kölcsönöz aktualitást, hogy az Ethereum kutatói is az ECDSA-ra épülő tárcák jövőjén dolgoznak.
A modell ráadásként hat görbe alappontjának (base point) eredetét is megtalálta, köztük a P-192-ét. Ezek Arjen Lenstra FreeLIP nevű nagyszám-aritmetikai csomagjának véletlenszám-generátorából származnak, kis egész kezdőértékekkel (a P-192-nél 20000). Az Anthropic tudomása szerint NIST-alappont eredetét eddig senki nem magyarázta meg.
Nyitott kérdések
Néhány dolog továbbra is tisztázatlan. A P-256 futásában a 876. jelölt is megfelelő, prímrendű görbét adott volna, mégis az 1842. lett a szabvány. A P-224 futása három ilyen görbét ugrott át, az ANSI X9.62 példagörbéinél még hetet hagytak ki. Hogy ez milyen szempont alapján történt, nem tudni. Az Anthropic szerint a kihagyások száma túl kicsi ahhoz, hogy gyengített görbék kiválasztására utaljon. A B-163 bináris görbe seedjét a modell nem tudta visszafejteni, és a P-224, P-256, P-384 és P-521 alappontjainak eredete is ismeretlen maradt.
A 36 864 dolláros díjat az Anthropic az Internet Security Research Groupnak, a Let’s Encrypt üzemeltetőjének adományozza. A reprodukáláshoz szükséges Python-kódot a cég közkincsként (CC0) tette közzé. Az eset arra is jó példa, hogy a modellek önálló kutatómunkája nem mindig ilyen ártalmatlan: az Anthropic korábban arról is beszámolt, hogy a Claude-modellek teszteken valódi oldalakon kerültek meg korlátokat.
