Erfaringer med bruk av MLDSA og MLKEM i Go-språket

Oversikt

Bakgrunn

I lang tid har den raske beregningskapasiteten til kvantedatamaskiner blitt oppfattet som en trussel mot eksisterende krypteringssystemer. Dette skyldes at de etablerte algoritmene RSA og ECC kan bli knekket av nettopp denne beregningskapasiteten. Men da begrepet kvantedatamaskin for alvor begynte å ta form for noen år siden, startet forskning og utvikling av alternativer, og NIST har siden arbeidet med standardisering av PQC (post-kvantekryptografi).

MLDSA og MLKEM

Til slutt vedtok NIST i august 2024 MLKEM og MLDSA, som bygger på CRYSTALS-Kyber og CRYSTALS-Dilithium, som standarder. Begge algoritmene opererer på grunnlag av problemet MLWE (Module Learning with Errors). Denne typen kalles gitterbasert kryptografi.

Gitterbasert kryptografi er, som navnet antyder, et krypteringssystem basert på vanskeligheten av matematiske problemer på gitter. Jeg har ikke en dyp matematisk kunnskap om dette, men oppsummert kan det beskrives som problemet med å løse lineære likninger med støy i et modulgitter. Hvor vanskelig dette er, er vanskelig å forestille seg, men det sies at slike problemer er så vanskelige at de ikke kan løses selv av kvantedatamaskiner.

MLDSA

La oss først se nærmere på MLDSA.

Oppbygning

MLDSA er, som navnet antyder, en asymmetrisk signaturalgoritme, og den består av totalt følgende to trinn.

1. Signaturgenerering: Generer en signatur for en melding ved hjelp av den private nøkkelen
2. Signaturverifisering: Bekreft gyldigheten av den genererte signaturen ved hjelp av den offentlige nøkkelen

MLDSA har dessuten følgende tre egenskaper.

1. Strong existential unforgeability: Det er ikke mulig å generere en annen gyldig signatur ut fra én signatur og den offentlige nøkkelen.
2. Chosen message attack: Selv med signaturen for en valgt melding er det ikke mulig å generere en ny gyldig signatur ved hjelp av den offentlige nøkkelen.
3. Side-channel attack: Ved signering brukes stadig nye tilfeldige verdier og pseudotilfeldige verdier avledet fra meldingen, noe som gir høy sikkerhet.
4. Domain separation: Ved å bruke ulike seed for ulike parametere forebygges gjentatte sikkerhetsproblemer.

Kode

La oss se et enkelt eksempel i programmeringsspråket Go. I dette eksemplet er mldsa fra cloudflare/circl brukt.

 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 nøkler 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 signaturen.
22    // En ting å merke seg er at med versjonen per 22. desember 2024 oppstår en feil dersom verdien ikke 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 scheme for den offentlige nøkkelen.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturverdien er utelatt fordi den er for lang. Hvis du vil se hele verdien, kan du kjøre koden på playground.

Selv om den er kodet i base64, er det nok litt tungt at den blir 3228 byte. Når man tenker på at vi kanskje snart må utveksle signaturer av denne størrelsen for å motstå kvantedatamaskiner, er det litt tungt å tenke på..

MLKEM

Oppbygning

MLKEM er en nøkkelinnkapslingsmekanisme (Key Encapsulation Mechanism). En KEM er en algoritme som gjør det mulig å generere en delt nøkkel mellom to parter ved hjelp av en asymmetrisk krypteringsmetode. Nøkkelutvekslingsmekanismen i MLKEM består av 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 først til mottakeren for bruk.
2. Nøkkelutpakking: Mottakeren bruker sin private nøkkel til å hente den delte nøkkelen fra den krypterte meldingen.

MLKEM har totalt tre parametere: MLKEM-512, MLKEM-768 og MLKEM-1024. Jo lavere tallet er, desto mindre blir nøkkelen og den krypterte teksten; jo høyere tallet er, desto lengre blir nøkkelen og den krypterte teksten, og sikkerhetsnivået er høyere.

Kode

MLKEM skal legges til i go 1.24, så derfor er go 1.24rc1, som er tilgjengelig nå, brukt.

 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    // I MLKEM brukes begrepet EncapsulationKey i stedet for PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // For enkelhets skyld er EncapsulationKey kopiert for å vise at nøkkelen kan hentes ut med Bytes() og gjenopprettes med NewEncapsulationKeyX og deretter brukes igjen.
20    // I praksis er denne prosessen den der avsenderen lager et objekt av mottakerens EncapsulationKey, som er offentlig tilgjengelig som tekst.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Encapsulate: avsenderen genererer den krypterte teksten og den delte nøkkelen.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Kopien er laget for å vise hvordan mottakerens private nøkkel kan lagres og hentes igjen.
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 den krypterte teksten 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 det genereres en delt nøkkel av samme størrelse!

Denne koden kan også sjekkes på playground.

Konklusjon

Spesifikasjonene, sikkerhetsnivåene og størrelsene på de private nøklene, de offentlige nøklene, signaturene eller chifferteksten for hver algoritme kan oppsummeres slik. Alle har, i tråd med navnet PQC, betydelig store størrelser.

Med disse algoritmene forventer vi å kunne bruke et internett som er tilstrekkelig sikkert også mot kvantedatamaskiner, men på grunn av de relativt større nøklene og signaturene/chifferteksten virker det uunngåelig at det blir flere beregninger.

Likevel er Go et språk der hver algoritme er effektivt implementert, og vi håper at den vil bli aktivt brukt på riktige steder for å beskytte din sikkerhet!