Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 12/2019

03-07-2019

More accurate results on the provable security of AES against impossible differential cryptanalysis

Authors: Qian Wang, Chenhui Jin

Published in: Designs, Codes and Cryptography | Issue 12/2019

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Whether there exist longer impossible differentials than existing ones for a block cipher, is an important problem in the provable security evaluation of a block cipher against impossible differential cryptanalysis. In this paper, we give more accurate results for this problem for the AES. After investigating the differential properties of both the S-box and the linear layer of AES, we theoretically prove that there do not exist impossible concrete differentials longer than 4 rounds for AES by proving that any concrete differential is possible for the 5-round AES, under the only assumption that the round keys are independent and uniformly random. We use a tool, called “(w, d)-Dependent Tree (DT)”, to show how any concrete differential \(\varDelta X \rightarrow \varDelta Z\) can be connected in the middle of the 5-round AES by some DTs. Our method might shed some light on bounding the length of impossible differentials with the differential properties of the S-boxes considered for some SPN block ciphers.
previous article New rank codes based encryption scheme using partial circulant matrices
next article Necessary field size and probability for MDP and complete MDP convolutional codes
Footnotes
1
Note that we only need to consider (truncated) differentials that are non-trivial and we will take this as a default setting.
 
2
Note that for any fixed-key cipher, it always has impossible differentials for arbitrary rounds.
 
3
Here, (*) represents the nonzero byte.
 
Literature
1.
Bahrak B., Aref M.R.: Impossible differential attack on seven-round AES-128. IET Inf. Secur. 2(2), 28–32 (2008).CrossRef
2.
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. Lecture Notes in Computer Science, vol. 1592, pp. 12–23. Springer, Berlin (1999).CrossRef
4.
Blondeau C., Bogdanov A., Leander G.: Bounds in shallows and in miseries. In: R. Canetti, J.A. Garay (eds.) Advances in Cryptology-CRYPTO 2013-33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Part I, Lecture Notes in Computer Science, vol. 8042, pp. 204–221. Springer, Berlin (2013).
5.
6.
Boura C., Lallemand V., Naya-Plasencia M., Suder V.: Making the impossible possible. J. Cryptol. 31(1), 101–133 (2018).MathSciNetCrossRef
7.
8.
Canteaut A., Roué J.: On the behaviors of affine equivalent sboxes regarding differential and linear attacks. In: Oswald and Fischlin [27], pp. 45–74.CrossRef
9.
Cui T., Jia K., Fu K., Chen S., Wang M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. In: IACR Cryptology ePrint Archive, vol. 2016, p. 689 (2016).
10.
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).CrossRef
11.
Daemen J., Rijmen V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and Cryptography. Springer, Berlin (2002).CrossRef
12.
Daemen J., Rijmen V.: Understanding two-round differentials in AES. In: R.D. Prisco, M. Yung (eds.) Security and Cryptography for Networks, 5th International Conference, SCN 2006, Maiori, Italy, September 6–8, 2006. Lecture Notes in Computer Science, vol. 4116, pp. 78–94. Springer, Berlin (2006).
13.
Derbez P.: Note on impossible differential attacks. In: T. Peyrin (ed.) Fast Software Encryption-23rd International Conference, FSE 2016, Bochum, Germany, March 20–23, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9783, pp. 416–427. Springer, Berlin (2016).
14.
Even S., Mansour Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997).MathSciNetCrossRef
15.
Grassi L., Rechberger C., Rønjom S.: A new structural-differential property of 5-round AES. 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 II, Lecture Notes in Computer Science, vol. 10211, pp. 289–317. Springer, Berlin (2017).
16.
Kim J., Hong S., Lim J.: Impossible differential cryptanalysis using matrix method. Discret. Math. 310(5), 988–1002 (2010).MathSciNetCrossRef
17.
Knudsen L.R.: DEAL-A 128-bit block cipher. Complexity 258(2), 216 (1998).
18.
Knudsen L.R., Mathiassen J.E.: On the role of key schedules in attacks on iterated ciphers. In: P. Samarati, P.Y.A. Ryan, D. Gollmann, R. Molva (eds.) Computer Security-ESORICS 2004, 9th European Symposium on Research Computer Security, Sophia Antipolis, France, September 13–15, 2004, Proceedings, Lecture Notes in Computer Science, vol. 3193, pp. 322–334. Springer, Berlin (2004).CrossRef
19.
Knudsen L.R.: The Block Cipher Companion. Information Security and Cryptography. Springer, Berlin (2011).CrossRef
20.
Lai X., Massey J.L., Murphy S.: Markov ciphers and differential cryptanalysis. In: D.W. Davies (ed.) Advances in Cryptology-EUROCRYPT ’91, Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, April 8–11, 1991. Lecture Notes in Computer Science, vol. 547, pp. 17–38. Springer, Berlin (1991).
21.
Leander G., Minaud B., Rønjom S.: A generic approach to invariant subspace attacks: cryptanalysis of robin, iSCREAM and zorro. In: Oswald and Fischlin [27], pp. 254–283.CrossRef
22.
Li S., Song C.: Improved impossible differential cryptanalysis of ARIA. In: Proceedings of the 2008 International Conference on Information Security and Assurance ISA 2008, pp. 129–132 (2008).
23.
Lidl R., Niederreiter H.: Finite Fields. Cambridge University Press, Cambridge (1997).MATH
24.
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).CrossRef
25.
Mala H., Dakhilalian M., Rijmen V., Modarres-Hashemi M.: improved impossible differential cryptanalysis of 7-round AES-128. In: G. Gong, K.C. Gupta (eds.) Progress in Cryptology-INDOCRYPT 2010-11th International Conference on Cryptology in India, Hyderabad, India, December 12–15, 2010. Lecture Notes in Computer Science, vol. 6498, pp. 282–291. Springer, Berlin (2010).CrossRef
26.
Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: C. Wu, M. Yung, D. Lin (eds.) Information Security and Cryptology-7th International Conference, Inscrypt 2011, Beijing, China, November 30–December 3, 2011. Revised Selected Papers, Lecture Notes in Computer Science, vol. 7537, pp. 57–76. Springer, Berlin (2011).
27.
Oswald E., Fischlin M. (eds.): Advances in Cryptology-EUROCRYPT 2015–34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26–30, 2015. Part I, vol. 9056. Lecture Notes in Computer Science. Springer, Berlin (2015).
28.
Rønjom S., Bardeh N.G., Helleseth T.: Yoyo tricks with AES. In: T. Takagi, T. Peyrin (eds.) Advances in Cryptology-ASIACRYPT 2017-23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017. Part I, Lecture Notes in Computer Science, vol. 10624, pp. 217–243. Springer, Berlin (2017).CrossRef
29.
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. Part III, Lecture Notes in Computer Science, vol. 10212, pp. 185–215. Springer, Berlin (2017).
30.
Sun B., Liu M., Guo J., Qu L., Rijmen V.: New insights on AES-Like SPN ciphers. In: M. Robshaw, J. Katz (eds.) Advances in Cryptology-CRYPTO 2016-36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2016. Part I, Lecture Notes in Computer Science, vol. 9814, pp. 605–624. Springer, Berlin (2016).
31.
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. Part I, Lecture Notes in Computer Science, vol. 9665, pp. 196–213. Springer, Berlin (2016).CrossRef
32.
Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: P. Sarkar, T. Iwata (eds.) Advances in Cryptology-ASIACRYPT 2014-20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014. Part I, Lecture Notes in Computer Science, vol. 8873, pp. 158–178. Springer, Berlin (2014).
33.
34.
Wang Q., Jin C.: Upper bound of the length of truncated impossible differentials for AES. Des. Codes Cryptogr. 86(7), 1541–1552 (2018).MathSciNetCrossRef
35.
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. Lecture Notes in Computer Science, vol. 7668, pp. 283–302. Springer, Berlin (2012).
36.
Xue W., Wang Q., Lai X.: Applicability of Markov-cipher theory on actual key schedules. J. Cryptol. Res. 1(1), 83–90 (2014).
Metadata
Title
More accurate results on the provable security of AES against impossible differential cryptanalysis
Authors
Qian Wang
Chenhui Jin
Publication date
03-07-2019
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 12/2019
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-019-00660-7

Other articles of this Issue 12/2019

Designs, Codes and Cryptography 12/2019 Go to the issue

OriginalPaper

Some (almost) optimally extendable linear codes

OriginalPaper

A new piggybacking design for systematic MDS storage codes

OriginalPaper

Steiner systems and 2-designs from ternary linear codes of length

OriginalPaper

Strongly leakage resilient authenticated key exchange, revisited

OriginalPaper

Necessary field size and probability for MDP and complete MDP convolutional codes

OriginalPaper

Construction of resilient Boolean functions in odd variables with strictly almost optimal nonlinearity

Premium Partner

    Image Credits