filippo.io/mlkem768: Kriptografi Tahan-Kuantum untuk Ekosistem Go

 (words.filippo.io)
1 poin oleh GN⁺ 2024-02-02 | 1 komentar | Bagikan ke WhatsApp
  • filippo.io/mlkem768 adalah implementasi ML-KEM-768 dalam Go murni, yang sedang distandardisasi oleh NIST, sehingga memungkinkan ekosistem Go meninjau pertukaran kunci tahan-kuantum
  • Terdiri dari sekitar 500 baris kode, 200 baris komentar, dan 650 baris pengujian; tanpa dependensi selain golang.org/x/crypto/sha3, sehingga bentuknya mudah dinaikkan menjadi paket internal pustaka standar Go
  • Ditulis dengan mengikuti langsung spesifikasi FIPS 203, bukan mem-port implementasi referensi pq-crystals, untuk memverifikasi apakah implementasi yang interoperabel bisa dibuat hanya dari spesifikasi
  • Area paling sulit adalah kompresi/dekompresi dan operasi constant-time; menggunakan Barrett reduction untuk menghindari risiko instruksi DIV variable-time yang bisa muncul pada turunan implementasi referensi
  • Optimasi performa bukan tujuan utama, tetapi jalur Bob sebanding dengan X25519 dan P-256 di Go, sementara jalur Alice masih di bawah 2 kali lipatnya, menunjukkan bahwa implementasi sederhana pun memiliki kecepatan yang layak dipakai

Implementasi ML-KEM-768 dalam Go murni

  • filippo.io/mlkem768 adalah implementasi ML-KEM-768 dalam Go murni, dengan prioritas pada kebenaran dan keterbacaan
  • ML-KEM sebelumnya dikenal sebagai Kyber, dan merupakan mekanisme pertukaran kunci tahan-kuantum yang sedang dalam proses standardisasi NIST
  • Paket ini terdiri dari sekitar 500 baris kode, 200 baris komentar, dan 650 baris pengujian
  • Dependensinya hanya golang.org/x/crypto/sha3
  • Tujuannya adalah upstream ke pustaka standar Go, dan awalnya direncanakan sebagai paket khusus internal yang digunakan dalam eksperimen crypto/tls opt-in

Pendekatan implementasi yang mengikuti FIPS 203 apa adanya

  • Implementasi ini ditulis dari awal tanpa mem-port pustaka referensi pq-crystals, dan tanpa membaca codebase lain secara mendetail
  • Tujuan utamanya adalah memastikan apakah implementasi yang interoperabel dapat dibuat hanya dari spesifikasi
  • Dokumen FIPS 203 menyediakan pseudocode yang rinci, definisi lengkap, dan informasi tipe yang konsisten, sehingga cocok sebagai panduan implementasi
  • Nama fungsi, nama variabel, dan urutan operasi sebisa mungkin mencerminkan spesifikasi FIPS agar mudah ditinjau dan dipelajari
  • Latar belakang matematika yang diperlukan untuk mengimplementasikan ML-KEM dirangkum terpisah di Enough Polynomials and Linear Algebra to Implement Kyber

Kompresi/dekompresi dan implementasi constant-time

  • Tiga tugas implementasi inti yang tersisa adalah:
    • Mengimplementasikan aritmetika modular untuk bilangan prima 3329
    • Mengimplementasikan fungsi kompresi/dekompresi yang memetakan nilai [0, 3329) ke [0, 2ᵈ) dan mengembalikannya
    • Menjamin operasi constant-time
  • Aritmetika modular relatif mudah berkat pengalaman dari implementasi RSA dan kurva eliptik, dan bilangan prima yang kecil membuat implementasinya sederhana
  • Kompresi dan dekompresi adalah bagian tersulit
    • Spesifikasi mendefinisikannya secara abstrak dengan pecahan dan aturan pembulatan
    • Implementasi nyata harus menanganinya dengan aritmetika constant-time dan operasi bit
  • Implementasi referensi dan banyak port-nya menggunakan pembagian yang, tergantung optimasi compiler dan platform, dapat menjadi instruksi DIV variable-time
  • Paket ini sejak awal menggunakan Barrett reduction, sehingga tidak terdampak; BoringSSL juga menggunakan pendekatan yang sama

Alasan hanya menargetkan ML-KEM-768

  • Implementasi ini hanya menargetkan ML-KEM-768 dari tiga tingkat keamanan ML-KEM: -512, -768, dan -1024
  • Tim Kyber merekomendasikan penggunaan -768 dibanding -512 demi margin keamanan yang lebih konservatif terhadap kriptoanalisis baru
  • -1024 dijelaskan sebagai opsi untuk alasan yang sama seperti tingkat keamanan 256-bit, yaitu kepatuhan regulasi dan penyesuaian kekuatan (strength matching)
  • Karena sebagian besar protokol yang masih eksperimental atau dalam standardisasi berkumpul di ML-KEM-768, menargetkan satu tingkat saja hampir tidak menambah biaya
  • Penargetan tunggal mengurangi bagian yang bergerak, sehingga menguntungkan keterbacaan, keamanan, dan performa
    • Misalnya, serialisasi integer 1, 4, 10, dan 12 bit tidak ditangani dengan satu encoder generik, melainkan dipisah menjadi encoder/decoder khusus
    • Karena hanya menargetkan ML-KEM-768, encoding 5 bit dan 11 bit tidak perlu diimplementasikan

Strategi pengujian dan test vector publik

  • Pengujian adalah pilar terpenting kedua setelah keterbacaan dalam strategi jaminan keamanan paket ini
  • Pengujian dasar mencakup round-trip pembuatan kunci, enkapsulasi, dan dekapsulasi, serta test coverage di atas 95%
  • Cakupan pengujian tambahan meliputi:
    • Pemeriksaan interoperabilitas dengan test vector dari NIST dan implementasi lain
    • Membandingkan semua kombinasi input untuk penjumlahan, pengurangan, dan perkalian modular 3329 dengan nilai harapan yang dihitung menggunakan metode variable-time
    • Menguji kompresi/dekompresi secara menyeluruh terhadap acuan math/big.Rat
    • Memastikan konstanta prakomputasi sesuai dengan definisinya
    • Memastikan semua input fungsi menghasilkan error yang tepat saat panjangnya terlalu panjang atau terlalu pendek
    • Menjalankan test vector yang disediakan Sophie Schmieg dan kelak akan dimasukkan ke Wycheproof
  • Test vector buatan sendiri dipublikasikan sebagai bagian dari proyek CCTV agar dapat digunakan ulang oleh implementasi lain
  • Vector CCTV menyertakan nilai antara untuk menguji dan men-debug setiap tahap antara dan sebagian algoritme

Error yang ditangkap oleh test vector khusus

  • Negative test vectors menyediakan kunci enkapsulasi tidak valid dengan koefisien lebih besar dari 3329
    • Vector seperti ini sering diminta karena vector dari tim Kyber dan NIST berfokus pada input normal
    • Semua nilai dari 3329 hingga 2¹²-1 dan semua posisi koefisien diuji satu per satu
    • Dengan berbagi koefisien lain, data 1–3 MiB dikompresi menjadi 12–28 KiB
  • Vector “Unlucky” menguji kasus ketika pembacaan XOF perlu dilakukan secara tidak lazim banyaknya
    • Ini adalah public key yang harus membaca 575 byte atau lebih dari SHAKE-128 XOF di SampleNTT, yang biasanya terjadi dengan probabilitas 2⁻³⁸
    • Vector Sophie di-bruteforce lebih jauh sehingga membutuhkan hingga 591 byte
  • strcmp vectors membuat implementasi yang memakai strcmp() di ML-KEM.Decaps gagal
    • Saat membandingkan ciphertext dengan keluaran K-PKE.Encrypt dalam dekapsulasi, adanya byte 0 dapat membuat strcmp() menghentikan perbandingan terlalu dini
  • Accumulated vectors diturunkan dari implementasi referensi pq-crystals
    • Alih-alih menyimpan keluaran vector acak 300 MB, vector tersebut diregenerasi saat pengujian dengan RNG deterministik lalu hash-nya dibandingkan dengan nilai harapan
    • Di luar 10 ribu vector implementasi referensi, hash untuk 1 juta pengujian acak juga dapat dibuat
  • Beberapa pengujian yang ditambahkan setelah selesai tidak menemukan masalah pada filippo.io/mlkem768, dan ada setidaknya satu laporan kasus ketika negative vector menemukan cacat pada implementasi utama

Hasil performa

  • Performa bukan tujuan utama paket ini maupun paket kriptografi Go, tetapi harus cukup cepat agar berguna
  • ML-KEM cukup cepat, dan implementasi sederhana ini pun berada pada level yang dapat bersaing dengan implementasi P-256 dan X25519 di Go yang dioptimalkan dengan assembly
  • Perbandingan harus didasarkan pada total pekerjaan yang perlu dilakukan masing-masing pihak saat penyiapan kunci
    • ECDH melakukan dua perkalian skalar, termasuk satu basepoint tetap
    • KEM melakukan pembuatan kunci dan dekapsulasi di satu pihak, serta enkapsulasi di pihak lain
    • ECDH bersifat simetris, tetapi penyiapan kunci ML-KEM bersifat asimetris
  • Dalam benchmark, “Alice” melakukan pembuatan kunci dan dekapsulasi, sementara “Bob” melakukan enkapsulasi
    • Dekapsulasi mencakup enkripsi penuh untuk memastikan input ciphertext dan hasilnya cocok
    • Alice melakukan enkripsi, dekripsi, dan pembuatan kunci, sehingga membutuhkan waktu lebih lama daripada Bob
  • Hasilnya, Bob secepat X25519 atau P-256, sementara Alice masih di bawah 2 kali lipatnya
  • Dibandingkan implementasi ML-KEM cepat seperti BoringSSL dan libcrux, paket ini memerlukan waktu kira-kira 2 kali lebih lama

Angka benchmark dan ruang optimasi

  • Angka pengukurannya sebagai berikut:
    • Di macOS arm64, ECDH/P256-8 adalah 49,43 µs, dan ECDH/X25519-8 adalah 77,46 µs
    • Di lingkungan yang sama, RoundTrip/Alice-8 adalah 109,4 µs, dan RoundTrip/Bob-8 adalah 56,19 µs
    • Di Linux amd64, ECDH/P256-4 adalah 78,88 µs, dan ECDH/X25519-4 adalah 115,6 µs
    • Di lingkungan yang sama, RoundTrip/Alice-4 adalah 223,8 µs, dan RoundTrip/Bob-4 adalah 114,7 µs
  • Implementasi ini mengikuti pola Go berperforma tinggi, seperti mengurangi alokasi heap
  • x/crypto/sha3 telah dikerjakan ulang agar dapat digunakan tanpa alokasi heap, tetapi karena berdampak negatif di Apple M2, perubahan itu belum digabungkan dan tidak disertakan dalam benchmark di atas
  • Ruang optimasi yang tersisa jelas:
    • Karena pembuatan kunci dan dekapsulasi melakukan sampling matriks dari nilai yang sama, menyimpan matriks saat kedua operasi dilakukan berurutan di sisi Alice dapat menghemat sekitar 10% waktu
    • Ada kemungkinan mengurangi penyalinan pada jalur baca sha3
    • Setelah itu, optimasi implementasi field diperlukan

Mendukung Kyber v3 dengan implementasi ML-KEM

  • NIST melakukan beberapa perubahan kecil pada kiriman Kyber Round 3, yang dirangkum di bagian 1.3 draf FIPS
  • Ada beberapa protokol eksperimental berbasis Kyber v3 atau “draft00”, termasuk pertukaran kunci PQ TLS yang telah banyak di-deploy
  • Kyber v3 dapat didukung dengan implementasi ML-KEM tanpa paket terpisah
  • Salah satu perubahan menambahkan validasi untuk kasus pengecualian berupa encoding koefisien nonkanonis pada public key
    • Implementasi normal tidak membuat kunci seperti itu, sehingga dapat ditolak sesuai draf FIPS
    • Perilaku ini membuat implementasi Kyber-on-ML-KEM dapat diidentifikasi, tetapi selain itu tidak berbahaya
  • Perubahan lain adalah penghapusan tahap hashing yang diterapkan pada input CSPRNG
    • Karena byte input bersifat acak, tidak ada pihak yang dapat membedakannya
  • Perubahan terbesar adalah perilaku yang melakukan hash ciphertext ke shared secret
    • Perbedaan ini dapat menghambat interoperabilitas
    • Setelah membuat shared secret K dengan ML-KEM, shared secret Kyber dapat dibuat dengan menerapkan SHAKE-256(K || SHA3-256(c))[:32]
    • Abstraksi ML-KEM tidak perlu dilanggar
  • Baik Kyber maupun ML-KEM melakukan hash atas secret dan ciphertext untuk implicit rejection dalam dekapsulasi
    • Jika derivasi kunci di atas diterapkan di atas ML-KEM, ciphertext akan di-hash dua kali dalam implicit rejection
    • Keluaran implicit rejection memang dirancang agar tidak dapat diprediksi dan bukan target interoperabilitas, sehingga ini bukan masalah

Bacaan terkait

1 komentar

 
GN⁺ 2024-02-02
Komentar Hacker News

  • Salam dari Kudelski Security. Ini sangat tepat waktu karena kami baru-baru ini harus menghentikan satu-satunya pustaka kriptografi tahan kuantum lain yang nyaris menjadi satu-satunya pilihan untuk Go
    Cerita lengkapnya ada di https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • Bukankah Kyber-512 sempat diduga sengaja dilemahkan oleh anggota pihak NSA di NIST?

  • Penasaran, sebenarnya komputasi kuantum sudah sampai tahap mana hingga hal seperti ini mulai diperlukan
    Apakah ini seperti AI, di mana bukan sesuatu yang benar-benar baru muncul, melainkan hanya definisinya yang bergeser agar produk baru bisa dirilis di bawah nama lama?

    • Kriptografi punya cara yang agak unik dalam menangani ancaman komputer kuantum. Sebab, sebagian data dan koneksi yang dienkripsi hari ini tidak boleh bisa didekripsi lagi 30 atau 50 tahun ke depan
      Jadi pertanyaannya bukan “apakah komputer kuantum akan segera datang”, melainkan “apakah komputer kuantum secara masuk akal bisa muncul dalam setengah abad ke depan”. Belum ada konsensus yang presisi, tetapi jawabannya juga bukan “tidak”, jadi wajar jika arah perkembangannya seperti ini sekarang
      Karena itu, kemajuan terlihat lebih besar di pertukaran kunci PQC daripada tanda tangan. Verifikasi tanda tangan hari ini tidak akan terpengaruh oleh komputer kuantum 50 tahun dari sekarang, tetapi enkripsi akan terpengaruh
    • Ini bukan soal menghentikan komputer kuantum yang ada sekarang
      Risikonya adalah penyerang bisa menyimpan ciphertext hari ini lalu mendekripsinya di masa depan. Semakin cepat beralih ke kriptografi aman-kuantum, semakin sedikit “tumpukan ciphertext” yang tertinggal dan rentan terhadap serangan masa depan
    • Jika jawabannya adalah “NSA sudah menjalankan kriptoanalisis kuantum di production dan ECDH harus dianggap sudah benar-benar jebol”, maka siapa pun yang tahu dan mengatakannya akan berada dalam masalah besar
      Kemungkinan itu tampaknya rendah, tetapi pertanyaan ini memang cukup sulit dijawab. Untuk saat ini itu bukan ancaman yang diketahui, tetapi seberapa paranoid kita terhadap potensinya tetap bersifat subjektif
    • Dalam sekitar dua tahun terakhir, NIST telah menetapkan beberapa algoritma kriptografi pascakuantum, dan sejak itu implementasinya juga makin banyak. Komputasi kuantum masih jauh, tetapi sikapnya tampak seperti “kalau mulai sekarang, apa ruginya?”
      Saya tidak yakin, tetapi tampaknya kriptografi kurva eliptik juga sudah cukup banyak diimplementasikan jauh sebelum dipakai secara luas. Kalau ada yang mengalami masa itu dan saya keliru, tolong koreksi
    • Agar komputer kuantum bisa memecahkan RSA-2048, kualitas physical qubit saat ini harus naik sekitar 10 kali, dan jumlahnya sekitar 10.000 kali lebih banyak. Ini angka yang sangat kasar
      Tonggak penting berikutnya yang perlu diperhatikan adalah logical qubit yang fidelitasnya 1000 kali lebih baik daripada physical qubit penyusunnya. Jika itu tercapai, artinya kualitas physical qubit sudah cukup dan tinggal mulai memperbesar skalanya

  • Untuk diskusi terkait, pengantar terbaru John Arundel tentang implementasi sistem kriptografi berbasis versi Go terbaru mungkin bisa membantu. Di bagian terakhir ada sedikit pembahasan tentang kriptografi pascakuantum, dan jika NIST PQ distandardisasi, mungkin nanti John akan menambahkan pustaka ini dan memperbarui bukunya
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • Tolong koreksi kalau salah, tetapi jika ini ditulis dalam Go murni, bukankah ia jadi rentan terhadap serangan saluran samping timing/daya?

    • Sulit mengatakan Go lebih rentan daripada C, bahkan bisa jadi justru kurang rentan. Bedanya, Go pada dasarnya hanya punya satu compiler utama dan biasanya tidak terlalu agresif dalam optimisasi, sedangkan di C kita perlu trik yang makin rumit agar compiler tidak menangkap maksud kita lalu mengubahnya menjadi percabangan waktu-variabel yang lebih efisien
      Implementasi ini ditulis untuk menghindari jalur kode yang berubah berdasarkan nilai rahasia. Saluran samping daya yang membutuhkan akses fisik berada di luar model ancaman Go
    • Tertulis bahwa “semua operasi inti dijalankan dalam waktu konstan”
      Saya seharusnya mengikuti tautan sampai ke dokumentasi proyeknya, tampaknya hal ini memang sudah dipertimbangkan
    • Adakah bahasa yang kebal terhadap serangan saluran samping daya? Gagasannya sendiri terdengar tidak masuk akal
      Soal serangan timing juga, saya tidak tahu mengapa Go akan lebih rentan terhadap saluran samping timing dibanding bahasa lain

  • Ada yang tahu implementasi untuk bahasa lain seperti Java atau C#?

  • Keren bahwa ini juga bisa berjalan dengan draft00/kyber v3
    Seberapa sulit menambahkan dukungan mode Kyber 90’s yang lebih cepat tanpa SHA-3? Mungkin untuk itu abstraksinya harus dibongkar

    • Mengganti hash akan butuh fork. Dalam implementasi ini, hanya sekitar 20% waktu CPU yang dipakai untuk SHA-3, jadi keuntungannya tidak terlalu besar
      Jika implementasi field dioptimalkan, persentase itu memang akan naik, tetapi tetap rasanya tidak cukup untuk membenarkan penggunaan mode yang tidak distandardisasi dan kurang teruji

  • Tidak terkait, tapi Filo, tabel system call 32-bit itu masih bertuliskan ‘coming soon’, kan :')

    • Hahaha, iya, betul. Setiap kali terpikir untuk merapikan halaman itu, cakupannya malah terus melebar ke ide seperti membuatnya dihasilkan otomatis dari source kernel lewat CI :)

  • Saya tidak punya kemampuan untuk menilai kualitas algoritme atau implementasi ini, tetapi saya sangat suka penggunaan Unicode pada nama variabel
    ρ, σ := G[:32], G[32:]
    Entah kenapa terasa jauh lebih baik daripada melihat "rho", "sigma"

    • Sulit untuk setuju. Memang terlihat keren, tetapi saya tidak terlalu ingin melihatnya di kode nyata
      Pertama, saya bahkan tidak tahu bagaimana cara mengetiknya di keyboard. Lalu, kebanyakan orang juga mungkin tidak tahu nama simbol-simbol ini. Tentu orang yang melihat kode itu kemungkinan lebih paham, tetapi menurut saya ini bukan kode yang ramah
      Kejelasan itu yang utama, dan "rho" atau "sigma" sudah cukup jelas. Ditambah lagi, kalau ada konstanta "n" dan konstanta "η" bersamaan, itu sangat mudah menimbulkan kebingungan
    • Saya sama sekali tidak suka. Karakter yang tidak ada di keyboard saya menambah langkah input sehingga gesekannya terlalu besar. Selain itu, saya merasa saya akan salah membaca ρ sebagai p lalu berhadapan dengan error kompilasi yang aneh
      Bagaimana kalau menambahkan tanda diakritik atau cedilla pada huruf? Itu hanya menambah kompleksitas. Lebih baik menyesuaikan ke penyebut umum terendah
    • Apakah Go mengizinkan subskrip Unicode dalam nama variabel?
      Dari bahasa yang saya cek, Perl, Python, dan JavaScript tidak mengizinkannya di Chrome maupun Firefox, sementara PHP mengizinkannya

  • Orang yang membuat ini adalah orang yang sama yang juga membuat https://github.com/FiloSottile/age
    Saya sangat menyukai alat itu

    • Sayang sekali tidak ada plausible deniability yang tertanam. Maksudnya, seharusnya bisa mengenkripsi setidaknya dua file, lalu tergantung kunci mana yang diberikan, salah satunya bisa didekripsi
      Ini tampak seperti kelemahan keamanan pada sebagian besar alat semacam ini. Jika hanya ada satu kemungkinan kunci, orang yang datang membawa palu bisa memaksa Anda menyerahkannya. Namun jika jumlah kuncinya tidak bisa diketahui, Anda bisa memberikan beberapa dan berharap penyerang pergi sementara file yang benar-benar ingin dilindungi tetap tersembunyi
    • Saya ingin menyukai alat ini, tetapi terasa kurang manual atau tutorial yang menjelaskan pola penggunaan yang umum. Bukan sekadar cara memakai command line, tetapi bagaimana kunci seharusnya dikelola dan didistribusikan, serta hal-hal apa yang perlu diwaspadai
      Seluruh lapisan sosial yang berada di atas teknologinya terasa tidak jelas bagi saya. Akan bagus kalau ada contoh cerita dengan Alice dan Bob
    • Age memang oke, tetapi terasa mandek. Rilis terakhirnya tahun 2022, dan tidak menggunakan fungsi derivasi kunci berbasis kata sandi yang lebih modern seperti argon
      Jika Anda mencari sesuatu yang dirancang untuk penyimpanan/pembagian rahasia, rot juga layak dilihat: https://github.com/candiddev/rot

  • Spesifikasi: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf juga ditautkan dalam artikelnya