Postkvantkryptografi – ny algoritm "borta på 60 minuter"

Vi har skrivit om PQC, förkortning för post-kvantkryptografi, flera gånger tidigare.

Om du har missat all mediaspänning de senaste åren om så kallad kvantberäkning...

…det är (om du ursäktar vad vissa experter förmodligen kommer att betrakta som en hänsynslös överförenkling) ett sätt att bygga datorenheter som kan hålla reda på flera möjliga resultat av en beräkning samtidigt.

Med mycket omsorg, och kanske lite tur, betyder detta att du kan skriva om vissa typer av algoritmer för att komma in på rätt svar, eller åtminstone korrekt kassera en hel radda felaktiga svar, utan att försöka testa alla möjliga resultat en och en.

Två intressanta kryptoanalytiska hastigheter är möjliga med hjälp av en kvantberäkningsenhet, förutsatt att en lämpligt kraftfull och pålitlig sådan faktiskt kan konstrueras:

• Grovers kvantsökningsalgoritm. Vanligtvis, om du vill söka i en slumpmässigt ordnad uppsättning svar för att se om ditt finns på listan, förväntar du dig att plöja igenom hela listan, i värsta fall, innan du får ett definitivt svar. Om du till exempel vill hitta 128-bitars AES-dekrypteringsnyckeln för att avkoda ett dokument, måste du söka i listan med alla möjliga nycklar, med början kl. 000..001, ..2, ..3, och så vidare, ända upp till FFF..FFF (värde för 16 bytes FF), för att vara säker på att problemet slutförs. Med andra ord, du måste ha budget för att prova alla 2¹²⁸ möjliga nycklar innan man antingen hittade rätt nyckel eller fastställde att det inte fanns någon. Grovers algoritm, med tanke på en tillräckligt stor och kraftfull kvantdator, gör anspråk på att kunna slutföra samma bedrift med roten ur av den vanliga ansträngningen, och knäcker därmed koden, i teorin, på bara 2⁶⁴ försöker istället.
• Shors kvantfaktoriseringsalgoritm. Flera samtida krypteringsalgoritmer förlitar sig på det faktum att multiplicera två stora primtal tillsammans kan göras snabbt, medan det är så gott som omöjligt att dela upp sin produkt i de två talen som du började med. För att få en känsla för detta, prova att multiplicera 59×87 med penna och papper. Det kan ta någon minut eller så att få ut det (5133 är svaret), men det är inte så svårt. Försök nu åt andra hållet. Dela, säg, 4171 tillbaka i dess två faktorer. Mycket svårare! (Det är 43×97.) Föreställ dig nu att du gör det här med ett tal som är 600 siffror långt. Löst sett har du fastnat för att försöka dividera det 600-siffriga numret med alla möjliga 300-siffriga primtal tills du träffar jackpotten, eller hittar att det inte finns något svar. Shors algoritm lovar dock att lösa detta problem med logaritm av den vanliga ansträngningen. Att faktorisera ett antal av 2048 binära siffror bör därför ta bara dubbelt så lång tid som att faktorisera ett 1024-bitars tal, inte dubbelt så lång tid som att faktorisera ett 2047-bitars tal, vilket representerar en enorm snabbhet.

Motverka hotet

Hotet från Grovers algoritm kan motverkas helt enkelt genom att öka storleken på siffrorna du använder genom att kvadrera dem, vilket innebär att du fördubblar antalet bitar i din kryptografiska hash eller din symmetriska krypteringsnyckel. (Med andra ord, om du tycker att SHA-256 är bra just nu, skulle användning av SHA-512 istället ge ett PQC-resistent alternativ.)

Men Shors algoritm kan inte motverkas så lätt.

En offentlig nyckel på 2048 bitar skulle behöva öka sin storlek exponentiellt, inte bara genom att kvadrera, så att istället för en nyckel på 2×2048=4096 bitar, antingen skulle du behöva en ny nyckel med den omöjliga storleken 2²⁰⁴⁸ bitar...

…eller så måste du anta en helt ny sorts post-kvantkrypteringssystem som Shors algoritm inte gällde.

Tja, det amerikanska standardiseringsorganet NIST har kört en PQC "tävling" sedan slutet av 2017.

Processen har varit öppen för alla, med alla deltagare välkomna, alla algoritmer öppet publicerade och offentlig granskning inte bara möjlig utan aktivt uppmuntras:

Ring för förslag. [Stängd 2017-11-30]. […] Det är avsett att de nya kryptografistandarderna för offentliga nyckel ska specificera en eller flera ytterligare oklassificerade, offentligt offentliggjorda digitala signaturer, kryptering av offentliga nycklar och nyckeletableringsalgoritmer som är tillgängliga över hela världen, och som kan skydda känslig myndighetsinformation långt in i överskådlig framtid, bland annat efter tillkomsten av kvantdatorer.

Efter tre omgångar av inlämningar och diskussioner, NIST meddelade2022-07-05, att den hade valt fyra algoritmer som den betraktade som "standarder" med omedelbar verkan, alla med ljuvligt klingande namn: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONoch SPHINCS+.

Den första (CRYSTALS-KYBER) används som vad som kallas a Viktig avtalsmekanism (KEM), där två ändar av en offentlig kommunikationskanal på ett säkert sätt skapar en engångs privat krypteringsnyckel för att utbyta en sessions värde av data konfidentiellt. (Enkelt uttryckt: snokare får bara strimlad kål, så de kan inte avlyssna samtalet.)

De andra tre algoritmerna används för Digitala signaturer, varigenom du kan se till att den information du fick ut i din ände matchar exakt vad avsändaren har lagt in hos den andra, vilket förhindrar manipulering och säkerställer integritet. (Enkelt uttryckt: om någon försöker korrumpera eller bråka med data, vet du det.)

Fler algoritmer behövs

Samtidigt som NIST tillkännagav de nya standarderna tillkännagav också en fjärde omgången av sin konkurrens och lägger fram ytterligare fyra algoritmer som möjliga alternativa KEM. (Kom ihåg att vi i skrivande stund redan har tre godkända digitala signaturalgoritmer att välja mellan, men bara en officiell KEM.)

Dessa var: BIKE, Classic McEliece, HQC och SIKE.

Spännande nog McEliece algoritm uppfanns långt tillbaka på 1970-talet av den amerikanske kryptografen Robert Mc Eliece, som dog 2019, långt efter att NIST:s tävling redan var igång.

Det slog dock aldrig fast eftersom det krävde enorma mängder nyckelmaterial jämfört med dagens populära alternativ, Diffie-Hellman-Merkle-algoritmen (DHM, eller ibland bara DH).

Tyvärr har en av de tre Round Four-algoritmerna, nämligen SIKE, verkar ha blivit sprucken.

I en hjärntvridande tidning med titeln EN EFFEKTIV NYCKELÅTERSTÄLLNINGSATTACK PÅ SIDH (PRELIMINÄR VERSION), verkar de belgiska kryptograferna Wouter Castryk och Thomas Decru ha tilldelat SIKE-algoritmen något av ett dödligt slag.

Om du undrar är SIKE en förkortning för Supersingular Isogeny Key Encapsulation, och SIDH står för Supersingular Isogeny Diffie-Hellman, en specifik användning av SIKE-algoritm varvid två ändar av en kommunikationskanal utför en DHM-liknande "kryptodans" för att utbyta ett gäng offentliga data som gör att varje ände kan härleda ett privat värde att använda som en engångshemlig krypteringsnyckel.

Vi ska inte försöka förklara attacken här; vi ska bara upprepa vad tidningen hävdar, nämligen att:

Mycket löst uttryckt inkluderar indata här de offentliga data som tillhandahålls av en av deltagarna i nyckeletableringens kryptodance, tillsammans med de förutbestämda (och därför allmänt kända) parametrarna som används i processen.

Men utdata som extraheras (informationen som kallas isogenin φ ovan) är tänkt att vara den aldrig avslöjade delen av processen – den så kallade privata nyckeln.

Med andra ord, från enbart offentlig information, såsom data som utbyts öppet under nyckelinstallationen, hävdar kryptograferna att de kan återställa den privata nyckeln för en av deltagarna.

Och när du väl känner till min privata nyckel kan du enkelt och oupptäckt låtsas vara jag, så krypteringsprocessen bryts.

Tydligen tar nyckelknäckningsalgoritmen ungefär en timme att göra sitt arbete, med bara en enda CPU-kärna med den typ av processorkraft du hittar i en vardaglig bärbar dator.

Det är emot SIKE-algoritmen när den är konfigurerad för att uppfylla nivå 1, NIST:s grundläggande krypteringssäkerhet.

Vad göra?

Ingenting!

(Det är de goda nyheterna.)

Som författarna till tidningen föreslår, efter att ha noterat att deras resultat fortfarande är preliminärt, "Med det nuvarande tillståndet verkar SIDH vara helt bruten för alla offentligt genererade baskurvor."

(Det är de dåliga nyheterna.)

Men med tanke på att SIKE-algoritmen inte är officiellt godkänd ännu, kan den nu antingen anpassas för att motverka just denna attack (något som författarna medger kan vara möjligt), eller helt enkelt släppas helt.

Vad som än händer med SIKE är detta en utmärkt påminnelse om varför det är farligt att försöka uppfinna dina egna krypteringsalgoritmer.

Det är också ett tydligt exempel på varför proprietära krypteringssystem som förlitar sig på sekretessen för själva algoritmen att upprätthålla sin säkerhet är helt enkelt oacceptabla 2022.

Om en PQC-algoritm som SIKE överlevde persual och sondering av experter från hela världen i mer än fem år, trots att den avslöjades specifikt för att den skulle kunna bli föremål för offentlig granskning...

…då finns det ingen anledning att fråga dig själv hur väl dina hemgjorda, dolda krypteringsalgoritmer sannolikt kommer att klara sig när de släpps ut i naturen!

---