Grunnleggende
Post-kvante-kryptografi (PQC)
Hvilke algoritmer som erstatter RSA og elliptiske kurver, hvordan de virker i grove trekk, og hvorfor det finnes flere typer.
Hva PQC er, og hva det ikke er
PQC er vanlig, matematisk kryptografi. Den bruker ikke kvantefysikk og krever ingen spesiell maskinvare. Navnet kommer av at algoritmene er valgt fordi de bygger på problemer som man ikke kjenner noen effektiv kvantealgoritme for. Det er forskjellig fra kvantenøkkeldistribusjon (QKD), som bruker fysiske kvanteeffekter over dedikerte linker.
Begrepet kvantesikker brukes ofte om det samme, men er litt misvisende: ingen algoritme er bevist sikker. Det riktige er at ingen kjenner et angrep, og at de er blitt vurdert grundig av kryptografer over mange år.
Hvorfor ikke bare lengre nøkler?
Mot kvantedatamaskiner hjelper det ikke å bruke lengre RSA-nøkler. Shors algoritme løser problemet i polynomisk tid, så en dobling av nøkkelstørrelsen koster angriperen lite ekstra. Forskere har riktignok vist at RSA kunne gjøres kvantesikker med nøkler på rundt én terabyte, men det er upraktisk. Derfor trengs helt nye algoritmer med andre matematiske grunnlag.
De fem familiene
| Familie | Bygger på | Eksempler | Status |
|---|---|---|---|
| Gitterbasert | Vanskelige problemer i høydimensjonale gitter (Learning With Errors, Short Integer Solution) | ML-KEM, ML-DSA, FN-DSA | Standardisert |
| Hashbasert | Kun sikkerheten til hashfunksjoner | SLH-DSA, LMS, XMSS | Standardisert |
| Kodebasert | Å dekode generelle feilrettende koder | HQC, Classic McEliece | HQC valgt, Classic McEliece i ISO-prosess |
| Multivariat | Å løse likningssystemer med mange variabler | Rainbow (brutt 2022) | Ikke i bruk |
| Isogenibasert | Avbildninger mellom elliptiske kurver | SIKE (brutt 2022) | Ikke i bruk |
At to av kandidatene ble brutt på vanlige datamaskiner i 2022, selv etter år med vurdering, er hovedgrunnen til at man ikke setter alle eggene i én kurv. Det er også grunnen til at NIST valgte algoritmer fra flere familier, og til at hybrid bruk anbefales.
ML-KEM: nøkkelutveksling
ML-KEM (FIPS 203, tidligere CRYSTALS-Kyber) er en nøkkelinnkapslingsmekanisme (KEM). Én part genererer et nøkkelpar og sender den offentlige nøkkelen. Den andre parten «innkapsler» en tilfeldig hemmelighet mot den nøkkelen og sender tilbake en chiffertekst. Bare den første parten kan åpne den. Begge sitter da med samme hemmelighet, som brukes til å utlede en symmetrisk nøkkel.
Standarden har tre parametersett: ML-KEM-512, ML-KEM-768 og ML-KEM-1024, som tilsvarer NIST sikkerhetskategori 1, 3 og 5. ML-KEM-768 er det vanligste valget og det som brukes i hybrid TLS.
ML-DSA og SLH-DSA: signaturer
ML-DSA (FIPS 204, tidligere CRYSTALS-Dilithium) er gitterbasert og er standardvalget for digitale signaturer. Parametersettene er ML-DSA-44, -65 og -87. Signaturene er mye større enn klassiske, for eksempel 3 309 byte for ML-DSA-65 mot 64 byte for Ed25519.
SLH-DSA (FIPS 205, tidligere SPHINCS+) bygger bare på hashfunksjoner. Det gir et konservativt sikkerhetsgrunnlag, men signaturene er enda større (fra rundt 8 til nesten 50 kilobyte) og signeringen er tregere. Den passer for tilfeller der man vil ha minst mulig antakelser om matematikken.
FN-DSA (FIPS 206, tidligere Falcon) gir kompakte signaturer, men er mer krevende å implementere riktig og er fortsatt under arbeid. For firmware-signering finnes i tillegg tilstandsbaserte hashsignaturer (LMS og XMSS, NIST SP 800-208).
Hybrid: klassisk og post-kvante sammen
I en hybrid løsning kjøres en klassisk algoritme (for eksempel X25519) og en post-kvante-algoritme (ML-KEM) parallelt, og de to hemmelighetene kombineres til én nøkkel. Forbindelsen er da trygg så lenge minst én av algoritmene holder.
- Er ML-KEM senere vist å ha en svakhet, beskytter X25519 mot vanlige angripere.
- Kommer det en kvantedatamaskin, beskytter ML-KEM.
Den mest brukte kombinasjonen er X25519MLKEM768 i TLS 1.3. Tyske BSI og franske ANSSI anbefaler hybrid i overgangsperioden. Prisen er litt mer data i håndtrykket (omtrent 1,1 til 1,2 kilobyte ekstra per retning) og litt mer regnekraft, noe som sjelden merkes i praksis.
Ytelse og størrelse
ML-KEM er rask. Selve beregningene er ofte på høyde med eller raskere enn klassisk elliptisk kurve-kryptografi. Det som koster er datamengden: nøkler og chiffertekster er et par tusen byte i stedet for noen titalls. Det merkes mest i protokoller med små pakker, på enheter med lite minne og i sertifikatkjeder, der mange signaturer og nøkler legges etter hverandre. Se størrelsestabellen.
Vanlige spørsmål
Er PQC det samme som kvantekryptering?
Nei. PQC er vanlige algoritmer som kjører på vanlig maskinvare og tåler kvanteangrep. «Kvantekryptering» eller QKD er en egen teknikk som bruker kvantefysikk og spesialutstyr.
Hvilken post-kvante-algoritme bør jeg bruke?
For nøkkelutveksling: ML-KEM-768, helst hybrid med X25519. For generelle signaturer: ML-DSA. For firmware og lange levetider kan LMS, XMSS eller SLH-DSA være aktuelle. Følg alltid produktets og myndighetenes gjeldende anbefalinger.
Kan post-kvante-algoritmene også bli brutt?
Det kan ikke utelukkes. Det er derfor man bruker hybrid i overgangen, og derfor man bygger kryptoagilitet: evnen til å bytte igjen om det trengs.