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
Published in:
Formal Treatment of Privacy-Enhancing Credential Systems Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Cryptanalysis of Feistel Networks with Secret Round Functions

Authors : Alex Biryukov, Gaëtan Leurent, Léo Perrin

Published in: Selected Areas in Cryptography – SAC 2015

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

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 yoyo game which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to \(\text {O}(2^{2n})\) encryptions where n is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively \(\text {O}(2^{n2^{n-1}+2n})\) and \(\text {O}(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 \(\text {O}(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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Related-Key Attack on Full-Round PICARO
next chapter Improved Meet-in-the-Middle Distinguisher on Feistel Schemes
Footnotes
1
However, such a yoyo game cannot be played against a \(\boxplus \)-Feistel, as explained in Sect. 3.4. It only works in characteristic 2.
 
2
It can also recover \(S_{4}\) in an identical fashion but this part is omitted for the sake of clarity.
 
3
We experimentally found that a lower bound of 0.1 is more than sufficient even for n as small as 4.
 
4
CPU: Intel core i7-3770 (3.40 GHz); 8 Gb of RAM. The program was compiled with g++ and optimization flag -O3.
 
5
A random permutation of a space of size N is expected to have about \(\log _{e}(N)\) cycles.
 
Literature
1.
Daemen, J., Rijmen, V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Springer, Heidelberg (2002)CrossRefMATH
2.
U.S. Department of commerce, National Institute of Standards and Technology: Data encryption standard. Federal Information Processing Standards Publication (1999)
3.
Barreto, P., Rijmen, V.: The Khazad legacy-level block cipher. Primitive submitted to NESSIE, vol. 97 (2000)
4.
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)CrossRef
5.
Biryukov, A., Bouillaguet, C., Khovratovich, D.: Cryptographic schemes based on the \(\sf 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)
6.
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394–405. Springer, Heidelberg (2001)
7.
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)CrossRef
8.
9.
10.
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)
11.
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)CrossRef
12.
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH
13.
14.
Knudsen, L.R.: DEAL - a 128-bit block cipher, AES submission (1998)
15.
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)CrossRef
16.
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
17.
Wagner, D.: The boomerang attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999)CrossRef
18.
National Security Agency, N.S.A.: SKIPJACK and KEA Algorithm Specifications (1998)
19.
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)CrossRef
20.
Derbez, P., Perrin, L.: Meet-in-the-middle attacks and structural analysis of round-reduced PRINCE. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 190–216. Springer, Heidelberg (2015)CrossRef
21.
Biryukov, A.: Analysis of involutional ciphers: Khazad and Anubis. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 45–53. Springer, Heidelberg (2003)CrossRef
22.
Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel Networks with Secret Round Functions. IACR eprint report 2015/723, July 2015
23.
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)CrossRef
24.
Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002)CrossRef
25.
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)
Metadata
Title
Cryptanalysis of Feistel Networks with Secret Round Functions
Authors
Alex Biryukov
Gaëtan Leurent
Léo Perrin
Copyright Year
2016
Publisher
Springer International Publishing
Book
Selected Areas in Cryptography – SAC 2015

Print ISBN: 978-3-319-31300-9

Electronic ISBN: 978-3-319-31301-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-31301-6_6

Premium Partner

    Image Credits