Sepuluh tahun desktop, algoritma penyulitan kuantum teras tunggal retak dalam masa 1 jam, kriptografi: terlalu mendadak

Komputer kuantum masa hadapan boleh memecahkan kriptografi moden dengan cepat. Oleh itu, ahli matematik dan kriptografi telah mencari algoritma penyulitan baharu yang sesuai untuk menentang serangan komputer kuantum. Generasi baru algoritma kriptografi yang boleh menahan serangan komputer kuantum pada algoritma kriptografi sedia ada dipanggil algoritma "kriptografi pasca-kuantum (PQC, kriptografi pascakuantum)".

Tetapi baru-baru ini, penyelidik dari Universiti Leuven di Belgium mendapati bahawa algoritma penyulitan PQC yang menjanjikan boleh dipecahkan sepenuhnya dalam masa hanya 1 jam (sesetengah versi boleh dipecahkan dalam masa 4 minit sahaja). Masalahnya ialah, rekod ini tidak ditetapkan oleh komputer mewah, tetapi oleh komputer meja dengan CPU berusia sepuluh tahun, berjalan pada teras tunggal. Penyelidik mengatakan kegagalan terbaru dan mengejutkan ini menyerlahkan banyak halangan yang perlu diatasi oleh kriptografi pasca-kuantum sebelum ia boleh diterima pakai.

Pautan kertas: https://eprint.iacr.org/2022/975

Secara teorinya, komputer kuantum boleh menyelesaikan masalah dengan cepat yang akan mengambil banyak masa untuk diselesaikan oleh komputer tradisional. Sebagai contoh, kriptografi moden sangat bergantung pada kesukaran melampau yang dihadapi oleh komputer klasik dalam menangani masalah matematik yang kompleks, seperti pemfaktoran nombor yang besar. Dan komputer kuantum pada dasarnya boleh menjalankan algoritma yang boleh memecahkan teknik penyulitan ini dengan cepat.

Untuk menangani ancaman ini, kriptografi di seluruh dunia telah menghabiskan 20 tahun mereka bentuk algoritma penyulitan pasca-kuantum. Algoritma ini adalah berdasarkan masalah matematik baharu yang sukar diselesaikan untuk kedua-dua komputer kuantum dan klasik.

Selama bertahun-tahun, penyelidik di institusi seperti Institut Piawaian dan Teknologi Kebangsaan (NIST) telah mengkaji algoritma PQC yang harus menjadi piawaian baharu yang boleh diterima pakai oleh dunia. Agensi itu mengumumkan pada 2016 bahawa ia sedang mencari algoritma PQC calon dan menerima 82 cadangan pada 2017. Selepas itu, selepas tiga pusingan semakan, NIST mengumumkan empat algoritma yang akan menjadi standard tidak lama lagi dan empat lagi yang akan memasuki pusingan semakan seterusnya sebagai pesaing yang mungkin.

Semakan belum berakhir dan salah satu pesaing telah hilang, terjejas oleh desktop berusia 10 tahun. Algoritma ini dipanggil SIKE (Supersingular Isogeny Key Encapsulation) dan telah dikaji oleh Microsoft, Amazon, Cloudflare dan lain-lain. Christopher Peikert, seorang kriptografi di Universiti Michigan, Ann Arbor, berkata: "Serangan ini datang begitu tiba-tiba sehingga ia adalah peluru perak (penyelesaian dengan keberkesanan yang melampau)." apa?

SIKE ialah keluarga algoritma PQC yang melibatkan lengkung elips. "Lengkung eliptik telah menjadi subjek kajian oleh ahli matematik untuk masa yang lama," kata Dustin Moody, seorang ahli matematik di NIST. "Ia diterangkan dengan persamaan seperti y^2 = x^3 + Ax + B, dengan A dan B ialah nombor. Contohnya, lengkung elips boleh menjadi y^2 = x^3 + 3x + 2." >

Pada tahun 1985, "ahli matematik memikirkan cara untuk membuat sistem kripto yang melibatkan lengkung elips yang kini digunakan secara meluas," kata Moody. "Walau bagaimanapun, sistem kriptografi lengkung eliptik ini terdedah kepada serangan daripada komputer kuantum." Adalah dipercayai bahawa idea baru ini tidak terdedah kepada serangan oleh komputer kuantum.

Kaedah baharu ini berdasarkan soalan: cara menambah dua titik pada lengkung elips untuk mendapatkan satu lagi titik pada lengkung elips. "isogeni" dalam nama algoritma bermaksud homologi, pemetaan dari satu lengkung elips ke yang lain, yang mengekalkan undang-undang penambahan.

"Jika anda membuat pemetaan ini cukup kompleks, maka cabaran penyulitan data ialah, memandangkan dua lengkung elips, sukar untuk mencari homologi antara mereka," kata rakan kajian. pengarang Thomas Decru, seorang kriptografi matematik di Universiti Leuven di Belgium.

SIKE ialah satu bentuk kriptografi berasaskan homologi berdasarkan protokol pertukaran kunci Super Singular Homology Diffie-Hellman (SIDH). "SIDH/SIKE ialah salah satu protokol penyulitan berasaskan asal praktikal yang terawal," kata Decru.

Walau bagaimanapun satu kelemahan SIKE ialah: agar ia berfungsi, ia perlu memberikan maklumat tambahan kepada orang ramai, iaitu titik pusing tambahan. "Musuh telah cuba mengeksploitasi maklumat tambahan ini untuk beberapa waktu tetapi tidak berjaya menggunakannya untuk mengalahkan SIKE," kata Moody. "Tetapi kertas baharu ini menemui jalan, menggunakan beberapa kaedah matematik yang cukup maju."

Untuk menjelaskan serangan baharu itu, Decru berkata walaupun lengkung elips ialah objek satu dimensi, dalam matematik, lengkung elips boleh divisualisasikan sebagai objek dua atau mana-mana objek berdimensi lain. Seseorang juga boleh mencipta homolog antara objek umum ini.

Dengan menggunakan teorem 25 tahun, serangan baharu menggunakan maklumat tambahan yang didedahkan oleh SIKE untuk membina homologi dua dimensi. Homologi ini kemudiannya boleh digunakan untuk membina semula kunci yang digunakan oleh SIKE untuk menyulitkan mesej.

"Perkara yang paling mengejutkan saya ialah serangan ini seolah-olah datang entah dari mana," kata Jonathan Katz, seorang kriptografi di University of Maryland, College Park. Walaupun dia tidak terlibat dalam penyelidikan baharu itu, dia berkata: "Terdapat sangat sedikit keputusan yang menunjukkan bahawa SIKE mempunyai sebarang kelemahan, dan keputusan ini tiba-tiba membawa serangan yang memusnahkan sepenuhnya terhadap SIKE kerana ia menemui kunci lengkap. Dan ia ditemui dengan cepat tanpa sebarang pengkomputeran kuantum. "

Diserang selama lebih daripada sepuluh tahun, retak dalam masa empat minit

Menggunakan algoritma berdasarkan kaedah serangan baharu di atas. , penyelidik mendapati bahawa komputer meja yang dilengkapi dengan CPU berusia sepuluh tahun (Intel Xeon CPU E5-2630v2) hanya memerlukan sekurang-kurangnya 4 minit untuk mencari kunci yang dilindungi oleh algoritma SIKE tertentu, dan kejayaan itu dianggap mencapai NIST Tahap keselamatan kuantum satu algoritma SIKE standard juga mengambil masa hanya 62 minit. Eksperimen ini dijalankan pada satu teras CPU.

"Biasanya, serangan serius terhadap sistem kriptografi berlaku sejurus selepas sistem dicadangkan, atau apabila sistem mula menarik perhatian semua orang. Lama kelamaan , serangan secara beransur-ansur menjadi lebih kuat, atau melemahkan sistem dengan ketara, tetapi serangan ini, tanpa sebarang amaran, sistem kripto tiba-tiba rosak sepenuhnya, Peikert berkata: "Sejak SIDH mula-mula dicadangkan, tiada tindak balas kepada SIDH/SIKE. Serangan itu telah membuat sedikit kemajuan selama hampir 12 tahun sehingga pelanggaran sepenuhnya ini."

Walaupun penyelidik telah menguji SIKE selama lebih sedekad, SIKE tidak dipilih sebagai standard. Salah satu sebabnya ialah kebimbangan bahawa ia terlalu baru dan tidak cukup dipelajari. Steven Galbraith, seorang ahli matematik di Universiti Auckland, berkata: "Orang ramai bimbang bahawa SIKE mungkin menghadapi risiko serangan besar, dan ia ternyata betul, jadi mengapa ia tidak dikesan sehingga sekarang? Galbraith percaya bahawa sebab penting ialah serangan baharu itu "menggunakan matematik yang sangat maju." Katz bersetuju, berkata: "Saya mengesyaki terdapat kurang daripada 50 orang di dunia yang mempunyai kedua-dua matematik asas PQC dan pengetahuan kriptografi yang diperlukan."

Selain itu, Kotak Pasir permulaan PQC Pakar Kriptozoologi AQ David Joseph pernah berkata: "Masalah asal yang sama adalah "terkenal sukar" dari sudut pelaksanaan dan teori, yang menjadikan kelemahan asasnya lebih berkemungkinan ditemui kemudian. "

Di samping itu, "Perlu diingatkan juga bahawa sebelum NIST menjalankan beberapa pusingan semakan saringan, terdapat banyak algoritma PQC yang tersedia untuk analisis, jadi usaha penyelidikan dicairkan. . Dan selepas beberapa pusingan saringan, penyelidik dapat memberi tumpuan kepada set kecil algoritma."

David Jao, salah seorang pencipta SIKE dan profesor di University of Waterloo di Kanada, berkata: "Saya rasa hasil baharu ini adalah karya yang menakjubkan, dan saya berikan kepada pengarang pujian tertinggi. .Pada mulanya, saya sedih tentang penggodaman SIKE kerana ia adalah penyelesaian yang elegan secara matematik."

"Tetapi penemuan baharu hanya mencerminkan cara sains berfungsi: Kami datang dengan sistem yang semua orang fikir kelihatan baik pada masa itu, dan kemudian selepas analisis, seseorang mendapati kelemahan di dalamnya, yang luar biasa, tetapi selain itu, mereka mengambil masa lebih 10 tahun untuk mencari kelemahan, perkara ini tidak di luar skop kemajuan saintifik biasa," tambah David Jao.

Pada pendapat Jao, ada baiknya SIKE telah dipecahkan sekarang, kerana ia belum digunakan secara meluas lagi.

Apakah maksudnya jika SIKE retak?

SIKE ialah algoritma calon NIST PQC kedua yang dipecahkan tahun ini. Pada Februari tahun ini, Ward Beullens, seorang kriptografi di IBM Research di Zurich, mendedahkan bahawa dia boleh menggunakan komputer ribanya untuk memecahkan algoritma Rainbow yang menyertai pusingan ketiga semakan NIST. "Ini menunjukkan bahawa semua pilihan PQC memerlukan kajian lanjut, " kata Katz.

Walau bagaimanapun, Moody menegaskan bahawa walaupun SIKE telah dipecahkan, sistem kriptografi lain berdasarkan homologi, seperti CSIDH atau SQIsign, belum dipecahkan "Sesetengah orang mungkin menganggap bahawa kriptografi berdasarkan homologi sudah mati. , tetapi ini jauh daripada kes itu, dan saya fikir masih banyak yang perlu dikaji dalam kriptografi berasaskan homologi,” kata Decru.

Selain itu, kerja baharu ini mungkin tidak menggambarkan tahap penyelidikan PQC NIST. Seperti yang dinyatakan oleh Decru, SIKE adalah satu-satunya sistem kriptografi berasaskan homologi antara 82 cadangan yang diterima NIST, Rainbow adalah satu-satunya algoritma multivariat di antara penyerahan tersebut.

Algoritma yang diterima pakai sebagai "standard" oleh NIST atau memasuki pusingan keempat semakannya adalah berdasarkan idea matematik yang telah dikaji dan dianalisis oleh pakar kriptografi untuk masa yang lama, kata Galbraith. "Ia tidak menjamin mereka selamat, ia hanya bermakna mereka menahan serangan untuk masa yang lebih lama orang ramai, tiada siapa yang menemui sebarang kelemahan dalam sistem kata laluan

"Program kami direka untuk membenarkan serangan dan retakan," kata Moody. "Kami telah melihat mereka dalam setiap pusingan penilaian. Ini satu-satunya cara untuk mendapatkan keyakinan dalam keselamatan, Galbraith bersetuju, dengan menyatakan bahawa kajian seperti ini "berfungsi."

Walau bagaimanapun, "Saya rasa pemusnahan kedua-dua Rainbow dan SIKE akan membuatkan lebih ramai orang mempertimbangkan dengan serius keperluan untuk pelan sandaran untuk mana-mana pemenang yang muncul daripada proses penyeragaman pasca-kuantum NIST," Decru berkata. "Mungkin terlalu berisiko untuk bergantung semata-mata pada konsep atau skema matematik. Ini juga pemikiran NIST sendiri - skema utama mereka mungkin berdasarkan kriptografi kekisi (berasaskan kekisi), tetapi mereka mahu skim kriptografi bukan kekisi untuk menyediakan Decru menyatakan bahawa penyelidik lain telah mula membangunkan versi baharu SIDH/SIKE yang mereka percaya boleh menghalang serangan baharu ini. "Saya menjangkakan apa yang akan berlaku apabila serangan meningkat dan orang ramai cuba menampal SIDH/SIKE," kata Decru.

Secara keseluruhannya, ternyata titik permulaan serangan baru ini adalah teorem yang "sama sekali tidak berkaitan dengan kriptografi" dan "mendedahkan kepentingan menjalankan penyelidikan asas dalam matematik tulen untuk memahami sistem kripto" ", Galbraith berkata.

Decru bersetuju, dengan menyatakan "Dalam matematik, tidak semuanya boleh digunakan serta-merta. Beberapa perkara hampir tidak akan dapat digunakan untuk sebarang situasi kehidupan sebenar. Tetapi ini tidak bermakna kita tidak sepatutnya biarkan penyelidikan membawa kepada isu-isu yang lebih kabur ini.”

Atas ialah kandungan terperinci Sepuluh tahun desktop, algoritma penyulitan kuantum teras tunggal retak dalam masa 1 jam, kriptografi: terlalu mendadak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!