Anvendelsen af MLDSA og MLKEM i Go-sproget

Oversigt

Baggrund

Ganske længe har hurtig databehandling i kvantecomputere været anerkendt som en trussel mod eksisterende krypteringssystemer. Eksisterende systemer som RSA og ECC kan potentielt dekrypteres på grund af kvantecomputeres databehandlingskapacitet. Men da konceptet med kvantecomputere begyndte at tage form for flere år siden, er alternativer blevet forsket i og udviklet, og NIST har arbejdet på PQC-standardisering (Post-Quantum Cryptography).

MLDSA og MLKEM

I sidste ende vedtog NIST i august 2024 MLKEM og MLDSA baseret på CRYSTALS-Kyber og CRYSTALS-Dilithium som standarder. Begge algoritmer fungerer baseret på problemet MLWE (Module Learning with Errors). Denne type kaldes gitterbaseret kryptografi.

Gitterbaseret kryptografi er, som navnet antyder, et krypteringssystem baseret på vanskeligheden af matematiske problemer på et gitter. Jeg har heller ikke dybtgående matematisk viden om dette, men i én linje er det et problem med at løse støjende lineære ligninger i et modulgitter. Jeg har ingen idé om, hvor vanskeligt det er, men det siges, at dette problem er så vanskeligt, at selv kvantecomputere ikke kan løse det.

MLDSA

Lad os først se på MLDSA.

Sammensætning

MLDSA er, som navnet antyder, en asymmetrisk signaturalgoritme, der består af følgende to trin.

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

Og MLDSA har følgende tre egenskaber.

1. strong existential unforgeability: Du kan ikke generere en anden gyldig signatur med én signatur og en offentlig nøgle.
2. chosen message attack: Du kan ikke generere en ny gyldig signatur med en offentlig nøgle, selv med en signatur for en given besked.
3. side-channel attack: Høj sikkerhed ved at bruge en ny tilfældig værdi og en pseudo-tilfældig værdi afledt af beskeden under signering.
4. domain separation: Forebygger gentagne sikkerhedsproblemer ved at bruge forskellige seeds til forskellige parametre.

Kode

Her er et simpelt Go-sprog kodeeksempel.
Dette eksempel bruger 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    // Generer en nøgle med 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    // Opret en signatur.
22    // En ting at bemærke er, at pr. 22. december 2024 vil der opstå en fejl, medmindre crypto.Hash(0) anvendes, baseret på den aktuelle version.
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    // Bekræft ved at kalde public key's scheme.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Jeg udelod signaturværdien, fordi den er for lang. Hvis du vil se hele teksten, kan du køre den på playground.

Selvom det er base64-kodet, kan det være lidt byrdefuldt, at det kommer ud som 3228 bytes.
Jeg synes, det er lidt byrdefuldt at tænke på, at vi snart skal udveksle denne størrelse som en signatur, der er modstandsdygtig over for kvantecomputere.

MLKEM

Sammensætning

MLKEM er en nøgleindkapslingsmekanisme (Key Encapsulation Mechanism). KEM er en algoritme, der giver to parter mulighed for at generere en delt nøgle ved hjælp af public-key-kryptografi. Nøgleudvekslingsmekanismen i MLKEM følger 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øgleudpakning: Modtageren bruger sin private nøgle til at udtrække den delte nøgle fra den krypterede besked.

Der er i alt 3 parametre i MLKEM. Der er MLKEM-512, MLKEM-768 og MLKEM-1024, og jo mindre tallet er, jo mindre er nøglen og den krypterede tekst, og jo større tallet er, jo længere er nøglen og den krypterede tekst, og jo højere er sikkerhedsniveauet.

Kode

MLKEM vil blive tilføjet i go 1.24, så jeg brugte go 1.24rc1, som er tilgængelig på nuværende tidspunkt.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Opret 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    // For at vise, at nøglen nemt kan udtrækkes og genbruges med EncapsulationKey's Bytes() og NewEncapsulationKeyX, blev den klonet.
20    // Selvfølgelig, hvis den bruges i virkeligheden, kan denne proces ses som den proces, hvor afsenderen opretter en offentlig EncapsulationKey for modtageren, som var offentliggjort som tekst.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Afsenderen genererer krypteret tekst og en delt nøgle med Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Jeg kopierede den bevidst for at vise, hvordan man gemmer og henter modtagerens private nøgle.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Modtageren bruger sin private nøgle til at Decapsulate den krypterede tekst for at 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 en delt nøgle af samme størrelse!

Denne kode kan også findes på playground.

Konklusion

Specifikationerne, sikkerhedsniveauet, private nøgler, offentlige nøgler og størrelsen på signaturer eller chiffertekster for hver algoritme kan opsummeres som følger. Hver især har en stor størrelse, der ikke skammer sig over navnet PQC.

Vi håber, at vi med disse algoritmer vil være i stand til at bruge et tilstrækkeligt sikkert internet selv på kvantecomputere, men det ser uundgåeligt ud, at der vil være mere databehandling på grund af de relativt store nøgle- og signatur-/chiffertekststørrelser.

Ikke desto mindre er go-sproget effektivt implementeret i hver algoritme, så vi håber, at det vil blive brugt aktivt til at beskytte din sikkerhed på de relevante steder!