logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 3: 032101(2019) https://doi.org/10.1007/s11432-017-9365-4

Improved impossible differential cryptanalysis of large-block Rijndael

More info
  • ReceivedNov 28, 2017
  • AcceptedJan 31, 2018
  • PublishedJul 6, 2018

Abstract

Rijndael is a substitution-permutation network (SPN) block cipher for the AES development process. Its block and key sizes range from 128 to 256 bits in steps of 32 bits, which can be denoted by Rijndael-$b$-$k$, where $b$ and $k$ are the block and key sizes, respectively. Among them, Rijndael-128-128/192/256, that is, AES, has been studied by many researchers, and the security of other large-block versions of Rijndael has been exploited less frequently. However, more attention has been paid to large-block versions of block ciphers with the fast development of quantum computers. In this paper, we propose improved impossible differential attacks on 10-round Rijndael-256-256, 10-round Rijndael-224-256, and 9-round Rijndael-224-224 using precomputation tables, redundancies of key schedules, and multiple impossible differentials. For 10-round Rijndael-256-256, the data, time, and memory complexities of our attack were approximately $2^{244.4}$ chosen plaintexts, $2^{240.1}$ encryptions, and $2^{181.4}$ blocks, respectively. For 10-round Rijndael-224-256, the data, time, and memory complexities of our attack were approximately $2^{214.4}$ chosen plaintexts, $2^{241.3}$ encryptions, and $2^{183.4}$ blocks, respectively. For 9-round Rijndael-224-224, the data, time, and memory complexities of our attack are approximately $2^{214.4}$ chosen plaintexts, $2^{113.4}$ encryptions, and $2^{87.4}$ blocks, respectively, or $2^{206.6}$ chosen plaintexts, $2^{153.6}$ encryptions, and $2^{111.6}$ blocks, respectively. To the best of our knowledge, our results are currently the best on Rijndael-256-256 and Rijndael-224-224/256.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61402288, 61772129, 61601292, 61672347, 61472250), Foundation of Science and Technology on Information Assurance Laboratory (Grant No. KJ-17-008), Shanghai Natural Science Foundation (Grant Nos. 15ZR1400300, 16ZR1401100), Opening Project of the Shanghai Key Laboratory of Integrated Administration Technologies for Information Security (Grant No. AGK201703), Opening Project of the Shanghai Key Laboratory of Scalable Computing and Systems, National Cryptography Development Fund, and Fundamental Research Funds for the Central Universities.


References

[1] Daemen J, Rijmen V. The design of Rijndael: AES, the advanced encryption standard. In: Information Security and Cryptography. Berlin: Springer, 2002. Google Scholar

[2] Daor J, Daemen J, Rijmen V. AES Proposal: Rijndael. http://jda.noekeon.org/ 1999. Google Scholar

[3] Phan R C W. Impossible differential cryptanalysis of 7-round Advanced Encryption Standard (AES). Inf Process Lett, 2004, 91: 33-38 CrossRef Google Scholar

[4] Biham E, Dunkelman O, Keller N. Related-key impossible differential attacks on 8-round AES-192. In: Proceedings of Cryptographers' Track at the RSA Conference — CT-RSA 2006. Berlin: Springer, 2006. 21--33. Google Scholar

[5] Biryukov A. The Boomerang attack on 5 and 6-round reduced AES. In: Proceedings of International Conference on Advanced Encryption Standard — AES 2004. Berlin: Springer, 2004. 11--15. Google Scholar

[6] Biryukov A, Khovratovich D. Related-key cryptanalysis of the full AES-192 and AES-256. In: Advances in Cryptology — ASIACRYPT 2009. Berlin: Springer, 2009. 1-18. Google Scholar

[7] Biryukov A, Khovratovich D, Nikolic I. Distinguisher and related-key attack on the full AES-256. In: Advances in Cryptology — CRYPTO 2009. Berlin: Springer, 2009. 231--249. Google Scholar

[8] Demirci H, Selçuk A A. A meet-in-the-middle attack on 8-round AES. In: Fast Software Encryption — FSE 2008. Berlin: Springer, 2008. 5086: 116--126. Google Scholar

[9] Gilbert H, Minier M. A collision attack on 7 rounds of Rijndael. In: Proceedings of the 3rd Advanced Encryption Standard Candidate Conference, New York, 2000. 230--241. Google Scholar

[10] Lu J, Dunkelman O, Keller N, et al. New impossible differential attacks on AES. In: Progress in Cryptology — INDOCRYPT 2008. Berlin: Springer, 2008. 279--293. Google Scholar

[11] Informatik T. Attacking seven rounds of Rijndael under 192-bit and 256-bit keys. In: Proceedings of the 3rd Advanced Encryption Standard Candidate Conference, New York, 2000. 215--229. Google Scholar

[12] Zhang W, Wu W, Feng D. New results on impossible differential cryptanalysis of reduced AES. In: Proceedings of International Conference on Information Security and Cryptology — ICISC 2007. Berlin: Springer, 2007. 4817: 239--250. Google Scholar

[13] Zhang W, Wu W, Zhang L, et al. Improved related-key impossible differential attacks on reduced-round AES-192. In: Selected Areas in Cryptography — SAC 2006. Berlin: Springer, 2007. 15--27. Google Scholar

[14] Biham E, Biryukov A, Shamir A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Advances in Cryptology — EUROCRYPT 1999. Berlin: Springer, 1999. 12--23. Google Scholar

[15] Daemen J, Knudsen L R, Rijmen V. The block cipher Square. In: Fast Software Encryption — FSE 1997. Berlin: Springer, 1997. 149--165. Google Scholar

[16] Biryukov A, Shamir A. Structural cryptanalysis of SASAS. In: Advances in Cryptology — EUROCRYPT 2001. Berlin: Springer, 2001. 395--405. Google Scholar

[17] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of Annual ACM Symposium on the Theory of Computing — STOC 1996. New York: ACM, 1996. 24: 212--219. Google Scholar

[18] Knudsen L R. DEAL — A 128-bit block cipher. Complexity, 1998. Google Scholar

[19] Lu J, Kim J, Keller N, et al. Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1. In: Cryptographers' Track at the RSA Conference — CT-RSA 2008. Berlin: Springer, 2008. 370--386. Google Scholar

[20] Boura C, Naya-Plasencia M, Suder V. Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and Simon. In: Advances in Cryptology — ASIACRYPT 2014. Berlin: Springer, 2014. 179--199. Google Scholar

[21] Tolba M, Abdelkhalek A, Youssef A M. Impossible Differential Cryptanalysis of reduced-round skinny. In: Progress in Cryptology — AFRICACRYPT 2017. Cham: Springer, 2017. 117--134. Google Scholar

[22] Kim J, Hong S, Lim J. Impossible differential cryptanalysis using matrix method. Discrete Math, 2010, 310: 988-1002 CrossRef Google Scholar

[23] Luo Y, Lai X, Wu Z. A unified method for finding impossible differentials of block cipher structures. Inf Sci, 2014, 263: 211-220 CrossRef Google Scholar

[24] Luo Y, Lai X. Improvement for finding impossible differentials of block cipher structures. IACR Cryptology ePrint Archive, 2017, 2017: 1209. Google Scholar

[25] Sasaki Y, Todo Y. New impossible differential search tool from design and cryptanalysis aspects. In: Advances in Cryptology — EUROCRYPT 2017. Cham: Springer, 2017. 185--215. Google Scholar

[26] Ding Y L, Wang X Y, Wang N, et al. Improved automatic search of impossible differentials for camellia with Sci China Inf Sci, 2018, 61: 038103. Google Scholar

[27] Nakahara J, Pavao I C. Impossible-Differential attacks on large-block Rijndael. In: Proceedings of International Conference on Information Security — ISC 2007. Berlin: Springer, 2007. 104-117. Google Scholar

[28] Zhang L, Wu W, Park J H, et al. Improved Impossible Differential Attacks on large-block Rijndael. In: Proceedings of International Conference on Information Security — ISC 2008. Berlin: Springer, 2008. 298--315. Google Scholar

[29] Wang Q, Gu D, Rijmen V, et al. Improved impossible differential attacks on large-block Rijndael. In: Proceedings of International Conference on Information Security and Cryptology — ICISC 2012. Berlin: Springer, 2012. 298--315. Google Scholar

[30] Minier M. Improving impossible-differential attacks against Rijndael-160 and Rijndael-224. Design Code and Cryptography, 2016, 82: 1--13. Google Scholar

[31] Boura C, Minier M, Naya-Plasencia M, et al. Improved impossible differential attacks against round-reduced LBlock. Cryptography and Security, 2014. Google Scholar

[32] Derbez P. Note on Impossible Differential Attacks. In: Fast Software Encryption — FSE 2016. Berlin: Springer, 2016. 416--427. Google Scholar

[33] Li Y J, Wu W L. Improved integral attacks on Rijndael. J Inf Sci Eng, 2011, 27: 2031--2045. Google Scholar

[34] Dunkelman O, Keller N. A new attack on the LEX stream cipher. In: Advances in Cryptology — ASIACRYPT 2008. Berlin: Springer, 2008. 539--556. Google Scholar

[35] Dunkelman O, Keller N, Shamir A. Improved single-key attacks on 8-round AES-192 and AES-256. In: Advances in Cryptology — ASIACRYPT 2010. Berlin: Springer, 2010. 158--176. Google Scholar

[36] Kim J, Hong S, Preneel B. Related-Key rectangle attacks on reduced AES-192 and AES-256. In: Fast Software Encryption — FSE 2007. Berlin: Springer, 2007. 225--241. Google Scholar

  • Figure 1

    A 6-round impossible differential path of Rijndael-256-256.

  • Figure 2

    Impossible differential attacks on 10-round Rijndael-256-256.

  • Figure 3

    A 6-round impossible differential path of Rijndael-224-224/256.

  • Figure 4

    Impossible differential attacks on 10-round Rijndael-224-256.

  • Figure 5

    The first impossible differential attack on 9-round Rijndael-224-224.

  • Figure 6

    The second impossible differential attack on 9-round Rijndael-224-224.

  •   

    Algorithm 1 Key schedule

    if (i mod N_k) = 0 then

    $W[i]~=~W[i~-~N_k]~\oplus~f(W[i~-~1])~\oplus~{\rm~rcon}[i/Nk]$

    else

    if $((N_k~>~6)$ and ($i$ mod $N_k~=~4))$ then

    $W[i]~=~W[i~-~N_k]~\oplus~g(W[i~-~1])$

    else

    $W[i]~=~W[i~-~N_k]~\oplus~W[i~-~1]$

    end if

    end if

  • Table 1   Summary of attacks on Rijndael-256-256 and Rijndael-224-256
    Cipher NR Data (CP) Time (Enc) Memory (Blocks) Attack type Source
    7 $2^{153}$ $2^{182}$ $2^{117}$ IDA [27]
    9 $2^{244.3}$ $2^{208.8}$ $2^{192}$ IDA [28]
    9 $2^{132.5}$ $2^{174.5}$ IA [33]
    Rijndael-256-256 9 $2^{237.3}$ $2^{159.1}$ $2^{115.3}$ IDA [29]
    9 $2^{245.3}$ $2^{127.1}$ $2^{90.9}$ IDA [29]
    10 $2^{244.2}$ $2^{253.9}$ $2^{186.8}$ IDA [29]
    10 $2^{244.4}$ $2^{240.1}$ $2^{181.4}$ IDA Subsection 3.2
    Rijndael-224-256 10 $2^{214.4}$ $2^{241.3}$ $2^{183.4}$ IDA Subsection 4.2
    7 $2^{138}$ $2^{167}$ $2^{104}$ IDA [27]
    9 $2^{212.3}$ $2^{209}$ $2^{192}$ IDA [28]
    9 $2^{196.5}$ $2^{196.5}$ IA [33]
    Rijndael-224-224 9 $2^{208}$ $2^{162}$ $2^{117}$ IDA [29]
    9 $2^{216}$ $2^{130}$ $2^{93.6}$ IDA [29]
    9 $2^{214.4}$ $2^{113.4}$ $2^{87.4}$ IDA Subsection 4.3
    9 $2^{206.6}$ $2^{153.6}$ $2^{111.6}$ IDA Subsection 4.3

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1