Jika protokol kriptografi saat ini gagal, tidak mungkin mengamankan koneksi online — untuk mengirim pesan rahasia, melakukan transaksi keuangan yang aman, atau mengotentikasi data. Siapapun bisa mengakses apapun; siapa pun bisa berpura-pura menjadi siapa pun. Ekonomi digital akan runtuh.
Kapan (atau if) komputer kuantum yang berfungsi penuh menjadi tersedia, itulah yang bisa terjadi. Akibatnya, pada tahun 2017 Institut Standar dan Teknologi Nasional (NIST) pemerintah AS meluncurkan kompetisi internasional untuk menemukan cara terbaik untuk mencapai kriptografi “pasca-kuantum”.
Bulan lalu, agensi memilih kelompok pemenang pertamanya: empat protokol yang, dengan beberapa revisi, akan digunakan sebagai perisai kuantum. Itu juga mengumumkan empat kandidat tambahan yang masih dalam pertimbangan.
Kemudian pada 30 Juli, sepasang peneliti mengungkapkan bahwa mereka telah melanggar salah satu kandidat itu dalam satu jam di laptop. (Sejak itu, yang lain membuat serangan lebih cepat, melanggar protokol dalam hitungan menit.) “Serangan yang begitu dramatis dan kuat … cukup mengejutkan,” kata Steven Galbraith, seorang matematikawan dan ilmuwan komputer di University of Auckland di Selandia Baru. Tidak hanya matematika yang mendasari serangan itu mengejutkan, tetapi juga mengurangi keragaman (yang sangat dibutuhkan) dari kriptografi pasca-kuantum — menghilangkan protokol enkripsi yang bekerja sangat berbeda dari sebagian besar skema dalam kompetisi NIST.
"Ini sedikit mengecewakan," kata Christopher Peikert, seorang kriptografer di University of Michigan.
Hasilnya telah membuat komunitas kriptografi pasca-kuantum terguncang dan terdorong. Terguncang, karena serangan ini (dan satu lagi dari putaran kompetisi sebelumnya) tiba-tiba mengubah apa yang tampak seperti pintu baja digital menjadi koran basah. "Itu muncul tiba-tiba," kata Dustin Moody, salah satu matematikawan yang memimpin upaya standardisasi NIST. Tetapi jika skema kriptografi akan rusak, yang terbaik adalah melakukannya dengan baik sebelum digunakan di alam liar. "Ada banyak emosi yang melewatimu," kata David Jao, seorang ahli matematika di University of Waterloo di Kanada yang, bersama dengan peneliti IBM Luka De Feo, mengusulkan protokol pada tahun 2011. Tentu kejutan dan kekecewaan di antara mereka. "Tapi juga," tambah Jao, "setidaknya sudah rusak sekarang."
Jalan Rahasia Di Antara Kurva
Jao dan De Feo telah melihat peluang untuk sistem kriptografi yang mirip dan sangat berbeda dari protokol terkenal. Skema mereka, yang disebut protokol supersingular isogeny Diffie-Hellman (SIDH), menangani kurva eliptik — objek matematika yang sama yang digunakan dalam salah satu jenis kriptografi paling luas yang digunakan saat ini. Tapi itu menggunakan mereka dengan cara yang sama sekali berbeda. Itu juga merupakan skema paling kompak yang dipertimbangkan NIST (dengan trade-off yang lebih lambat daripada banyak kandidat lainnya).
Dan "secara matematis, itu sangat elegan," kata Jao. “Pada saat itu, sepertinya itu ide yang bagus.”
Katakanlah dua pihak, Alice dan Bob, ingin bertukar pesan secara rahasia, bahkan di bawah tatapan waspada dari penyerang potensial. Mereka mulai dengan kumpulan titik yang dihubungkan oleh tepi yang disebut grafik. Setiap titik mewakili kurva eliptik yang berbeda. Jika Anda dapat mengubah satu kurva menjadi kurva lain dengan cara tertentu (melalui peta yang disebut isogeni), gambarlah tepi di antara pasangan titik. Grafik yang dihasilkan sangat besar dan mudah tersesat: Jika Anda berjalan relatif singkat di sepanjang tepinya, Anda akan berakhir di suatu tempat yang terlihat benar-benar acak.
Grafik Alice dan Bob memiliki semua titik yang sama, tetapi tepinya berbeda — mereka didefinisikan oleh isogeni yang berbeda. Alice dan Bob mulai pada titik yang sama, dan mereka masing-masing melompat di sepanjang tepi acak pada grafik mereka sendiri, melacak jalur mereka dari satu titik ke titik lain. Masing-masing kemudian mempublikasikan lokasi akhir mereka tetapi merahasiakan jalur mereka.
Sekarang mereka bertukar tempat: Alice pergi ke poin terakhir Bob, dan Bob ke Alice. Masing-masing mengulangi perjalanan rahasia mereka. Mereka melakukan ini sedemikian rupa sehingga mereka berdua akan berakhir pada titik yang sama.
Lokasi ini telah ditemukan secara rahasia, sehingga Alice dan Bob dapat menggunakannya sebagai kunci rahasia mereka — informasi yang memungkinkan mereka untuk mengenkripsi dan mendekripsi pesan satu sama lain dengan aman. Bahkan jika seorang penyerang melihat titik tengah yang Alice dan Bob kirimkan satu sama lain, mereka tidak tahu jalan rahasia Alice atau Bob, jadi mereka tidak bisa mengetahui titik akhir terakhir itu.
Tetapi untuk membuat SIDH berfungsi, Alice dan Bob juga perlu bertukar beberapa informasi tambahan tentang jalan-jalan mereka. Informasi tambahan itulah yang menyebabkan kejatuhan SIDH.
Sentuhan Baru pada Matematika Lama
Thomas Decru tidak berangkat untuk memecahkan SIDH. Dia mencoba membangunnya — untuk menggeneralisasi metode untuk meningkatkan jenis kriptografi lainnya. Itu tidak berhasil, tetapi itu memicu sebuah ide: Pendekatannya mungkin berguna untuk menyerang SIDH. Jadi dia mendekat Wouter Castryck, rekannya di Universitas Katolik Leuven di Belgia dan salah satu mantan penasihat doktoralnya, dan keduanya mendalami literatur yang relevan.
Mereka menemukan makalah yang diterbitkan oleh ahli matematika Ernst Kani pada tahun 1997. Di dalamnya ada teorema yang "hampir segera berlaku untuk SIDH," kata Castryck. “Saya pikir begitu kami menyadari bahwa … serangan itu datang cukup cepat, dalam satu atau dua hari.”
Akhirnya, untuk memulihkan jalan rahasia Alice (dan karena itu kunci yang dibagikan), Castryck dan Decru memeriksa produk dari dua kurva eliptik — kurva awal Alice dan kurva yang dia kirimkan secara publik ke Bob. Kombinasi itu menghasilkan semacam permukaan yang disebut permukaan abelian. Mereka kemudian menggunakan permukaan abelian ini, teorema Kani (yang menghubungkan permukaan abelian dengan kurva eliptik), dan informasi tambahan yang diberikan Alice kepada Bob untuk mengungkap setiap langkah yang diambil Alice.
"Ini hampir seperti sinyal homing yang memungkinkan Anda mengunci [permukaan abelian tertentu]," kata Jao. “Dan sinyal itu memberi tahu Anda bahwa ini adalah cara yang harus Anda tempuh untuk mengambil langkah berikutnya untuk menemukan [jalan rahasia] yang benar.” Yang membawa mereka langsung ke kunci bersama Alice dan Bob.
"Ini adalah pendekatan yang sangat tidak terduga, pergi ke objek yang lebih rumit untuk mendapatkan hasil tentang objek yang lebih sederhana," kata Jao.
“Saya sangat senang melihat teknik ini digunakan,” kata Kristin Lauter, seorang matematikawan dan kriptografer di Meta AI Research yang tidak hanya membantu mengembangkan kriptografi berbasis isogeni tetapi juga bekerja pada permukaan abelian. “Sangat memalukan bagi saya karena tidak memikirkannya sebagai cara untuk menghancurkannya.”
Serangan Castryck dan Decru memecahkan versi keamanan terendah dari protokol SIDH dalam 62 menit dan tingkat keamanan tertinggi hanya dalam waktu kurang dari satu hari. Kemudian, tak lama kemudian, pakar lain mengubah serangan itu sehingga hanya butuh 10 menit untuk memecahkan versi keamanan rendah dan beberapa jam untuk memecahkan versi keamanan tinggi. Serangan yang lebih umum diposting dalam beberapa minggu terakhir membuatnya tidak mungkin bahwa SIDH dapat diselamatkan.
“Itu adalah perasaan yang istimewa,” kata Castryck, meskipun pahit. “Kami membunuh salah satu sistem favorit kami.”
Momen DAS
Tidak mungkin untuk menjamin bahwa suatu sistem aman tanpa syarat. Sebaliknya, kriptografer mengandalkan cukup waktu berlalu dan cukup banyak orang yang mencoba memecahkan masalah untuk merasa percaya diri. "Itu tidak berarti bahwa Anda tidak akan bangun besok dan menemukan bahwa seseorang telah menemukan algoritma baru untuk melakukannya," kata Jeffrey Hoffstein, seorang matematikawan di Brown University.
Oleh karena itu mengapa kompetisi seperti NIST sangat penting. Di babak kompetisi NIST sebelumnya, Ward Beullens, seorang kriptografer di IBM, merancang serangan yang memecahkan skema yang disebut Rainbow di akhir pekan. Seperti Castryck dan Decru, dia hanya bisa melancarkan serangannya setelah dia melihat masalah matematika yang mendasarinya dari sudut yang berbeda. Dan seperti serangan terhadap SIDH, yang satu ini merusak sistem yang mengandalkan matematika yang berbeda dari kebanyakan protokol pasca-kuantum yang diusulkan.
“Serangan baru-baru ini adalah momen yang menentukan,” kata Thomas Perst, seorang kriptografer di startup PQShield. Mereka menyoroti betapa sulitnya kriptografi pasca-kuantum, dan seberapa banyak analisis yang mungkin diperlukan untuk mempelajari keamanan berbagai sistem. "Sebuah objek matematika mungkin tidak memiliki struktur yang jelas dalam satu perspektif, dan memiliki struktur yang dapat dieksploitasi di perspektif lain," katanya. “Bagian yang sulit adalah mengidentifikasi perspektif baru yang tepat.”
