SIDH ve SIKE: Tasarım ve Kriptanaliz

2011 yılında Jao ve De Feo tarafından önerilen Supersingular Isogeny Diffie-Hellman (SIDH), Diffie-Hellman'a benzeyen ancak süpersingüler eliptik eğriler üzerindeki izojenileri kullanan bir açık anahtar değişimi protokolüdür. Her iki taraf da Fp2 üzerinde aynı süpersingüler E eğrisiyle başlar. Alice, gizli bir izojeni phi_A: E -> E_A hesaplar (2^a-torsiyon alt grubunda rastgele bir çekirdek kullanarak); E_A'yı ve Bob'un torsiyon üreteçlerinin phi_A altındaki görüntülerini yayımlar. Bob, phi_B: E -> E_B izojenisini hesaplar (3^b-torsiyon alt grubunda rastgele bir çekirdek kullanarak); E_B'yi ve Alice'in torsiyon üreteçlerinin phi_B altındaki görüntülerini yayımlar. Alice, yayımlanan Bob verilerini kullanarak phi_A': E_B -> E_AB izojenisini hesaplar; Bob ise phi_B': E_A -> E_AB izojenisini hesaplar. Her ikisi de ortak sır olarak j(E_AB) değerine ulaşır.

SIDH'in özel asal biçimi p = 2^a * 3^b * f - 1 (f, asallık için kullanılan küçük bir kofaktördür), Fp2 üzerindeki E eğrisinin gerekli torsiyon yapısına sahip olmasını sağlar. SIKEp434 için (NIST Seviye 1, 128 bit kuantum sonrası güvenlik): p = 2^216 * 3^137 - 1, a = 216, b = 137. Bu, Alice'in 2-izojenilerden oluşan 216 adımlık bir yol, Bob'un ise 3-izojenilerden oluşan 137 adımlık bir yol izlemesi anlamına gelir. Anahtar boyutları: Alice'in açık anahtarı E_A ile iki Fp2 noktasından (phi_A(P_B), phi_A(Q_B)) oluşur ve boyutu 3 * 2 * 54 = 324 bayttır. SIKEp751, 192 bit klasik / 128 bit kuantum güvenliği hedefler ve 564 baytlık açık anahtarlara sahiptir. Bunlar, NIST PQC adayları arasındaki en küçük açık anahtarlardır; bunun bedeli ise 100-1000 kat daha yavaş olmalarıdır.

SIKE (Supersingular Isogeny Key Encapsulation), Fujisaki-Okamoto dönüşümü kullanılarak SIDH'den oluşturulmuş, IND-CCA2 güvenli bir KEM'dir. SIKE.Encaps: rastgele bir m mesajı seçer, (c0 = m tohumlu SIDH açık anahtarı, c1 = H2(m) XOR pk) değerlerini hesaplar ve (c0, c1) çiftini gönderir. SIKE.Decaps: gizli anahtarı kullanarak c0'dan m'yi geri elde eder, c1'i doğrular, tutarlılığı denetlemek için (c0, c1) çiftini yeniden hesaplar ve K = H3(m, c0) değerini çıktı olarak verir. FO dönüşümü, CPA güvenli SIDH değişimini CCA2 güvenli KEM'e dönüştürür. SIKE, NIST PQC'nin 2017-2022 arasındaki dört turunun tamamında yarıştı ve kapsamlı kriptanalizden sağ çıktı; ta ki Temmuz 2022'de yıkıcı bir klasik saldırı ortaya çıkana kadar.

2011'den 2022'ye kadar SIDH, önemli bir kriptanaliz çabasına karşı dayandı. SIDH'e karşı bilinen en iyi saldırılar şunlardı: (1) Genel SSIP algoritması: klasik olarak O(p^{1/4}), Tani algoritması kullanıldığında kuantum olarak O(p^{1/6}). (2) İzojeni yolu üzerinde ortadan buluşma saldırısı: klasik olarak O(p^{1/4}), SSIP ile aynı. (3) Belirli yapısal saldırılar için polinom zamanlı algoritmalar (van Oorschot-Wiener): SIDH'e uygulanamaz. Onlarca makale SIDH güvenliğini analiz etti ve 11 yıl boyunca polinom zamanlı hiçbir klasik veya kuantum saldırı bulunamadı. Bu geçmiş performans, SIKE'yi güvenilir bir NIST finalisti yaptı. Sonunda gerçekleşen kırılma, SSIP'ye doğrudan yapılan bir saldırıdan değil, SIDH'in yardımcı torsiyon noktası bilgilerinden yararlanılmasından kaynaklandı.

30 Temmuz 2022'de Wouter Castryck ve Thomas Decru, SIDH'e karşı polinom zamanlı klasik bir saldırı gösteren bir ön baskı yayımladı. Saldırı, SIDH'in yardımcı torsiyon noktalarındaki ek bilgiyi kullanır: phi_A(P_B) ve phi_A(Q_B) içindeki bu bilgi, phi_A'nın 3^b-torsiyon alt grubu üzerindeki etkisini esasen açığa çıkarır. Bu bilgi, görüntü eğrisi E_A ile birleştirildiğinde, karmaşık çarpımlı eliptik eğriler kuramından ve Richelot izojenilerinden yararlanılarak phi_A'nın çekirdeğinin ve dolayısıyla phi_A'nın kendisinin yeniden oluşturulmasına olanak tanır. Saldırı, kuantum sonrası 128 bit güvenlik sağlaması beklenen SIKEp434 parametre kümesi için bir dizüstü bilgisayarda 62 dakikada gerçekleştirildi. Birkaç gün içinde bağımsız araştırmacılar saldırıyı doğruladı ve tüm SIDH parametrelerine genişletti.

SIDH'in tasarımı, her iki tarafın da kendi gizli izojenisi altındaki karşı tarafın torsiyon tabanı noktalarının görüntülerini yayımlamasını gerektiriyordu. Bu, protokolün çalışması için gerekliydi: phi_A(P_B) ve phi_A(Q_B) olmadan Bob, ortak sırrı hesaplamak üzere kendi izojenisini Alice'in eğrisine taşıyamazdı. Ancak phi_A'nın 3^b-torsiyonuyla sınırlı etkisini açığa çıkaran bu ek bilginin, beklenenden çok daha fazla bilgi sızdırdığı ve bunun felaket düzeyinde olduğu ortaya çıktı. Castryck-Decru saldırısı, problemi daha yüksek cinsli nesnelere taşımak için cins-2 eğrilerini (Richelot izojenilerini) kullanır; bu nesnelerde sınırlı etki, phi_A'yı tamamen belirler. Bu sızıntı SIDH'in yapısal bir özelliğidir ve protokolün temel tasarımı değiştirilmeden düzeltilemez.

5 Temmuz 2022'de (Castryck-Decru'dan önce) NIST, ilk PQC standardizasyon tercihlerini açıklamıştı: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+), ve FN-DSA (Falcon) — SIKE bunların arasında değildi; ikinci bir değerlendirme turundaydı. Temmuz 2022'deki Castryck-Decru saldırısı, NIST'in SIKE'yi değerlendirmeden tamamen çıkarmasına yol açtı. NIST şu açıklamayı yaptı: "SIKE artık standardizasyon için değerlendirilmiyor." Bu, NIST PQC yarışmasındaki en çarpıcı kriptanalitik gelişmeydi ve 11 yıllık analizden sağ çıkan bir şemanın bile temelden yeni bir matematiksel içgörüyle kırılabileceğini gösterdi.

Castryck-Decru'dan sonraki bir hafta içinde Thomas Decru ve Luciano Maino bağımsız olarak, daha sonra da Damien Robert başka geliştirmeler yayımladı. Robert'ın saldırı çeşidi aynı içgörüyü kullanır; ancak izojeni çekirdeğini doğrudan hesaplamak yerine E_A'nın endomorfizma halkasını hesaplar ve matematiksel olarak açıklanması muhtemelen daha basittir. Bu hızlı bağımsız yeniden keşifler, Castryck-Decru saldırısının belirsiz bir hileyi değil, temel bir yapısal zayıflığı ortaya çıkardığını doğruladı. Sonraki makalelerin hızında, birçok araştırmacının SIDH'in torsiyon noktası sızıntısını olası bir saldırı vektörü olarak incelemiş olması da etkiliydi. Araştırmacılar bunun alışılmadık bir bilgi ifşası olduğunun farkındaydı, ancak Castryck ve Decru cins-2 köprüsünü bulana kadar bu bilgiden yararlanamamışlardı.

FESTA (Süpersingüler Torsiyon Saldırılarından Hızlı Şifreleme, 2023), SIDH'den esinlenen ancak yardımcı torsiyon noktası verilerinden kaçınan bir KEM tasarımıdır. FESTA farklı bir protokol yapısı kullanır: açık anahtar, karşı tarafın torsiyon tabanının görüntülerini içermez; bunun yerine gizli izojeni yalnızca görüntü eğrisi üzerinden taahhüt edilir (yardımcı noktalar kullanılmaz). FESTA, daha az yapısal bilgi açığa çıkaracak şekilde izojeniler kullanarak şifreleme yapar. İlk güvenlik analizleri, FESTA'nın Castryck-Decru saldırısının yapısından kaçındığını göstermektedir. Ancak FESTA daha yenidir ve SIKE'nin 11 yıllık geçmişine kıyasla daha az incelenmiştir; izojeni topluluğu da kapsamlı analizden önce yeni şemaları kullanıma sunma konusunda temkinlidir.

SIKE'nin kırılması önemli dersler sunar. (1) Yardımcı bilgilerin ifşası tehlikelidir: SIDH'in ek torsiyon noktası verileri protokol için gerekliydi, ancak ölümcül miktarda bilgi sızdırdı. Protokol tasarımcıları yalnızca ana değerleri değil, herkese açık verilerin her parçasını da analiz etmelidir. (2) Geçmiş performans bir güvenlik kanıtı değildir: Bilinen bir saldırı olmadan geçen 11 yıl güven vericidir, ancak garanti değildir. Kriptografik kanıtlar (iyi tanımlanmış zor bir probleme indirgeme), otoriteye dayalı savlardan veya incelemeden geçmiş olmaktan daha güvenilirdir. (3) Yeni matematiksel araçlar risk oluşturur: Castryck-Decru saldırısı, daha önce izojeni kriptanalizine uygulanmamış bir matematik aracı olan cins-2 Richelot izojenilerini kullandı. Yeni kriptografik ilkelleri inceleyen kriptanalistler, yeni matematik alanlarını da değerlendirmelidir.

SIKE'nin kırılmasına rağmen izojeni tabanlı kriptografi bir araştırma alanı olarak devam etmektedir. SQISign imzaları (Seviye 1'de 177 bayt), bilinen en kompakt PQC imzaları olmayı sürdürmektedir ve SIDH saldırısından etkilenmeyen farklı bir zorluk varsayımı olan endomorfizma halkası problemini kullanır. CSIDH tabanlı protokoller, torsiyon noktası sızıntısı içermeyen sınıf grubu etkisi yapısını (değişmeli izojenileri) kullanır; ancak CSIDH'in de kendi zorlukları vardır (SIDH'den daha yavaştır ve kuantum güvenlik analizi sürmektedir). İzojeni topluluğu, SIKE'nin kırılmasını, izojeni protokollerinde hangi bilgilerin gizlenmesi gerektiğine ilişkin anlayışı derinleştiren bir öğrenme deneyimi olarak görür. Bu, gelecekteki şemaların tasarlanması için değerli bir bilgidir.

SIDH tasarımının hangi yönü Castryck-Decru saldırısını mümkün kıldı?

SIDH, iki taraf arasında dönüşümlü 2^a ve 3^b izojeni zincirleri kullanır ve anahtar değişimini mümkün kılmak için yardımcı torsiyon noktalarının görüntülerini paylaşır. SIKE, CCA2 güvenliği sağlamak için SIDH üzerine Fujisaki-Okamoto dönüşümünü uygular. SIKE, NIST PQC adayları arasındaki en küçük anahtarlara sahipti (374 bayt), ancak 100-1000 kat daha yavaştı. 11 yıllık güvenlik incelemesinin ardından Castryck-Decru, Temmuz 2022'de torsiyon noktası sızıntısından yararlanmak için cins-2 Richelot izojenilerini kullanarak SIKE'yi kırdı. NIST, SIKE'yi eledi. FESTA, torsiyon noktası ifşasından kaçınır. SQISign, endomorfizma halkası zorluğunu kullanmaya devam eder. SIKE'nin kırılması, yardımcı herkese açık verilerin birincil protokol değerleri kadar dikkatli analiz edilmesi gerektiğini gösterir.