Improbable differential cryptanalysis

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2014

Öğrenci: CİHANGİR TEZCAN

Eş Danışman: ALİ DOĞANAKSOY, ERSAN AKYILDIZ

Özet:

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 \textsc{Clefia} for the key sizes of length 128, 192, and 256 bits, respectively. These are the best cryptanalytic results on \textsc{Clefia} up to this date. We introduce a new criteria for evaluating S-boxes that we call undisturbed bits and attack \textsc{Present} and \textsc{Serpent} by exploiting their S-boxes. Without using undisturbed bits, the longest improbable differential attack we could find for \textsc{Present} had a length of 7-rounds. However, we show that \textsc{Present} has 6 undisturbed bits and by using them, we can construct 10-round improbable differentials and attack \textsc{Present} reduced to 13 rounds. Similarly, without using undisturbed bits, the longest impossible differential we could find on \textsc{Serpent} had a length of 3.5 rounds. However, we obtained four 5.5-round impossible differentials on \textsc{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 \textsc{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.