To resultater mot en pensjonert nøkkellengde

Google DeepMind la fredag fram to kryptoanalyseresultater som laben sier ble laget av KI-agenter under menneskelig tilsyn, begge mot 1024-bits RSA — en nøkkellengde som er ute av moderne praksis og som forskere holder på som en trygg øvingsbane. Laben skrev at systemene “kan knekkes med et lavere beregningsbudsjett enn man tidligere trodde var mulig”.

Meldingen kom fra Pushmeet Kohli, sjefforsker i Google Cloud og visedirektør i DeepMind, som skrev at resultatene ble ledet av Dj Dvijotham og Abhradeep Thakurta i samarbeid med Nadia Heninger ved UC San Diego og Inria og Emmanuel Thomé ved Inria. To tekniske rapporter ble lagt fram samtidig.

DeepMinds egen innramming handler om fart, ikke om et gjennombrudd i å knekke kryptering. Framskritt av dette slaget har historisk tatt år eller tiår, skriver laben, noe som lot forsvarere gå ut fra at vanskelighetsmarginene under RSA flyttet seg langsomt. Selskapets påstand er at et agentsystem presset arbeidet ned til uker.

Utfyllingen hjelper ikke når angriperen styrer halve blokken

Det første resultatet gjelder digitale signaturer — mekanismen som lar en datamaskin kontrollere at en programvareoppdatering eller et dokument virkelig kommer fra den oppgitte kilden. Før signering fyller mange standarder ut meldingen til en blokk av fast størrelse. Kryptografer visste at utfylling gjør forfalskning vanskeligere; det de manglet, var et mål på hvor mye vern den gir når en angriper kan mate valgte inndata inn i en signeringsenhet.

Etter DeepMinds framstilling er det avgjørende hvor stor del av den signerte blokken angriperen styrer. Når den andelen når omtrent halvparten eller mer, sier selskapet, gir utfyllingen ikke noe vern i det hele tatt, og å forfalske en signatur blir like utsatt for matematiske snarveier som å signere helt uten utfylling.

En rad serverskap i en gang i et datasenter
Angrepet ble kjørt i en avskjermet simulering, ikke mot systemer i drift. Illustrerende arkivbilde. Brett Sayles · pexels · Pexels License

Teamet prøvde påstanden i en avskjermet simulering, ikke mot systemer i drift. På en allerede løst 1024-bits referansenøkkel fra en tidligere akademisk studie sier DeepMind at agentene bygde en implementasjon som gjenskapte resultatet med 3,5 ganger mindre prosessortid, og med mindre enn en tusendel av regnekraften som trengs for å knekke selve nøkkelen. Når angriperen styrer en mindre del av blokken — for eksempel et kort 32-bytes sammendrag — er forfalskning vanskeligere, men laben sier den fant en ny algoritme som forbedrer den forrige beste metoden med rundt 1 600 ganger for 1024-bits nøkler. Tallet er et teoretisk anslag, ikke en målt kjøring.

En rimeligere nøkkel nummer to, og en rimeligere nummer tre

Det andre resultatet handler om å faktorisere mange tall av samme størrelse, noe som betyr noe for RSA fordi nøkler gis ut i standardiserte bitlengder. Den som angriper mange nøkler samtidig, kan i prinsippet fordele én stor innledende beregning over alle. DeepMind sier agentene fant en algoritme med bedre asymptotisk kompleksitet enn kjente satsvise metoder, noe som kutter gjennomsnittskostnaden for hver ekstra 1024-bits nøkkel med rundt 30 ganger.

Begge tallene er labens egne, og ingen av rapportene er fagfellevurdert. Samarbeidet omfatter likevel to av dem som har kjørt feltets rekordfaktoriseringer: Heninger og Thomé var med i teamet som faktoriserte RSA-240 og RSA-250.

Nettverkskabler koblet til et patchpanel
Moderne protokoller bruker nøkler på 2048 bit eller mer, sier DeepMind. Illustrerende arkivbilde. Brett Sayles · pexels · Pexels License

Hva det ikke betyr

Ingenting av dette rører krypteringen i vanlig bruk. DeepMind sier at resultatene bare gjelder utdatert 1024-bits RSA, og at moderne protokoller, som nesten alltid bruker nøkler på 2048 bit eller mer, fortsatt er sikre. Labens oppgitte grunn til å publisere er at sikkerhetsmiljøet skal kunne bruke innsikten til å måle kryptografisk styrke og holde standardene foran trusselen.

Det større argumentet er at beregningsmessig vanskelighet ikke lenger kan behandles som en fast forutsetning som forvitrer etter en forutsigbar plan. Hvis et agentsystem kan sondere en slik forutsetning på uker, krymper avstanden mellom et teoretisk og et praktisk framskritt — for forsvarere like mye som for angripere.

Det som er verdt å følge, er om uavhengige kryptoanalytikere gjenskaper de to algoritmene, og særlig om anslaget på 1 600 ganger holder når det møter en implementasjon. Begge rapportene er offentlige, så det arbeidet kan starte med en gang.