Användning av MLDSA och MLKEM i Go-språket

Översikt

Bakgrund

Under ganska lång tid har kvantdatorers snabba beräkningar uppfattats som ett hot mot befintliga krypteringssystem. Detta beror på att befintliga system som RSA och ECC potentiellt skulle kunna dekrypteras med hjälp av kvantdatorers beräkningsförmåga. Men för flera år sedan började konceptet med kvantdatorer att konkretiseras, vilket ledde till att alternativa lösningar började forskas fram och utvecklas, och NIST har drivit standardiseringen av PQC (Post-Quantum Cryptography).

MLDSA och MLKEM

NIST antog slutligen MLKEM och MLDSA som standarder i augusti 2024, baserade på CRYSTALS-Kyber och CRYSTALS-Dilithium. Båda algoritmerna fungerar baserat på problemet MLWE (Module Learning with Errors). Denna typ av kryptografi kallas gitterbaserad kryptografi.

Gitterbaserad kryptografi är, som namnet antyder, ett kryptografiskt system baserat på svårigheten hos matematiska problem på ett gitter. Även om jag inte har djupgående matematisk kunskap om detta, kan det sammanfattas som "problemet med att lösa linjära ekvationer med brus i ett modulgitter". Det är svårt att förstå hur svårt det är, men sådana problem sägs vara så svåra att de inte kan lösas ens med kvantdatorer.

MLDSA

Låt oss först titta på MLDSA.

Struktur

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

1. Signaturgenerering: En signatur för ett meddelande genereras med hjälp av en privat nyckel.
2. Signaturverifiering: Giltigheten av den genererade signaturen kontrolleras med hjälp av en publik nyckel.

MLDSA har dessutom följande tre egenskaper:

1. strong existential unforgeability: Det är inte möjligt att generera en annan giltig signatur med en befintlig signatur och en publik nyckel.
2. chosen message attack: Det är inte möjligt att generera en ny giltig signatur med en publik nyckel från en signatur för ett valfritt meddelande.
3. side-channel attack: Säkerheten är hög genom att kontinuerligt använda nya slumpmässiga värden och pseudo-slumpmässiga värden härledda från meddelandet vid signering.
4. domain separation: Genom att använda olika seed för olika parametrar förebyggs återkommande säkerhetsproblem.

Kod

Här är ett enkelt exempel på Go-kod. I detta exempel har mldsa från cloudflare/circl använts.

 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 en nyckel 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 en signatur.
22    // En sak att notera är att med den nuvarande versionen (22 december 2024) uppstår ett fel om det inte är 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    // Anropar publik nyckels schema för att verifiera.
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, prova att köra det på playground.

Även om det är base64-kodat, är 3228 byte kanske lite betungande. Det känns lite betungande att tänka att vi kanske snart måste utbyta signaturer av denna storlek för att motstå kvantdatorer...

MLKEM

Struktur

MLKEM är en Key Encapsulation Mechanism. KEM är en algoritm som möjliggör generering av en delad nyckel mellan två parter med hjälp av asymmetrisk kryptering. MLKEM:s nyckelutbytesmekanism genomgår följande process:

1. Nyckelkapsling: Avsändaren använder mottagarens publika nyckel för att generera ett krypterat meddelande (cipher text) och en delad nyckel (shared key). Detta krypterade meddelande överförs initialt till mottagaren för användning.
2. Nyckelavkapsling: Mottagaren använder sin privata nyckel för att extrahera den delade nyckeln från det krypterade meddelandet.

MLKEM har totalt tre parametrar. MLKEM-512, MLKEM-768 och MLKEM-1024 finns, där ett lägre nummer ger mindre nycklar och krypterad text, och ett högre nummer ger längre nycklar och krypterad text samt en högre säkerhetsnivå.

Kod

MLKEM planeras att läggas till i Go 1.24, så den för närvarande tillgängliga Go 1.24rc1 användes.

 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    // MLKEM använder termen EncapsulationKey istället för PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // En enkel replikering för att visa att nyckeln kan extraheras och återanvändas med EncapsulationKey.Bytes() och NewEncapsulationKeyX.
20    // I verkligheten skulle denna process motsvara att avsändaren skapar ett objekt från mottagarens EncapsulationKey som har varit offentligt tillgänglig som text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Avsändaren genererar krypterad text och en delad nyckel med Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Avsiktligt replikerad för att visa hur mottagarens privata nyckel sparas och hämtas.
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 generera 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 ett resultat kan vi se att delade nycklar av samma storlek genereras!

Denna kod kan även ses på playground.

Slutsats

Specifikationerna, säkerhetsnivåerna och storlekarna för privata nycklar, publika nycklar, signaturer och chiffertexter för varje algoritm kan sammanfattas enligt följande. De har alla betydande storlekar, vilket är passande för PQC.

Vi förväntar oss att dessa algoritmer ska möjliggöra ett tillräckligt säkert internet även med kvantdatorer, men det verkar oundvikligt med fler beräkningar på grund av de relativt större nyckel- och signatur/chiffertextstorlekarna.

Trots detta är Go-språket effektivt implementerat för varje algoritm, och vi hoppas att det aktivt kommer att användas för att skydda din säkerhet på lämpliga platser!