Post-kvantekryptografi – ny algoritme «borte på 60 minutter»

Vi har skrevet om PQC, en forkortelse for post-kvante kryptografi, flere ganger før.

I tilfelle du har gått glipp av all mediespenningen de siste årene om såkalt kvantedatabehandling...

…det er (hvis du vil unnskylde det noen eksperter sannsynligvis vil betrakte som en hensynsløs overforenkling) en måte å bygge dataenheter på som kan holde styr på flere mulige utfall av en beregning samtidig.

Med mye forsiktighet, og kanskje litt flaks, betyr dette at du kan skrive om noen typer algoritmer for å finne det riktige svaret, eller i det minste forkaste en hel rekke feil svar, uten å prøve og teste alle mulige utfall. en etter en.

To interessante kryptoanalytiske hastigheter er mulige ved å bruke en kvanteberegningsenhet, forutsatt at en passende kraftig og pålitelig en faktisk kan konstrueres:

• Grovers kvantesøkealgoritme. Vanligvis, hvis du ønsker å søke i et tilfeldig ordnet sett med svar for å se om ditt er på listen, forventer du å pløye gjennom hele listen, i verste fall, før du får et definitivt svar. For eksempel, hvis du ønsker å finne 128-biters AES-dekrypteringsnøkkelen for å dekryptere et dokument, må du søke i listen over alle mulige nøkler, fra kl. 000..001, ..2, ..3, og så videre, helt opp til FFF..FFF (16 bytes verdt FF), for å være sikker på å fullføre problemet. Med andre ord, du må budsjettere for å prøve alle 2¹²⁸ mulige nøkler før du enten finner den rette nøkkelen, eller fastslår at det ikke var en. Grovers algoritme, gitt en stor og kraftig nok kvantedatamaskin, hevder imidlertid å kunne fullføre den samme bragden med kvadratroten av den vanlige innsatsen, og dermed knekker koden, i teorien, på bare 2⁶⁴ prøver i stedet.
• Shors kvantefaktoriseringsalgoritme. Flere moderne krypteringsalgoritmer er avhengige av det faktum at å multiplisere to store primtall sammen kan gjøres raskt, mens det er så godt som umulig å dele produktet tilbake i de to tallene du startet med. For å få en følelse av dette, prøv å multiplisere 59×87 med penn-og-papir. Det kan ta et minutt eller så å få det ut (5133 er svaret), men det er ikke så vanskelig. Prøv nå den andre veien. Del for eksempel 4171 tilbake i de to faktorene. Mye vanskeligere! (Det er 43×97.) Tenk deg nå å gjøre dette med et tall som er 600 sifre langt. Løst sett står du fast med å prøve å dele det 600-sifrede tallet med alle mulige 300-sifrede primtall til du treffer jackpotten, eller finner at det ikke er et svar. Shors algoritme lover imidlertid å løse dette problemet med logaritmen av vanlig innsats. Derfor bør faktorisering av et antall 2048 binære sifre ta bare dobbelt så lang tid som å faktorisere et 1024-bits tall, ikke dobbelt så lang tid som å faktorisere et 2047-biters tall, noe som representerer en enorm hastighetsøkning.

Motvirke trusselen

Trusselen fra Grovers algoritme kan motvirkes ganske enkelt ved å øke størrelsen på tallene du bruker ved å kvadrere dem, noe som betyr å doble antall biter i din kryptografiske hash eller din symmetriske krypteringsnøkkel. (Med andre ord, hvis du synes SHA-256 er bra akkurat nå, vil bruk av SHA-512 i stedet gi et PQC-resistent alternativ.)

Men Shors algoritme kan ikke motvirkes så enkelt.

En offentlig nøkkel på 2048 biter vil trenge at størrelsen økes eksponentielt, ikke bare ved å kvadrere, slik at i stedet for en nøkkel på 2×2048=4096 biter, trenger du enten en ny nøkkel med den umulige størrelsen 2²⁰⁴⁸ biter...

…eller du må ta i bruk en helt ny type post-kvantekrypteringssystem som Shors algoritme ikke gjaldt.

Vel, det amerikanske standardiseringsorganet NIST har kjørt en PQC "konkurranse" siden slutten av 2017.

Prosessen har vært åpen for alle, med alle deltakere velkommen, alle algoritmer åpent publisert, og offentlig gransking ikke bare mulig, men aktivt oppmuntret:

Innkalling av forslag. [Stengt 2017-11-30]. […] Det er ment at de nye kryptografistandardene for offentlig nøkkel skal spesifisere en eller flere ekstra uklassifiserte, offentlig avslørte digital signaturer, kryptering med offentlig nøkkel og nøkkeletableringsalgoritmer som er tilgjengelig over hele verden, og som er i stand til å beskytte sensitiv myndighetsinformasjon langt inn i overskuelig fremtid, inkludert etter at kvantedatamaskiner kom.

Etter tre runder med innleveringer og diskusjoner, NIST annonsert, 2022-07-05, at den hadde valgt fire algoritmer som den betraktet som "standarder" med umiddelbar virkning, alle med herlig-klingende navn: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONog SPHINCS+.

Den første (CRYSTALS-KYBER) brukes som det som kalles a Nøkkelavtalemekanisme (KEM), der to ender av en offentlig kommunikasjonskanal sikkert lager en engangs privat krypteringsnøkkel for konfidensiell utveksling av data i en økt. (For å si det enkelt: snokere får bare strimlet kål, så de kan ikke avlytte samtalen.)

De tre andre algoritmene brukes til Digitale signaturer, hvorved du kan sikre at dataene du fikk ut på slutten samsvarer nøyaktig med det avsenderen la inn på den andre, og dermed forhindre tukling og sikre integritet. (For å si det enkelt: hvis noen prøver å ødelegge eller rote med dataene, får du vite det.)

Det trengs flere algoritmer

Samtidig med kunngjøringen av de nye standardene, kunngjorde NIST også en fjerde runde av konkurrentene, og presenterer ytterligere fire algoritmer som mulige alternative KEM-er. (Husk at vi i skrivende stund allerede har tre godkjente digitale signaturalgoritmer å velge mellom, men bare én offisiell KEM.)

Disse var: BIKE, Classic McEliece, HQC og SIKE.

Spennende nok McEliece algoritme ble oppfunnet helt tilbake på 1970-tallet av den amerikanske kryptografen Robert Mc Eliece, som døde i 2019, godt etter at NISTs konkurranse allerede var i gang.

Det fanget imidlertid aldri, fordi det krevde enorme mengder nøkkelmateriale sammenlignet med dagens populære alternativ, Diffie-Hellman-Merkle-algoritmen (DHM, eller noen ganger bare DH).

Dessverre er en av de tre runde fire algoritmene, nemlig SIKE, ser ut til å ha blitt sprukket.

I et hjernevridende papir med tittelen ET EFFEKTIV NØKKEPONTROLLANSgrep PÅ SIDH (PRELIMINÆR VERSJON), ser de belgiske kryptografene Wouter Castryk og Thomas Decru ut til å ha gitt noe av et dødelig slag mot SIKE-algoritmen

I tilfelle du lurer, er SIKE en forkortelse for Supersingular Isogeny Key Encapsulation, og SIDH står for Supersingular Isogeny Diffie-Hellman, en spesifikk bruk av SIKE-algoritme hvorved to ender av en kommunikasjonskanal utfører en DHM-lignende "kryptodance" for å utveksle en haug med offentlige data som lar hver ende utlede en privat verdi for å bruke som en engangs hemmelig krypteringsnøkkel.

Vi skal ikke prøve å forklare angrepet her; vi vil bare gjenta det avisen hevder, nemlig at:

Svært løst sagt inkluderer inndataene her de offentlige dataene levert av en av deltakerne i nøkkeletableringskrypteringen, sammen med de forhåndsbestemte (og derfor offentlig kjente) parameterne som brukes i prosessen.

Men utdataene som er hentet ut (informasjonen referert til som isogenien φ ovenfor) er ment å være den aldri avslørte delen av prosessen – den såkalte private nøkkelen.

Med andre ord, fra offentlig informasjon alene, slik som dataene som utveksles åpent under nøkkeloppsett, hevder kryptografene å kunne gjenopprette den private nøkkelen til en av deltakerne.

Og når du først kjenner min private nøkkel, kan du enkelt og uoppdagelig late som du er meg, så krypteringsprosessen blir brutt.

Tilsynelatende tar nøkkel-cracking-algoritmen omtrent en time å gjøre arbeidet sitt, ved å bruke bare en enkelt CPU-kjerne med den typen prosessorkraft du finner i en daglig bærbar datamaskin.

Det er mot SIKE-algoritmen når den er konfigurert til å møte nivå 1, NISTs grunnleggende krypteringssikkerhet.

Hva gjør jeg?

Ingenting!

(Det er de gode nyhetene.)

Som forfatterne av artikkelen antyder, etter å ha lagt merke til at resultatet deres fortsatt er foreløpig, "Med dagens tilstand ser SIDH ut til å være fullstendig brutt for enhver offentlig generert basiskurve."

(Det er den dårlige nyheten.)

Men gitt at SIKE-algoritmen ikke er offisielt godkjent ennå, kan den nå enten tilpasses for å hindre dette spesielle angrepet (noe som forfatterne innrømmer kan være mulig), eller ganske enkelt droppet helt.

Uansett hva som til slutt skjer med SIKE, er dette en utmerket påminnelse om hvorfor det er farlig å prøve å finne opp dine egne krypteringsalgoritmer.

Det er også et godt eksempel på hvorfor proprietære krypteringssystemer som er avhengige av hemmeligholdet til selve algoritmen å opprettholde sin sikkerhet er rett og slett uakseptabelt i 2022.

Hvis en PQC-algoritme som SIKE overlevde persual og sondering av eksperter fra hele verden i mer enn fem år, til tross for at den ble avslørt spesifikt slik at den kunne bli gjenstand for offentlig gransking ...

…da er det ingen grunn til å spørre deg selv hvor godt dine hjemmelagde, skjulte krypteringsalgoritmer sannsynligvis vil klare seg når de slippes ut i naturen!

---