ML-KEM (FIPS 203): Standar CRYSTALS-Kyber

ML-KEM (Mekanisme Enkapsulasi Kunci berbasis Kisi-Modul), yang distandardisasi sebagai FIPS 203 pada Agustus 2024, merupakan pengganti pascakuantum untuk pertukaran kunci Diffie-Hellman dan RSA. ML-KEM mengenkapsulasi kunci simetris dengan kunci publik, sehingga menghasilkan rahasia bersama yang dapat digunakan kedua pihak untuk enkripsi simetris. ML-KEM diturunkan dari CRYSTALS-Kyber dengan modifikasi kecil agar spesifikasinya lebih rapi.

ML-KEM menetapkan tiga set parameter. ML-KEM-512 menargetkan tingkat keamanan klasik sekitar 128 bit dan keamanan pascakuantum 100 bit, dengan kunci publik berukuran 800 bita dan teks sandi berukuran 768 bita. ML-KEM-768 menargetkan keamanan klasik 192 bit (kunci publik 1184 bita, teks sandi 1088 bita). ML-KEM-1024 menargetkan keamanan klasik 256 bit (kunci publik 1568 bita, teks sandi 1568 bita). NIST merekomendasikan ML-KEM-768 untuk sebagian besar aplikasi.

Pembuatan kunci ML-KEM berlangsung sebagai berikut: ambil sampel matriks acak A dari sebuah benih menggunakan SHAKE-128, ambil sampel vektor rahasia kecil s dan vektor galat e, lalu hitung t = As + e mod q. Kunci publik adalah (seed, t), sedangkan kunci privat adalah s beserta nilai pencincangan kunci publik. Penggunaan benih alih-alih menyimpan A menghemat memori dan lebar pita secara signifikan.

Untuk melakukan enkapsulasi, pengirim membuat pesan acak m dan menurunkan kunci simetris K serta keacakan r melalui SHA-3. Teks sandi terdiri atas dua bagian: u = Ar + e1 mod q dan v = t^T r + e2 + encode(m) mod q. Rahasia bersama K diturunkan dari nilai pencincangan m. Keacakan diturunkan secara deterministik dari m, sehingga teks sandi terikat pada kunci.

Dekapsulasi memulihkan m dengan menghitung v - s^T u dan mendekodenya, lalu menurunkan kembali K dari m. Transformasi Fujisaki-Okamoto menambahkan langkah penting: lakukan enkripsi ulang menggunakan m yang dipulihkan dan periksa apakah teks sandinya cocok. Jika tidak cocok, kembalikan nilai semuacak yang diturunkan dari nilai pencincangan kunci privat dan teks sandi. Hal ini mencegah serangan teks-sandi-terpilih dengan membuat dekapsulasi bersifat deterministik dan dapat diverifikasi.

ML-KEM mencapai keamanan IND-CCA2 dalam model orakel acak kuantum (QROM), yang dibuktikan berdasarkan asumsi Module-LWE. QROM penting karena lawan pascakuantum dapat mengajukan kueri ke fungsi pencincangan dalam superposisi. Bukti keamanan oleh Hofheinz, Hovelmanns, dan Kiltz (kerangka HHK) memberikan reduksi ketat dari Module-LWE ke keamanan ML-KEM dalam QROM.

ML-KEM secara drastis mengungguli RSA untuk pertukaran kunci pada tingkat keamanan yang setara. Pembuatan kunci ML-KEM-768 membutuhkan sekitar 16 mikrodetik pada CPU modern, enkapsulasi 20 mikrodetik, dan dekapsulasi 18 mikrodetik. Pembuatan kunci RSA-2048 membutuhkan waktu beberapa detik. Kunci publik ML-KEM (1184 bita) lebih besar daripada ECDH (32-64 bita), tetapi jauh lebih kecil daripada RSA-2048 (256 bita hanya untuk kuncinya, tetapi dalam praktiknya lebih panjang).

Selama masa transisi, pertukaran kunci hibrida menggabungkan ML-KEM dengan algoritma klasik (biasanya X25519 atau P-256 ECDH). Rahasia bersama adalah nilai pencincangan dari kedua keluaran KEM: K = Hash(K_classical || K_pqc). Hal ini memastikan bahwa keamanan tidak lebih lemah daripada komponen mana pun. TLS hibrida ditetapkan dalam draft-ietf-tls-hybrid-design IETF dan didukung oleh BoringSSL, OpenSSL 3.x, dan Rustls.

IETF telah menetapkan X25519ML-KEM-768 sebagai mekanisme berbagi kunci hibrida untuk TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome menambahkan dukungan pada versi 124 (April 2024), sedangkan Firefox pada versi 132 (2024). Cloudflare menerapkan ML-KEM dalam infrastruktur terminasi TLS-nya. Adopsi yang cepat ini berarti ratusan juta koneksi TLS per hari kini mencakup pertukaran kunci pascakuantum.

Karena suku galat dalam LWE, terdapat kemungkinan sangat kecil bahwa dekapsulasi gagal bahkan tanpa adanya lawan. Untuk ML-KEM-512, probabilitas kegagalannya sekitar 2^{-139}; untuk ML-KEM-768, probabilitasnya 2^{-164}. Tingkat ini jauh di bawah tingkat yang perlu dikhawatirkan secara praktis (sebagai perbandingan, kesalahan perangkat keras jauh lebih sering terjadi) dan tidak memengaruhi keamanan, tetapi harus diperhitungkan dalam spesifikasi.

ML-KEM diimplementasikan dalam banyak pustaka sumber terbuka. Implementasi referensi dari tim Kyber berada dalam domain publik. PQClean menyediakan implementasi C yang telah dibersihkan dan portabel. liboqs (proyek Open Quantum Safe) mengintegrasikan ML-KEM ke dalam pembungkus pustaka. AWS-LC (fork Amazon dari BoringSSL) menyertakan ML-KEM untuk titik akhir TLS AWS. Standar NIST FIPS 203 menyertakan kode semu terperinci untuk semua operasi.

Set parameter ML-KEM manakah yang direkomendasikan NIST untuk sebagian besar aplikasi?

ML-KEM (FIPS 203) adalah KEM pascakuantum yang distandardisasi NIST dan berbasis Module-LWE. Tiga set parameter (512/768/1024) menyediakan keamanan klasik 128/192/256 bit. Pembuatan kunci menghasilkan kunci publik ringkas dari benih acak; enkapsulasi menurunkan rahasia bersama; dekapsulasi menggunakan transformasi FO untuk keamanan CCA2. ML-KEM jauh lebih cepat daripada RSA dan telah diterapkan pada TLS Chrome, Firefox, dan Cloudflare.