Kriptografi pasca-kuantum – algoritma baru “hilang dalam 60 menit”

Kami telah menulis tentang PQC, kependekan dari kriptografi pasca-kuantum, beberapa kali sebelumnya.

Jika Anda melewatkan semua kegembiraan media selama beberapa tahun terakhir tentang apa yang disebut komputasi kuantum…

…ini (jika Anda mau memaafkan apa yang mungkin dianggap oleh beberapa ahli sebagai penyederhanaan berlebihan yang sembrono) cara membangun perangkat komputasi yang dapat melacak beberapa kemungkinan hasil dari perhitungan pada saat yang sama.

Dengan sangat hati-hati, dan mungkin sedikit keberuntungan, ini berarti Anda dapat menulis ulang beberapa jenis algoritme untuk mendapatkan jawaban yang benar, atau setidaknya dengan benar membuang banyak jawaban yang salah, tanpa mencoba dan menguji setiap hasil yang mungkin. satu per satu.

Dua percepatan cryptanalytical yang menarik dimungkinkan menggunakan perangkat komputasi kuantum, dengan asumsi perangkat yang kuat dan andal yang sesuai benar-benar dapat dibangun:

• Algoritma pencarian kuantum Grover. Biasanya, jika Anda ingin mencari serangkaian jawaban yang diurutkan secara acak untuk melihat apakah jawaban Anda ada dalam daftar, Anda akan berharap untuk menelusuri seluruh daftar, paling buruk, sebelum mendapatkan jawaban yang pasti. Misalnya, jika Anda ingin menemukan kunci dekripsi AES 128-bit untuk menguraikan dokumen, Anda perlu mencari daftar semua kunci yang mungkin, mulai dari 000..001, ..2, ..3, dan seterusnya, sampai FFF..FFF (16 byte senilai FF), untuk memastikan penyelesaian masalah. Dengan kata lain, Anda harus menganggarkan untuk mencoba semua 2¹²⁸ kemungkinan kunci sebelum menemukan kunci yang tepat, atau menentukan bahwa tidak ada satu pun. Algoritme Grover, bagaimanapun, dengan komputer kuantum yang cukup besar dan kuat, mengklaim dapat menyelesaikan prestasi yang sama dengan akar pangkat dua dari upaya biasa, sehingga memecahkan kode, secara teori, hanya dalam 2⁶⁴ mencoba sebagai gantinya.
• Algoritma faktorisasi kuantum Shor. Beberapa algoritme enkripsi kontemporer mengandalkan fakta bahwa mengalikan dua bilangan prima besar bersama-sama dapat dilakukan dengan cepat, sedangkan membagi produk mereka kembali menjadi dua angka yang Anda mulai sama baiknya dengan tidak mungkin. Untuk merasakannya, coba kalikan 59×87 menggunakan pena dan kertas. Mungkin perlu sekitar satu menit untuk mengeluarkannya (5133 adalah jawabannya), tetapi tidak terlalu sulit. Sekarang coba cara lain. Bagilah, katakanlah, 4171 kembali menjadi dua faktornya. Jauh lebih sulit! (Ini 43 × 97.) Sekarang bayangkan melakukan ini dengan angka yang panjangnya 600 digit. Secara longgar, Anda terjebak dengan mencoba membagi angka 600 digit dengan setiap kemungkinan 300 digit bilangan prima sampai Anda mendapatkan jackpot, atau menemukan tidak ada jawaban. Algoritma Shor, bagaimanapun, menjanjikan untuk memecahkan masalah ini dengan logaritma dari usaha biasa. Dengan demikian, memfaktorkan sejumlah 2048 digit biner harus memakan waktu hanya dua kali lebih lama daripada memfaktorkan angka 1024-bit, bukan dua kali lebih lama dari memfaktorkan angka 2047-bit, mewakili percepatan yang sangat besar.

Melawan ancaman

Ancaman dari algoritma Grover dapat dilawan hanya dengan meningkatkan ukuran angka yang Anda gunakan dengan mengkuadratkannya, yang berarti menggandakan jumlah bit dalam hash kriptografi atau kunci enkripsi simetris Anda. (Dengan kata lain, jika menurut Anda SHA-256 baik-baik saja saat ini, menggunakan SHA-512 sebagai gantinya akan memberikan alternatif yang tahan PQC.)

Tapi algoritma Shor tidak bisa dilawan dengan mudah.

Kunci publik 2048 bit perlu ditingkatkan ukurannya secara eksponensial, tidak hanya dengan mengkuadratkan, sehingga alih-alih kunci 2×2048=4096 bit, Anda juga memerlukan kunci baru dengan ukuran 2 yang tidak mungkin.²⁰⁴⁸ sedikit…

…atau Anda harus mengadopsi jenis sistem enkripsi pasca-kuantum yang benar-benar baru yang tidak diterapkan oleh algoritma Shor.

Nah, badan standar AS NIST telah berjalan "Persaingan" PQC sejak akhir 2017.

Prosesnya terbuka untuk semua orang, dengan semua peserta diterima, semua algoritme dipublikasikan secara terbuka, dan pengawasan publik tidak hanya mungkin tetapi juga didorong secara aktif:

Panggilan untuk Proposal. [Tutup 2017-11-30]. […] Hal ini dimaksudkan agar standar kriptografi kunci publik yang baru akan menentukan satu atau lebih tanda tangan digital tambahan yang tidak diklasifikasikan, diungkapkan secara publik, enkripsi kunci publik, dan algoritme pembuatan kunci yang tersedia di seluruh dunia, dan mampu melindungi informasi sensitif pemerintah jauh ke masa mendatang, termasuk setelah munculnya komputer kuantum.

Setelah tiga putaran pengajuan dan diskusi, NIST mengumumkan, pada 2022-07-05, bahwa ia telah memilih empat algoritme yang dianggap "standar" dengan efek langsung, semuanya dengan nama yang terdengar menyenangkan: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, dan SPHINCS+.

Yang pertama (CRYSTALS-KYBER) digunakan sebagai apa yang disebut a Mekanisme Perjanjian Utama (KEM), di mana dua ujung saluran komunikasi publik dengan aman menyusun kunci enkripsi pribadi satu kali untuk bertukar data senilai sesi secara rahasia. (Sederhananya: pengintai hanya mendapatkan kubis yang diparut, jadi mereka tidak bisa menguping pembicaraan.)

Tiga algoritma lainnya digunakan untuk Tanda Tangan Digital, di mana Anda dapat memastikan bahwa data yang Anda dapatkan di pihak Anda sama persis dengan apa yang dimasukkan pengirim di pihak lain, sehingga mencegah gangguan dan memastikan integritas. (Sederhananya: jika ada yang mencoba merusak atau mengacaukan data, Anda akan tahu.)

Dibutuhkan lebih banyak algoritma

Pada saat yang sama saat mengumumkan standar baru, NIST juga mengumumkan ronde keempat persaingannya, mengedepankan empat algoritme lebih lanjut sebagai KEM alternatif yang mungkin. (Ingat bahwa, pada saat penulisan, kami telah memiliki tiga algoritme tanda tangan digital yang disetujui untuk dipilih, tetapi hanya satu KEM resmi.)

Ini adalah: BIKE, Classic McEliece, HQC dan SIKE.

Menariknya, Algoritma McEliece ditemukan jauh di tahun 1970-an oleh kriptografer Amerika Robert Mc Eliece, yang meninggal pada tahun 2019, jauh setelah kontes NIST sudah berlangsung.

Namun, itu tidak pernah berhasil, karena membutuhkan material kunci dalam jumlah besar dibandingkan dengan alternatif populer saat itu, algoritma Diffie-Hellman-Merkle (DHM, atau kadang-kadang hanya DH).

Sayangnya, salah satu dari tiga algoritma Putaran Empat, yaitu SIKE, tampaknya telah retak.

Dalam makalah yang memutar otak berjudul SERANGAN PEMULIHAN KUNCI YANG EFISIEN PADA SIDH (VERSI PERTAMA), kriptografer Belgia Wouter Castryk dan Thomas Decru tampaknya telah memberikan pukulan mematikan pada algoritma SIKE

Jika Anda bertanya-tanya, SIKE adalah kependekan dari Enkapsulasi Kunci Isogeni Supersingular, dan SIDH singkatan dari Isogeni Supersingular Diffie-Hellman, penggunaan khusus dari algoritma SIKE di mana dua ujung saluran komunikasi melakukan "cryptodance" seperti DHM untuk bertukar sekelompok data publik yang memungkinkan setiap ujung memperoleh nilai pribadi untuk digunakan sebagai kunci enkripsi rahasia satu kali.

Kami tidak akan mencoba menjelaskan serangan di sini; kami hanya akan mengulangi apa yang diklaim oleh makalah tersebut, yaitu bahwa:

Sangat longgar, input di sini termasuk data publik yang disediakan oleh salah satu peserta dalam cryptodance pembentukan kunci, bersama dengan parameter yang telah ditentukan (dan karena itu diketahui publik) yang digunakan dalam proses.

Tetapi output yang diekstraksi (informasi yang disebut sebagai isogeni di atas) seharusnya menjadi bagian proses yang tidak pernah terungkap – yang disebut kunci pribadi.

Dengan kata lain, dari informasi publik saja, seperti data yang dipertukarkan secara terbuka selama penyiapan kunci, kriptografer mengklaim dapat memulihkan kunci pribadi salah satu peserta.

Dan begitu Anda mengetahui kunci pribadi saya, Anda dapat dengan mudah dan tidak terdeteksi berpura-pura menjadi saya, sehingga proses enkripsi rusak.

Rupanya, algoritme pemecahan kunci membutuhkan waktu sekitar satu jam untuk melakukan tugasnya, hanya menggunakan satu inti CPU dengan jenis kekuatan pemrosesan yang Anda temukan di laptop sehari-hari.

Itu bertentangan dengan algoritme SIKE ketika dikonfigurasi untuk memenuhi Level 1, tingkat keamanan enkripsi dasar NIST.

Apa yang harus dilakukan?

Tidak ada!

(Itu kabar baiknya.)

Seperti yang disarankan oleh penulis makalah, setelah mencatat bahwa hasil mereka masih awal, “Dengan keadaan saat ini, SIDH tampaknya sepenuhnya rusak untuk setiap kurva dasar yang dihasilkan secara publik.”

(Itu berita buruknya.)

Namun, mengingat bahwa algoritma SIKE belum disetujui secara resmi, sekarang dapat disesuaikan untuk menggagalkan serangan khusus ini (sesuatu yang penulis akui mungkin), atau hanya dijatuhkan sama sekali.

Apa pun yang akhirnya terjadi pada SIKE, ini adalah pengingat yang sangat baik tentang mengapa mencoba menciptakan algoritme enkripsi Anda sendiri penuh dengan bahaya.

Ini juga merupakan contoh nyata mengapa sistem enkripsi berpemilik yang mengandalkan kerahasiaan algoritme itu sendiri untuk menjaga keamanan mereka sama sekali tidak dapat diterima pada tahun 2022.

Jika algoritme PQC seperti SIKE bertahan dari pengamatan dan penyelidikan oleh para ahli dari seluruh dunia selama lebih dari lima tahun, meskipun diungkapkan secara khusus sehingga dapat menjadi sasaran pengawasan publik…

…maka tidak perlu bertanya pada diri sendiri seberapa baik algoritme enkripsi tersembunyi-dari-tampilan buatan Anda cenderung berjalan saat dirilis ke alam liar!

---