A new method for accelerating impossible differential cryptanalysis and its application on LBlock



1 Department of Information and Communication Technology, Malek-e-Ashtar University of Technology, Tehran, Iran

2 Institute of Research on Information and Communication Security (IRICS), Malek-e-Ashtar University of Technology, Tehran, Iran


Impossible differential cryptanalysis, the extension of differential cryptanalysis, is one of the most efficient attacks against block ciphers. This cryptanalysis method has been applied to most of the block ciphers and has shown significant results. Using structures, key schedule considerations, early abort, and pre-computation are some common methods to reduce complexities of this attack. In this paper, we present a new method for decreasing the time complexity of impossible differential cryptanalysis through breaking down the target key space into subspaces, and extending the results on subspaces to the main target key space. The main advantage of this method is that there is no need to consider the effects of changes in the values of independent key bits on each other. Using the 14-round impossible differential characteristic observed by Boura et al. at ASIACRYPT 2014, we implement this method on 23-round LBlock and demonstrate that it can reduce the time complexity of the previous attacks to 271.8 23-round encryptions using 259 chosen plaintexts and 2 73 blocks of memory.


[1] Biham E., Shamir A.: "Differential cryptanalysis of DES-like cryptosystems", Journal of Cryptology, pp. 3-72, 1991.

[2] Biham E., Biryukov A., Shamir A.: "Cryptanalysis of Skipjack reduced to 31 rounds", Proc. of Int. Conf. EUROCRYPT'99, LNCS 1592, pp. 12-23, 1999.

[3] Wu W., Zhang L.: "LBlock: A Lightweight Block Cipher", Proc. Int. Conf. ACNS 2011, LNCS 6715, pp. 327-344, 2011.

[4] Liu Y., Gu D., Liu Z., Li W.: "Impossible differential attacks on reduced-round LBlock", Proc. Int. Conf. ISPEC 2012, LNCS 7232, pp. 97-108, 2012.

[5] Karakoc F., Demirci H., Harmanci A.E.: "Impossible differential cryptanalysis of reduced-round LBlock", Proc. Int. Conf. WISTP 2012, LNCS 7322, pp. 179-188, 2012.

[6] Minier M., Naya-Plasenica M.: "A related key impossible differential attack against 22 rounds of the lightweight block cipher LBlock", Inf. Process. Lett., 112(16), pp. 624-629, 2012.

[7] Knudsen L.R.: "DEAL A 128-bit cipher", Technical Report, Department of Informatics, University of Bergen, Norway, 1998.

[8] Wen L., Wang M., Zhao J.: "Related-key impossible differential attack on reduced-round LBlock", Journal of Computer Science and Technology, 29(1), pp. 165-176, 2014.

[9] Chen J., Futa Y., Miyaji A., Su C.: "Impossible differential cryptanalysis of LBlock with concrete investigation of key scheduling algorithm", Proc. Int. Conf. NSS 2014, LNCS 8792, pp. 184-197, 2014.

[10] Boura C., Minier M., Naya-Plasencia M., Suder V.: "Improved Impossible Differential Attacks against Round-Reduced LBlock", Cryptology ePrint Archive, Report 2014/279, 2014.

[11] shakiba M., Dakhilalian M., Mala H.: "On computational complexity of impossible differential cryptanalysis", Inf. Process. Lett., 114, pp. 252-255, 2014.

[12] Boura C., Minier M., Naya-Plasencia M., Suder V.: "Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and SIMON (Full Version)", Cryptology ePrint Archive, Report 2014/699, 2014.

[13] Boura C., Minier M., Naya-Plasencia M., Suder V.: "Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and SIMON", Proc. Int. Conf. ASIACRYPT 2014, LNCS 8873, pp. 179-199, 2014.

[14] Soleimani H., Nyberg K.: "Zero-Correlation Linear Cryptanalysis of Reduced-Round LBlock", Journal of Des. Codes Cryptogr., pp. 683-698, 2014.

[15] Wang Y., Wu W.: "Improved Multidimensional Zero-Correlation Linear Cryptanalysis and Applications to LBlock and TWINE", Proc. Int. Conf. ACISP 2014, LNCS 8544, pp. 1-17, 2014.

[16] Sasaki Y., Wang L.: "Comprehensive Study of Integral Analysis on 22-round LBlock", Proc. Int. Conf. ICISC 2012, LNCS 7839, pp. 156-169, 2012.

[17] Sasaki Y., Wang L.: Meet-in-the-Middle Technique for Integral Attacks against Feistel Ciphers', Proc. Int. Conf. SAC 2012, LNCS 7707, pp. 235-251, 2013.

[18] Wang Y., Wu W., Yu X., Zhang L.: "Security on LBlock against Biclique Cryptanalysis", Proc. Int. Conf. WISA 2012, LNCS 7690, pp. 1-14, 2012.

[19] Bogdanov A., Boura C., Rijmen V., Wang M., Wen L., Zhao J.: "Key Difference Invarient Bias in Block Ciphers", Proc. Int. Conf. ASIACRYPT 2013, LNCS 8269, pp. 357-376, 2013.

[20] AlTawy R., Tolba M., Youssef A. M.: "A Higher Order Key Partitioning Attack with Application to LBlock", Proc. Int. Conf. C2SI 2015, LNCS 9084, pp. 215-227, 2015.

[21] Khalesi A., Bahramgiri H., Mansuri D.: "Impossible Differential Cryptanalysis of LBlock Through Breaking Down the Key Space", Proc. Int. Conf. ISCISC 2014, 2014.