Gebruik van MLDSA en MLKEM in de Go-programmeertaal

Overzicht

Achtergrond

Al geruime tijd wordt de snelle rekenkracht van kwantumcomputers gezien als een bedreiging voor bestaande cryptografische systemen. Bestaande systemen zoals RSA en ECC kunnen mogelijk worden ontcijferd door de rekenkracht van kwantumcomputers. Echter, nu het concept van kwantumcomputers de afgelopen jaren steeds concreter is geworden, is men begonnen met het onderzoeken en ontwikkelen van alternatieven. Het NIST heeft een PQC (Post-Quantum Cryptography) standaardisatieproces gestart.

MLDSA en MLKEM

Uiteindelijk heeft het NIST in augustus 2024 MLKEM en MLDSA, gebaseerd op CRYSTALS-Kyber en CRYSTALS-Dilithium, als standaard aangenomen. Beide algoritmen werken op basis van het MLWE (Module Learning with Errors) probleem. Deze vorm noemen we roostergebaseerde cryptografie.

Roostergebaseerde cryptografie is, zoals de naam al doet vermoeden, een cryptografisch systeem dat gebaseerd is op de moeilijkheid van wiskundige problemen op een rooster. Hoewel ik geen diepgaande wiskundige kennis heb, kan het in één regel worden samengevat als het oplossen van een lineaire vergelijking met ruis in een module rooster. Het is moeilijk in te schatten hoe moeilijk het is, maar men zegt dat dit probleem zo moeilijk is dat het zelfs met een kwantumcomputer niet kan worden opgelost.

MLDSA

Laten we eerst eens kijken naar MLDSA.

Samenstelling

MLDSA is, zoals de naam al doet vermoeden, een asymmetrisch handtekeningalgoritme dat in totaal uit de volgende 2 stappen bestaat.

1. Handtekening genereren: Genereer een handtekening voor een bericht met behulp van de privésleutel.
2. Handtekening verifiëren: Verifieer de geldigheid van de gegenereerde handtekening met behulp van de publieke sleutel.

MLDSA heeft de volgende 3 kenmerken:

1. strong existential unforgeability: Het is niet mogelijk om een andere geldige handtekening te genereren met één handtekening en publieke sleutel.
2. chosen message attack: Het is niet mogelijk om een nieuwe geldige handtekening te genereren met een publieke sleutel, zelfs niet met de handtekening van een willekeurig bericht.
3. side-channel attack: Het gebruikt continu nieuwe willekeurige waarden en pseudo-willekeurige waarden afgeleid van berichten tijdens het ondertekenen, wat de beveiliging verhoogt.
4. domain separation: Het voorkomt herhalende beveiligingsproblemen door verschillende seeds te gebruiken voor verschillende parameters.

Code

Hier is een eenvoudig voorbeeld van Go-taalcode. In dit voorbeeld gebruiken we de mldsa van 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    // Genereer een sleutel met de mldsa44 specificatie.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Genereer de handtekening.
22    // Een belangrijk punt om op te merken is dat per 22 december 2024 een fout optreedt als crypto.Hash(0) niet wordt gebruikt.
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    // Verifieer door het schema van de publieke sleutel aan te roepen.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

De handtekeningwaarde is te lang, dus is deze weggelaten. Als je de volledige waarde wilt zien, probeer hem dan uit te voeren in de playground.

Hoewel het base64-gecodeerd is, is het een beetje overweldigend om 3228 bytes te krijgen. Het is een beetje beangstigend om te bedenken dat we binnenkort deze grootte moeten uitwisselen als handtekening om kwantumcomputers te weerstaan.

MLKEM

Samenstelling

MLKEM is een Key Encapsulation Mechanism. KEM is een algoritme dat het mogelijk maakt om een gedeelde sleutel tussen twee partijen te genereren met behulp van public key cryptografie. Het sleuteluitwisselingsmechanisme van MLKEM doorloopt het volgende proces:

1. Sleutel inkapseling: De afzender gebruikt de publieke sleutel van de ontvanger om een versleuteld bericht (ciphertext) en een gedeelde sleutel te genereren. Dit versleutelde bericht wordt in eerste instantie aan de ontvanger doorgegeven zodat deze het kan gebruiken.
2. Sleutel decapsulatie: De ontvanger gebruikt zijn privésleutel om de gedeelde sleutel uit het versleutelde bericht te halen.

Er zijn in totaal 3 parameters in MLKEM. Er zijn MLKEM-512, MLKEM-768 en MLKEM-1024, waarbij kleinere parameters resulteren in kleinere sleutels en versleutelde tekst, en grotere parameters resulteren in langere sleutels en versleutelde tekst, met een hoger beveiligingsniveau.

Code

MLKEM zal worden toegevoegd in Go 1.24, dus ik heb Go 1.24rc1 gebruikt, die op dit moment beschikbaar is.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Genereer de PrivateKey van de ontvanger.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM gebruikt de term EncapsulationKey in plaats van PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Ik heb het gekloond om aan te tonen dat het mogelijk is om de sleutel te extraheren en opnieuw te gebruiken met Bytes() en NewEncapsulationKeyX van de EncapsulationKey.
20    // Natuurlijk, in de praktijk, is dit proces het proces waarin de afzender de EncapsulationKey van de ontvanger, die in de vorm van tekst is gepubliceerd, in een object maakt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // De afzender genereert ciphertext en een gedeelde sleutel met Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Ik heb het met opzet gekloond om te laten zien hoe de privésleutel van de ontvanger wordt opgeslagen en opgehaald.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // De ontvanger Decapsulate de ciphertext met behulp van de privésleutel om een andere gedeelde sleutel te genereren.
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=

Als resultaat kunnen we zien dat gedeelde sleutels van dezelfde grootte worden gegenereerd!

Deze code kan ook worden gecontroleerd in de playground.

Conclusie

De specificaties, beveiligingsniveaus en de grootte van de privésleutel, publieke sleutel, handtekening en ciphertext van elk algoritme kunnen als volgt worden samengevat. Elk van hen heeft een aanzienlijke omvang, wat hun PQC-naam waardig is.

We hopen dat we met deze algoritmen een veilig internet kunnen gebruiken, zelfs in het tijdperk van kwantumcomputers, maar het lijkt onvermijdelijk dat er meer berekeningen nodig zullen zijn door de relatief grotere sleutels en handtekening-/ciphertextgroottes.

Desalniettemin is elk algoritme effectief geïmplementeerd in de programmeertaal Go, dus we hopen dat het actief gebruikt zal worden om je beveiliging op de juiste plaats te waarborgen!