Zkušenosti s používáním MLDSA a MLKEM v jazyce Go

Přehled

Pozadí

Už poměrně dlouho je rychlé výpočetní řešení kvantových počítačů vnímáno jako hrozba pro stávající kryptografické systémy. Je tomu tak proto, že tradiční systémy RSA a ECC by mohly být díky této výpočetní schopnosti kvantových počítačů prolomeny. Před několika lety se však koncept kvantových počítačů začal konkretizovat, a proto začaly být zkoumány a vyvíjeny jejich alternativy; NIST zároveň pokračuje v standardizaci PQC (post-kvantové kryptografie).

MLDSA a MLKEM

Nakonec NIST v srpnu 2024 přijal jako standardy MLKEM a MLDSA, které vycházejí z CRYSTALS-Kyber a CRYSTALS-Dilithium. Oba algoritmy fungují na základě problému MLWE (Module Learning with Errors). Tento typ označujeme jako kryptografii založenou na mřížkách.

Kryptografie založená na mřížkách je, jak už název napovídá, kryptografický systém založený na obtížnosti matematických úloh nad mřížkami. Ani já nemám hluboké matematické znalosti v této oblasti, ale shrnuto do jedné věty se říká, že jde o problém řešení lineárních rovnic s šumem v modulární mřížce. Není mi jasné, jak obtížný tento problém je, ale říká se, že je natolik náročný, že jej nelze vyřešit ani kvantovými počítači.

MLDSA

Nejprve se tedy podívejme na MLDSA.

Struktura

Jak již napovídá název, MLDSA je asymetrický podpisový algoritmus, který prochází následujícími dvěma kroky:

1. Generování podpisu: vytvoření podpisu zprávy pomocí soukromého klíče
2. Ověření podpisu: ověření platnosti vygenerovaného podpisu pomocí veřejného klíče

MLDSA dále disponuje těmito čtyřmi vlastnostmi:

1. Silná existenční nepadělatelnost (strong existential unforgeability): z jednoho podpisu a veřejného klíče nelze vytvořit jiný platný podpis.
2. Útok volenou zprávou (chosen message attack): ani podpis libovolné zprávy nedovolí s použitím veřejného klíče vytvořit nový platný podpis.
3. Postranní kanálové útoky (side-channel attack): při podepisování se neustále používají nové náhodné hodnoty a pseudonáhodné hodnoty odvozené ze zprávy, což zvyšuje bezpečnost.
4. Oddělení domén (domain separation): pro různé parametry se používají různé seedy, čímž se předchází opakovaným bezpečnostním problémům.

Kód

Nyní si ukažme jednoduchý příklad kódu v jazyce Go. V tomto příkladu byl použit modul 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    // Vygenerujeme klíč podle specifikace 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    // Vytvoříme podpis.
22    // Jedna věc, na kterou je třeba dát pozor: podle verze aktuální k 22. prosinci 2024 dojde k chybě, pokud crypto.Hash(0) není použito.
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    // Ověření provedeme voláním scheme veřejného klíče.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Hodnota podpisu je příliš dlouhá, proto byla vynechána. Pokud si chcete prohlédnout úplný výstup, spusťte kód na playground.

I když je podpis zakódován pomocí base64, délka 3228 bajtů je poměrně znepokojivá. Když si uvědomíme, že v budoucnu budeme možná muset takto velké podpisy vyměňovat jako ochranu proti kvantovým počítačům, je to trochu znepokojivé...

MLKEM

Struktura

MLKEM je mechanismus zapouzdření klíče (Key Encapsulation Mechanism). KEM je algoritmus, který pomocí asymetrické kryptografie umožňuje vytvořit sdílený klíč mezi dvěma stranami. Výměna klíčů v MLKEM probíhá následovně:

1. Zapouzdření klíče: odesílatel pomocí veřejného klíče příjemce vytvoří zašifrovanou zprávu (cipher text) a sdílený klíč (shared key). Tuto zašifrovanou zprávu odešle příjemci, aby ji mohl použít.
2. Rozbalení klíče: příjemce pomocí svého soukromého klíče extrahuje sdílený klíč ze zašifrované zprávy.

MLKEM má celkem 3 parametry: MLKEM-512, MLKEM-768 a MLKEM-1024. Čím nižší číslo, tím menší klíče a šifrovaný text; čím vyšší číslo, tím delší klíče a šifrovaný text a tím vyšší úroveň zabezpečení.

Kód

Protože MLKEM bude přidán až v Go 1.24, byla použita verze go 1.24rc1, která je k dispozici již nyní.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Vytvoříme soukromý klíč příjemce.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM nepoužívá termín PublicKey, ale EncapsulationKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Pro jednoduchost jsme klíč EncapsulationKey zkopírovali, abychom ukázali, že jej lze extrahovat pomocí Bytes() a znovu použít pomocí NewEncapsulationKeyX.
20    // V praxi tento krok odpovídá tomu, že odesílatel z veřejně zveřejněného textového EncapsulationKey příjemce vytvoří objekt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Pomocí Encapsulate odesílatel vytvoří šifrovaný text a sdílený klíč.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Zkopírovali jsme soukromý klíč příjemce záměrně, abychom ukázali uložení a načtení soukromého klíče.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Příjemce pomocí soukromého klíče provede Decapsulate šifrovaného textu a vytvoří další sdílený klíč.
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=

Výsledkem je, že se vytvoří sdílený klíč stejné velikosti, což lze ověřit!

Tento kód si můžete prohlédnout také na playground.

Závěr

Specifikace jednotlivých algoritmů, úrovně zabezpečení a velikosti soukromých klíčů, veřejných klíčů, podpisů a šifrovaných textů lze shrnout do následující tabulky. Každý z nich si vede s názvem PQC dobře a nabízí značné rozměry.

Díky těmto algoritmům doufáme, že budeme moci používat internet, který zůstane dostatečně bezpečný i v prostředí kvantových počítačů. Relativně větší klíče a podpisy či šifrované texty však zřejmě nevyhnutelně přinesou vyšší výpočetní náročnost.

Jazyk Go má každý z těchto algoritmů efektivně implementovaný, a proto doufám, že budou na vhodných místech aktivně využívány k ochraně vaší bezpečnosti!