An Automated Evaluation Tool for Improved Rebound Attack: New Distinguishers and Proposals of ShiftBytes Parameters for Gr?stl

详细信息    查看全文

• 作者：Yu Sasaki (17)
  Yuuki Tokushige (18)
  Lei Wang (19)
  Mitsugu Iwamoto (18)
  Kazuo Ohta (18)
  
• 关键词：Rijndael ; Gr?stl ; rebound attack ; ShiftRows ; ShiftBytes
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8366
• 期：1
• 页码：424-443
• 全文大小：370 KB
• 参考文献：1. Daemen, J., Rijmen, V.: AES Proposal: Rijndael (1998)
  2. Knudsen, L.R., Rijmen, V.: Known-key distinguishers for some block ciphers. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol.?4833, pp. 315-24. Springer, Heidelberg (2007) CrossRef
  3. Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: The rebound attack: Cryptanalysis of reduced Whirlpool and Gr?stl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol.?5665, pp. 260-76. Springer, Heidelberg (2009) CrossRef
  4. Mendel, F., Peyrin, T., Rechberger, C., Schl?ffer, M.: Improved cryptanalysis of the reduced Gr?stl compression function, ECHO permutation and AES block cipher. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol.?5867, pp. 16-5. Springer, Heidelberg (2009) CrossRef
  5. Gilbert, H., Peyrin, T.: Super-sbox cryptanalysis: Improved attacks for AES-like permutations. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol.?6147, pp. 365-83. Springer, Heidelberg (2010) CrossRef
  6. Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schl?ffer, M.: Rebound distinguishers: Results on the full Whirlpool compression function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 126-43. Springer, Heidelberg (2009) CrossRef
  7. Matusiewicz, K., Naya-Plasencia, M., Nikoli?, I., Sasaki, Y., Schl?ffer, M.: Rebound attack on the full lane compression function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 106-25. Springer, Heidelberg (2009) CrossRef
  8. Peyrin, T.: Improved differential attacks for ECHO and Gr?stl. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 370-92. Springer, Heidelberg (2010) CrossRef
  9. Sasaki, Y., Li, Y., Wang, L., Sakiyama, K., Ohta, K.: Non-full-active super-sbox analysis: Applications to ECHO and Gr?stl. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.?6477, pp. 38-5. Springer, Heidelberg (2010) CrossRef
  10. Naya-Plasencia, M.: How to improve rebound attacks. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.?6841, pp. 188-05. Springer, Heidelberg (2011) CrossRef
  11. Jean, J., Naya-Plasencia, M., Peyrin, T.: Improved rebound attack on the finalist Gr?stl. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol.?7549, pp. 110-26. Springer, Heidelberg (2012) CrossRef
  12. Fouque, P.-A., Jean, J., Peyrin, T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128 . In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol.?8042, pp. 183-03. Springer, Heidelberg (2013) CrossRef
  13. Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schl?ffer, M., Thomsen, S.S.: Gr?stl addendum. Submission to NIST (2009) (updated)
  14. Minier, M., Phan, R.C.-W., Pousse, B.: Distinguishers for ciphers and known key attack against rijndael with large blocks. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol.?5580, pp. 60-6. Springer, Heidelberg (2009) CrossRef
  15. Sasaki, Y.: Known-key attacks on rijndael with large blocks and strengthening / shiftRow parameter. In: Echizen, I., Kunihiro, N., Sasaki, R. (eds.) IWSEC 2010. LNCS, vol.?6434, pp. 301-15. Springer, Heidelberg (2010) CrossRef
  16. Daemen, J., Rijmen, V.: The design of Rijndeal: AES -the Advanced Encryption Standard (AES). Springer, Heidelberg (2002) CrossRef
  17. U.S. Department of Commerce, National Institute of Standards and Technology: Specification for the ADVANCED ENCRYPTION STANDARD (AES) (Federal Information Processing Standards Publication 197) (2001)
  18. U.S. Department of Commerce, National Institute of Standards and Technology: Federal Register /Vol. 72, No. 212/Friday, November 2, 2007/Notices (2007) http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf .
  19. Tokushige, Y.: Implemented tool of the improved rebound attack. Contact to the authors if the link is closed (2013), http://ohta-lab.jp/member/yuuki-tokushige/an-automated-evaluation-tool-for-improved-rebound-attack/
  20. Iwamoto, M., Peyrin, T., Sasaki, Y.: Limited-birthday distinguishers for hash functions: Collisions beyond the birthday bound can be meaningful. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol.?8270, pp. 504-23. Springer, Heidelberg (2013) CrossRef
  21. Nakasone, T., Li, Y., Sasaki, Y., Iwamoto, M., Ohta, K., Sakiyama, K.: Key-dependent weakness of AES-based ciphers under clockwise collision distinguisher. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012. LNCS, vol.?7839, pp. 395-09. Springer, Heidelberg (2013) CrossRef
  
• 作者单位：Yu Sasaki (17)
  Yuuki Tokushige (18)
  Lei Wang (19)
  Mitsugu Iwamoto (18)
  Kazuo Ohta (18)
  
  17. NTT Secure Platform Laboratories, Japan
  18. The University of Electro-Communications, Japan
  19. Nanyang Technological University, Singapore
  
• ISSN：1611-3349

文摘

In this paper, we study the security of AES-like permutations against the improved rebound attack proposed by Jean et al. at FSE 2012 which covers three full-active rounds in the inbound phase. The attack is very complicated and hard to verify its optimality when the state size is large and rectangle, namely the numbers of rows and columns are different. In the inbound phase of the improved rebound attack, several SuperSBoxes are generated for each of forward analysis and backward analysis. The attack searches for paired values that are consistent with all SuperSBoxes. The attack complexity depends on the order of the SuperSBoxes to be analyzed, and detecting the best order is hard. In this paper, we develop an automated complexity evaluation tool with several fast implementation techniques. The tool enables us to examine all the possible orders of the SuperSBoxes, and provides the best analysis order and complexity. We apply the tool to large block Rijndael in the known-key setting and the Gr?stl-512 permutation. As a result, we obtain the first 9-round distinguisher for Rijndael-192 and Rijndael-224. It also shows the impossibility of the improved rebound attack against 9-round Rijndael-160 and 10-round Rijndael-256, and the optimality of the previous distinguisher against the 10-round Gr?stl-512 permutation. Moreover, the efficiency of the improved rebound attack depends on the parameter of the ShiftRows operation. Our tool can exhaustively examine all the possible ShiftRows parameters to search for the ones that can resist the attack. We show new parameters for the Gr?stl-512 permutation obtained by our tool, which can resist a 10-round improved rebound attack while the specification parameter cannot resist it.