Günümüzün kriptografi protokolleri başarısız olursa, çevrimiçi bağlantıların güvenliğini sağlamak - gizli mesajlar göndermek, güvenli finansal işlemler yapmak veya verileri doğrulamak - imkansız olurdu. Herkes her şeye erişebilir; herkes herhangi biri gibi davranabilir. Dijital ekonomi çökecek.
Ne zaman (veya if) tamamen işlevsel bir kuantum bilgisayar kullanılabilir hale gelir, tam olarak olabilecek olan budur. Sonuç olarak, 2017'de ABD hükümetinin Ulusal Standartlar ve Teknoloji Enstitüsü (NIST), “kuantum sonrası” kriptografi elde etmenin en iyi yollarını bulmak için uluslararası bir yarışma başlattı.
Geçen ay, ajans ilk kazanan grubunu seçti: bazı revizyonlarla kuantum kalkanı olarak dağıtılacak dört protokol. Ayrıca, halen incelenmekte olan dört aday daha açıkladı.
Daha sonra 30 Temmuz'da bir çift araştırmacı, bu adaylardan birini kırdı bir dizüstü bilgisayarda bir saat içinde. (O zamandan beri, diğerleri birkaç dakika içinde protokolü bozarak saldırıyı daha da hızlandırdı.) “Çok dramatik ve güçlü bir saldırı… oldukça şok oldu” dedi. Steven Galbraith, Yeni Zelanda'daki Auckland Üniversitesi'nde matematikçi ve bilgisayar bilimcisi. Saldırının altında yatan matematik şaşırtıcı olmakla kalmadı, aynı zamanda (çok ihtiyaç duyulan) kuantum sonrası kriptografinin çeşitliliğini azalttı - NIST yarışmasındaki şemaların büyük çoğunluğundan çok farklı çalışan bir şifreleme protokolünü ortadan kaldırdı.
"Biraz sıkıcı" dedi Christopher Peikert, Michigan Üniversitesi'nde bir kriptograf.
Sonuçlar, kuantum sonrası kriptografi topluluğunu hem sarstı hem de cesaretlendirdi. Sarsılmış, çünkü bu saldırı (ve yarışmanın önceki bir turundan bir başka saldırı), dijital çelik bir kapıya benzeyen bir şeyi aniden ıslak gazeteye dönüştürdü. "Aniden ortaya çıktı" dedi Dustin Karamsar, NIST standardizasyon çabalarına öncülük eden matematikçilerden biri. Ancak bir şifreleme şeması bozulacaksa, vahşi doğada kullanılmadan çok önce gerçekleşmesi en iyisidir. "İçinden geçen birçok duygu var" dedi David Jao, IBM araştırmacısı ile birlikte Kanada'daki Waterloo Üniversitesi'nde bir matematikçi Luca DeFeo, 2011 yılında protokolü önerdi. Elbette sürpriz ve hayal kırıklığı bunların arasında. "Ama ayrıca," diye ekledi Jao, "en azından şimdi kırıldı."
Eğriler Arasında Gizli Yürüyüşler
Jao ve De Feo, iyi bilinen protokollere hem benzer hem de uygun şekilde farklı olan bir şifreleme sistemi için bir fırsat görmüştü. Tekil izogeni Diffie-Hellman protokolü (SIDH) olarak adlandırılan şemaları, eliptik eğrilerle ilgileniyordu - bugün kullanılan en yaygın şifreleme türlerinden birinde kullanılan aynı matematiksel nesneler. Ama onları tamamen farklı bir şekilde kullandı. Aynı zamanda NIST'in düşündüğü en kompakt şemaydı (diğer adayların çoğundan daha yavaş olduğu gibi).
Jao, "matematiksel olarak gerçekten zarif" dedi. “O zaman, güzel bir fikir gibi görünüyordu.”
Diyelim ki iki taraf, Alice ve Bob, potansiyel bir saldırganın dikkatli bakışları altında bile gizlice bir mesaj alışverişinde bulunmak istiyor. Grafik adı verilen kenarlarla birbirine bağlanan bir noktalar topluluğu ile başlarlar. Her nokta farklı bir eliptik eğriyi temsil eder. Bir eğriyi belirli bir şekilde (izogeni adı verilen bir harita aracılığıyla) diğerine dönüştürebiliyorsanız, nokta çifti arasına bir kenar çizin. Ortaya çıkan grafik çok büyük ve kaybolması kolay: Kenarları boyunca nispeten kısa bir yürüyüş yaparsanız, tamamen rastgele görünen bir yere varırsınız.
Alice'in ve Bob'un grafiklerinin hepsi aynı noktalara sahiptir, ancak kenarlar farklıdır - farklı izojenitelerle tanımlanırlar. Alice ve Bob aynı noktadan başlarlar ve her biri kendi grafiklerinde rastgele kenarlar boyunca zıplarlar ve bir noktadan diğerine olan yollarının izini sürerler. Her biri daha sonra bitiş konumlarını yayınlar, ancak yollarını gizli tutar.
Şimdi yer değiştiriyorlar: Alice, Bob'un son noktasına ve Bob da Alice'in noktasına gidiyor. Her biri gizli yürüyüşlerini tekrarlar. Bunu öyle bir şekilde yapıyorlar ki, ikisi de aynı noktada buluşacak.
Bu konum gizli olarak bulundu, bu nedenle Alice ve Bob onu gizli anahtarları olarak kullanabilirler - birbirlerinin mesajlarını güvenli bir şekilde şifrelemelerine ve şifrelerini çözmelerine olanak tanıyan bilgiler. Saldırgan, Alice ve Bob'un birbirlerine gönderdiği ara noktaları görse bile, Alice'in veya Bob'un gizli yürüyüşünü bilmiyorlar, bu yüzden o son noktayı çözemiyorlar.
Ancak SIDH'nin çalışması için Alice ve Bob'un yürüyüşleri hakkında bazı ek bilgi alışverişinde bulunmaları gerekir. Bu ekstra bilgi, SIDH'nin düşüşüne neden oldu.
Eski Matematikte Yeni Bir Büküm
Thomas Decru SIDH'yi kırmak için yola çıkmadı. Başka bir kriptografi türünü geliştirmek için yöntemi genelleştirmek için bunun üzerine inşa etmeye çalışıyordu. Bu işe yaramadı, ancak bir fikir ortaya çıkardı: Yaklaşımı SIDH'ye saldırmak için faydalı olabilir. Ve böylece yaklaştı Wouter Castryck, Belçika'daki Leuven Katolik Üniversitesi'ndeki meslektaşı ve eski doktora danışmanlarından biri ve ikisi ilgili literatüre daldı.
Matematikçi tarafından yayınlanan bir makaleye rastladılar Ernst Kani Castryck, "SIDH için hemen hemen geçerli olan" bir teoremdi. “Sanırım bir kez fark ettiğimizde… saldırı bir veya iki gün içinde oldukça hızlı geldi.”
Sonunda, Alice'in gizli yürüyüşünü (ve dolayısıyla paylaşılan anahtarı) kurtarmak için Castryck ve Decru, iki eliptik eğrinin çarpımını incelediler - Alice'in başlangıç eğrisi ve Bob'a alenen gönderdiği eğri. Bu kombinasyon, değişmeli yüzey adı verilen bir tür yüzey üretir. Daha sonra bu değişmeli yüzeyleri, Kani teoremi (değişen yüzeyleri eliptik eğrilerle ilişkilendirir) ve Alice'in attığı her adımı ortaya çıkarmak için Bob'a verdiği ekstra bilgiyi kullandılar.
Jao, "Neredeyse [belirli değişmeli yüzeylere] kilitlenmenizi sağlayan bir hedef arama sinyali gibi" dedi. "Ve bu sinyal size doğru [gizli yürüyüşü] bulmak için bir sonraki adımı atmanız gereken yolun bu olduğunu söylüyor." Bu da onları doğrudan Alice ve Bob'un ortak anahtarına götürdü.
Jao, "Daha basit nesne hakkında sonuçlar elde etmek için daha karmaşık nesnelere gitmek çok beklenmedik bir yaklaşım" dedi.
“Bu tekniğin kullanıldığını görmek beni çok heyecanlandırdı” dedi. Kristin Lauter, Meta AI Research'te yalnızca izogeni tabanlı şifrelemenin geliştirilmesine yardımcı olmakla kalmayıp aynı zamanda değişmeli yüzeyler üzerinde de çalışan bir matematikçi ve kriptograf. “Bunu [onu] kırmanın bir yolu olarak düşünmediğim için utanıyorum.”
Castryck ve Decru'nun saldırısı, SIDH protokolünün en düşük güvenlikli versiyonunu 62 dakikada ve en yüksek güvenlik seviyesini bir günden kısa bir sürede kırdı. Ardından, kısa bir süre sonra, başka bir uzman, düşük güvenlikli sürümü kırmak sadece 10 dakika ve yüksek güvenlikli sürümü kırmak için birkaç saat sürecek şekilde saldırıyı değiştirdi. Daha genel saldırılar geçtiğimiz haftalarda yayınlandı SIDH'nin kurtarılmasını pek olası kılmaz.
Castryck, acı tatlı da olsa, "Özel bir duyguydu," dedi. "En sevdiğimiz sistemlerden birini öldürdük."
Bir Havza Anı
Bir sistemin koşulsuz olarak güvenli olduğunu garanti etmek imkansızdır. Bunun yerine, kriptograflar yeterli zamana ve kendinden emin hissetmek için sorunu çözmeye çalışan yeterli sayıda insana güvenir. "Bu, yarın uyanıp birinin bunu yapmak için yeni bir algoritma bulduğunu görmeyeceğiniz anlamına gelmiyor" dedi. Jeffrey Hoffstein, Brown Üniversitesi'nde bir matematikçi.
Bu nedenle NIST'ler gibi yarışmalar neden bu kadar önemlidir. NIST yarışmasının bir önceki turunda, IBM'de bir kriptograf olan Ward Beullens, bir saldırı tasarladı. Rainbow adlı bir planı bozdu bir haftasonunda. Castryck ve Decru gibi, saldırısını ancak temel matematik problemine farklı bir açıdan baktıktan sonra gerçekleştirebildi. Ve SIDH'ye yapılan saldırı gibi, bu da önerilen çoğu kuantum sonrası protokolden farklı matematiğe dayanan bir sistemi kırdı.
“Son saldırılar bir dönüm noktasıydı” dedi Thomas Perst, PQShield başlangıcında bir kriptograf. Kuantum sonrası kriptografinin ne kadar zor olduğunu ve çeşitli sistemlerin güvenliğini incelemek için ne kadar analiz gerekebileceğini vurgularlar. "Matematiksel bir nesne, bir perspektifte belirgin bir yapıya sahip olmayabilir ve diğerinde sömürülebilir bir yapıya sahip olabilir" dedi. "Zor kısım, doğru yeni bakış açısını belirlemektir."
