Publication: Analysis of block ciphers using stochastic methods
Abstract
BLOK ŞİFRELEME ALGORİTMALARININ STOKASTİK METOTLAR YARDIMI İLE ANALİZİ Bu çalışmada blok şifreleme algoritmalarının analizi üzerinde durulmuştur. İki özel algoritma üzerinde çalıştık. Rijndael, ABD'nin yeni standart şifreleme algoritmasıdır. IDEA ise Markov şifresi kavramının ilk olarak geliştirildiği algoritmadır. Her iki algoritma da yaygın olarak kullanılmaktadır. Her bir algoritmanın özel yapılarını kullanarak bu algoritmaların bazı yeni özelliklerini ortaya çıkardık. Şifreleme algoritmalarının çıktılarını rastgele bir permütasyondan ayırt etmek ve yapılan saldırıların karmaşıklığını hesaplamak için temel olasılık ve istatistik yöntemlerini kullandık. Rijndael blok şifreleme algoritması için yarım kare özelliği bulunmuştur. Algoritmanın küçültülmüş hallerinde gözlenen ama gerçek algoritmada bulunmayan bazı özellikler ifade edilmiştir. Rijndael algoritmasına iki basamaktan oluşan bir eleme saldırısı geliştirilmiştir. Atağın birinci bölümünde bir değişkenin alabileceği tüm olası dizilimlerden oluşan bir küme çıkarılır. İkinci bölümde bu kümedeki dizilimlerden hiçbirini sağlamayan anahtar adayları elenir. IDEA blok şifreleme algoritması için, algoritmanın kelime tabanlı yapısının bir sonucu olan bazı değişkenlerin dağılımı ile ilgili özellikler sunulmuştur. Daha sonra bu özellikleri kullanarak iki tane kare-benzeri saldırı algoritması geliştirilmiştir. Bu özellikler IDEA algoritmasının çıktısını çok az sayıda seçilen mesaj kullanarak rastgele bir permütasyondan ayırdedebilmesi bakımından değerlidir. Bu özellikler daha da geliştirilerek, eleme saldırısı IDEA algoritmasına da uygulanmıştır. Mayıs, 2004 Hüseyin Demirci
ANALYSIS OF BLOCK CIPHERS USING STOCHASTIC METHODS In this study we have focused on cryptanalysis of block ciphers. We worked on two specific algorithms. Rijndael is the new standard encryption algorithm of USA, and IDEA is the block cipher where the concept of a Markov cipher has been developed. Both algorithms are being widely used. We have investigated new properties of these ciphers by exploiting the specific structure of each algorithm. We have used basic probability and statistics methods to distinguish the ciphers output from a random permutation and to evaluate the complexity of the developed attacks. For the Rijndael block cipher we have described the half square property. We have presented some square properties of mini versions of the cipher which can not be observed in the real version. We have also applied an elimination attack on Rijndael consisting of two steps. In the first part, we construct a set for the possible sequences of a variable. In the second part, we eliminate the key candidates from the lower part of the cipher which do not produce any of the elements of the previously calculated possible sequence set. For the IDEA block cipher we have presented properties related with the distribution of some variables as a result of the word structure. Then, we have developed two square-like attacks using these properties. These properties are strong in the sense that they provide to distinguish IDEA block cipher output from a random permutation with very few chosen plaintexts. The properties are further developed and the elimination attack has also been applied on IDEA. May, 2004 Hüseyin Demirci
ANALYSIS OF BLOCK CIPHERS USING STOCHASTIC METHODS In this study we have focused on cryptanalysis of block ciphers. We worked on two specific algorithms. Rijndael is the new standard encryption algorithm of USA, and IDEA is the block cipher where the concept of a Markov cipher has been developed. Both algorithms are being widely used. We have investigated new properties of these ciphers by exploiting the specific structure of each algorithm. We have used basic probability and statistics methods to distinguish the ciphers output from a random permutation and to evaluate the complexity of the developed attacks. For the Rijndael block cipher we have described the half square property. We have presented some square properties of mini versions of the cipher which can not be observed in the real version. We have also applied an elimination attack on Rijndael consisting of two steps. In the first part, we construct a set for the possible sequences of a variable. In the second part, we eliminate the key candidates from the lower part of the cipher which do not produce any of the elements of the previously calculated possible sequence set. For the IDEA block cipher we have presented properties related with the distribution of some variables as a result of the word structure. Then, we have developed two square-like attacks using these properties. These properties are strong in the sense that they provide to distinguish IDEA block cipher output from a random permutation with very few chosen plaintexts. The properties are further developed and the elimination attack has also been applied on IDEA. May, 2004 Hüseyin Demirci