Post-kvantekryptografi - ny algoritme "forsvundet på 60 minutter"

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

Hvis du er gået glip af al mediespændingen fra de sidste par år om såkaldt kvantecomputere...

…det er (hvis du vil undskylde, hvad nogle eksperter sandsynligvis vil betragte som en hensynsløs overforenkling) en måde at bygge computerenheder på, som kan holde styr på flere mulige udfald af en beregning på samme tid.

Med stor omhu og måske lidt held betyder det, at du kan omskrive nogle typer algoritmer for at finde det rigtige svar, eller i det mindste korrekt kassere en hel række forkerte svar uden at prøve og teste alle mulige resultater en efter en.

To interessante kryptoanalytiske speedups er mulige ved brug af en kvantecomputerenhed, forudsat at en passende kraftfuld og pålidelig en faktisk kan konstrueres:

• Grovers kvantesøgningsalgoritme. Normalt, hvis du vil søge i et tilfældigt ordnet sæt af svar for at se, om dit er på listen, ville du forvente at pløje hele listen igennem, i værste fald, før du får et endeligt svar. Hvis du f.eks. ønskede at finde 128-bit AES-dekrypteringsnøglen for at afkode et dokument, skal du søge på listen over alle mulige nøgler, startende kl. 000..001, ..2, ..3, og så videre, helt op til FFF..FFF (16 bytes værdi af FF), for at være sikker på at løse problemet. Med andre ord, du skal have budget for at prøve alle 2¹²⁸ mulige nøgler, før du enten finder den rigtige nøgle eller fastslår, at der ikke var en. Grovers algoritme, givet en stor og kraftig nok kvantecomputer, hævder dog at være i stand til at fuldføre den samme bedrift med kvadrat rod af den sædvanlige indsats, og knækker dermed koden, i teorien, på kun 2⁶⁴ forsøger i stedet.
• Shors kvantefaktoriseringsalgoritme. Flere nutidige krypteringsalgoritmer er afhængige af det faktum, at gange to store primtal sammen kan gøres hurtigt, hvorimod det er så godt som umuligt at dele deres produkt tilbage i de to tal, som du startede med. For at få en fornemmelse af dette, prøv at gange 59×87 ved hjælp af pen-og-papir. Det kan tage et minut eller deromkring at få det ud (5133 er svaret), men det er ikke så svært. Prøv nu den anden vej. Del f.eks. 4171 tilbage i sine to faktorer. Meget sværere! (Det er 43×97.) Forestil dig nu at gøre dette med et tal, der er 600 cifre langt. Løst sagt sidder du fast med at forsøge at dividere det 600-cifrede tal med alle mulige 300-cifrede primtal, indtil du rammer jackpotten, eller finder ud af, at der ikke er et svar. Shor's algoritme lover dog at løse dette problem med logaritme af den sædvanlige indsats. Faktorering af et antal på 2048 binære cifre bør derfor tage bare dobbelt så lang tid som faktorisering af et 1024-bit tal, ikke dobbelt så lang tid som faktorisering af et 2047-bit tal, hvilket repræsenterer en enorm speedup.

Imødegå truslen

Truslen fra Grovers algoritme kan imødegås blot ved at øge størrelsen af ​​de tal, du bruger, ved at kvadrere dem, hvilket betyder at fordoble antallet af bits i din kryptografiske hash eller din symmetriske krypteringsnøgle. (Med andre ord, hvis du synes, at SHA-256 er i orden lige nu, vil brug af SHA-512 i stedet give et PQC-resistent alternativ.)

Men Shors algoritme kan ikke imødegås helt så let.

En offentlig nøgle på 2048 bit ville have brug for, at dens størrelse øges eksponentielt, ikke blot ved at kvadrere, så i stedet for en nøgle på 2×2048=4096 bit, ville du enten have brug for en ny nøgle med den umulige størrelse på 2²⁰⁴⁸ bidder…

…eller du bliver nødt til at adoptere en helt ny slags post-kvantekrypteringssystem, som Shors algoritme ikke gjaldt for.

Nå, det amerikanske standardiseringsorgan NIST har kørt en PQC "konkurrence" siden slutningen af ​​2017.

Processen har været åben for alle, med alle deltagere velkomne, alle algoritmer åbenlyst offentliggjort, og offentlig kontrol er ikke kun mulig, men aktivt opmuntret:

Indkaldelse af forslag. [Lukket 2017-11-30]. […] Det er meningen, at de nye kryptografistandarder med offentlig nøgle skal specificere en eller flere yderligere uklassificerede, offentligt offentliggjorte digital signaturer, kryptering af offentlige nøgler og nøgleetableringsalgoritmer, der er tilgængelige over hele verden og er i stand til at beskytte følsomme regeringsoplysninger langt ud i en overskuelig fremtid, herunder efter kvantecomputernes indtog.

Efter tre runder af indlæg og diskussioner, NIST annonceret2022-07-05, at den havde valgt fire algoritmer, som den betragtede som "standarder" med øjeblikkelig virkning, alle med dejligt klingende navne: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONog SPHINCS+.

Den første (CRYSTALS-KYBER) bruges som det, der kaldes en Nøgleaftalemekanisme (KEM), hvor to ender af en offentlig kommunikationskanal sikkert sammensætter en engangs privat krypteringsnøgle til fortrolig udveksling af en sessions værdi af data. (Kort fortalt: snokere får bare revet kål, så de kan ikke aflytte samtalen.)

De tre andre algoritmer bruges til Digitale signaturer, hvorved du kan sikre dig, at de data, du fik ud i din ende, matcher nøjagtigt, hvad afsenderen har lagt ind hos den anden, og dermed forhindre manipulation og sikre integritet. (Kort fortalt: hvis nogen forsøger at korrumpere eller rode med dataene, ved du det.)

Der er brug for flere algoritmer

Samtidig med annonceringen af ​​de nye standarder annoncerede NIST også en fjerde runde af sin konkurrence, og fremlægger yderligere fire algoritmer som mulige alternative KEM'er. (Husk, at vi i skrivende stund allerede har tre godkendte digitale signaturalgoritmer at vælge imellem, men kun én officiel KEM.)

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

Spændende nok McEliece algoritme blev opfundet helt tilbage i 1970'erne af den amerikanske kryptograf Robert Mc Eliece, der døde i 2019, længe efter at NISTs konkurrence allerede var i gang.

Det fangede dog aldrig, fordi det krævede enorme mængder nøglemateriale sammenlignet med datidens populære alternativ, Diffie-Hellman-Merkle-algoritmen (DHM, eller nogle gange bare DH).

Desværre er en af ​​de tre runde fire algoritmer, nemlig SIKE, ser ud til at være revnet.

I et hjernevridende papir med titlen ET EFFEKTIV NØGLEGENDANNELSE ANGREP PÅ SIDH (PRELIMINÆR VERSION), ser de belgiske kryptografer Wouter Casttryk og Thomas Decru ud til at have givet SIKE-algoritmen noget af et dødbringende slag.

Hvis du undrer dig, er SIKE en forkortelse for Supersingular Isogeny Key Encapsulation, og SIDH står for Supersingular isogeni Diffie-Hellman, en specifik brug af SIKE algoritme hvorved to ender af en kommunikationskanal udfører en DHM-lignende "cryptodance" for at udveksle en masse offentlige data, der tillader hver ende at udlede en privat værdi til at bruge som en engangs hemmelig krypteringsnøgle.

Vi vil ikke forsøge at forklare angrebet her; vi vil bare gentage, hvad avisen hævder, nemlig at:

Meget løst sagt inkluderer inputs her de offentlige data leveret af en af ​​deltagerne i nøgleetableringskryptodancen sammen med de forudbestemte (og derfor offentligt kendte) parametre, der bruges i processen.

Men det output, der er udtrukket (informationen, der omtales som isogenien φ ovenfor) formodes at være den aldrig afslørede del af processen - den såkaldte private nøgle.

Med andre ord, fra offentlig information alene, såsom de data, der udveksles åbent under nøgleopsætning, hævder kryptograferne at være i stand til at gendanne den private nøgle fra en af ​​deltagerne.

Og når du kender min private nøgle, kan du nemt og uopdageligt foregive at være mig, så krypteringsprocessen er brudt.

Tilsyneladende tager key-cracking-algoritmen omkring en time at udføre sit arbejde, idet den kun bruger en enkelt CPU-kerne med den slags processorkraft, du finder i en daglig bærbar computer.

Det er imod SIKE-algoritmen, når den er konfigureret til at opfylde niveau 1, NISTs grundlæggende krypteringssikkerhed.

Hvad skal jeg gøre?

Intet!

(Det er den gode nyhed.)

Som forfatterne af papiret foreslår, efter at have bemærket, at deres resultat stadig er foreløbigt, "Med den nuværende situation ser SIDH ud til at være fuldstændig brudt for enhver offentligt genereret basiskurve."

(Det er den dårlige nyhed.)

Men i betragtning af at SIKE-algoritmen ikke er officielt godkendt endnu, kan den nu enten tilpasses til at modarbejde dette særlige angreb (noget som forfatterne indrømmer kan være muligt), eller simpelthen droppes helt.

Uanset hvad der til sidst sker med SIKE, er dette en fremragende påmindelse om, hvorfor det er forbundet med fare at forsøge at opfinde dine egne krypteringsalgoritmer.

Det er også et spidst eksempel på, hvorfor proprietære krypteringssystemer der er afhængige af hemmeligholdelsen af ​​selve algoritmen at opretholde deres sikkerhed er simpelthen uacceptable i 2022.

Hvis en PQC-algoritme som SIKE overlevede persual og sondering af eksperter fra hele verden i mere end fem år, på trods af at den blev afsløret specifikt, så den kunne blive underkastet offentlig kontrol...

…så er der ingen grund til at spørge dig selv, hvor godt dine hjemmelavede, skjulte krypteringsalgoritmer sandsynligvis vil klare sig, når de slippes ud i naturen!

---