Anthropic kertoi perjantaina, että sen Claude-malli on selvittänyt yhden kryptografian sitkeimmistä arvoituksista. Kyse on NIST:n standardoimien elliptisten käyrien siemenarvoista, joiden alkuperä on ollut tuntematon lähes 30 vuotta. Vastaus osoittautui arkiseksi: siemenet ovat 1990-luvun C-kirjaston satunnaislukugeneraattorin tulosteita, ja generaattori alustettiin Unix-aikaleimalla.
Löytö ei murra mitään salausta. Se sen sijaan hälventää vuosia jatkuneet epäilyt siitä, että Yhdysvaltain kansallinen turvallisuusvirasto NSA olisi upottanut käyriin takaportin. Anthropicin tutkimusblogin mukaan sisäinen tutkimusmalli löysi ratkaisun alle puolessa tunnissa.
Lähes 30 vuotta vanha kysymys
ECDSA on maailman käytetyin elliptisiin käyriin perustuva allekirjoitusstandardi. NIST hyväksyi sen vuonna 2000 osana FIPS 186-2 -standardia, joka määrittelee joukon valmiita käyriä eri turvallisuustasoille. Jokaisen käyrän kerroin johdettiin julkaistusta siemenarvosta tiivistefunktion avulla.
Ongelma oli siemenissä itsessään. NSA toimitti ne ilman mitään selitystä siitä, miten ne oli valittu. Esimerkiksi laajasti käytetyn P-256-käyrän siemen on pelkkä 20 tavun heksadesimaalijono, jolle ei ollut annettu perustetta.
Selittämättömät vakiot herättivät kryptografiyhteisössä epäluuloa, varsinkin Dual_EC_DRBG-skandaalin jälkeen. Pitkäaikainen NSA-työntekijä Jerry Solinas muisteli vuonna 2015, että siemenet syntyivät leikkisän tunnuslauseen tiivisteestä. Solinas kuoli vuonna 2023, eikä lausetta koskaan löytynyt. Siementen löytäjälle luvattiin lopulta 36 864 dollarin palkkio.
Arvoitusta selvittivät vuosien mittaan sekä tutkijat että harrastajat. Kryptografit Neal Koblitz ja Alfred Menezes kokosivat kiistan historian laajaan katsaukseen, ja Filippo Valsorda järjesti siemenille julkisen palkkiokilpailun. Kukaan ei silti onnistunut toistamaan arvoja, koska kaikki etsivät väärää asiaa: tunnuslausetta.
Kellonaika paljasti generaattorin
Useat Anthropicin työntekijät olivat jahdanneet tunnuslausetta tuloksetta. Lokakuussa yksi heistä kysyi sisäiseltä tutkimusmallilta, pystyisikö se selvittämään siementen synnyn ilman vihjettä. Claude lähestyi ongelmaa toisesta suunnasta ja arvioi, millaista ohjelmistoa käyrien luojat olivat 1990-luvulla todennäköisesti käyttäneet.
Malli kirjoitti skannerin, joka testasi, olivatko siementen peräkkäiset osat vanhan näennäissatunnaislukugeneraattorin peräkkäisiä tulosteita. Neljässä siemenessä jokaisen 32-bittisen sanan ylin bitti oli nolla. Sattumalta näin käy noin kerran 5 810 tapauksesta, ja kuvio on tyypillinen lrand48-funktiolle, joka palauttaa vain 31 bittiä 48-bittisestä tilastaan.
Alkulukukäyrien siemenistä generaattorin tila jouduttiin palauttamaan katkaistuista biteistä. Claude ratkaisi tämän hilan perusteiden redusointiin perustuvalla LLL-algoritmilla, joka on tunnettu työkalu juuri tällaisiin tehtäviin. Kun tila oli löytynyt, generaattoria voitiin ajaa taaksepäin alkuarvoon asti.
Kaikkien kymmenen alkulukukäyrän alkuarvot osoittautuivat Unix-aikaleimoiksi toukokuun 1997 ja huhtikuun 1998 väliltä. P-256-käyrän siemen syntyi elokuussa 1997, ja kelvollinen ehdokas löytyi 1 842. kierroksella.
Myös osa tukipisteistä selvisi
Siementen lisäksi jokaisella käyrällä on kiinteä tukipiste, jonka monikerta jokainen ECDSA-julkinen avain on. Claude selvitti kuuden toukokuussa 1997 luodun käyrän tukipisteiden alkuperän. Ne tulivat Arjen Lenstran FreeLIP-kirjaston satunnaislukugeneraattorista, joka alustettiin pienellä kokonaisluvulla, kuten P-192:n tapauksessa luvulla 20000.
Anthropicin mukaan yhtäkään NIST:n tukipistettä ei ole aiemmin pystytty selittämään. P-224-, P-256-, P-384- ja P-521-käyrien tukipisteet eivät kuitenkaan noudata samaa reseptiä, ja niiden alkuperä on yhä auki.
Avoimia kysymyksiä jäi muitakin. Yhden binäärikäyrän, B-163:n, siemen ei vastaa mitään kokeiltua mallia. Lisäksi käyrien luojat ohittivat muutamia kelvollisia ehdokkaita, esimerkiksi P-256:n kohdalla ehdokkaan 876, eikä valintaperustetta tunneta.
Anthropicin tutkijat julkaisivat myös lyhyen Python-ohjelman, jolla kuka tahansa voi tuottaa siemenet uudelleen pelkistä aikaleimoista ja kierrosnumeroista. Jokainen palautettu 48-bittinen tila tuottaa kaikki siemenen 160 bittiä, mikä ei voi tapahtua sattumalta.
Mitä löytö tarkoittaa tietoturvalle
Anthropic korostaa, ettei kyse ole hyökkäyksestä tai heikkoudesta. Löytö päinvastoin vahvistaa luottamusta käyriin. Kun siemenet syntyivät tavallisella generaattorilla kellonajasta, tilaa tarkoitukselliselle manipuloinnille jää hyvin vähän, ja kuka tahansa voi nyt toistaa laskennan.
Ohitettujen ehdokkaiden pieni määrä ei yhtiön mukaan viittaa heikennettyjen käyrien valintaan. Sellainen edellyttäisi, että heikot käyrät olisivat yleisiä ja helppoja löytää. Käyttäjien tai ylläpitäjien ei siis tarvitse muuttaa mitään.
Tapaus näyttää myös, miten kielimallit soveltuvat tutkimustyöhön. Claude yhdisti ohjelmistohistoriaa, tilastollista päättelyä ja hila-algoritmeja ongelmaan, jota ihmiset olivat yrittäneet ratkaista väärän vihjeen varassa vuosia. Anthropic lahjoittaa 36 864 dollarin palkkion Let's Encryptiä ylläpitävälle Internet Security Research Groupille.
Yhteenveto
Claude selvitti, että NIST:n ECDSA-käyrien siemenet ovat lrand48-generaattorin tulosteita, jotka alustettiin vuosien 1997 ja 1998 aikaleimoilla. Löytö ei heikennä salausta vaan vahvistaa, ettei käyriin ole piilotettu takaporttia.
Osa arvoituksesta jäi edelleen auki. Neljän yleisimmän alkulukukäyrän tukipisteet ja B-163-käyrän siemen odottavat yhä selitystä.