Vägen mot den kvantsäkra kryptostandarden
Nuläge
Kvantdatorer hotar att inom en inte allt för avlägsen framtid allvarligt äventyra säkerheten i vår kommunikation. Det finns redan idag väletablerade algoritmer för att knäcka asymmetriska kryptoalgoritmer som RSA och EDC, vilka är ämnade för kvantdatorer. Dessa kryptoalgoritmer är idag välanvända vid nyckelutbyte, digital signering och används i många kryptovalutor. I grund bygger asymmetriska kryptering på matematiska problem som är lätta att lösa åt ett håll, men svåra åt det motsatta. RSA t.ex. bygger på primtalsfaktorisering. Det är svårt (långsamt) att primtalsfaktorisera ett stort tal, men det är lätt (snabbt) att multiplicera primtalen för att nå talet. Kvantdatorer kan komma runt många problem av detta slaget genom unika algoritmer som enbart fungerar på kvantdatorer som nyttjar superpositioner av qubits.
Det finns redan idag kvantdatorer i liten skala, och de algoritmer som kan knäcka asymmetrisk kryptering har testats och visats fungera på dessa. Det enda som saknas är möjlighet att skala upp detta till tillräckligt många kvantbitar (“qubits”) för att matcha de nycklar som används. Detta innebär alltså att oavsett hur felfri implementeringen av dessa kryptoalgoritmer är kommer de att vara sårbara mot kvantdatorer i framtiden, då knäckning av algoritmerna kan ske på några få ögonblick istället för som med dagens datorer, miljarder år.
Än har vi inte kraftfulla kvantdatorer som behövs för att knäcka de implementationer av asymmetrisk kryptering som används idag. De mest kraftfulla (kända) kvantprocessorerna idag jobbar med runt 30-60 qubits, långt under de mängder som behövs som behövs för att snabbt och effektivt knäcka de nyckelstorlekar som används idag (ett par tusen qubits). Men det pågår aktiv forskning och utveckling inom området. Stora resurser dedikeras till vidareutveckling av allt kraftigare kvantdatorer och kvantalgoritmer. Både stater och stora företag inom IT branschen (som Google, IBM, Intel, Microsoft med flera) bedriver stora satsningar inom området. Det handlar inte längre om “om” vi kommer nå tillräckligt kraftfulla kvantdatorer, det handlar om “när” vi når dit. Vanliga uppskattningar om detta “när” ligger inom runt 10-20 år.
Dessutom, för att göra saken värre, krypterade meddelanden som skickas idag kan kan lagras av en angripare, för att när kvantdatorerna är stora nog, dekrypteras. För information eller privata nycklar som är viktigt att de förbli konfidentiella i många år framåt är det därför fördelaktigt att redan idag påbörja arbetet att säkra sin organisation mot framtidens angreppsmetoder.
Lösningen(?) – Post-Quantum Cryptography Standardization
2016 initierade NIST (Arerikanska “National Institute of Standards and Technology”) en tävling för att hitta en ny standard för algoritmer som ska vara säker från kvantdatorer, så kallad “post quantum cryptography”. Dessa är ämnade att kunna ersätta nuvarande kryptoalgoritmer, gärna innan tillräckligt kraftfulla kvantdatorer har utvecklats. En viktig aspekt med dessa algoritmer jämfört med många alternativ är att de är designade för att fungera på dagens datorer. Det vill säga, det finns inga behov av att utveckla komplicerad ny hårdvara, vilket t.ex. behövs för den typ av kryptoalgoritmer som nyttjar kvantfenomen (t.ex. osäkerhetsprincipen eller kvant-sammanflätning).
Denna tävling, som på många sätt liknar tidigare metoder för framtagning av AES eller SHA3 (som också utfärdades av NIST), annonserades 2016, med deadline för skicka in bidrag 2017 och planerad en första draft av en ny standard redan 2022, dock förväntas viss försening pga pandemi. Totalt mottogs 69 godkända bidrag. Bidragen kan delas upp i ett antal olika aspekter;
- Digital signering
- Nyckelutbyte
- Kryptering
Bidrag delar upp i 5 säkerhetsnivåer, grovt kan man säga de motsvarar nuvarande AES128 för lägsta nivån och AES256 för högsta nivån. Bidragen kan grovt delas upp i ett antal större grupper med liknande bakomliggande mekanismer; baserade på gitter, kodkorrektion, hashning, och multivariata polynom, samt ett antal mer unika bidrag. Nedan listas typiska nackdelar med de olika grundmekanismerna.
- Gitter
- Relativt nytt koncept, inte lika välstuderat som andra kryptoalgoritmer
- Multivaiata polynom
- Nycklar är stora (kB – MB)
- Hashning
- Långsamt, kan ta upp till nån sekund att signera
- Signaturer blir stora (fåtal kB)
- Kod-korrektion
- Nycklar är stora (kB – MB)
- Signering inte möjligt
Inkluderat i de ursprungliga bidragen finns några försök att göra existerande algoritmer kvantsäkra (både ECC och RSA). Det förstnämnda bygger på att man nyttjar en mappning mellan funktioner istället för multiplikation av punkter på en kurva. Hittills har denna inte kunnat visats vara svag mot kvantdatorer, men beräkningstider är betydligt långsammare än många av de alternativa algoritmerna. För att få RSA vara kvantsäkert behöver man vidta ganska extrema åtgärder. Bland annat nycklar som är flera GB stora, och beräkningstider för att nyckelgenerering på ett par dagar. Det ser onekligen ut som att dessa kryptoalgortimer som troget tjänat oss i 30-40 år kommer börja fasas ut inom ett par år.
Planen för tävlingen är att under fyra faser eliminera fler och fler algoritmer tills det att endast en algoritm kvarstår. Utvärdering av bidragen fokuserar på säkerhet, huruvida det är praktiskt möjligt att knäcka de. Detta görs både mot kvantdatorer och konventionella datorer/metoder, men även utvärdering av andra typer av mer klassiska sårbarheter och sekundära aspekter utvärderas, som:
- Är de enkelt att ersätta nuvarande algoritmer i existerande protokoll.
- Säkerhet mot side-channel attacker (t.ex. information som tidsåtgång eller elförbrukning).
- Forward secrecy (att röjande av privata nycklar inte äventyrar tidigare kommunikation)
Efter fas 1 kvarstod 23 bidrag. Efter fas 2 kvarstår 15 bidrag, uppdelade i två grupper; snabbspår för de algoritmer som visat störst potential, samt ett alternativt spår för övriga algoritmer. Fas 3 förväntas vara den sista fasen där där de slutgiltiga algoritmerna fastställs.
Av algoritmerna som lagts i snabbspåret är hela 5 av dessa gitterbaserade. Det ser alltså just nu ut som att det finns en stor chans att framtidens kryptoalgoritmer kommer att vara gitterbaserade. Är man intresserad av utvecklingen här och vill få lite bättre insyn i vad gittervaserade kryptoalgoritmer handlar om, håller NIST en konferens som är öppen för allmänheten idag 17:00 Svensk tid, med ämnet “Side-Channel Analysis of Lattice-based PQC Candidates”. Om du missade detta bör konferensen vara tillgänglig efteråt via länken nedan.
https://csrc.nist.gov/projects/post-quantum-cryptography/workshops-and-timeline/round-3-seminars