Die Verwendung von MLDSA und MLKEM in der Go-Programmiersprache

Übersicht

Hintergrund

Schon seit geraumer Zeit wird die rasche Rechenleistung von Quantencomputern als Bedrohung für bestehende Verschlüsselungssysteme angesehen. Bestehende Systeme wie RSA oder ECC könnten aufgrund dieser Rechenleistung von Quantencomputern möglicherweise entschlüsselt werden. Mit der zunehmenden Konkretisierung des Konzepts von Quantencomputern in den letzten Jahren wurden jedoch Alternativen erforscht und entwickelt, und das NIST hat die Standardisierung von PQC (Post-Quantum-Kryptographie) vorangetrieben.

MLDSA und MLKEM

Schließlich hat das NIST im August 2024 MLKEM und MLDSA, basierend auf CRYSTALS-Kyber und CRYSTALS-Dilithium, als Standards übernommen. Beide Algorithmen basieren auf dem Problem des MLWE (Module Learning with Errors). Diese Form nennen wir gitterbasierte Kryptographie.

Gitterbasierte Kryptographie ist, wie der Name schon sagt, ein Verschlüsselungssystem, das auf der Schwierigkeit mathematischer Probleme auf einem Gitter basiert. Ich selbst habe keine tiefergehenden mathematischen Kenntnisse darüber, aber zusammenfassend lässt es sich als das Lösen einer verrauschten linearen Gleichung in einem Modulgitter beschreiben. Wie schwierig das ist, ist schwer zu sagen, aber es heißt, dass dieses Problem so schwierig ist, dass es selbst von Quantencomputern nicht gelöst werden kann.

MLDSA

Betrachten wir zunächst MLDSA genauer.

Struktur

MLDSA ist, wie der Name schon sagt, ein asymmetrischer Signaturalgorithmus, der insgesamt die folgenden zwei Schritte durchläuft:

1. Signaturerstellung: Erstellung einer Signatur für eine Nachricht unter Verwendung des privaten Schlüssels.
2. Signaturüberprüfung: Überprüfung der Gültigkeit der erstellten Signatur unter Verwendung des öffentlichen Schlüssels.

MLDSA hat darüber hinaus die folgenden drei Eigenschaften:

1. strong existential unforgeability: Es ist nicht möglich, mit einer Signatur und einem öffentlichen Schlüssel eine andere gültige Signatur zu erstellen.
2. chosen message attack: Es ist nicht möglich, mit einer Signatur für eine beliebige Nachricht mit einem öffentlichen Schlüssel eine neue gültige Signatur zu erstellen.
3. side-channel attack: Bei der Signatur werden fortlaufend neue Zufallswerte und von der Nachricht abgeleitete Pseudozufallswerte verwendet, was die Sicherheit erhöht.
4. domain separation: Es wird sichergestellt, dass für unterschiedliche Parameter unterschiedliche Seeds verwendet werden, um wiederholende Sicherheitsprobleme zu vermeiden.

Code

Hier ist ein einfaches Beispiel in Go. In diesem Beispiel wurde cloudflare/circl (github.com/cloudflare/circl) mldsa 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 Schlüssel mit der mldsa44-Spezifikation.
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 eine Signatur.
22    // Beachten Sie, dass ab dem 22. Dezember 2024, basierend auf der aktuellen Version, 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    // Führt eine Verifizierung durch, indem das Schema des öffentlichen Schlüssels aufgerufen wird.
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 Wert sehen möchten, führen Sie ihn auf playground aus.

Es ist etwas belastend, dass, obwohl es in base64 kodiert ist, 3228 Bytes entstehen. Es ist etwas beunruhigend, wenn man bedenkt, dass wir diese Größe möglicherweise bald als Signatur verwenden müssen, um uns vor Quantencomputern zu schützen.

MLKEM

Struktur

MLKEM ist ein Key Encapsulation Mechanism (Schlüsselverkapselungsmechanismus). KEM ist ein Algorithmus, der es zwei Parteien ermöglicht, mithilfe von Public-Key-Kryptografie einen gemeinsamen Schlüssel zu generieren. Der Schlüsselaustauschmechanismus von MLKEM läuft wie folgt ab:

1. Schlüsselverkapselung: Der Sender generiert 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 dem Empfänger zunächst übermittelt, damit er sie nutzen kann.
2. Schlüsselentkapselung: Der Empfänger extrahiert den gemeinsamen Schlüssel aus der verschlüsselten Nachricht mithilfe seines privaten Schlüssels.

MLKEM hat insgesamt drei Parameter. Es gibt MLKEM-512, MLKEM-768 und MLKEM-1024. Je kleiner die Zahl, desto kleiner sind der Schlüssel und der verschlüsselte Text. Je größer die Zahl, desto länger sind der Schlüssel und der verschlüsselte Text und desto höher ist das Sicherheitsniveau.

Code

MLKEM wird voraussichtlich in Go 1.24 hinzugefügt, daher wurde Go 1.24rc1 verwendet, das zum jetzigen Zeitpunkt 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    // In MLKEM wird der Begriff EncapsulationKey anstelle von PublicKey verwendet.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    //  Einfachheitshalber wurde der Schlüssel dupliziert, um zu zeigen, dass der Schlüssel mit EncapsulationKey.Bytes() extrahiert und mit NewEncapsulationKeyX wiederverwendet werden kann.
20    // In der Praxis würde dieser Prozess jedoch darin bestehen, dass der Absender den EncapsulationKey-Schlüssel des Empfängers, der als Text veröffentlicht wurde, in ein Objekt umwandelt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Der Absender erzeugt mit Encapsulate einen verschlüsselten Text und einen gemeinsamen Schlüssel.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Der Empfänger dupliziert den privaten Schlüssel absichtlich, um zu zeigen, wie er gespeichert und abgerufen wird.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Der Empfänger decapsuliert den verschlüsselten Text mit dem privaten Schlüssel 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=

Es kann festgestellt werden, dass als Ergebnis gemeinsame Schlüssel gleicher Größe generiert werden!

Dieser Code kann auch im Playground eingesehen werden.

Fazit

Die Spezifikationen, Sicherheitsniveaus und Größen von privaten Schlüsseln, öffentlichen Schlüsseln, Signaturen oder Chiffretexten der einzelnen Algorithmen sind wie folgt zusammengefasst. Sie alle haben eine beachtliche Größe, was ihrem Namen als PQC gerecht wird.

Wir hoffen, dass wir mit diesen Algorithmen auch auf Quantencomputern ein ausreichend sicheres Internet nutzen können, aber es scheint unvermeidlich, dass aufgrund der relativ großen Schlüssel- und Signatur-/Chiffretextgrößen mehr Berechnungen erforderlich sein werden.

Da jedoch die jeweiligen Algorithmen in Go effizient implementiert sind, hoffen wir, dass sie an geeigneter Stelle aktiv zur Wahrung Ihrer Sicherheit eingesetzt werden können!