Kuantum sonrası kriptografi – yeni algoritma “60 dakikada gitti”

PQC hakkında yazdık, kısaltması kuantum sonrası kriptografi, daha önce birkaç kez.

Son birkaç yılın sözde kuantum hesaplamayla ilgili tüm medya heyecanını kaçırdıysanız…

…bu (bazı uzmanların muhtemelen pervasız bir aşırı basitleştirme olarak değerlendireceği şeyi affederseniz), takip edebilecek bilgi işlem cihazları oluşturmanın bir yolu. çoklu olası sonuçlar aynı anda bir hesaplama.

Büyük bir dikkatle ve belki biraz da şansla, bu, bazı algoritma türlerini doğru cevabı bulmak için yeniden yazabileceğiniz veya en azından olası her sonucu denemeden ve test etmeden bir dizi yanlış cevabı doğru bir şekilde atabileceğiniz anlamına gelir. birer birer.

Uygun bir şekilde güçlü ve güvenilir bir tanesinin gerçekten inşa edilebileceği varsayılarak, bir kuantum hesaplama cihazı kullanılarak iki ilginç kriptanalitik hızlandırma mümkündür:

• Grover'ın kuantum arama algoritması. Genellikle, sizinkinin listede olup olmadığını görmek için rastgele sıralanmış bir dizi cevap aramak istiyorsanız, kesin bir cevap almadan önce en kötü ihtimalle tüm listeyi karıştırmayı beklersiniz. Örneğin, bir belgenin şifresini çözmek için 128-bit AES şifre çözme anahtarını bulmak istiyorsanız, şu andan başlayarak tüm olası anahtarların listesini aramanız gerekir. 000..001, ..2, ..3, ve benzeri, sonuna kadar FFF..FFF (16 bayt değerinde FF), sorunu tamamladığınızdan emin olmak için. Diğer bir deyişle, 2'sini de denemek için bütçe ayırmanız gerekir.¹²⁸ doğru anahtarı bulmadan veya olmadığını belirlemeden önce olası anahtarlar. Bununla birlikte, Grover'ın algoritması, yeterince büyük ve güçlü bir kuantum bilgisayar verildiğinde, aynı başarıyı kare kök olağan çabanın, böylece kodu teorik olarak, sadece 2'de kırmak⁶⁴ yerine çalışır.
• Shor'un kuantum çarpanlara ayırma algoritması. Birkaç çağdaş şifreleme algoritması, iki büyük asal sayıyı birlikte çarpmanın hızlı bir şekilde yapılabileceği gerçeğine dayanırken, ürünlerini başladığınız iki sayıya bölmenin imkansız olduğu kadar iyidir. Bunun için bir fikir edinmek için, kalem-kağıt kullanarak 59×87'yi çarpmayı deneyin. Çıkarmak bir dakika kadar sürebilir (5133 cevaptır), ama o kadar da zor değil. Şimdi diğer yolu deneyin. Diyelim ki 4171'i iki faktörüne bölün. Çok daha zor! (43×97.) Şimdi bunu 600 basamaklı bir sayı ile yaptığınızı hayal edin. Basitçe söylemek gerekirse, ikramiyeye ulaşana veya bir cevap olmadığını bulana kadar 600 basamaklı sayıyı olası her 300 basamaklı asal sayıya bölmeye çalışmak zorunda kaldınız. Shor'un algoritması, ancak, bu sorunu aşağıdakilerle çözmeyi vaat ediyor: logaritma olağan çabanın sonucu. Bu nedenle, bir dizi 2048 ikili basamağı çarpanlara ayırmak, 1024 bitlik bir sayıyı çarpanlara ayırmanın iki katı kadar sürmelidir, 2047 bitlik bir sayıyı çarpanlara ayırmanın iki katı değil, büyük bir hızlanma anlamına gelir.

Tehdide karşı koymak

Grover'ın algoritmasından gelen tehdide, kullandığınız sayıların karesini alarak boyutunu artırarak basitçe karşılanabilir; bu, şifreleme karmanızdaki veya simetrik şifreleme anahtarınızdaki bit sayısını iki katına çıkarmak anlamına gelir. (Başka bir deyişle, şu anda SHA-256'nın iyi olduğunu düşünüyorsanız, bunun yerine SHA-512'yi kullanmak PQC'ye dayanıklı bir alternatif sağlayacaktır.)

Ancak Shor'un algoritmasına bu kadar kolay karşı konulamaz.

2048 bitlik bir genel anahtarın boyutunun yalnızca kare alarak değil, katlanarak büyütülmesi gerekir, böylece 2×2048=4096 bitlik bir anahtar yerine, imkansız 2 boyutunda yeni bir anahtara ihtiyacınız olur.²⁰⁴⁸ bitler…

…ya da Shor'un algoritmasının uygulanmadığı tamamen yeni bir tür kuantum sonrası şifreleme sistemini benimsemeniz gerekir.

ABD standartları kuruluşu NIST, PQC "rekabet" 2017 sonundan beri.

Süreç herkese açıktı, tüm katılımcılar memnuniyetle karşılandı, tüm algoritmalar açıkça yayınlandı ve kamu denetimi sadece mümkün değil, aynı zamanda aktif olarak teşvik:

Teklif Çağrısı. [Kapalı 2017-11-30]. […] Yeni açık anahtar şifreleme standartlarının, dünya çapında mevcut olan ve hassas devlet bilgilerini koruma yeteneğine sahip bir veya daha fazla sınıflandırılmamış, kamuya açıklanmış dijital imza, açık anahtar şifreleme ve anahtar oluşturma algoritmalarını belirtmesi amaçlanmaktadır. Kuantum bilgisayarların ortaya çıkışı da dahil olmak üzere, öngörülebilir geleceğe doğru.

Üç tur sunum ve tartışmadan sonra, NIST duyurdu, 2022-07-05 tarihinde, “standartlar” olarak kabul ettiği ve hemen geçerli olacak dört algoritma seçtiğini ve bunların hepsi kulağa hoş gelen isimlerle: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, ve SPHINCS+.

İlki (CRYSTALS-KYBER) denilen şey olarak kullanılır Anahtar Anlaşma Mekanizması (KEM), bir genel iletişim kanalının iki ucunun, bir oturumun değerindeki verileri gizli bir şekilde değiş tokuş etmek için tek seferlik bir özel şifreleme anahtarını güvenli bir şekilde oluşturduğu yer. (Basit ifadeyle: Snoopers sadece rendelenmiş lahana alır, bu yüzden konuşmaya kulak misafiri olamazlar.)

Diğer üç algoritma için kullanılır Dijital imzalar, böylece, sonunda çıkardığınız verilerin, gönderenin diğerine koyduğuyla tam olarak eşleşmesini sağlayarak, kurcalamayı önler ve bütünlüğü sağlarsınız. (Basit ifadeyle: herhangi biri verileri bozmaya veya bozmaya çalışırsa, bileceksiniz.)

Daha fazla algoritma gerekli

NIST, yeni standartları duyururken aynı zamanda bir dördüncü tur olası alternatif KEM'ler olarak dört algoritma daha öne sürüyor. (Yazma sırasında, aralarından seçim yapabileceğiniz üç onaylanmış dijital imza algoritmamız olduğunu, ancak yalnızca bir resmi KEM olduğunu unutmayın.)

Bunlar: BIKE, Classic McEliece, HQC ve SIKE.

İlginç bir şekilde, McEliece algoritması 1970'lerde, NIST'in yarışmasının başlamasından çok sonra, 2019'da ölen Amerikalı kriptograf Robert Mc Eliece tarafından icat edildi.

Ancak, günün popüler alternatifi olan Diffie-Hellman-Merkle algoritmasına (DHM veya bazen sadece DH) kıyasla çok büyük miktarda anahtar malzeme gerektirdiğinden hiçbir zaman tutmadı.

Ne yazık ki, üç Yuvarlak Dört algoritmadan biri, yani SIKE, kırılmış görünüyor.

başlıklı bir beyin büküm kağıdında SIDH ÜZERİNE ETKİLİ BİR ANAHTAR KURTARMA SALDIRISI (ÖN VERSİYON), Belçikalı kriptograflar Wouter Castryk ve Thomas Decru, SIKE algoritmasına ölümcül bir darbe indirmiş gibi görünüyor.

Merak ediyorsanız, SIKE kısaltması Süper Tekil İzogeni Anahtar Kapsülleme, ve SIDH şu anlama gelir: Süper Tekil İzogeny Diffie-Hellman, belirli bir kullanım SIKE algoritması bu sayede bir iletişim kanalının iki ucu, her bir ucun tek seferlik bir gizli şifreleme anahtarı olarak kullanmak üzere özel bir değer türetmesine izin veren bir grup genel veri alışverişi yapmak için DHM benzeri bir "kriptodans" gerçekleştirir.

Burada saldırıyı açıklamaya çalışmayacağız; sadece makalenin iddia ettiği şeyi tekrarlayacağız, yani:

Çok gevşek bir şekilde ifade etmek gerekirse, buradaki girdiler, süreçte kullanılan önceden belirlenmiş (ve dolayısıyla herkes tarafından bilinen) parametrelerle birlikte, anahtar oluşturma kripto dansındaki katılımcılardan biri tarafından sağlanan genel verileri içerir.

Ancak çıkarılan çıktı (olarak adlandırılan bilgiler izogeni φ yukarıda), sürecin asla açıklanmayan parçası olduğu varsayılır - sözde özel anahtar.

Başka bir deyişle, kriptograflar, anahtar kurulumu sırasında açıkça değiş tokuş edilen veriler gibi yalnızca genel bilgilerden, katılımcılardan birinin özel anahtarını kurtarabileceklerini iddia ederler.

Ve bir kez özel anahtarımı öğrendikten sonra, kolayca ve fark edilmeden benmişim gibi davranabilirsin, böylece şifreleme işlemi bozulur.

Görünüşe göre, anahtar kırma algoritmasının, günlük bir dizüstü bilgisayarda bulacağınız türde bir işlem gücüne sahip tek bir CPU çekirdeği kullanarak işini yapması yaklaşık bir saat sürüyor.

Bu, NIST'in temel şifreleme güvenliği düzeyi olan Düzey 1'i karşılayacak şekilde yapılandırıldığında SIKE algoritmasına aykırıdır.

Ne yapalım?

Hiçbir şey!

(Bu iyi haber.)

Makalenin yazarlarının önerdiği gibi, sonuçlarının henüz başlangıç ​​aşamasında olduğunu belirttikten sonra, "Mevcut durumla, SIDH, kamuya açık olarak oluşturulmuş herhangi bir taban eğrisi için tamamen kırılmış görünüyor."

(Bu kötü haber.)

Ancak, SIKE algoritmasının henüz resmi olarak onaylanmadığını düşünürsek, artık bu özel saldırıyı engellemek için uyarlanabilir (yazarların kabul ettiği bir şey olabilir) veya tamamen bırakılabilir.

Sonunda SIKE'a ne olursa olsun, bu, kendi şifreleme algoritmalarınızı icat etmeye çalışmanın neden tehlikelerle dolu olduğunun mükemmel bir hatırlatıcısıdır.

Ayrıca, neden tescilli şifreleme sistemlerinin algoritmanın kendisinin gizliliğine dayanan 2022'de güvenliklerini sürdürmek kesinlikle kabul edilemez.

SIKE gibi bir PQC algoritması, kamu incelemesine tabi tutulabilmesi için özel olarak ifşa edilmesine rağmen, dünyanın dört bir yanından uzmanlar tarafından beş yıldan fazla bir süre boyunca ikna edilmiş ve araştırılmışsa…

… o zaman kendinize, ev yapımı, görünümden gizlenen şifreleme algoritmalarınızın doğaya salındığında ne kadar başarılı olacağını sormanıza gerek yok!

---