×

Bounding the length of impossible differentials for SPN block ciphers. (English) Zbl 1475.94173

Summary: Evaluating the security of a block cipher against impossible differential cryptanalysis, is an important aspect during the design process. The maximum length of impossible differentials is often used to evaluate this security. There have been many methods on giving upper bounds on the length of impossible differentials or finding longer impossible differentials. Two notable examples are the “Primitive Index” method proposed by B. Sun et al. [Lect. Notes Comput. Sci. 9665, 196–213 (2016; Zbl 1347.94058)] and the MILP method proposed by Y. Sasaki and Y. Todo [ibid. 10212, 185–215 (2017; Zbl 1394.94941)]. However, these existing methods can only give upper bounds for some special SPN block ciphers or cannot give upper bounds due to the high time complexity. In this paper, we show that when ignoring the differential property of the underlying S-box, giving upper bounds on the length of impossible differentials is a linear problem. By using linear algebra, we propose the Expansion Index of the linear layer, with which we can give upper bounds on the length of impossible differentials for any SPN block cipher with the detail of the S-box omitted. The core of this method is establishing and solving systems of linear equations, thus the verification of a single differential has linear time complexity. What’s more, to give upper bounds with this method, we only need to establish and solve systems for differentials whose input and output differences have only one active S-box, which greatly reduces its time complexity from \(O(2^t)\) to \(O(t)\) (here \(t\) denotes the number of S-boxes in the S-layer). The method in this paper is implemented in C and encapsulated into a tool freely available to readers. By applying our method on some SPN block ciphers, we give, for the first time, upper bounds on the length of impossible differentials for Midori, Skinny, CRYPTON, mCrypton, Minalpher.

MSC:

94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block cipher for low energy. In: T. Iwata, J.H. Cheon (eds.) Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9453, pp. 411-436. Springer, Berlin (2015). · Zbl 1382.94057
[2] Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: M. Robshaw, J. Katz (eds.) Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815, pp. 123-153. Springer, Berlin (2016). · Zbl 1372.94412
[3] Biham E., Biryukov A., Shamir A.: Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: J. Stern (ed.) Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding. Lecture Notes in Computer Science, vol. 1592, pp. 12-23. Springer, Berlin (1999). · Zbl 0927.94013
[4] Boura, C.; Coggia, D., Efficient MILP modelings for sboxes and linear layers of SPN ciphers, IACR Trans. Symmetric Cryptol., 2020, 3, 327-361 (2020)
[5] Boura, C.; Lallemand, V.; Naya-Plasencia, M.; Suder, V., Making the impossible possible, J. Cryptol., 31, 1, 101-133 (2018) · Zbl 1421.94041
[6] Cui, T.; Jia, K.; Fu, K.; Chen, S.; Wang, M., New automatic search tool for impossible differentials and zero-correlation linear approximations, IACR Cryptol., 2016, 689 (2016)
[7] Cui, T.; Jin, C.; Zhang, B.; Chen, Z.; Zhang, G., Searching all truncated impossible differentials in SPN, IET Inf. Secur., 11, 2, 89-96 (2017)
[8] Daemen, J.; Rijmen, V., The Design of Rijndael: AES—The Advanced Encryption Standard (2002), Berlin: Springer, Berlin · Zbl 1065.94005
[9] Kim, J.; Hong, S.; Lim, J., Impossible differential cryptanalysis using matrix method, Discret. Math., 310, 5, 988-1002 (2010) · Zbl 1235.94048
[10] Knudsen L.R.: DEAL - A 128-bit Block Cipher. Complexity (1998).
[11] Kwon D., Kim J., Park S., Sung S.H., Sohn Y., Song J.H., Yeom Y., Yoon E., Lee S., Lee J., Chee S., Han D., Hong J.: New block cipher: ARIA. In: J.I. Lim, D.H. Lee (eds.) Information Security and Cryptology - ICISC 2003, 6th International Conference, Seoul, Korea, November 27-28, 2003, Revised Papers. Lecture Notes in Computer Science, vol. 2971, pp. 432-445. Springer, Berlin (2003). · Zbl 1092.94509
[12] Lim C.H.: A revised version of crypton - crypton V1.0. In: L.R. Knudsen (ed.) Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, March 24-26, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1636, pp. 31-45. Springer, Berlin (1999). · Zbl 0942.94002
[13] Lim C.H., Korkishko T.: mCrypton—a lightweight block cipher for security of low-Cost RFID tags and sensors. In: J. Song, T. Kwon, M. Yung (eds.) Information Security Applications, 6th International Workshop, WISA 2005, Jeju Island, Korea, August 22-24, 2005, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3786, pp. 243-258. Springer (2005).
[14] Luo, Y.; Lai, X.; Wu, Z.; Gong, G., A unified method for finding impossible differentials of block cipher structures, Inf. Sci., 263, 211-220 (2014) · Zbl 1345.94078
[15] Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects - revealing structural properties of several ciphers. In: J. Coron, J.B. Nielsen (eds.) Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III. Lecture Notes in Computer Science, vol. 10212, pp. 185-215 (2017). · Zbl 1394.94941
[16] Sasaki Y., Todo Y., Aoki K., Naito Y., Sugawara T., Murakami Y., Matsui M., Hirose S.: Minalpher v1.1. Submitted to CAESAR (2015).
[17] Sun B., Liu M., Guo J., Rijmen V., Li R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: M. Fischlin, J. Coron (eds.) Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9665, pp. 196-213. Springer, Berlin (2016). · Zbl 1347.94058
[18] Wang, Q.; Jin, C., More accurate results on the provable security of AES against impossible differential cryptanalysis, Des. Codes Cryptogr., 87, 12, 3001-3018 (2019) · Zbl 1423.94112
[19] Wu S., Wang M.: Automatic search of truncated impossible differentials for word-oriented block ciphers. In: S.D. Galbraith, M. Nandi (eds.) Progress in Cryptology - INDOCRYPT 2012, 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7668, pp. 283-302. Springer, Berlin (2012). · Zbl 1295.94157
[20] Yang, D.; Qi, W.; Chen, H., Provable security against impossible differential and zero correlation linear cryptanalysis of some Feistel structures, Des. Codes Cryptogr., 87, 11, 2683-2700 (2019) · Zbl 1440.94084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.