Anthropic Claude atrisinājis 25 gadus vecu mīklu par NIST eliptisko līkņu sēklām

Anthropic pētnieki ziņo, ka uzņēmuma iekšējais MI modelis Claude mazāk nekā 30 minūtēs atrisinājis gadu desmitiem neatbildētu jautājumu kriptogrāfijā: no kurienes nāk NIST standartā iekļauto eliptisko līkņu sēklas. Modelis noskaidroja, ka tās nav SHA-1 jaukums no kādas humora frāzes, kā ilgstoši tika pieņemts, bet gan vecās C bibliotēkas pseidonejaušo skaitļu ģeneratora lrand48 izvade, kas inicializēta ar Unix laika zīmogiem no 1997. un 1998. gada.

NIST 2000. gadā FIPS 186-2 standartā pieņēma līknes, kuru parametrus ANSI X9.62 metode atvasina no sēklas. Sēklas bija publiskas, taču Nacionālā drošības aģentūra (NSA), kas tās nodeva, neizskaidroja to izcelsmi. Pēc Edvarda Snoudina atklājumiem par NSA mēģinājumiem vājināt kriptogrāfiskos standartus aizdomas par slēptu aizmugurējo durvju iespēju uzturēja arī plašāku sabiedrību.

Ilgstošā versija bija, ka NSA matemātiķis Džerijs Solinass sēklas ieguvis, aprēķinot jaukumu no angļu teikuma, kuru vēlāk aizmirsis. Solinass miris 2023. gadā, un meklējumi pēc frāzes bija bez rezultāta. 2023. gadā kriptogrāfs Filipo Valsorda un citi izsludināja balvu; Anthropic komanda to pieprasīja 2026. gada 15. oktobrī un 36 864 ASV dolāru summu ziedoja Internet Security Research Group, kas uztur Let’s Encrypt.

Claude pieņēma citu pieeju: meklēja, kādu 1990. gadu PRNG programmatūra varētu būt lietojusi. Modelis pamanīja, ka vairākām sēklām visu 32 bitu vārdu augšējie biti ir nulles — tipiska lrand48 pazīme, jo tas atdod tikai 48 bitu stāvokļa augšējos 31 bitus. Atjaunojot ģeneratora stāvokli un soļojot atpakaļ līdz srand48 inicializācijai, visas desmit pārbaudītās pirmskaitļu līkņu sēklas sakrita ar Unix laika zīmogiem no 1997. gada maija līdz 1998. gada aprīlim. Piemēram, plaši izmantotās P-256 sēkla ir 1842. kandidāts no skrējiena, kas sākts 1997. gada 16. augustā.

Anthropic uzsver, ka tas nav kriptogrāfisks uzbrukums un lietotājiem nekas nav jāmaina. Gluži pretēji — atklājums samazina iespēju, ka līknes tīši izvēlētas ar vājumu, jo tagad ikviens var atkārtot skaitļošanu. Valsorda, pārbaudījis algoritmu neatkarīgi Go valodā, raksta, ka atrastie brīvības biti ir pārāk mazi, lai iegultu speciālu aizmugurējo durvju mehānismu.

Daži jautājumi paliek atvērti: kāpēc dažas derīgas kandidātsēklas tika izlaistas, kā ģenerēti P-224, P-256, P-384 un P-521 bāzes punkti, un kāpēc B-163 binārā sēkla joprojām neatbilst atrastajam modelim. Tomēr galvenā mīkla par NIST pirmo līkņu sēklām ir atrisināta, un MI šoreiz darbojās kā pētniecības instruments, nevis kā drošības risks.