Kokemuksia MLDSA:n ja MLKEM:n käytöstä Go-kielessä

Yleiskatsaus

Tausta

Kvanttitietokoneiden nopea laskenta on jo pitkään nähty uhkana nykyisille salausjärjestelmille. Perinteiset menetelmät, kuten RSA ja ECC, saattavat murtua tämänkaltaisen laskentakyvyn avulla. Kun kvanttitietokoneen käsite alkoi kuitenkin konkretisoitua muutama vuosi sitten, alettiin tutkia ja kehittää vaihtoehtoisia ratkaisuja, ja NIST on edistänyt PQC (kvanttikestävä salaus) -standardointia.

MLDSA ja MLKEM

Lopulta NIST hyväksyi elokuussa 2024 standardeiksi CRYSTALS-Kyberiin ja CRYSTALS-Dilithiumiin perustuvat MLKEM:n ja MLDSA:n. Molemmat algoritmit perustuvat MLWE (Module Learning with Errors) -ongelmaan. Tällaista muotoa kutsumme hilapohjaiseksi salaukseksi.

Hilapohjainen salaus on, kuten nimensäkin perusteella voi päätellä, salausjärjestelmä, joka perustuu hilalla esiintyvien matemaattisten ongelmien vaikeuteen. Minulla ei ole syvällistä matemaattista osaamista tästä aiheesta, mutta yhdellä lauseella tiivistettynä se on ongelma, jossa ratkaistaan kohinaa sisältäviä lineaarisia yhtälöitä modulihilalla. Vaikeusastetta on vaikea hahmottaa, mutta tämänkaltaisten ongelmien sanotaan olevan niin vaikeita, etteivät ne ratkea kvanttitietokoneillakaan.

MLDSA

Tarkastellaan ensin MLDSA:ta.

Rakenne

MLDSA on nimestäkin ilmenevä epäsymmetrinen allekirjoitusalgoritmi, ja se etenee seuraavien kahden vaiheen kautta:

1. Allekirjoituksen luonti: viestille luodaan allekirjoitus yksityistä avainta käyttäen
2. Allekirjoituksen varmennus: luodun allekirjoituksen voimassaolo tarkistetaan julkisen avaimen avulla

Lisäksi MLDSA:lla on seuraavat kolme ominaisuutta:

1. Vahva olemassaolon väärennettävyyden kestävyys (strong existential unforgeability): yhdestä allekirjoituksesta ja julkisesta avaimesta ei voida luoda toista pätevää allekirjoitusta.
2. Valitun viestin hyökkäys (chosen message attack): minkään viestin allekirjoituksen perusteella ei voida julkisen avaimen avulla luoda uutta pätevää allekirjoitusta.
3. Sivukanavahyökkäys (side-channel attack): allekirjoituksen yhteydessä käytetään jatkuvasti uusia satunnaisarvoja ja viestistä johdettuja pseudosatunnaisarvoja, minkä vuoksi turvallisuus on korkea.
4. Toimialueen erottelu (domain separation): eri parametreille käytetään eri siemeniä, mikä ehkäisee toistuvia turvallisuusongelmia.

Koodi

Esitellään seuraavaksi yksinkertainen Go-kielinen esimerkkikoodi. Tässä esimerkissä on käytetty cloudflare/circl:n mldsa-pakettia.

 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    // Luodaan avaimet mldsa44-määrittelyn mukaisesti.
14	pub, priv, err := mldsa44.GenerateKey(rand.Reader)
15	if err != nil {
16		panic(err)
17	}
18
19	message := []byte("Hello, World!")
20
21    // Luodaan allekirjoitus.
22    // Yksi huomioitava seikka: 22.12.2024 vallitsevan version mukaan virhe syntyy, jos crypto.Hash(0) ei ole käytössä.
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    // Varmennetaan allekirjoitus julkisen avaimen scheme-kutsulla.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Allekirjoitusarvo on liian pitkä, joten jätin sen pois. Jos haluat nähdä koko tuloksen, voit suorittaa koodin playground-ympäristössä.

Vaikka allekirjoitus on koodattu base64-muotoon, 3228 tavun koko on varmasti hieman raskas. Kun ajattelee, että pian meidän saattaa olla vaihdettava tämän kokoisia kvanttitietokoneen uhkaa vastaan suunniteltuja allekirjoituksia, tuntuu se hieman raskaalta...

MLKEM

Rakenne

MLKEM on avainkapselointimekanismi (Key Encapsulation Mechanism). KEM on algoritmi, jonka avulla kahden osapuolen välinen jaettu avain voidaan luoda julkisen avaimen salausmenetelmää käyttäen. MLKEM:n avainvaihtomekanismi etenee seuraavasti:

1. Avaimen kapselointi: lähettäjä luo vastaanottajan julkista avainta käyttäen salatun viestin (cipher text) ja jaetun avaimen (shared key). Salattu viesti toimitetaan ensin vastaanottajalle, jotta tämä voi käyttää sitä.
2. Avaimen kapseloinnin purku: vastaanottaja erottaa jaetun avaimen salatusta viestistä omaa yksityistä avaintaan käyttäen.

MLKEM:llä on yhteensä kolme parametria: MLKEM-512, MLKEM-768 ja MLKEM-1024. Mitä pienempi luku on, sitä pienempiä ovat avaimet ja salatut tekstit, ja mitä suurempi luku on, sitä pidempiä ovat avaimet ja salatut tekstit ja sitä korkeampi on turvallisuustaso.

Koodi

MLKEM on tarkoitus lisätä Go 1.24:ään, joten tämän hetkisessä tilanteessa käytin Go 1.24rc1-versiota.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Luodaan vastaanottajan PrivateKey.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // MLKEM:ssä käytetään termiä EncapsulationKey eikä PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Kopioitiin EncapsulationKey, jotta näkyisi yksinkertaisesti, miten avain voidaan purkaa Bytes()-metodilla ja luoda uudelleen NewEncapsulationKeyX-funktiolla.
20    // Todellisuudessa tämä vaihe vastaa sitä, että lähettäjä muodostaa objektin vastaanottajan EncapsulationKey-avaimesta, joka on julkaistu tekstimuodossa.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Encapsulate-metodilla lähettäjä luo salatun tekstin ja jaetun avaimen.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Kopioitiin vastaanottajan yksityinen avain, jotta näkyisi, miten se tallennetaan ja haetaan.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Vastaanottaja purkaa salatun tekstin Decapsulate-metodilla omaa yksityistä avainta käyttäen ja luo siitä toisen jaetun avaimen.
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=

Tuloksena voidaan todeta, että syntyy samankokoinen jaettu avain!

Tämän koodin voi tarkistaa myös playground-ympäristössä.

Johtopäätökset

Kunkin algoritmin määrittelyt, turvallisuustasot sekä yksityisen avaimen, julkisen avaimen, allekirjoituksen ja salatekstin koot voidaan koota seuraavaan taulukkoon. Kaikki ne ovat PQC-nimen veroisia ja tarjoavat reilun kokoisia avaimia ja allekirjoituksia.

Näiden algoritmien avulla toivomme voivamme käyttää internetiä, joka on turvallinen myös kvanttitietokoneiden aikakaudella. Suhteellisen suurten avainten sekä allekirjoitusten ja salatekstien koon vuoksi lisälaskentaa on kuitenkin ilmeisesti vältettävissä vain vaikeasti.

Kuitenkin Go-kieli on toteuttanut kunkin algoritmin tehokkaasti, joten toivon, että niitä hyödynnetään aktiivisesti oikeissa kohdissa ja että ne auttavat suojaamaan turvallisuuttanne!