Anvendelse af MLDSA og MLKEM i Go-sprog

Oversigt

Baggrund

I lang tid er kvantecomputeres hurtige beregninger blevet opfattet som en trussel mod eksisterende krypteringssystemer. Dette skyldes, at eksisterende systemer som RSA og ECC potentielt kan afkodes på grund af kvantecomputernes beregningsevner. Men for flere år siden begyndte konceptet med kvantecomputere at blive en realitet, og alternativer er blevet forsket i og udviklet, og NIST har standardiseret PQC (Post-Quantum Cryptography).

MLDSA og MLKEM

NIST vedtog i august 2024 endelig MLKEM og MLDSA, baseret på CRYSTALS-Kyber og CRYSTALS-Dilithium, som standarder. Begge algoritmer fungerer baseret på problemet MLWE (Module Learning with Errors). Denne form kalder vi gitterbaseret kryptografi.

Gitterbaseret kryptografi er, som navnet antyder, et krypteringssystem baseret på sværhedsgraden af matematiske problemer på et gitter. Jeg har ikke en grundig matematisk viden herom, men for at opsummere det i én sætning, er det "problemet med at løse lineære ligninger med støj i et modulært gitter". Jeg kan ikke forestille mig, hvor svært det er, men det siges, at sådanne problemer er så svære, at selv kvantecomputere ikke kan løse dem.

MLDSA

Lad os først se på MLDSA.

Struktur

MLDSA er, som navnet antyder, en asymmetrisk signaturalgoritme, der gennemgår følgende to trin:

1. Signaturgenerering: Opretter en signatur for en besked ved hjælp af en privat nøgle.
2. Signaturverifikation: Verificerer gyldigheden af den genererede signatur ved hjælp af en offentlig nøgle.

Og MLDSA har følgende 3 karakteristika:

1. strong existential unforgeability: En anden gyldig signatur kan ikke genereres med én signatur og offentlig nøgle.
2. chosen message attack: En ny gyldig signatur kan ikke genereres med en offentlig nøgle ud fra en signatur for en vilkårlig besked.
3. side-channel attack: Sikkerheden er høj, da der konsekvent bruges nye tilfældige værdier og pseudo-tilfældige værdier afledt af beskeden under signaturprocessen.
4. domain separation: Forhindrer gentagne sikkerhedsproblemer ved at bruge forskellige seeds til forskellige parametre.

Kode

Her er et simpelt Go-eksempel på kode. Dette eksempel brugte 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 nøgler i mldsa44-specifikationen.
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    // Bemærk venligst, at med den nuværende version pr. 22. december 2024, vil der opstå en fejl, hvis det 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    // Verificerer ved at kalde skemaet for den offentlige nøgle.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturværdien blev udeladt, da den var for lang. Hvis du vil se den fulde tekst, kan du køre den i playground.

Selvom den er base64-kodet, vil 3228 bytes nok føles lidt besværligt. Det er lidt bekymrende at tænke på, at vi måske snart skal udveksle denne størrelse for signaturer, der er modstandsdygtige over for kvantecomputere...

MLKEM

Struktur

MLKEM er en Key Encapsulation Mechanism. KEM er en algoritme, der gør det muligt at generere en delt nøgle mellem to parter ved hjælp af offentlig nøglekryptering. MLKEM's nøgleudvekslingsmekanisme gennemgår følgende proces:

1. Nøgleindkapsling: Afsenderen bruger modtagerens offentlige nøgle til at generere en krypteret besked (cipher text) og en delt nøgle (shared key). Denne krypterede besked sendes oprindeligt til modtageren til brug.
2. Nøgleafkapsling: Modtageren bruger sin private nøgle til at udtrække den delte nøgle fra den krypterede besked.

MLKEM har i alt 3 parametre. Der findes MLKEM-512, MLKEM-768 og MLKEM-1024, hvor et lavere tal resulterer i en mindre nøgle og cipher text, og et højere tal resulterer i en længere nøgle og cipher text samt et højere sikkerhedsniveau.

Kode

MLKEM forventes at blive tilføjet i Go 1.24, så den aktuelt tilgængelige Go 1.24rc1 blev brugt.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Genererer modtagerens PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // I MLKEM bruges udtrykket EncapsulationKey i stedet for PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Duplikerede den for at vise, at nøglen kan udtrækkes og genbruges med EncapsulationKey's Bytes() og NewEncapsulationKeyX.
20    // I virkeligheden kan denne proces betragtes som afsenderen, der skaber et objekt fra modtagerens EncapsulationKey, der var offentligt tilgængelig som tekst.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Afsenderen genererer cipher text og den delte nøgle med Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Duplikerede den med vilje for at vise, hvordan modtagerens private nøgle gemmes og hentes.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Modtageren bruger den private nøgle til at Decapsulate cipher text og generere en anden delt nøgle.
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=

Som et resultat kan vi se, at der genereres delte nøgler af samme størrelse!

Denne kode kan også ses på legepladsen.

Konklusion

Specifikationerne, sikkerhedsniveauerne, private nøgler, offentlige nøgler og størrelsen af signaturer eller ciphertekster for hver algoritme kan opsummeres som følger. Hver algoritme har en betydelig størrelse, der lever op til navnet PQC.

Med disse algoritmer forventer vi at kunne bruge et internet, der er tilstrækkeligt sikkert selv på kvantecomputere, men det ser ud til, at et øget antal beregninger er uundgåeligt på grund af de relativt større nøgle- og signatur-/ciphertekststørrelser.

Ikke desto mindre, da Go-sproget har effektive implementeringer af hver algoritme, forventes det, at disse vil blive aktivt brugt til at beskytte jeres sikkerhed de rette steder!