Pengalaman Menggunakan MLDSA dan MLKEM di Bahasa Go

Ikhtisar

Latar Belakang

Sejak cukup lama, kemampuan komputasi cepat dari komputer kuantum telah dipandang sebagai ancaman bagi sistem kriptografi yang ada. Hal ini karena RSA dan ECC yang digunakan saat ini berpotensi dapat dipecahkan oleh kemampuan komputasi tersebut. Namun, sejak beberapa tahun lalu, konsep komputer kuantum mulai menjadi nyata, sehingga alternatifnya mulai diteliti dan dikembangkan, dan NIST telah melakukan standardisasi PQC (Post-Quantum Cryptography, atau kriptografi tahan kuantum).

MLDSA dan MLKEM

Pada Agustus 2024, NIST akhirnya mengadopsi MLKEM dan MLDSA, yang didasarkan pada CRYSTALS-Kyber dan CRYSTALS-Dilithium, sebagai standar. Kedua algoritma ini beroperasi berdasarkan masalah yang disebut MLWE (Module Learning with Errors). Bentuk kriptografi seperti ini kami sebut sebagai kriptografi berbasis lattice.

Kriptografi berbasis lattice, sesuai namanya, adalah sistem kriptografi yang didasarkan pada tingkat kesulitan masalah matematika pada lattice. Saya sendiri tidak memiliki pengetahuan matematika yang mendalam mengenai hal ini, tetapi jika diringkas dalam satu baris, hal ini disebut masalah menyelesaikan persamaan linear dengan noise pada module lattice. Seberapa sulit masalah ini masih belum terbayangkan dengan jelas, tetapi konon masalah semacam ini begitu sulit sehingga tidak dapat diselesaikan bahkan dengan komputer kuantum.

MLDSA

Pertama-tama, mari kita pelajari MLDSA.

Konfigurasi

MLDSA, seperti yang terlihat dari namanya, adalah algoritma tanda tangan asimetris dan melalui dua tahap berikut.

1. Pembuatan tanda tangan: Membuat tanda tangan untuk sebuah pesan menggunakan kunci privat
2. Verifikasi tanda tangan: Memeriksa keabsahan tanda tangan yang dibuat menggunakan kunci publik

Selain itu, MLDSA memiliki tiga karakteristik berikut.

1. strong existential unforgeability: Dari satu tanda tangan dan kunci publik, tidak dapat dibuat tanda tangan valid lain.
2. chosen message attack: Bahkan dengan tanda tangan untuk pesan apa pun, tidak dapat dibuat tanda tangan valid yang baru menggunakan kunci publik.
3. side-channel attack: Keamanannya tinggi karena selama penandatanganan selalu digunakan nilai acak baru serta nilai pseudo-acak yang diturunkan dari pesan.
4. domain separation: Dengan menggunakan seed yang berbeda untuk parameter yang berbeda, masalah keamanan yang berulang dapat dicegah.

Kode

Berikut ini saya tunjukkan contoh kode sederhana dalam bahasa Go. Pada contoh ini, mldsa dari cloudflare/circl digunakan.

 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    // Membuat kunci dengan spesifikasi 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    // Membuat tanda tangan.
22    // Yang perlu diperhatikan adalah bahwa pada versi saat ini, per 22 Desember 2024, akan terjadi error jika nilainya bukan 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    // Memanggil scheme dari kunci publik untuk melakukan verifikasi.
32	ok := pub.Scheme().Verify(pub, message, signature, nil)
33	fmt.Println(ok)
34}

13228 oaSaOA-...
2true

Nilai tanda tangan terlalu panjang sehingga saya hilangkan. Jika ingin melihat keseluruhannya, silakan jalankan di playground.

Meskipun sudah di-encode dengan base64, ukuran 3228 byte tentu cukup memberatkan.
Kami berpikir bahwa suatu saat kita mungkin harus saling bertukar tanda tangan berukuran ini sebagai tanda tangan yang melawan komputer kuantum, dan hal itu membuat kami sedikit khawatir..

MLKEM

Konfigurasi

MLKEM adalah Key Encapsulation Mechanism. KEM adalah algoritma yang memungkinkan pembuatan kunci bersama antara dua pihak dengan menggunakan metode kriptografi kunci publik. Mekanisme pertukaran kunci MLKEM melalui proses berikut.

1. Enkapsulasi kunci: Pengirim menggunakan kunci publik penerima untuk menghasilkan pesan terenkripsi (cipher text) dan kunci bersama (shared key). Pesan terenkripsi ini pertama-tama dikirimkan kepada penerima agar dapat digunakan olehnya.
2. Dekapsulasi kunci: Penerima menggunakan kunci privatnya untuk mengekstrak kunci bersama dari pesan terenkripsi.

MLKEM memiliki tiga parameter: MLKEM-512, MLKEM-768, dan MLKEM-1024. Semakin kecil nilainya, semakin kecil kunci dan teks terenkripsi yang dihasilkan; semakin besar nilainya, semakin panjang kunci dan teks terenkripsi yang dihasilkan, serta tingkat keamanannya semakin tinggi.

Kode

MLKEM akan ditambahkan di go 1.24, sehingga pada saat ini kami menggunakan go 1.24rc1 yang tersedia.

 1package main
 2
 3import (
 4	"crypto/mlkem"
 5	"encoding/base64"
 6	"fmt"
 7)
 8
 9func main() {
10    // Membuat PrivateKey penerima.
11	receiverKey, err := mlkem.GenerateKey1024()
12	if err != nil {
13		panic(err)
14	}
15
16    // Pada MLKEM digunakan istilah EncapsulationKey, bukan PublicKey.
17	receiverPubKey := receiverKey.EncapsulationKey()
18
19    // Agar dapat menunjukkan bahwa kunci EncapsulationKey dapat diekstrak dengan Bytes() dan dipakai kembali melalui NewEncapsulationKeyX, objeknya disalin secara sederhana.
20    // Tentu saja, dalam penggunaan nyata, proses ini dapat dipahami sebagai pengirim membuat objek dari kunci EncapsulationKey penerima yang telah dipublikasikan dalam bentuk teks.
21	clonedReceiverPubKey, err := mlkem.NewEncapsulationKey1024(receiverPubKey.Bytes())
22	if err != nil {
23		panic(err)
24	}
25
26    // Pengirim membuat teks terenkripsi dan kunci bersama dengan Encapsulate.
27	cipherText, SenderSharedKey := clonedReceiverPubKey.Encapsulate()
28
29    // Objek disalin dengan sengaja untuk menunjukkan proses menyimpan dan mengambil kembali kunci privat penerima.
30	clonedReceiverKey, err := mlkem.NewDecapsulationKey1024(receiverKey.Bytes())
31	if err != nil {
32		panic(err)
33	}
34
35    // Penerima melakukan Decapsulate terhadap teks terenkripsi menggunakan kunci privat untuk menghasilkan kunci bersama yang lain.
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=

Hasilnya dapat dipastikan bahwa kunci bersama dengan ukuran yang sama berhasil dibuat!

Kode ini juga dapat diperiksa di Playground.

Kesimpulan

Spesifikasi setiap algoritma, tingkat keamanannya, serta ukuran kunci privat, kunci publik, tanda tangan, atau teks terenkripsi dapat dirangkum seperti tabel berikut. Masing-masing menunjukkan ukuran yang cukup besar, sesuai dengan namanya sebagai PQC.

Dengan algoritma-algoritma ini, kami berharap dapat menggunakan internet yang cukup aman bahkan di era komputer kuantum, tetapi tampaknya tidak dapat dihindari bahwa komputasi yang lebih banyak akan diperlukan akibat ukuran kunci serta tanda tangan/teks terenkripsi yang relatif membesar.

Meski demikian, bahasa Go telah mengimplementasikan setiap algoritma dengan efektif, sehingga kami berharap bahasa ini dapat secara aktif dimanfaatkan di tempat yang tepat untuk menjaga keamanan Anda sekalian!