New Attacks on Feistel Structures with Improved Memory Complexities

详细信息    查看全文

• 关键词：Cryptanalysis ; Block cipher ; Feistel structure ; Dissection ; Meet ; in ; the ; middle ; Splice ; and ; cut ; CAST ; 128 ; DEAL
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9215
• 期：1
• 页码：433-454
• 全文大小：478 KB
• 参考文献：1.Adams, C.: The CAST-128 Encryption Algorithm. RFC 2144 (1997). https://?tools.?ietf.?org/?html/?rfc2144
  2. Aoki, K., Sasaki, Y.: Preimage attacks on one-block MD4, 63-step MD5 and more. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 103-19. Springer, Heidelberg (2009) View Article
  3. Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique cryptanalysis of the full AES. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 344-71. Springer, Heidelberg (2011) View Article
  4. Bogdanov, A., Rechberger, C.: A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 229-40. Springer, Heidelberg (2011) View Article
  5. Boura, C., Naya-Plasencia, M., Suder, V.: Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and Simon . In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 179-99. Springer, Heidelberg (2014)
  6. Canteaut, A., Naya-Plasencia, M., Vayssière, B.: Sieve-in-the-middle: improved MITM attacks. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 222-40. Springer, Heidelberg (2013) View Article
  7. Chaum, D., Evertse, J.-H.: Cryptanalysis of DES with a reduced number of rounds: sequences of linear factors in block ciphers. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 192-11. Springer, Heidelberg (1986)
  8.Diffie, W., Hellman, M.E.: Cryptanalysis of the NBS data encryption standard. Computer 10(6), 74-4 (1977)View Article
  9. Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 719-40. Springer, Heidelberg (2012) View Article
  10.Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. IACR Cryptology ePrint Arch. 2015, 146 (2015)
  11. Guo, J., Jean, J., Nikoli?, I., Sasaki, Y.: Meet-in-the-middle attacks on generic Feistel constructions. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 458-77. Springer, Heidelberg (2014)
  12. Isobe, T., Shibutani, K.: Generic key recovery attack on Feistel scheme. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 464-85. Springer, Heidelberg (2013) View Article
  13. Isobe, T., Shibutani, K.: Improved All-subkeys recovery attacks on FOX, KATAN and SHACAL-2 block ciphers. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 104-26. Springer, Heidelberg (2015)
  14. Junod, P., Vaudenay, S.: FOX : a new family of block ciphers. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 114-29. Springer, Heidelberg (2004) View Article
  15. Khovratovich, D., Rechberger, C., Savelieva, A.: Bicliques for preimages: attacks on skein-512 and the SHA-2 family. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 244-63. Springer, Heidelberg (2012) View Article
  16.Knudsen, L.: DEAL - A 128-bit Block Cipher. NIST AES Proposal (1998)
  17.Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373-86 (1988)MathSciNet View Article MATH
  18.National Bureau of Standards. Data encryption standard. Federal Information Processing Standards Publications (FIPS) 46 (1977)
  19. Sarkar, P., Iwata, T. (eds.): Advances in Cryptology - ASIACRYPT 2014-0th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-1, 2014. Proceedings, Part I. Lecture Notes in Computer Science, vol. 8873. Springer, Heidelberg (2014)
  20. Wang, L., Sasaki, Y.: Finding preimages of tiger up to 23 steps. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 116-33. Springer, Heidelberg (2010) View Article
  21.Wang, M., Wang, X., Chow, K., Hui, L.C.K.: New Differential Cryptanalytic Results for Reduced-Round CAST-128. IEICE Trans. 93(12), 2744-754 (2010)View Article
  
• 作者单位：Itai Dinur (15)
  Orr Dunkelman (16) (18)
  Nathan Keller (17) (18)
  Adi Shamir (18)
  
  15. Département d’Informatique, école Normale Supérieure, Paris, France
  16. Computer Science Department, University of Haifa, Haifa, Israel
  18. Computer Science Department, The Weizmann Institute, Rehovot, Israel
  17. Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
  
• 丛书名：Advances in Cryptology -- CRYPTO 2015
• ISBN：978-3-662-47989-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Feistel structures are an extremely important and extensively researched type of cryptographic schemes. In this paper we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n-bit inputs with seven independent round keys of n?/?2 bits each, a MITM attack can use (\(2^{1.5n}\), \(2^{1.5n}\)) time and memory, while dissection requires (\(2^{2n}\), \(2^{n}\)) time and memory. Our new attack requires only (\(2^{1.5n}\), \(2^{n}\)) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multicollisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions -in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as round-reduced CAST-128 (where we reduce the memory complexity from \(2^{111} \) to \(2^{64}\)) and full DEAL-256 (where we reduce the memory complexity from \(2^{200}\) to \(2^{144}\)), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures -for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of \(2^{16}\).