Bruk av MLDSA og MLKEM i Go-språket

Oversikt

Bakgrunn

I lang tid har kvantecomputeres raske beregningsevne vært ansett som en trussel mot eksisterende kryptografiske systemer. Dette skyldes at eksisterende systemer som RSA og ECC potensielt kan dekrypteres av kvantecomputeres beregningsevne. Imidlertid, etter hvert som konseptet med kvantecomputere ble mer konkret for flere år siden, begynte alternative løsninger å bli forsket på og utviklet, og NIST har arbeidet med standardisering av PQC (Post-Quantum Cryptography).

MLDSA og MLKEM

NIST vedtok til slutt MLKEM og MLDSA, basert på CRYSTALS-Kyber og CRYSTALS-Dilithium, som standarder i august 2024. Begge algoritmene opererer basert på problemet MLWE (Module Learning with Errors). Denne formen omtales som gitterbasert kryptografi.

Gitterbasert kryptografi er, som navnet antyder, et kryptografisk system basert på vanskeligheten med matematiske problemer på et gitter. Jeg har ikke inngående matematisk kunnskap om dette, men for å oppsummere det i én setning, sies det å være "problemet med å løse lineære ligninger med støy i et modulært gitter". Jeg har ingen følelse av hvor vanskelig det er, men slike problemer sies å være så vanskelige at selv kvantecomputere ikke kan løse dem.

MLDSA

La oss først undersøke MLDSA.

Struktur

MLDSA er, som navnet indikerer, en asymmetrisk signaturalgoritme som gjennomgår følgende to trinn:

1. Signaturgenerering: Genererer en signatur for en melding ved hjelp av en privat nøkkel.
2. Signaturverifisering: Verifiserer gyldigheten av den genererte signaturen ved hjelp av en offentlig nøkkel.

MLDSA har også følgende tre egenskaper:

1. strong existential unforgeability: En annen gyldig signatur kan ikke genereres fra en enkelt signatur og offentlig nøkkel.
2. chosen message attack: En ny gyldig signatur kan ikke genereres med en offentlig nøkkel fra en signatur for en hvilken som helst melding.
3. side-channel attack: Høy sikkerhet oppnås ved kontinuerlig bruk av nye tilfeldige verdier og pseudo-tilfeldige verdier avledet fra meldingen under signaturprosessen.
4. domain separation: Forhindrer repeterende sikkerhetsproblemer ved å sikre at forskjellige seeds brukes for forskjellige parametere.

Kode

Her er et enkelt eksempel på Go-kode. I dette eksemplet har jeg brukt mldsa fra cloudflare/circl.

 1package main
 2
 3import (
 4	"crypto"
 5	"crypto/rand"
 6	"encoding/base64"
 7	"fmt"
 8
 9	"github.com/cloudflare/circl/sign/mldsa/mldsa44"
10)
11
12func main() {
13    // Genererer en nøkkel med mldsa44-spesifikasjonen.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Genererer en signatur.
22    // Merk at per 22. desember 2024, med gjeldende versjon, oppstår en feil med mindre det er crypto.Hash(0).
23	signature, err := priv.Sign(rand.Reader, message, crypto.Hash(0))
24	if err != nil {
25		panic(err)
26	}
27
28	encodedSignature := base64.URLEncoding.EncodeToString(signature)
29	fmt.Println(len(encodedSignature), encodedSignature)
30
31    // Verifiserer ved å kalle PublicKey-skjemaet.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturverdien er utelatt på grunn av lengden. Hvis du ønsker å se hele teksten, kjør den på playground.

Selv om den er base64-kodet, kan en størrelse på 3228 byte være litt tungvint. Det er litt bekymringsfullt å tenke på at vi kanskje snart må utveksle signaturer av denne størrelsen for å motstå kvantecomputere.

MLKEM

Struktur

MLKEM er en Key Encapsulation Mechanism. KEM er en algoritme som gjør det mulig å generere en delt nøkkel mellom to parter ved å bruke en offentlig nøkkelkryptografisk metode. MLKEMs nøkkelutvekslingsmekanisme gjennomgår følgende prosess:

1. Nøkkelinnkapsling: Avsenderen bruker mottakerens offentlige nøkkel til å generere en kryptert melding (cipher text) og en delt nøkkel (shared key). Denne krypterte meldingen overføres deretter til mottakeren for bruk.
2. Nøkkelutpakking: Mottakeren bruker sin private nøkkel til å trekke ut den delte nøkkelen fra den krypterte meldingen.

Det finnes tre parametere i MLKEM: MLKEM-512, MLKEM-768 og MLKEM-1024. Jo lavere tallet er, desto mindre er nøkkelen og ciphertexten; jo høyere tallet er, desto lengre er nøkkelen og ciphertexten, og desto høyere er sikkerhetsnivået.

Kode

MLKEM er planlagt å bli lagt til i Go 1.24, så jeg har brukt Go 1.24rc1, som er tilgjengelig for øyeblikket.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Genererer mottakerens PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM bruker termen EncapsulationKey i stedet for PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Klonet for å vise at nøkkelen kan ekstraheres og gjenbrukes med EncapsulationKey.Bytes() og NewEncapsulationKeyX.
20    // I en reell bruk kan dette betraktes som prosessen der avsenderen konverterer mottakerens EncapsulationKey, som var offentlig tilgjengelig som tekst, til et objekt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Avsenderen genererer cipher text og den delte nøkkelen med Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Klonet for å vise hvordan mottakerens private nøkkel lagres og hentes.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Mottakeren bruker sin private nøkkel til å Decapsulate cipher text og generere en annen delt nøkkel.
36	sharedKeyReceiver, err := clonedReceiverKey.Decapsulate(cipherText)
37	if err != nil {
38		panic(err)
39	}
40
41	fmt.Println(base64.StdEncoding.EncodeToString(SenderSharedKey))
42	fmt.Println(base64.StdEncoding.EncodeToString(sharedKeyReceiver))
43}

1Q1ciS818WFHTK7D4MTvsQvciMTGF+dSGqMllOxW80ew=
2Q1ciS818WFHTK7D4MTvsQvciMTGF+dSGqMllOxW80ew=

Resultatet viser at en delt nøkkel av samme størrelse genereres!

Denne koden kan også finnes på playground.

Konklusjon

Spesifikasjonene, sikkerhetsnivåene, størrelsene på private nøkler, offentlige nøkler, signaturer og chiffertekster for hver algoritme kan oppsummeres som følger. De kan alle vise frem betydelige størrelser, noe som er passende for navnet PQC.

Med disse algoritmene forventer vi å kunne bruke et tilstrekkelig sikkert internett selv på kvantecomputere, men det er uunngåelig at det vil være mer beregning på grunn av de relativt større nøkkel- og signatur-/chiffertekststørrelsene.

Likevel, ettersom Go-språket har effektive implementeringer av hver algoritme, forventes det at de aktivt vil bli brukt til å beskytte sikkerheten din der det er hensiktsmessig!