Ervaringen met MLDSA en MLKEM in de Go-taal

Overzicht

Achtergrond

Al geruime tijd wordt het snelle rekenvermogen van kwantumcomputers beschouwd als een bedreiging voor bestaande cryptografische systemen. Traditionele versleutelingsmethoden zoals RSA en ECC lopen het risico te worden gekraakt door dit rekenvermogen. Sinds enkele jaren het concept van kwantumcomputers meer concreet vorm begint te krijgen, zijn er echter alternatieven onderzocht en ontwikkeld, en heeft NIST de standaardisatie van PQC (Post-Quantum Cryptography, kwantumbestendige versleuteling) doorgevoerd.

MLDSA en MLKEM

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

Gittergebaseerde versleuteling is, zoals de naam al aangeeft, een versleutelingssysteem dat berust op de moeilijkheid van wiskundige problemen op een rooster. Hoewel ik zelf geen diepgaande wiskundige kennis hierover heb, wordt het in één zin samengevat als het oplossen van een lineaire vergelijking met ruis in een modulair rooster. Hoe moeilijk dit precies is, is moeilijk in te schatten, maar men zegt dat dit soort problemen zelfs voor kwantumcomputers te moeilijk zijn om op te lossen.

MLDSA

Laten we eerst kijken naar MLDSA.

Opbouw

Zoals de naam al laat zien, is MLDSA een asymmetrisch handtekeningalgoritme dat in totaal de volgende twee stappen doorloopt.

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

Bovendien heeft MLDSA de volgende drie kenmerken.

1. Strong existential unforgeability: met één handtekening en de publieke sleutel kan geen andere geldige handtekening worden gegenereerd.
2. Chosen message attack: ook met handtekeningen voor willekeurige berichten kan met de publieke sleutel geen nieuwe geldige handtekening worden gegenereerd.
3. Side-channel attack: bij het ondertekenen worden steeds nieuwe willekeurige waarden en pseudowillekeurige waarden afgeleid van het bericht gebruikt, wat de beveiliging verhoogt.
4. Domain separation: voor verschillende parameters worden verschillende seeds gebruikt, zodat herhaalde beveiligingsproblemen worden voorkomen.

Code

Hieronder volgt een eenvoudig voorbeeld in de programmeertaal Go. In dit voorbeeld is de mldsa van cloudflare/circl gebruikt.

 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 een handtekening.
22    // Let op: volgens de versie van 22 december 2024 treedt een fout op 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 via het Scheme van de publieke sleutel.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

De handtekeningwaarde is weggelaten omdat deze te lang is. Wilt u de volledige tekst zien, voer dan de code uit op de playground.

Ook al is de handtekening met base64 gecodeerd, het feit dat het 3228 bytes zijn, zal wel enigszins belastend zijn. Wanneer ik bedenk dat we in de nabije toekomst mogelijk handtekeningen van deze omvang moeten uitwisselen om ons tegen kwantumcomputers te beschermen, vind ik dit toch wel een beetje zwaar..

MLKEM

Opbouw

MLKEM is een Key Encapsulation Mechanism (KEM). Een KEM is een algoritme dat met behulp van een asymmetrische versleutelingsmethode een gedeelde sleutel tussen twee partijen kan genereren. Het sleuteluitwisselingsmechanisme van MLKEM verloopt via de volgende stappen.

1. Sleutelinkapseling: de afzender genereert met de publieke sleutel van de ontvanger een versleuteld bericht (ciphertext) en een gedeelde sleutel (shared key). Dit versleutelde bericht wordt eerst aan de ontvanger overgedragen zodat deze het kan gebruiken.
2. Sleutelontkapseling: de ontvanger haalt met zijn of haar privésleutel de gedeelde sleutel uit het versleutelde bericht.

MLKEM kent in totaal drie parameters: MLKEM-512, MLKEM-768 en MLKEM-1024. Hoe kleiner het getal, hoe kleiner de sleutels en het versleutelde bericht; hoe groter het getal, hoe langer de sleutels en het versleutelde bericht, en hoe hoger het beveiligingsniveau.

Code

Aangezien MLKEM naar verwachting in Go 1.24 zal worden toegevoegd, is op dit moment go 1.24rc1 gebruikt, die al 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    // In MLKEM wordt de term EncapsulationKey gebruikt in plaats van PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Om eenvoudig te laten zien dat de EncapsulationKey via Bytes() kan worden geëxtraheerd en via NewEncapsulationKey1024 opnieuw kan worden gebruikt, is deze gekloond.
20    // In de praktijk is dit proces, waarin de EncapsulationKey van de ontvanger die als tekst openbaar is gemaakt door de afzender als object wordt aangemaakt, te zien als de werkelijke situatie.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // De afzender genereert met Encapsulate de ciphertext en de gedeelde sleutel.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Om te laten zien hoe de privésleutel van de ontvanger wordt opgeslagen en teruggehaald, is deze bewust gekloond.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // De ontvanger gebruikt zijn privésleutel om de ciphertext te Decapsulate en genereert zo een andere gedeelde sleutel.
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=

Het resultaat laat zien dat er gedeelde sleutels van dezelfde grootte worden gegenereerd!

Deze code kan ook worden bekeken op de playground.

Conclusie

De specificaties, beveiligingsniveaus en de groottes van privésleutels, publieke sleutels, handtekeningen of ciphertexten van elk algoritme kunnen als volgt worden samengevat. Elk van deze algoritmen toont, passend bij de naam PQC, een flinke omvang.

Met deze algoritmen hopen wij dat we ook in een kwantumcomputertijdperk een voldoende veilig internet kunnen gebruiken, maar door de relatief grotere sleutels en handtekening- en ciphertextgroottes lijkt een toename van het aantal berekeningen onvermijdelijk.

Desalniettemin is Go goed in staat deze algoritmen effectief te implementeren, en wij hopen dat het op de juiste plaatsen actief wordt ingezet om uw veiligheid te waarborgen!