Použití MLDSA a MLKEM v jazyce Go

Přehled

Pozadí

Již poměrně dlouhou dobu je rychlá výpočetní kapacita kvantových počítačů vnímána jako hrozba pro stávající kryptografické systémy. Je tomu tak proto, že stávající systémy jako RSA nebo ECC by mohly být kvůli této výpočetní schopnosti kvantových počítačů potenciálně dešifrovány. Nicméně, před několika lety, s nástupem konceptu kvantových počítačů, začaly být zkoumány a vyvíjeny alternativy a NIST standardizoval PQC (Post-Quantum Cryptography).

MLDSA a MLKEM

NIST nakonec v srpnu 2024 přijal MLKEM a MLDSA, založené na CRYSTALS-Kyber a CRYSTALS-Dilithium, jako standardy. Oba algoritmy fungují na základě problému MLWE (Module Learning with Errors). Tento formát nazýváme kryptografie založená na mřížkách.

Kryptografie založená na mřížkách je, jak název napovídá, kryptografický systém založený na obtížnosti matematických problémů na mřížce. Ačkoli nemám komplexní matematické znalosti v této oblasti, lze to shrnout do jedné věty: „Problém řešení lineárních rovnic s šumem v modulární mřížce.“ I když si nedokážu představit, jak obtížné to je, uvádí se, že tyto problémy jsou tak obtížné, že je nelze vyřešit ani pomocí kvantových počítačů.

MLDSA

Nyní se podívejme na MLDSA.

Konfigurace

MLDSA, jak název napovídá, je asymetrický podpisový algoritmus, který prochází následujícími dvěma fázemi:

1. Generování podpisu: Použití soukromého klíče k vytvoření podpisu pro zprávu.
2. Ověření podpisu: Použití veřejného klíče k ověření platnosti vytvořeného podpisu.

MLDSA má navíc následující tři vlastnosti:

1. strong existential unforgeability: Z jednoho podpisu a veřejného klíče nelze vytvořit jiný platný podpis.
2. chosen message attack: Nelze vytvořit nový platný podpis s veřejným klíčem z podpisu pro jakoukoli zprávu.
3. 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ž zajišťuje vysokou úroveň zabezpečení.
4. domain separation: Zabraňuje opakovaným bezpečnostním problémům tím, že se pro různé parametry používají různé seed.

Kód

Nyní vám ukážu jednoduchý příklad kódu v jazyce Go. Tento příklad používá 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    // Generuje klíče se specifikací 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    // Generuje podpis.
22    // Jedna věc, na kterou je třeba si dát pozor, je, že k 22. prosinci 2024, s aktuální verzí, 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ěřuje 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 byla vynechána, protože je příliš dlouhá. Pokud si přejete vidět celý text, spusťte jej na playground.

I když je zakódován v base64, 3228 bajtů může být trochu zatěžující. Je trochu znepokojivé, když si pomyslíme, že v blízké budoucnosti možná budeme muset vyměňovat takové velikosti pro podpisy odolné proti kvantovým počítačům.

MLKEM

Konfigurace

MLKEM je Key Encapsulation Mechanism. KEM je algoritmus, který umožňuje generování sdílených klíčů mezi dvěma stranami pomocí asymetrického šifrování. Mechanismus výměny klíčů MLKEM prochází následujícími kroky:

1. Encapsulation klíče: Odesílatel používá veřejný klíč příjemce k vytvoření šifrované zprávy (cipher text) a sdíleného klíče (shared key). Tato šifrovaná zpráva je zpočátku předána příjemci k použití.
2. Decapsulation klíče: Příjemce používá svůj soukromý klíč k extrakci sdíleného klíče ze šifrované zprávy.

MLKEM má celkem tři parametry: MLKEM-512, MLKEM-768 a MLKEM-1024. Čím menší je číslo, tím menší je klíč a šifrovaný text, a čím větší je číslo, tím delší je klíč a šifrovaný text, a tím vyšší je úroveň zabezpečení.

Kód

MLKEM má být přidán do Go 1.24, takže v tuto chvíli byla použita verze Go 1.24rc1.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Generuje PrivateKey příjemce.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM používá termín EncapsulationKey namísto PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Jednoduchá demonstrace, že klíče lze extrahovat a znovu použít pomocí Bytes() a NewEncapsulationKeyX z EncapsulationKey.
20    // Samozřejmě, v reálném světě by tento proces představoval, jak odesílatel vytvoří objekt z EncapsulationKey příjemce, který byl zveřejněn jako text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Odesílatel generuje šifrovaný text a sdílený klíč pomocí Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Úmyslně jsem klonoval privátní klíč příjemce, abych ukázal, jak se ukládá a načítá.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Příjemce používá svůj privátní klíč k Decapsulate šifrovaného textu a generuje 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 vidíme, že jsou generovány sdílené klíče stejné velikosti!

Tento kód je k dispozici také na playground.

Závěr

Specifikace, úroveň zabezpečení, velikosti soukromého klíče, veřejného klíče, podpisu a šifrovaného textu pro každý algoritmus lze shrnout následovně. Každý z nich se může pochlubit značnou velikostí, což odpovídá označení PQC.

Očekáváme, že tyto algoritmy nám umožní používat internet, který je dostatečně bezpečný i proti kvantovým počítačům, nicméně se zdá, že se nelze vyhnout většímu počtu operací kvůli relativně větším klíčům a velikostem podpisu/šifrovaného textu.

Přestože jsou tyto algoritmy efektivně implementovány v jazyce Go, doufáme, že budou aktivně využívány k ochraně vašeho zabezpečení na vhodných místech!