Použitie MLDSA a MLKEM v jazyku Go

Prehľad

Pozadie

Už pomerne dlho sa rýchly výpočtový výkon kvantových počítačov vníma ako hrozba pre existujúce kryptografické systémy. Je to preto, že existujúce systémy ako RSA alebo ECC by mohli byť dešifrované vďaka takýmto výpočtovým schopnostiam kvantových počítačov. Avšak, keďže sa koncept kvantových počítačov stal hmatateľným pred niekoľkými rokmi, začali sa skúmať a vyvíjať alternatívy, a NIST štandardizoval PQC (Post-Quantum Cryptography).

MLDSA a MLKEM

NIST nakoniec v auguste 2024 prijal MLKEM a MLDSA, založené na CRYSTALS-Kyber a CRYSTALS-Dilithium, ako štandardy. Oba algoritmy fungujú na základe problému MLWE (Module Learning with Errors). Tento formát nazývame kryptografia založená na mriežke.

Kryptografia založená na mriežke je, ako už názov napovedá, kryptografický systém založený na obtiažnosti matematických problémov na mriežke. Hoci nemám hlboké matematické znalosti v tejto oblasti, možno to zhrnúť jednou vetou ako „problém riešenia lineárnych rovníc s šumom v modulárnej mriežke“. Je ťažké odhadnúť, aké je to náročné, ale hovorí sa, že tieto problémy sú tak ťažké, že ich nedokážu vyriešiť ani kvantové počítače.

MLDSA

Najprv sa pozrime na MLDSA.

Konfigurácia

MLDSA, ako už názov napovedá, je asymetrický podpisový algoritmus, ktorý prechádza nasledujúcimi dvoma fázami:

1. Generovanie podpisu: Vytvorenie podpisu pre správu pomocou súkromného kľúča.
2. Overenie podpisu: Overenie platnosti vygenerovaného podpisu pomocou verejného kľúča.

MLDSA má nasledujúce 3 vlastnosti:

1. strong existential unforgeability: S jedným podpisom a verejným kľúčom nie je možné vygenerovať iný platný podpis.
2. chosen message attack: S verejným kľúčom nie je možné vygenerovať nový platný podpis z podpisu pre akúkoľvek správu.
3. side-channel attack: Pri podpisovaní sa neustále používajú nové náhodné hodnoty a pseudo-náhodné hodnoty odvodené zo správy, čo zvyšuje bezpečnosť.
4. domain separation: Zabraňuje opakovaným bezpečnostným problémom použitím rôznych seedov pre rôzne parametre.

Kód

Teraz vám ukážem jednoduchý príklad kódu v jazyku Go. V tomto príklade som použil 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 kľúče so špecifikáciou 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 vec, na ktorú treba pamätať, je, že k 22. decembru 2024 aktuálna verzia vyvolá chybu, ak crypto.Hash(0) nie je použité.
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    // Overuje volaním schémy verejného kľúča.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Hodnota podpisu bola príliš dlhá, takže som ju vynechal. Ak si chcete pozrieť celú správu, spustite ju v playground.

Je trochu zaťažujúce, že zakódovaná hodnota base64 má 3228 bajtov. Je trochu znepokojujúce pomyslieť si, že možno budeme musieť vymieňať podpisy tejto veľkosti, aby sme sa bránili kvantovým počítačom v blízkej budúcnosti.

MLKEM

Konfigurácia

MLKEM je mechanizmus zapuzdrenia kľúča (Key Encapsulation Mechanism). KEM je algoritmus, ktorý umožňuje dvom stranám generovať zdieľaný kľúč pomocou metódy šifrovania s verejným kľúčom. Mechanizmus výmeny kľúčov MLKEM prebieha nasledujúcim procesom:

1. Zapuzdrenie kľúča: Odosielateľ generuje šifrovanú správu (cipher text) a zdieľaný kľúč (shared key) pomocou verejného kľúča príjemcu. Táto šifrovaná správa sa pôvodne prenáša príjemcovi na použitie.
2. Dekapsulácia kľúča: Príjemca extrahuje zdieľaný kľúč zo šifrovanej správy pomocou svojho súkromného kľúča.

MLKEM má celkovo 3 parametre. Existujú MLKEM-512, MLKEM-768 a MLKEM-1024, pričom menšie čísla vedú k menším kľúčom a šifrovanému textu a väčšie čísla k dlhším kľúčom a šifrovanému textu, s vyššou úrovňou zabezpečenia.

Kód

MLKEM má byť pridaný v Go 1.24, takže som použil Go 1.24rc1, ktorý je k dispozícii v súčasnosti.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Vygeneruje PrivateKey príjemcu.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // V MLKEM sa namiesto PublicKey používa termín EncapsulationKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Klonovalo sa, aby sa ukázalo, že EncapsulationKey možno extrahovať a znova použiť pomocou Bytes() a NewEncapsulationKeyX.
20    // V reálnom scenári by tento proces predstavoval, ako odosielateľ vytvorí objekt z EncapsulationKey príjemcu, ktorý bol verejne dostupný ako text.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Odosielateľ generuje šifrovaný text a zdieľaný kľúč pomocou Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Zámerne som klonoval súkromný kľúč príjemcu, aby som ukázal, ako sa ukladá a načítava.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Príjemca používa súkromný kľúč na dekapsuláciu šifrovaného textu a generuje ďalší zdieľaný kľúč.
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=

Vo výsledku vidíme, že sa vygenerujú zdieľané kľúče rovnakej veľkosti!

Tento kód si môžete pozrieť aj na playground.

Záver

Špecifikácie, úrovne zabezpečenia, veľkosti súkromných kľúčov, verejných kľúčov, podpisov a šifrovaných textov každého algoritmu možno zhrnúť nasledovne. Každý z nich sa pýši značnou veľkosťou, čo je v súlade s označením PQC.

Očakávame, že vďaka týmto algoritmom budeme môcť používať dostatočne bezpečný internet aj s kvantovými počítačmi, avšak zdá sa, že sa nedá vyhnúť väčšiemu počtu operácií v dôsledku relatívne zväčšenej veľkosti kľúčov a podpisov/šifrovaných textov.

Napriek tomu, keďže sú algoritmy efektívne implementované v jazyku Go, dúfame, že budú aktívne využívané na ochranu vašej bezpečnosti na vhodných miestach!