Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Formal Treatment of Privacy-Enhancing Credential Systems Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Cryptanalysis of Feistel Networks with Secret Round Functions

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

Erschienen in: Selected Areas in Cryptography – SAC 2015

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Related-Key Attack on Full-Round PICARO
Nächstes Kapitel Improved Meet-in-the-Middle Distinguisher on Feistel Schemes
Fußnoten
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.
 
Literatur
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)
Metadaten
Titel
Cryptanalysis of Feistel Networks with Secret Round Functions
verfasst von
Alex Biryukov
Gaëtan Leurent
Léo Perrin
Copyright-Jahr
2016
Verlag
Springer International Publishing
Buch
Selected Areas in Cryptography – SAC 2015

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise