[en] Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions.
When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to $\bigO(2^{2n})$ encryptions where $n$ is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively $\bigO(2^{n2^{n-1}+2n})$ and $\bigO(2^{n2^{n}+2n})$. However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity $\bigO(2^{n2^{3n/4}})$.
Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.
Disciplines :
Computer science
Author, co-author :
Biryukov, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Leurent, Gaëtan; Inria
Perrin, Léo Paul ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
yes
Language :
English
Title :
Cryptanalysis of Feistel Networks with Secret Round Functions
Publication date :
March 2016
Event name :
Selected Areas in Cryptography -- SAC 2015
Event place :
Sackville, Canada
Event date :
August 12-14, 2015
Audience :
International
Main work title :
Selected Areas in Cryptography -- SAC 2015, 21st International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers
Daemen, J., Rijmen, V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Springer, Heidelberg (2002)
U.S. Department of commerce, National Institute of Standards and Technology: Data encryption standard. Federal Information Processing Standards Publication (1999)
Barreto, P., Rijmen, V.: The Khazad legacy-level block cipher. Primitive submitted to NESSIE, vol. 97 (2000)
Gérard, B., Grosso, V., Naya-Plasencia, M., Standaert, F.-X.: Block ciphers that are easier to mask: how far can we go? In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 383-399. Springer, Heidelberg (2013)
Biryukov, A., Bouillaguet, C., Khovratovich, D.: Cryptographic schemes based on the ASASA structure: black-box, white-box, and public-key (extended abstract). In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 63-84. Springer, Heidelberg (2014)
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394-405. Springer, Heidelberg (2001)
Biryukov, A., Perrin, L.: On reverse-engineering S-Boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 116-140. Springer, Heidelberg (2015)
Brier, E., Peyrin, T., Stern, J.: BPS: a format-preserving encryption proposal. Submission to NIST (2010). http://csrc.nist.gov/groups/ST/toolkit/BCM/modesdevelopment.html
Bellare, M., Rogaway, P., Spies, T.: The FFX mode of operation for formatpreserving encryption. Submission to NIST (2010). http://csrc.nist.gov/groups/ST/toolkit/BCM/modes development.html
Lampe, R., Seurin, Y.: Security analysis of key-alternating Feistel ciphers. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 243-264. Springer, Heidelberg (2015)
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 433-454. Springer, Heidelberg (2015)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373-386 (1988)
Biham, E., Biryukov, A., Dunkelman, O., Richardson, E., Shamir, A.: Initial observations on Skipjack: cryptanalysis of Skipjack-3XOR. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 362-375. Springer, Heidelberg (1999)
Kelsey, J., Schneier, B., Wagner, D.: Related-key cryptanalysis of 3-way, Biham- DES, CAST, DES-X, newDES, RC2, and TEA. In: Proceedings of the First International Conference on Information and Communication Security, ICICS 1997, pp. 233-246. Springer, London (1997). ISBN: 3-540-63696-X. http://dl.acm.org/citation.cfm?id=646277.687180
Wagner, D.: The boomerang attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156-170. Springer, Heidelberg (1999)
National Security Agency, N.S.A.: SKIPJACK and KEA Algorithm Specifications (1998)
Borghoff, J., et al.: PRINCE - a low-latency block cipher for pervasive computing applications. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 208-225. Springer, Heidelberg (2012)
Derbez, P., Perrin, L.: Meet-in-the-middle attacks and structural analysis of roundreduced PRINCE. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 190-216. Springer, Heidelberg (2015)
Biryukov, A.: Analysis of involutional ciphers: Khazad and Anubis. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 45-53. Springer, Heidelberg (2003)
Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel Networks with Secret Round Functions. IACR eprint report 2015/723, July 2015
Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher SQUARE. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149-165. Springer, Heidelberg (1997)
Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112-127. Springer, Heidelberg (2002)
Gall, F.L.: Powers of tensors and fast matrix multiplication. In: Nabeshima, K., Nagasaka, K., Winkler, F., Szántó, á. (eds.) International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, Kobe, Japan, 23-25 July 2014, pp. 296-303. ACM (2014)
