SIDH dan SIKE: Desain dan Kriptanalisis

Supersingular Isogeny Diffie-Hellman (SIDH), yang diusulkan oleh Jao dan De Feo pada 2011, adalah protokol pertukaran kunci publik yang analog dengan Diffie-Hellman, tetapi menggunakan isogeni pada kurva eliptik supersingular. Kedua pihak memulai dengan kurva supersingular E yang sama di atas Fp2. Alice menghitung isogeni rahasia phi_A: E -> E_A (kernel acak pada torsi 2^a), lalu memublikasikan E_A dan citra generator torsi Bob berdasarkan phi_A. Bob menghitung phi_B: E -> E_B (kernel acak pada torsi 3^b), lalu memublikasikan E_B dan citra generator torsi Alice berdasarkan phi_B. Alice menggunakan data yang dipublikasikan Bob untuk menghitung phi_A': E_B -> E_AB; Bob menghitung phi_B': E_A -> E_AB. Keduanya memperoleh j(E_AB) sebagai rahasia bersama.

Bentuk prima khusus SIDH, p = 2^a * 3^b * f - 1 (f adalah kofaktor kecil untuk keprimaan), memastikan bahwa kurva E di atas Fp2 memiliki struktur torsi yang diperlukan. Untuk SIKEp434 (Tingkat 1 NIST, keamanan pascakuantum 128 bit): p = 2^216 * 3^137 - 1, a = 216, b = 137. Artinya, Alice menempuh 216 langkah isogeni-2, sedangkan Bob menempuh 137 langkah isogeni-3. Ukuran kunci: kunci publik Alice adalah E_A ditambah dua titik Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 byte. SIKEp751 menargetkan keamanan klasik 192 bit / kuantum 128 bit dan memiliki kunci publik berukuran 564 byte. Ini adalah kunci publik terkecil di antara semua kandidat PQC NIST—dengan konsekuensi kecepatannya 100–1000 kali lebih rendah.

SIKE (Enkapsulasi Kunci Isogeni Supersingular) adalah KEM aman terhadap IND-CCA2 yang dibangun dari SIDH menggunakan transformasi Fujisaki-Okamoto. SIKE.Encaps: pilih pesan acak m, hitung (c0 = kunci publik SIDH dengan benih m, c1 = H2(m) XOR pk), lalu kirimkan (c0, c1). SIKE.Decaps: pulihkan m dari c0 menggunakan kunci rahasia, verifikasi c1, hitung ulang (c0, c1) untuk memeriksa konsistensi, lalu keluarkan K = H3(m, c0). Transformasi FO mengubah pertukaran SIDH yang aman terhadap CPA menjadi KEM yang aman terhadap CCA2. SIKE berkompetisi dalam keempat putaran PQC NIST (2017–2022) dan bertahan dari kriptanalisis ekstensif—hingga serangan klasik yang menghancurkan muncul pada Juli 2022.

Dari 2011 hingga 2022, SIDH bertahan dari upaya kriptanalisis yang signifikan. Serangan terbaik yang diketahui terhadap SIDH adalah: (1) Algoritme SSIP generik: O(p^{1/4}) secara klasik, O(p^{1/6}) secara kuantum menggunakan algoritme Tani. (2) Serangan temu-tengah pada jalur isogeni: O(p^{1/4}) secara klasik, sama seperti SSIP. (3) Algoritme waktu polinomial untuk serangan struktural tertentu (van Oorschot-Wiener): tidak berlaku pada SIDH. Puluhan makalah menganalisis keamanan SIDH, dan tidak ditemukan serangan klasik atau kuantum waktu polinomial selama 11 tahun. Rekam jejak ini menjadikan SIKE finalis NIST yang kredibel. Pembobolan akhirnya bukan berasal dari serangan langsung terhadap SSIP, melainkan dari eksploitasi informasi titik torsi tambahan SIDH.

Pada 30 Juli 2022, Wouter Castryck dan Thomas Decru menerbitkan pracetak yang menunjukkan serangan klasik waktu polinomial terhadap SIDH. Serangan tersebut menggunakan informasi ekstra dalam titik torsi tambahan SIDH phi_A(P_B), phi_A(Q_B): informasi ini pada dasarnya mengungkapkan aksi phi_A pada subgrup torsi 3^b. Jika digabungkan dengan kurva citra E_A, hal ini memungkinkan rekonstruksi kernel phi_A (dan dengan demikian phi_A itu sendiri) menggunakan teknik dari teori kurva eliptik dengan perkalian kompleks dan isogeni Richelot. Serangan tersebut berjalan selama 62 menit pada sebuah laptop untuk SIKEp434—sebuah set parameter yang seharusnya menyediakan keamanan pascakuantum 128 bit. Dalam hitungan hari, peneliti independen mengonfirmasi dan memperluas serangan tersebut ke semua parameter SIDH.

Rancangan SIDH mengharuskan kedua pihak memublikasikan citra titik basis torsi pihak lain berdasarkan isogeni rahasia mereka. Hal ini diperlukan agar protokol dapat berfungsi: tanpa phi_A(P_B) dan phi_A(Q_B), Bob tidak dapat memindahkan isogeninya ke kurva Alice untuk menghitung rahasia bersama. Namun, informasi tambahan ini—yang mengungkapkan aksi phi_A yang dibatasi pada torsi 3^b—ternyata membocorkan informasi yang jauh lebih banyak daripada perkiraan, dengan dampak yang sangat fatal. Serangan Castryck-Decru menggunakan kurva bergenus-2 (isogeni Richelot) untuk mengangkat masalah ke objek bergenus lebih tinggi, tempat aksi yang dibatasi tersebut sepenuhnya menentukan phi_A. Kebocoran ini bersifat struktural pada SIDH dan tidak dapat diperbaiki tanpa mengubah rancangan fundamental protokol.

Pada 5 Juli 2022 (sebelum Castryck-Decru), NIST telah mengumumkan pilihan standardisasi PQC awalnya: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+), dan FN-DSA (Falcon)—SIKE tidak termasuk di dalamnya karena masih berada dalam putaran pertimbangan kedua. Serangan Castryck-Decru pada Juli 2022 membuat NIST secara resmi menghapus SIKE sepenuhnya dari pertimbangan. NIST menyatakan: "SIKE tidak lagi dipertimbangkan untuk standardisasi." Ini adalah perkembangan kriptanalisis paling dramatis dalam kompetisi PQC NIST, yang menunjukkan bahwa bahkan skema yang bertahan dari analisis selama 11 tahun dapat dibobol oleh wawasan matematis yang benar-benar baru.

Dalam waktu seminggu setelah Castryck-Decru, Thomas Decru dan Luciano Maino (secara independen), kemudian Damien Robert, menerbitkan penyempurnaan lebih lanjut. Varian serangan Robert menggunakan wawasan yang sama, tetapi menghitung gelanggang endomorfisme E_A alih-alih menghitung langsung kernel isogeni, dan secara matematis bisa dibilang lebih sederhana untuk dijelaskan. Penemuan ulang independen yang berlangsung cepat ini menegaskan bahwa serangan Castryck-Decru mengidentifikasi kelemahan struktural yang mendasar, bukan trik yang tidak jelas. Kecepatan makalah-makalah berikutnya juga mencerminkan banyaknya peneliti yang telah mempelajari kebocoran titik torsi SIDH sebagai kemungkinan jalur serangan; mereka menyadari bahwa kebocoran tersebut merupakan pengungkapan informasi yang tidak biasa, tetapi belum dapat mengeksploitasinya hingga Castryck dan Decru menemukan jembatan bergenus-2.

FESTA (Enkripsi Cepat dari Serangan Torsi Supersingular, 2023) adalah rancangan KEM yang terinspirasi oleh SIDH, tetapi menghindari data titik torsi tambahan. FESTA menggunakan struktur protokol yang berbeda: kunci publik tidak menyertakan citra basis torsi pihak lawan—sebaliknya, isogeni rahasia dikomitmenkan hanya melalui kurva citra (tanpa titik tambahan). FESTA melakukan enkripsi menggunakan isogeni dengan cara yang mengungkapkan lebih sedikit informasi struktural. Analisis keamanan awal menunjukkan bahwa FESTA menghindari struktur serangan Castryck-Decru. Namun, FESTA lebih baru dan telah menerima lebih sedikit pemeriksaan dibandingkan rekam jejak SIKE selama 11 tahun, sehingga komunitas isogeni berhati-hati dalam menerapkan skema baru sebelum analisis ekstensif dilakukan.

Pembobolan SIKE memberikan pelajaran penting. (1) Pengungkapan informasi tambahan berbahaya: data titik torsi ekstra SIDH diperlukan agar protokol berfungsi, tetapi secara fatal membocorkan informasi. Perancang protokol harus menganalisis setiap bagian data publik, bukan hanya nilai utama. (2) Rekam jejak bukanlah bukti keamanan: 11 tahun tanpa serangan yang diketahui memang meyakinkan, tetapi bukan jaminan. Bukti kriptografi (reduksi ke masalah sulit yang terdefinisi dengan baik) lebih dapat diandalkan daripada argumen berdasarkan otoritas atau sekadar berhasil melewati pemeriksaan. (3) Perangkat matematika baru menimbulkan risiko: serangan Castryck-Decru menggunakan isogeni Richelot bergenus-2—perangkat dari matematika yang sebelumnya belum diterapkan pada kriptanalisis isogeni. Kriptanalis yang mengkaji primitif baru harus mempertimbangkan ranah matematika baru.

Meskipun SIKE dibobol, kriptografi berbasis isogeni terus berkembang sebagai bidang penelitian. Tanda tangan SQISign (177 byte pada Tingkat 1) tetap menjadi tanda tangan PQC paling ringkas yang diketahui dan menggunakan asumsi kesulitan yang berbeda (masalah gelanggang endomorfisme) yang tidak terpengaruh oleh serangan SIDH. Protokol berbasis CSIDH menggunakan struktur aksi grup kelas (isogeni komutatif) tanpa kebocoran titik torsi, meskipun CSIDH menghadapi tantangannya sendiri (lebih lambat daripada SIDH sebelumnya, dan analisis keamanan kuantumnya masih berlangsung). Komunitas isogeni memandang pembobolan SIKE sebagai pengalaman pembelajaran yang memperdalam pemahaman tentang informasi yang harus disembunyikan dalam protokol isogeni—pengetahuan berharga untuk merancang skema di masa mendatang.

Aspek apa dari rancangan SIDH yang memungkinkan serangan Castryck-Decru?

SIDH menggunakan rantai isogeni 2^a dan 3^b yang berselang-seling di antara dua pihak, dengan berbagi citra titik torsi tambahan untuk memungkinkan pertukaran kunci. SIKE melapisi SIDH dengan Fujisaki-Okamoto untuk mendapatkan keamanan CCA2. SIKE memiliki kunci terkecil di antara semua kandidat PQC NIST (374 byte), tetapi 100–1000 kali lebih lambat. Setelah 11 tahun menjalani analisis keamanan, Castryck-Decru membobol SIKE pada Juli 2022 menggunakan isogeni Richelot bergenus-2 untuk mengeksploitasi kebocoran titik torsi. NIST menghapus SIKE dari pertimbangan. FESTA menghindari pengungkapan titik torsi. SQISign tetap menggunakan kesulitan masalah gelanggang endomorfisme. Pembobolan SIKE menunjukkan bahwa data publik tambahan harus dianalisis secermat nilai protokol utama.