XSL saldırısı - XSL attack

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (Kasım 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

İçinde kriptografi, Genişletilmiş Seyrek Doğrusallaştırma (XSL) saldırısı bir yöntemdir kriptanaliz için blok şifreleri. Saldırı ilk olarak 2002 yılında araştırmacılar tarafından yayınlandı Nicolas Courtois ve Josef Pieprzyk. Kırılma potansiyeline sahip olduğu iddia edildiği için bazı tartışmalara neden olmuştur. Gelişmiş Şifreleme Standardı (AES) şifre, Ayrıca şöyle bilinir Rijndael, daha hızlı Ayrıntılı arama. AES, ticarette ve hükümette gizli bilgilerin iletimi için zaten yaygın olarak kullanıldığından, anahtara sahip olmadan gizli mesajı almak için gereken süreyi kısaltabilecek bir teknik bulmanın geniş etkileri olabilir.

Yöntemin yüksek bir iş faktörü vardır ve bu, azaltılmadıkça, tekniğin kapsamlı bir aramaya kıyasla AES'yi kırma çabasını azaltmadığı anlamına gelir. Bu nedenle, yakın gelecekte blok şifrelerin gerçek dünyadaki güvenliğini etkilemez. Bununla birlikte, saldırı bazı uzmanların mevcut AES'nin cebirsel basitliğinden daha büyük bir rahatsızlık ifade etmesine neden oldu.

Genel olarak, XSL saldırısı önce bir şifrenin iç kısımlarını analiz etmeye ve bir şifreleme sistemi türetmeye dayanır. ikinci dereceden eşzamanlı denklemler. Bu denklem sistemleri tipik olarak çok büyüktür, örneğin 1.600 ile 8.000 denklem değişkenler 128 bit AES için. Bu tür sistemleri çözmek için çeşitli yöntemler bilinmektedir. XSL saldırısında, adı verilen özel bir algoritma Genişletilmiş Seyrek Doğrusallaştırma, daha sonra bu denklemleri çözmek ve anahtar.

Saldırı, yalnızca bir avuç dolusu bilinen düz metinler gerçekleştirmek; önceki kriptanaliz yöntemleri, örneğin doğrusal ve diferansiyel kriptanaliz, genellikle gerçekçi olmayan çok sayıda bilinen veya seçili düz metinler.

Çok değişkenli ikinci dereceden denklemleri çözme

Çözme çok değişkenli sonlu bir sayı kümesi üzerindeki ikinci dereceden denklemler (MQ) bir NP-zor kriptografide çeşitli uygulamalarda problem (genel durumda). XSL saldırısı, MQ ile mücadele için verimli bir algoritma gerektirir. 1999'da Kipnis ve Shamir belirli bir genel anahtar algoritması, olarak bilinir Gizli Alan Denklemleri şema (HFE), bir üst belirlenmiş sistem ikinci dereceden denklemlerin (bilinmeyenlerden daha fazla denklem). Bu tür sistemleri çözmek için bir teknik, doğrusallaştırma, her ikinci dereceden terimin bağımsız bir değişkenle değiştirilmesini ve ortaya çıkan doğrusal sistemi aşağıdaki gibi bir algoritma kullanarak çözmeyi içerir: Gauss elimine etme. Başarılı olmak için doğrusallaştırma yeterli Doğrusal bağımsız denklemler (yaklaşık olarak terim sayısı kadar). Bununla birlikte, HFE'nin kriptanalizi için çok az denklem vardı, bu nedenle Kipnis ve Shamir, yeniden doğrusallaştırmaDoğrusallaştırmadan sonra ekstra doğrusal olmayan denklemlerin eklendiği ve sonuçtaki sistemin ikinci bir doğrusallaştırma uygulamasıyla çözüldüğü bir teknik. Yeniden doğrusallaştırma, diğer şemalara uygulanabilecek kadar genel olduğunu kanıtladı.

2000 yılında, Courtois ve ark. olarak bilinen MQ için geliştirilmiş bir algoritma önerdi XL (için Genişletilmiş Doğrusallaştırma), denklemlerin sayısını tümü ile çarparak arttıran tek terimli belli derece. Karmaşıklık tahminleri, XL saldırısının AES gibi blok şifrelerden türetilen denklemlere karşı çalışmayacağını gösterdi. Bununla birlikte, üretilen denklem sistemleri özel bir yapıya sahipti ve XSL algoritması, XL'in bu yapıdan yararlanabilecek bir iyileştirmesi olarak geliştirildi. XSL'de denklemler yalnızca dikkatlice seçilmiş tek terimlilerle çarpılır ve çeşitli varyantlar önerilmiştir.

XL ve türev algoritmalarının etkinliği ile ilgili araştırmalar devam etmektedir (Yang ve Chen, 2004).

Şifreleri engelleme uygulaması

Courtois ve Pieprzyk (2002) şunu gözlemledi: AES (Rijndael) ve kısmen de Yılan ikinci dereceden denklemler sistemi olarak ifade edilebilir. Değişkenler yalnızca düz metin, şifreli metin ve anahtar bitleri, fakat aynı zamanda algoritma içindeki çeşitli ara değerler. S-kutusu AES, cebirsel olarak basit olana dayandığından, bu tür analizlere karşı özellikle savunmasız görünmektedir. ters fonksiyon. Daha sonra, hangi denklem sistemlerinin üretilebileceğini görmek için diğer şifreler üzerinde çalışıldı (Biryukov ve De Cannière, 2003) Kamelya, KHAZAD, MISTY1 ve KASUMI. Diğer kriptanaliz biçimlerinden farklı olarak, örneğin diferansiyel ve doğrusal kriptanaliz, sadece bir veya iki bilinen düz metinler gerekmektedir.

XSL algoritması, üretilen denklem sistemlerinin türünü çözmek için uyarlanmıştır. Courtois ve Pieprzyk, "iyimser bir değerlendirme, XSL saldırısının Rijndael'i [256 bit ile] ve Serpent'i [192 ve 256 bitlik anahtar uzunlukları için] kırabileceğini gösteriyor." Ancak analizleri evrensel olarak kabul edilmiyor. Örneğin:

Courtois-Pieprzyk çalışmasının kusurlu olduğuna inanıyorum. Doğrusal bağımsız denklemlerin sayısını aşıyorlar. Sonuç, aslında sistemi çözmek için yeterli doğrusal denklemlere sahip olmadıklarıdır ve yöntem Rijndael'i bozmaz… Yöntemin bir değeri vardır ve araştırılmaya değerdir, ancak Rijndael'i olduğu gibi bozmaz.

— Don Bakırcı, Crypto-Gram 15 Ekim 2002: Okuyucuların Yorumları

Rijndael'in mucitlerinden Bonn 2004 AES 4 Konferansı'nda, Vincent Rijmen, "XSL saldırısı bir saldırı değil, bir rüya." yorumunu yaptı. Courtois hemen cevap verdi, "XSL bir rüya olabilir. Aynı zamanda çok kötü bir rüya olabilir ve bir kabusa dönüşebilir."^[1] Ancak ne daha sonraki bir kağıt ne de NSA veya NIST Courtois'in bu sözüne herhangi bir destek verin.

2003'te, Murphy ve Robshaw AES'nin alternatif bir tanımını keşfetti, onu "BES" adı verilen daha büyük bir şifreye gömerek, tek bir alan, GF (2⁸). Bu sisteme monte edilen bir XSL saldırısı, AES'yi yaklaşık 2 karmaşıklıkla bozan daha basit bir denklem seti sağlar.¹⁰⁰Courtois ve Pieprzyk analizi doğruysa. 2005 yılında Cid ve Leurent, XSL algoritmasının önerilen biçiminde AES denklem sistemini çözmek için etkili bir yöntem sağlamadığına dair kanıt verdi; ancak Courtois bulgularına itiraz etti.^{[kaynak belirtilmeli ]} FSE 2007'de Chu-Wee Lim ve Khoongming Khoo, bunun^{[açıklama gerekli ]} muhtemelen sunulduğu gibi çalışamaz.^{[kaynak belirtilmeli ]}

XSL bazı modern algoritmalara karşı çalışsa bile, saldırı şu anda pratik güvenlik açısından çok az tehlike arz etmektedir. Birçok modern kriptanalitik sonuç gibi, bu sözde bir "sertifikasyon zayıflığı" olacaktır: kaba kuvvet saldırısı, gerekli kaynaklar hala çok büyük ve gerçek dünyadaki sistemlerin kullanılmasıyla tehlikeye atılması pek olası değil. Bununla birlikte, gelecekteki iyileştirmeler bir saldırının pratikliğini artırabilir. Bu tür bir saldırı yeni ve beklenmedik olduğu için, bazıları kriptograflar Rijndael gibi şifrelerin cebirsel basitliğinden duyulan rahatsızlığı ifade etmişlerdir. Bruce Schneier ve Niels Ferguson "AES ile ilgili bir eleştirimiz var: güvenliğe pek güvenmiyoruz ... Bizi AES hakkında en çok endişelendiren basit cebirsel yapısı ... Bildiğimiz başka hiçbir blok şifrenin bu kadar basit bir cebirsel temsili yoktur. Hiçbir fikrimiz yok. bunun bir saldırıya yol açıp açmadığı, ancak bilmemek AES kullanımı konusunda şüpheci olmak için yeterli bir nedendir. " (Pratik Kriptografi, 2003, s. 56–57)

Referanslar

• Alex Biryukov, Christophe De Cannière (2003). Johansson, Thomas (ed.). İkinci Dereceden Denklemlerin Blok Şifreleri ve Sistemleri. LNCS. Bilgisayar Bilimlerinde Ders Notları. 2887. s. 274–289. doi:10.1007 / b93938. ISBN  978-3-540-20449-7.
• Nicolas Courtois; Alexander Klimov; Jacques Patarin; Adi Shamir (2000). Çok Değişkenli Polinom Denklemlerinin Aşırı Tanımlanmış Sistemlerini Çözmek İçin Etkin Algoritmalar (PDF). LNCS. Bilgisayar Bilimlerinde Ders Notları. 1807. s. 392–407. doi:10.1007/3-540-45539-6_27. ISBN  978-3-540-67517-4.
• Nicolas Courtois; Josef Pieprzyk (2002). Aşırı Tanımlı Denklem Sistemleri ile Blok Şifrelerin Kriptanalizi. LNCS. Bilgisayar Bilimlerinde Ders Notları. 2501. s. 267–287. doi:10.1007/3-540-36178-2_17. ISBN  978-3-540-00171-3.
• Aviad Kipnis; Adi Shamir (1999). HFE Açık Anahtarlı Kripto Sisteminin Yeniden Doğrusallaştırma ile Kriptanalizi. LNCS. Bilgisayar Bilimlerinde Ders Notları. 1666. s. 19–30. doi:10.1007/3-540-48405-1_2. ISBN  978-3-540-66347-8.
• Chu-Wee Lim; Khoongming Khoo (2007). BES'e Uygulanan XSL Analizi (PDF). LNCS. Bilgisayar Bilimlerinde Ders Notları. 4593. sayfa 242–253. doi:10.1007/978-3-540-74619-5_16. ISBN  978-3-540-74617-1.
• Dana Mackenzie (2003). "Bir şans oyunu". Yeni Bilim Adamı. 178 (2398): 36.
• Sean Murphy; Matthew J. B. Robshaw (2002). AES içindeki Temel Cebirsel Yapı. LNCS. Bilgisayar Bilimlerinde Ders Notları. 2442. s. 1–16. CiteSeerX  10.1.1.20.5249. doi:10.1007/3-540-45708-9_1. ISBN  978-3-540-44050-5.
• S. Murphy, M. Robshaw AES Güvenliği ve XSL Tekniği Üzerine Yorumlar.
• Bo-Yin Yang, Jiun-Ming Chen (2004). Wang, Huaxiong; Pieprzyk, Josef; Varadharajan, Vijay (editörler). XL'nin Küçük Alanlar Üzerindeki Teorik Analizi (PDF). LNCS. Bilgisayar Bilimlerinde Ders Notları. 3108. s. 277–288. doi:10.1007 / b98755. ISBN  978-3-540-22379-5.
• C. Cid, G. Leurent (2005). Roy, Bimal (ed.). XSL Algoritmasının Analizi (PDF). LNCS. Bilgisayar Bilimlerinde Ders Notları. 3788. s. 333–335. doi:10.1007/11593447. ISBN  978-3-540-30684-9.
• C. Diem (2004). Lee, Pil Joong (ed.). XL-Algoritması ve Değişmeli Cebirden Bir Varsayım (PDF). LNCS. Bilgisayar Bilimlerinde Ders Notları. 3329. s. 323–337. doi:10.1007 / b104116. ISBN  978-3-540-23975-8.

Dış bağlantılar

• Courtois'in AES'deki sayfası
• J. J. G. Savard'ın XSL saldırısının açıklaması olan "Kuadratik Kriptanaliz"
• T. Moh'dan "AES bozuk DEĞİL"
• EPrint üzerine Courtois ve Pieprzyk kağıdı
• Yorum Kripto gram haber bülteni: [1], [2], [3].
• AES ve XSL'ye genel bakış