Skúsenosti s používaním MLDSA a MLKEM v jazyku Go

Prehľad

Pozadie

Už dlhší čas sa rýchle výpočty kvantových počítačov považujú za hrozbu pre existujúce kryptografické systémy. Tradičné algoritmy ako RSA alebo ECC by mohli byť dešifrované práve vďaka tejto výpočtovej schopnosti kvantových počítačov. Keď však pred niekoľkými rokmi začal pojem kvantového počítača nadobúdať konkrétnejšie kontúry, začali sa skúmať a vyvíjať alternatívy, a NIST pokračuje v štandardizácii PQC (post-kvantovej kryptografie).

MLDSA a MLKEM

NIST nakoniec v auguste 2024 prijal ako štandardy MLKEM a MLDSA, ktoré vychádzajú z CRYSTALS-Kyber a CRYSTALS-Dilithium. Oba algoritmy fungujú na základe problému MLWE (Module Learning with Errors). Tento typ označujeme ako kryptografiu založenú na mriežkach.

Kryptografia založená na mriežkach je, ako už názov napovedá, kryptografický systém založený na obtiažnosti matematických úloh na mriežkach. Ani ja nemám hlboké matematické znalosti v tejto oblasti, no zhrnuté jednou vetou ide o problém riešenia lineárnych rovníc s šumom v modulárnej mriežke. Aký je to problém v praxi, si neviem celkom predstaviť, no údajne je natoľko náročný, že ho nemožno vyriešiť ani kvantovým počítačom.

MLDSA

Najprv sa pozrieme na MLDSA.

Zloženie

MLDSA je, ako napovedá jeho názov, algoritmus asymetrického podpisu a prebieha v nasledujúcich dvoch krokoch.

1. Generovanie podpisu: pomocou súkromného kľúča sa vytvorí podpis správy
2. Overenie podpisu: pomocou verejného kľúča sa overí platnosť vytvoreného podpisu

MLDSA má navyše tieto tri vlastnosti.

1. strong existential unforgeability: z jedného podpisu a verejného kľúča nemožno vytvoriť iný platný podpis.
2. chosen message attack: ani na základe podpisu ľubovoľnej správy nemožno pomocou verejného kľúča vytvoriť nový platný podpis.
3. side-channel attack: pri podpisovaní sa neustále používajú nové náhodné hodnoty a pseudonáhodné hodnoty odvodené zo správy, čím sa zvyšuje bezpečnosť.
4. domain separation: pre rôzne parametre sa používajú rôzne seedy, čím sa predchádza opakovaným bezpečnostným problémom.

Kód

Teraz ukážem jednoduchý príklad kódu v jazyku Go. V tomto príklade sa používa 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 kľúč 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    // Vytvoríme podpis.
22    // Treba si dať pozor na to, že k dátumu 22. decembra 2024 v aktuálnej verzii vyvolá chybu, ak nie je crypto.Hash(0).
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    // Overenie vykonáme volaním scheme verejného kľúča.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Hodnota podpisu je príliš dlhá, preto bola vynechaná. Ak chcete vidieť celý výstup, spustite ho na playground.

Aj keď je výsledok zakódovaný v base64, 3228 bajtov je isto dosť veľa. Keď si uvedomíme, že v blízkej budúcnosti budeme možno musieť takto veľké podpisy vymieňať kvôli ochrane pred kvantovými počítačmi, je to trochu znepokojujúce..

MLKEM

Zloženie

MLKEM je mechanizmus zapuzdrenia kľúča (Key Encapsulation Mechanism). KEM je algoritmus, ktorý umožňuje vytvoriť zdieľaný kľúč medzi dvoma stranami pomocou šifrovania verejným kľúčom. Výmena kľúčov v MLKEM prebieha v nasledujúcich krokoch.

1. Zapuzdrenie kľúča: odosielateľ pomocou verejného kľúča príjemcu vytvorí zašifrovanú správu (cipher text) a zdieľaný kľúč (shared key). Túto zašifrovanú správu odošle príjemcovi, aby ju mohol použiť.
2. Rozbalenie kľúča: príjemca pomocou svojho súkromného kľúča extrahuje zdieľaný kľúč zo zašifrovanej správy.

MLKEM má celkovo 3 parametre: MLKEM-512, MLKEM-768 a MLKEM-1024. Čím menší parameter, tým menšie kľúče a šifrový text; čím väčší, tým dlhšie kľúče a šifrový text a tým vyššia úroveň bezpečnosti.

Kód

MLKEM má byť pridaný až v Go 1.24, preto som na použitie v súčasnosti zvolil go 1.24rc1.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Vygenerujeme súkromný kľúč príjemcu.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // V MLKEM sa namiesto pojmu PublicKey používa pojem EncapsulationKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Pre jednoduchosť sme EncapsulationKey extrahovali pomocou Bytes() a znova vytvorili pomocou NewEncapsulationKeyX, aby sme ukázali, že ho možno znova použiť.
20    // V praxi ide o to, že odosielateľ z textovej podoby verejného EncapsulationKey príjemcu, ktorý je zverejnený, vytvorí objekt.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Pomocou Encapsulate odosielateľ vytvorí šifrovaný text a zdieľaný kľúč.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Úmyselne klonujeme, aby sme ukázali uloženie a obnovenie súkromného kľúča príjemcu.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Príjemca pomocou svojho súkromného kľúča Decapsulate šifrovaný text a vytvorí ď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=

Výsledkom je, že sa vytvoria zdieľané kľúče rovnakej veľkosti, čo môžeme overiť!

Tento kód si môžete vyskúšať aj na playground.

Záver

Špecifikácie jednotlivých algoritmov, úroveň bezpečnosti a veľkosti súkromného kľúča, verejného kľúča, podpisu alebo šifrového textu možno zhrnúť takto. Každý z nich sa právom môže hrdiť názvom PQC a má pomerne veľké rozmery.

Týmito algoritmami dúfame, že na internete budeme môcť bezpečne komunikovať aj v prostredí kvantových počítačov, no vzhľadom na väčšie kľúče a podpisy/šifrové texty sa zrejme nevyhneme vyššej výpočtovej záťaži.

Jazyk Go má však jednotlivé algoritmy efektívne implementované, preto dúfam, že sa budú na vhodných miestach aktívne využívať na ochranu vašej bezpečnosti!