Erfarenheter av att använda MLDSA och MLKEM i Go-språket

Översikt

Bakgrund

Sedan för ganska länge sedan har kvantdatorers snabba beräkningsförmåga betraktats som ett hot mot befintliga krypteringssystem. Detta beror på att de traditionella algoritmerna RSA och ECC kan komma att knäckas genom just denna beräkningsförmåga hos kvantdatorer. Men sedan för några år tillbaka, när begreppet kvantdatorer började ta mer konkret form, inleddes forskning och utveckling av alternativ, och NIST har sedan dess drivit standardiseringen av PQC (Post-Quantum Cryptography, kvantresistent kryptering).

MLDSA och MLKEM

Slutligen antog NIST i augusti 2024 MLKEM och MLDSA, vilka baseras på CRYSTALS-Kyber och CRYSTALS-Dilithium, som standarder. Båda algoritmerna fungerar utifrån problemet MLWE (Module Learning with Errors). Denna typ kallas av oss för gitterbaserad kryptering.

Gitterbaserad kryptering är, som namnet antyder, ett krypteringssystem som bygger på svårigheten hos matematiska problem på gitter. Jag saknar själv djupgående matematiska kunskaper inom området, men sammanfattat i en mening sägs det vara problemet att lösa ett linjärt ekvationssystem med brus i ett modulgitter. Hur svårt det är går inte riktigt att greppa, men dessa problem sägs vara så svåra att de inte ens kan lösas av kvantdatorer.

MLDSA

Låt oss först titta närmare på MLDSA.

Uppbyggnad

MLDSA är, som namnet antyder, en asymmetrisk signaturalgoritm och genomgår totalt följande två steg.

1. Signaturgenerering: En signatur för ett meddelande skapas med hjälp av den privata nyckeln
2. Signaturverifiering: Giltigheten hos den genererade signaturen kontrolleras med hjälp av den publika nyckeln

MLDSA har dessutom följande tre egenskaper.

1. Strong existential unforgeability: Med en signatur och en publik nyckel kan ingen annan giltig signatur skapas.
2. Chosen message attack: Med en signatur för ett godtyckligt meddelande kan ingen ny giltig signatur skapas med hjälp av den publika nyckeln.
3. Side-channel attack: Vid signering används hela tiden nya slumpmässiga värden och pseudoslumpmässiga värden härledda från meddelandet, vilket ger hög säkerhet.
4. Domain separation: Olika seed används för olika parametrar, vilket förebygger upprepade säkerhetsproblem.

Kod

Här är ett enkelt exempel i Go-språket. I detta exempel används mldsa från 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    // Genererar nycklar 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    // Genererar signaturen.
22    // En sak att notera är att med versionen per den 22 december 2024 uppstår ett fel om inte crypto.Hash(0) används.
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    // Verifierar genom att anropa schemat för den publika nyckeln.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Signaturvärdet har utelämnats eftersom det är för långt. Om du vill se hela värdet kan du köra det på playground.

Även om det är base64-kodat är det kanske lite betungande att det blir 3228 byte. När man tänker på att vi inom kort kanske behöver utbyta signaturer med denna storlek för att skydda oss mot kvantdatorer känns det lite betungande, faktiskt..

MLKEM

Uppbyggnad

MLKEM är en Key Encapsulation Mechanism (nyckelinkapslingsmekanism). KEM är en algoritm som med hjälp av asymmetrisk kryptering gör det möjligt för två parter att skapa en gemensam nyckel. Nyckelutbytesmekanismen i MLKEM genomgår följande process.

1. Nyckelinkapsling: Avsändaren skapar en krypterad meddelandetext (cipher text) och en delad nyckel (shared key) med hjälp av mottagarens publika nyckel. Den krypterade meddelandetexten överförs först till mottagaren för användning.
2. Nyckelupplösning: Mottagaren extraherar den delade nyckeln från den krypterade meddelandetexten med hjälp av sin privata nyckel.

MLKEM har totalt tre parametrar. Det finns MLKEM-512, MLKEM-768 och MLKEM-1024. Ju lägre siffra, desto mindre nycklar och krypterad text, och ju högre siffra, desto längre nycklar och krypterad text samt en högre säkerhetsnivå.

Kod

MLKEM planeras att läggas till i Go 1.24, så vi använde go 1.24rc1, som är tillgänglig i nuläget.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Genererar mottagarens PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // I MLKEM används termen EncapsulationKey i stället för PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // För att enkelt visa att EncapsulationKey kan extraheras med Bytes() och återskapas med NewEncapsulationKeyX och användas igen har den klonats.
20    // I verkligheten är detta steg den process i vilken avsändaren skapar ett objekt av mottagarens EncapsulationKey, som tidigare publicerats som text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Med Encapsulate skapar avsändaren den krypterade texten och den delade nyckeln.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Klonas medvetet för att visa hur mottagarens privata nyckel kan lagras och hämtas igen.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Mottagaren använder sin privata nyckel för att Decapsulate den krypterade texten och skapar en annan delad nyckel.
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 resultat kan vi se att delade nycklar av samma storlek skapas!

Koden kan också köras på playground.

Slutsats

Specifikationerna, säkerhetsnivåerna samt storlekarna för privata nycklar, publika nycklar, signaturer och krypterad text för varje algoritm kan sammanfattas enligt följande tabell. Alla uppvisar, i linje med namnet PQC, betydande storlekar.

Med hjälp av dessa algoritmer hoppas vi kunna använda internet på ett säkert sätt även i en värld med kvantdatorer, men de relativt större nycklarna samt signaturerna och krypterad text innebär att fler beräkningar oundvikligen kommer att behövas.

Ändå är Go-språket väl lämpat, eftersom varje algoritm är effektivt implementerad, och vi hoppas att den kommer att användas aktivt på rätt ställen för att skydda er säkerhet!