Doświadczenia z użyciem MLDSA i MLKEM w języku Go

Przegląd

Kontekst

Od dość dawna szybkie obliczenia komputerów kwantowych są postrzegane jako zagrożenie dla istniejących systemów kryptograficznych. Dzieje się tak, ponieważ tradycyjne algorytmy, takie jak RSA czy ECC, mogą zostać złamane dzięki tej zdolności obliczeniowej komputerów kwantowych. Jednak od kilku lat koncepcja komputerów kwantowych zaczęła nabierać realnych kształtów, dlatego rozpoczęto badania i rozwój alternatyw, a NIST prowadzi standaryzację kryptografii postkwantowej (PQC).

MLDSA i MLKEM

Ostatecznie w sierpniu 2024 roku NIST przyjął jako standardy MLKEM i MLDSA, oparte na CRYSTALS-Kyber oraz CRYSTALS-Dilithium. Oba algorytmy działają w oparciu o problem MLWE (Module Learning with Errors). Taki rodzaj konstrukcji nazywamy kryptografią opartą na kratach.

Kryptografia oparta na kratach, zgodnie ze swoją nazwą, jest systemem kryptograficznym opartym na trudności problemów matematycznych w kratach. Nie posiadam głębokiej wiedzy matematycznej na ten temat, jednak w jednym zdaniu można to ująć jako problem rozwiązywania zaszumionych równań liniowych w module kraty. Trudno mi wyczuć, jak bardzo jest to trudne, ale podobno tego rodzaju problemów nie da się rozwiązać nawet za pomocą komputerów kwantowych.

MLDSA

Najpierw przyjrzyjmy się MLDSA.

Budowa

MLDSA, jak wskazuje sama nazwa, jest asymetrycznym algorytmem podpisu cyfrowego i przebiega w następujących 2 etapach:

1. Generowanie podpisu: tworzenie podpisu dla wiadomości przy użyciu klucza prywatnego
2. Weryfikacja podpisu: sprawdzanie ważności wygenerowanego podpisu przy użyciu klucza publicznego

Ponadto MLDSA charakteryzuje się następującymi 4 właściwościami:

1. strong existential unforgeability: z jednego podpisu i klucza publicznego nie można wygenerować innego poprawnego podpisu.
2. chosen message attack: nawet na podstawie podpisów dla dowolnie wybranych wiadomości nie można, przy użyciu klucza publicznego, wygenerować nowego poprawnego podpisu.
3. side-channel attack: podczas podpisywania stale wykorzystywane są nowe losowe wartości oraz pseudolosowe wartości wyprowadzane z wiadomości, co zwiększa bezpieczeństwo.
4. domain separation: dla różnych parametrów stosowane są różne seedy, co zapobiega powtarzającym się problemom bezpieczeństwa.

Kod

Przedstawię teraz prosty przykład kodu w języku Go. W tym przykładzie wykorzystano mldsa z 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    // Generujemy klucze w specyfikacji 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    // Generujemy podpis.
22    // Należy zwrócić uwagę, że według wersji aktualnej na dzień 22 grudnia 2024 roku, jeśli crypto.Hash(0) nie zostanie użyty, wystąpi błąd.
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    // Weryfikujemy podpis, wywołując scheme klucza publicznego.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Wartość podpisu jest zbyt długa, dlatego ją pominięto. Jeśli chcesz zobaczyć pełną wersję, uruchom ją na playground.

Mimo zakodowania w base64, wynik wynoszący 3228 bajtów może budzić pewne obawy. Biorąc pod uwagę, że w przyszłości być może będziemy wymieniać podpisy chroniące przed komputerami kwantowymi o tym rozmiarze, jest to trochę niepokojące..

MLKEM

Budowa

MLKEM jest mechanizmem enkapsulacji klucza (Key Encapsulation Mechanism). KEM to algorytm, który pozwala dwóm stronom wygenerować wspólny klucz przy użyciu kryptografii z kluczem publicznym. Mechanizm wymiany kluczy w MLKEM przebiega w następujących etapach:

1. Enkapsulacja klucza: nadawca, korzystając z klucza publicznego odbiorcy, generuje zaszyfrowaną wiadomość (cipher text) oraz klucz współdzielony (shared key). Zaszyfrowaną wiadomość przekazuje najpierw odbiorcy, aby mógł ją wykorzystać.
2. Dekapsulacja klucza: odbiorca, korzystając ze swojego klucza prywatnego, wyodrębnia klucz współdzielony z zaszyfrowanej wiadomości.

MLKEM posiada łącznie 3 parametry: MLKEM-512, MLKEM-768 oraz MLKEM-1024. Im mniejsza wartość, tym mniejsze klucze i tekst zaszyfrowany, a im większa, tym dłuższe klucze i tekst zaszyfrowany oraz wyższy poziom bezpieczeństwa.

Kod

Ponieważ MLKEM ma zostać dodany w Go 1.24, w chwili obecnej wykorzystano go 1.24rc1, dostępne już obecnie.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generujemy PrivateKey odbiorcy.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // W MLKEM używa się terminu EncapsulationKey, a nie PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Aby w prosty sposób pokazać, że klucze można wyodrębnić przez Bytes() i NewEncapsulationKeyX oraz ponownie użyć, klucz został sklonowany.
20    // Oczywiście w praktyce ten proces oznacza, że nadawca tworzy obiekt z EncapsulationKey odbiorcy, który był publicznie udostępniony w formie tekstowej.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Encapsulate: nadawca generuje tekst zaszyfrowany oraz klucz współdzielony.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Klucz został sklonowany celowo, aby pokazać zapisywanie i odczytywanie klucza prywatnego odbiorcy.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Odbiorca, korzystając z klucza prywatnego, dokonuje Decapsulate tekstu zaszyfrowanego i generuje kolejny klucz współdzielony.
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=

W rezultacie można potwierdzić, że generowane są współdzielone klucze o tym samym rozmiarze!

Ten kod można również sprawdzić na playground.

Podsumowanie

Specyfikacje poszczególnych algorytmów, poziomy bezpieczeństwa oraz rozmiary kluczy prywatnych, publicznych, podpisów i tekstów zaszyfrowanych można zestawić w następujący sposób. Każdy z nich, zgodnie z nazwą PQC, charakteryzuje się imponująco dużymi rozmiarami.

Dzięki tym algorytmom mamy nadzieję korzystać z Internetu, który będzie wystarczająco bezpieczny nawet w obliczu komputerów kwantowych, jednak większe klucze oraz rozmiary podpisów i szyfrogramów nieuchronnie wiążą się z większą liczbą obliczeń.

Mimo to język Go zawiera efektywne implementacje tych algorytmów, dlatego mamy nadzieję, że zostaną one aktywnie wykorzystane w odpowiednich miejscach, aby chronić Wasze bezpieczeństwo!