AI-ja zgjidh misterin 25-vjeçar të një numri të NSA-së

Një model i inteligjencës artificiale antropike ka zbuluar një nga misteret më jetëgjata të kriptografisë, duke gjurmuar numrat që NSA ia dorëzoi qeverisë amerikane në fund të viteve 1990, të cilët dyshohej prej kohësh se fshihnin një derë të pasme, drejt një programi të zakonshëm numrash të rastësishëm të ushqyer me pulla kohore nga viti 1997 dhe 1998.

Modelit i duhej vetëm rreth gjysmë ore për të gjetur një zgjidhje — një zgjidhje që kriptografët e kishin kërkuar për 25 vjet.

Pjesa më e madhe e internetit mbështetet në kriptografinë me kurbë eliptike, familja e matematikës që përdoret gjithashtu për të mbrojtur portofolet bitcoin. Kjo i lejon dikujt të provojë se mban një çelës sekret pa zbuluar detajet e vetë çelësit.

Mendojeni kurbën si një dizajn bravash që kushdo mund ta inspektojë. Çdo person që e përdor atë ka çelësin e vet sekret, por të gjithë mbështeten në vështirësinë e thyerjes së dizajnit.

Por kush e zgjodhi matematikën që të gjithë do t’i besonin?

Në vitin 2000, Instituti Kombëtar i Standardeve dhe Teknologjisë i SHBA-së, ose NIST, miratoi një sërë kurbash të ofruara nga Agjencia e Sigurisë Kombëtare. NSA i ofroi këto dizajne pa shpjeguar se nga vinin disa nga numrat e përdorur për t’i gjeneruar ato.

Sekreti u bë edhe më i vështirë për t’u shpërfillur pasi zbulimet e Snowden e lidhën NSA-në me përpjekjet për të dobësuar standardet kriptografike. Më vonë, NIST e hoqi atë mjet , gjeneratorin e numrave të rastësishëm Dual EC, nga rekomandimet e tij.

Ato numra fillestarë, të quajtur “fara”, ishin publikë. Por NSA nuk shpjegoi kurrë se si i zgjodhi ato, duke nxitur vite me radhë dyshime se kishte testuar shumë alternativa derisa gjeti një kurbë me një dobësi që vetëm ajo dinte ta shfrytëzonte. Teoria e aluminit ishte se NSA kishte një derë të pasme për çdo sistem që e përdorte atë.

Kriptografët Neal Koblitz dhe Alfred Menezes e shqyrtuan këtë polemikë në punimin e tyre të vitit 2015, “Një gjëegjëzë e mbështjellë me një enigmë”. Menezes kishte ndihmuar në shkrimin e standardit origjinal dhe kujtoi se i kishte marrë farat nga matematikani i NSA-së, Jerry Solinas, në vitin 1997.

Studiuesi i sigurisë Steve Weis kaloi vite duke kërkuar një shpjegim, duke përfshirë edhe paraqitjen e kërkesave për të dhëna publike në vitin 2018. NIST tha se nuk kishte dokumentacion, ndërsa NSA pushoi së përgjigjuri. Një pistë premtuese sugjeroi se numrat vinin nga një frazë humoristike që Solinas e kishte harruar, duke i detyruar hetuesit të kërkonin kombinime të mundshme fjalësh.

Në vitin 2023, inxhinieri i kriptografisë Filippo Valsorda dhe kontribues të tjerë ofruan një shpërblim prej 12,288 dollarësh për një përgjigje, që shkonte në mbi 36,000 dollarë nëse fituesi e dhuronte atë për bamirësi. Solinas kishte vdekur më herët atë vit, duke i lënë studiuesit të punonin me kujtimet e vjetra dhe vetë numrat, por pa asnjë rezultat.

Derisa në skenë hyri Claude. Këtë muaj, një punonjës i Anthropic i kërkoi një modeli të brendshëm kërkimor të hetonte, pa ndarë teorinë e vjetër se farat vinin nga një frazë e harruar.

Modelit i duhej më pak se gjysmë ore për të gjurmuar pesë fillesa të kurbës NIST deri te lrand48, një gjenerator numrash të rastësishëm që gjendet në bibliotekat më të vjetra të softuerëve C.

Claude riprodhoi sekuencën pas P-256, një kurbë e përdorur gjerësisht, dhe gjeti një përputhje të saktë për farën e saj të botuar në kandidatin e 1,842-të.

“Kjo është e habitshme: zgjidh misterin 25-vjeçar”, shkroi modeli në arsyetimin e tij të regjistruar, pasi vuri shkurt në pikëpyetje nëse po funksiononte brenda një testi të simuluar. “Hmm, a është e besueshme në realitet? Sipas njohurive të mia… shpërblimi ishte i pazgjidhur. … Të gjitha pjesët kryesore të qarta – 20 pjesë, shansi 1e-6. Pra, me të vërtetë në botën reale.”

“Uau, është një zbulim i vërtetë.”

Kushdo tani mund ta riekzekutojë programin dhe të marrë numrat që NSA ka dhënë. Anthropic thotë se kjo e bën një dobësi të fshehur shumë më pak të mundshme, megjithëse ekipi ende nuk mund të shpjegojë pse programi i ka anashkaluar disa kandidatë të përdorshëm ose si janë zgjedhur pjesë të tjera të kurbave.

Kjo parashikueshmëri është ajo që e lejoi Claude të rindërtonte numrat, dhe kjo do të ishte një katastrofë brenda një portofoli. Një çelës sekret i gjeneruar me lrand48 mund të rikrijohej nga kushdo që e llogariste përafërsisht kohën kur u krijua, duke u dhënë atyre gjithçka që nevojitej për të harxhuar fondet.

Farat e NSA-së ishin publike që nga dita e parë, kështu që nuk kishte kurrë ndonjë sekret për t’u vjedhur.

Bitcoin nuk ishte kurrë pjesë e kësaj loje me hamendje. Portofolet e tij funksionojnë në secp256k1, një kurbë e ndërtuar nga një ekuacion më i thjeshtë.

Versioni i Bitcoin përcaktohet nga dy numra të vegjël, të fiksuar që nuk lënë pothuajse asgjë për t’u rregulluar, ndërsa versioni i P-256 mbart një numër 77-shifror që doli nga burimi i pashpjegueshëm i NSA-së.

Me kaq pak kthesa për të kthyer, ka pak hapësirë ​​që dikush të ketë ndërtuar në heshtje një dobësi në kurbën e bitcoin, dhe kriptografët e kanë theksuar prej kohësh këtë si një pikë në favor të tij.

Krijuesi Satoshi Nakamoto nuk e shpjegoi kurrë publikisht pse e zgjodhi atë, dhe kurba përdorej rrallë përpara se bitcoin ta bënte të famshëm. Ethereum më vonë e adoptoi edhe atë, dhe bitcoin e mbajti atë kur përditësimi i tij Taproot në vitin 2021 prezantoi një stil më të ri nënshkrimi.

Një kompjuter kuantik i fuqishëm do të sillte një rrezik të ndryshëm, siç e eksploroi CoinDesk më parë këtë vit. Ai mund të punonte prapa nga një çelës publik i dukshëm në blockchain-in e Bitcoin-it te çelësi sekret pas tij, pavarësisht se si është zgjedhur kurba.

Përparimet në harduer vazhdojnë ta ngushtojnë hendekun midis kësaj teorie dhe një sulmi funksional. Google tha këtë javë se çipi i saj Willow i redukton gabimet rreth 40-fish, në një nga hapat më të kushtueshëm që do të nevojiteshin për një makinë të tillë.

Megjithatë, askush nuk ka ndërtuar ende një kompjuter kuantik aq të madh ose të besueshëm sa për të deshifruar një çelës bitcoin, dhe nuk ka një afat kohor të qartë se kur mund të dalë një i tillë.

Ndërkohë, Anthropic tha në blogun e tij se njerëzit që përdorin kurbat NIST nuk kanë nevojë të ndryshojnë asgjë. Pas dekadash pyetjesh rreth origjinës së farave, kushdo tani mund ta ekzekutojë programin dhe të rikthehet në rrugën e tij deri te numrat e publikuar.

Kërkimi kishte edhe një çmim. Shpërblimi prej 36,864 dollarësh do t’i shkojë Grupit të Kërkimit të Sigurisë në Internet, organizatës jofitimprurëse që qëndron pas Let’s Encrypt, e cila u jep faqeve të internetit certifikata sigurie falas.