Erfahrungsbericht zur Verwendung von MLDSA und MLKEM in der Programmiersprache Go

Übersicht

Hintergrund

Seit geraumer Zeit wird die schnelle Rechenleistung von Quantencomputern als Bedrohung für bestehende Verschlüsselungssysteme angesehen. Herkömmliche Verfahren wie RSA oder ECC könnten aufgrund dieser Rechenfähigkeit von Quantencomputern entschlüsselt werden. Seit einigen Jahren, als das Konzept des Quantencomputers zunehmend Gestalt annahm, begann man jedoch, Alternativen zu erforschen und zu entwickeln, und das NIST hat die Standardisierung von PQC (Post-Quantum-Kryptografie) vorangetrieben.

MLDSA und MLKEM

Schließlich hat das NIST im August 2024 MLKEM und MLDSA, die auf CRYSTALS-Kyber und CRYSTALS-Dilithium basieren, als Standards angenommen. Beide Algorithmen beruhen auf dem Problem Module Learning with Errors (MLWE). Diese Art von Verfahren bezeichnen wir als gitterbasierte Kryptografie.

Gitterbasierte Kryptografie ist, wie der Name schon sagt, ein Verschlüsselungssystem, das auf der Schwierigkeit mathematischer Probleme auf Gittern beruht. Auch ich verfüge über kein tiefgehendes mathematisches Wissen dazu, doch lässt sich das Ganze in einem Satz zusammenfassen als das Problem, lineare Gleichungen mit Rauschen in einem Modul-Gitter zu lösen. Wie schwierig das genau ist, lässt sich nur schwer einschätzen, doch heißt es, dass dieses Problem selbst für Quantencomputer nicht lösbar ist.

MLDSA

Zunächst wollen wir uns MLDSA ansehen.

Aufbau

Wie der Name bereits andeutet, ist MLDSA ein asymmetrischer Signaturalgorithmus, der insgesamt die folgenden zwei Schritte durchläuft:

1. Signaturerzeugung: Mithilfe des privaten Schlüssels wird eine Signatur für eine Nachricht erzeugt
2. Signaturverifikation: Mithilfe des öffentlichen Schlüssels wird die Gültigkeit der erzeugten Signatur überprüft

Darüber hinaus weist MLDSA die folgenden drei Eigenschaften auf:

1. Strong Existential Unforgeability: Aus einer Signatur und dem öffentlichen Schlüssel lässt sich keine andere gültige Signatur erzeugen.
2. Chosen Message Attack: Auch mit Signaturen zu beliebigen Nachrichten lässt sich unter Verwendung des öffentlichen Schlüssels keine neue gültige Signatur erzeugen.
3. Side-Channel Attack: Bei der Signaturerzeugung werden stets neue Zufallswerte und pseudozufällige Werte verwendet, die aus der Nachricht abgeleitet werden, wodurch das Sicherheitsniveau hoch ist.
4. Domain Separation: Für unterschiedliche Parameter werden unterschiedliche Seeds verwendet, um wiederholte Sicherheitsprobleme zu vermeiden.

Code

Nun zeige ich Ihnen ein einfaches Beispiel in der Programmiersprache Go. In diesem Beispiel wurde das mldsa-Paket aus cloudflare/circl verwendet.

 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    // Erzeugt einen Schlüssel gemäß der Spezifikation mldsa44.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Erzeugt die Signatur.
22    // Zu beachten ist, dass nach dem Stand der Version vom 22. Dezember 2024 ein Fehler auftritt, wenn crypto.Hash(0) nicht verwendet wird.
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    // Ruft das Scheme des öffentlichen Schlüssels auf, um die Verifikation durchzuführen.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Der Signaturwert wurde aufgrund seiner Länge weggelassen. Wenn Sie den vollständigen Text sehen möchten, führen Sie das Programm bitte im Playground aus.

Auch wenn er base64-kodiert wurde, ist es sicherlich etwas belastend, dass 3228 Bytes entstehen. Wenn man bedenkt, dass wir womöglich bald Signaturen zum Schutz vor Quantencomputern in dieser Größe austauschen müssen, ist das schon ein wenig beunruhigend ..

MLKEM

Aufbau

MLKEM ist ein Key Encapsulation Mechanism (Schlüsselkapselungsmechanismus). KEM ist ein Algorithmus, der es ermöglicht, mithilfe eines Public-Key-Verschlüsselungsverfahrens einen gemeinsamen Schlüssel zwischen zwei Parteien zu erzeugen. Der Schlüsselaustauschmechanismus von MLKEM durchläuft die folgenden Schritte:

1. Schlüsselkapselung: Der Sender erzeugt mithilfe des öffentlichen Schlüssels des Empfängers eine verschlüsselte Nachricht (Ciphertext) und einen gemeinsamen Schlüssel (Shared Key). Diese verschlüsselte Nachricht wird zunächst an den Empfänger übermittelt, damit dieser sie verwenden kann.
2. Schlüsselkapselung aufheben: Der Empfänger extrahiert mithilfe seines privaten Schlüssels den gemeinsamen Schlüssel aus der verschlüsselten Nachricht.

MLKEM umfasst insgesamt drei Parameter: MLKEM-512, MLKEM-768 und MLKEM-1024. Je kleiner der Parameter, desto kleiner die Schlüssel und Chiffretexte; je größer der Parameter, desto länger die Schlüssel und Chiffretexte, und desto höher das Sicherheitsniveau.

Code

Da MLKEM voraussichtlich in Go 1.24 aufgenommen wird, wurde für den gegenwärtigen Zeitpunkt Go 1.24rc1 verwendet, das bereits verfügbar ist.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Erzeugt den PrivateKey des Empfängers.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // Bei MLKEM wird nicht der Begriff PublicKey, sondern EncapsulationKey verwendet.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Zur einfachen Demonstration, dass sich der EncapsulationKey über Bytes() extrahieren und mit NewEncapsulationKey1024 wieder verwenden lässt, wurde er kopiert.
20    // Im realen Einsatz entspricht dieser Schritt dem Vorgang, bei dem der Sender den als Text veröffentlichten EncapsulationKey des Empfängers in ein Objekt umwandelt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Mit Encapsulate erzeugt der Sender den Chiffretext und den gemeinsamen Schlüssel.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Der Schlüssel wurde absichtlich kopiert, um zu zeigen, wie der private Schlüssel des Empfängers gespeichert und wieder abgerufen wird.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Der Empfänger führt mit seinem privaten Schlüssel Decapsulate auf dem Chiffretext aus und erzeugt so einen weiteren gemeinsamen Schlüssel.
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=

Im Ergebnis lässt sich bestätigen, dass ein gemeinsamer Schlüssel von gleicher Größe erzeugt wird!

Dieser Code kann auch im Playground eingesehen werden.

Fazit

Die Spezifikationen der einzelnen Algorithmen, ihre Sicherheitsniveaus sowie die Größen der privaten Schlüssel, öffentlichen Schlüssel und Signaturen bzw. Chiffretexte lassen sich wie folgt zusammenfassen. Sie alle weisen, dem Namen PQC durchaus würdig, beachtliche Größen auf.

Mit diesen Algorithmen hoffen wir, auch im Zeitalter der Quantencomputer ein hinreichend sicheres Internet nutzen zu können; allerdings scheint der höhere Rechenaufwand aufgrund der vergrößerten Schlüssel sowie der größeren Signaturen bzw. Chiffretexte unvermeidlich zu sein.

Dennoch hoffen wir, dass Go, da die einzelnen Algorithmen darin effizient implementiert sind, an geeigneten Stellen aktiv dazu beiträgt, Ihre Sicherheit zu schützen!