Erfaringer med brugen af MLDSA og MLKEM i Go-sproget

Oversigt

Baggrund

Allerede for længe siden blev kvantecomputerens hurtige beregningsevne opfattet som en trussel mod de eksisterende krypteringssystemer. Det skyldes, at de eksisterende systemer såsom RSA og ECC potentielt kan knækkes med denne beregningsevne fra kvantecomputere. Men for nogle år siden begyndte begrebet kvantecomputere at blive mere konkret, og derfor begyndte man at forske i og udvikle alternativer, og NIST har gennemført standardiseringen af PQC (post-kvante kryptografi).

MLDSA og MLKEM

Endelig vedtog NIST i august 2024 MLKEM og MLDSA, som er baseret på CRYSTALS-Kyber og CRYSTALS-Dilithium, som standarder. De to algoritmer fungerer ud fra problemet Module Learning with Errors (MLWE). Denne type kaldes vi gitterbaseret kryptografi.

Gitterbaseret kryptografi er, som navnet antyder, et krypteringssystem baseret på vanskeligheden ved matematiske problemer på et gitter. Jeg har heller ikke en dybdegående matematisk viden om dette, men kort sagt siges det at være problemet med at løse lineære ligninger med støj i et modulgitter. Hvor svært det er, er svært at forestille sig, men man siger, at sådanne problemer er så vanskelige, at de ikke kan løses selv med kvantecomputere.

MLDSA

Lad os først se nærmere på MLDSA.

Opbygning

MLDSA er, som navnet antyder, en asymmetrisk signaturalgoritme, som gennemløber i alt følgende to trin.

1. Signaturgenerering: En signatur for en besked genereres ved hjælp af den private nøgle
2. Signaturverifikation: Gyldigheden af den genererede signatur kontrolleres ved hjælp af den offentlige nøgle

Og MLDSA har følgende tre egenskaber.

1. Strong existential unforgeability: Med én signatur og den offentlige nøgle kan man ikke generere en anden gyldig signatur.
2. Chosen message attack: Selv med signaturen for en vilkårlig besked kan man ikke med den offentlige nøgle generere en ny gyldig signatur.
3. Side-channel attack: Ved signering bruges konstant nye tilfældige værdier og pseudotilfældige værdier afledt af beskeden, hvilket giver høj sikkerhed.
4. Domain separation: Der anvendes forskellige seeds for forskellige parametre, hvilket forebygger gentagne sikkerhedsproblemer.

Kode

Lad os nu se et simpelt eksempel i Go-sprog. I dette eksempel er mldsa fra cloudflare/circl anvendt.

 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 nøgler 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    // Generer signaturen.
22    // Bemærk, at fra versionen pr. 22. december 2024 opstår der en fejl, hvis værdien 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    // Verificer ved at kalde schemet for den offentlige nøgle.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturværdien er udeladt, da den er for lang. Hvis du ønsker at se den fulde version, kan du køre den på playground.

Selvom den er kodet i base64, er det nok lidt tungt, at den fylder 3228 bytes. Når man tænker på, at vi snart måske må udveksle signaturer af denne størrelse for at modstå kvantecomputere, er det lidt tungt at forestille sig..

MLKEM

Opbygning

MLKEM er en nøgleindkapslingsmekanisme (Key Encapsulation Mechanism). KEM er en algoritme, der gør det muligt for to parter at generere en fælles nøgle ved hjælp af offentlig nøglekryptering. Nøgleudvekslingsmekanismen i MLKEM gennemløber 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 overføres først til modtageren, så denne kan anvende den.
2. Nøgleudpakning: Modtageren bruger sin private nøgle til at udtrække den delte nøgle fra den krypterede besked.

MLKEM har i alt tre parametre. Der findes MLKEM-512, MLKEM-768 og MLKEM-1024. Jo lavere tal, desto mindre nøgler og krypteret tekst; jo højere tal, desto længere nøgler og krypteret tekst, og desto højere sikkerhedsniveau.

Kode

MLKEM forventes at blive tilføjet i Go 1.24, og da den kan anvendes på nuværende tidspunkt, er Go 1.24rc1 blevet anvendt.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generer modtagerens PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // I MLKEM bruges begrebet EncapsulationKey i stedet for PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // For at vise, at man kan udtrække og genbruge EncapsulationKey via Bytes() og NewEncapsulationKeyX, er den blevet klonet.
20    // I praksis er denne proces, hvor afsenderen opretter et objekt ud fra modtagerens EncapsulationKey, der er offentliggjort som tekst.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Afsenderen genererer chifferteksten og den delte nøgle med Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Der er med vilje lavet en klon for at vise, hvordan modtagerens private nøgle kan gemmes og hentes igen.
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 chifferteksten og genererer 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=

Resultatet viser, at der genereres en delt nøgle af samme størrelse!

Denne kode kan også ses på playground.

Konklusion

Specifikationerne, sikkerhedsniveauerne og størrelserne af de private nøgler, offentlige nøgler, signaturer og krypteret tekst for hver algoritme kan opsummeres som følger. Hver af dem har, i overensstemmelse med navnet PQC, en stor størrelse.

Med disse algoritmer håber vi at kunne bruge et internet, der er tilstrækkeligt sikkert, også på kvantecomputere, men de relativt større nøgle- og signatur-/krypteretekststørrelser gør, at flere beregninger uundgåeligt vil være nødvendige.

Ikke desto mindre er Go-sproget velimplementeret for hver algoritme, og vi håber, at de bliver aktivt anvendt til at beskytte din sikkerhed de rette steder!