Improbable differential cryptanalysis

Abstract

Doğru anahtar kullanıldığında daha az ihtimalle gözlemlenen diferansiyeller kullanan ve olası olmayan diferansiyel kriptanaliz ismini verdiğimiz yeni bir istatistiksel kriptanaliz tekniği sunuyoruz. Bu tür atakların veri karmaşıklığının yaklaşık olarak hesaplarını ve imkansız diferansiyelleri olası olmayan diferansiyellere genişleten bir metod sunuyoruz. Bu genişletme tekniğiyle Clefia şifresinin 13, 14 ve 15 döngüsüne ataklar sunuyoruz. Bu ataklar Clefia için bilinen en iyi ataklardır. Değişim kutuları için rahatsız edilmemiş bit ismini verdiğimiz yeni bir özellik öneriyoruz ve Present ve Serpent şifrelerine bu özelliği kullanarak saldırıyoruz. Rahatsız edilmemiş bit kullanmadan Present şifresinin en fazla 7 döngüsüne olası olmayan diferansiyel atak yapabildik. Ama bu şifredeki 6 rahatsız edilmemiş bit sayesinde 10 döngülük olası olmayan diferansiyel ile 13 döngüsünü kırabiliyoruz. Benzer şekilde rahatsız edilmemiş bit kullanmadan Serpent şifresine en fazla 3.5 döngülük imkansız diferansiyel bulabildik. Ama rahatsız edilmemiş bitler sayesinde 5.5 döngülük imkansız diferansiyel elde ettik ve şifrenin 7 döngüsüne olası olmayan diferansiyel atak uygulayabildik. Bu nedenlerle değişim kutusu tasarımcılarının rahatsız edilmemiş bitlerden kaçınmalarını tavsiye ediyoruz. Sunduğumuz diğer bir değişim kutusu özelliği de diferansiyel faktörler. Anahtar elde etme ataklarında diferansiyel faktörü olan değişim kutularına saldırırken, buradaki anahtar bitlerinin bazılarını elde etmek mümkün olmayabilir. Bu özellik saldırıyı gerçekleştirenin daha az anahtar bitini tahmin etmesine ve bu sayede atağın zaman karmaşıklığının azalmasına neden olacaktır. Diferansiyel faktörleri kullanarak Serpent şifresine Dunkelman ve diğerlerinin yaptığı 10, 11 ve 12 döngülük diferansiyel-lineer atakların zaman karmaşıklığının sırasıyla 4, 4 ve 8de bire azaltılabileceğini gösteriyoruz.

We present a new statistical cryptanalytic technique that we call improbable differential cryptanalysis which uses a differential that is less probable when the correct key is used. We provide data complexity estimates for this kind of attacks and we also show a method to expand impossible differentials to improbable differentials. By using this expansion method, we cryptanalyze 13, 14, and 15-round Clefia for the key sizes of length 128, 192, and 256 bits, respectively. These are the best cryptanalytic results on Clefia up to this date. We introduce a new criteria for evaluating S-boxes that we call undisturbed bits and attack Present and Serpent by exploiting their S-boxes. Without using undisturbed bits, the longest improbable differential attack we could find for Present had a length of 7-rounds. However, we show that Present has 6 undisturbed bits and by using them, we can construct 10-round improbable differentials and attack Present reduced to 13 rounds. Similarly, without using undisturbed bits, the longest impossible differential we could find on Serpent had a length of 3.5 rounds. However, we obtained four 5.5-round impossible differentials on Serpent and provided a 7-round improbable differential attack. Hence, undisturbed bits should be avoided by S-box designers. Moreover, we provide a second S-box property that we call differential factors. A key recovery attack may not capture the whole subkey corresponding to a S-box with a differential factor. This helps the attacker to guess less subkey bits and reduce the time complexity of the attack. By using differential factors, we show that 10, 11, and 12-round differential-linear attacks of Dunkelman et al. on Serpent can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively. Furthermore, we slightly reduce the data complexity of these attacks by changing the differential with a more probable one but end up with an attack with higher time complexity.