nach oben

Designs, Codes and Cryptography

Erschienen in:

01.09.2016

Extended meet-in-the-middle attacks on some Feistel constructions

verfasst von: Jian Guo, Jérémy Jean, Ivica Nikolić, Yu Sasaki

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2016

Einloggen, um Zugang zu erhalten

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

search-config

KI-gestützte Suche

Aus

Abstract

We show key recovery attacks on generic balanced Feistel ciphers. The analysis is based on the meet-in-the-middle technique and exploits truncated differentials that are present in the ciphers due to the Feistel construction. Depending on the type of round function, we differentiate and show attacks on two types of Feistels. For the first type, which is one of the most practical Feistels, we show a 5-round distinguisher based on a truncated differential, which allows to launch 6-round and 10-round attacks, for single-key and double-key sizes, respectively. For the second type of Feistels, with round functions that follow the SPN structure composed of linear layers with maximal branch number, based on a 7-round distinguisher we show attacks that reach up to 14 rounds. Our attacks outperform all the known attacks for any key sizes and provide new lower bounds on the number of rounds required to achieve a practical and a secure Feistel. The attacks on first type have been experimentally verified with computer implementations of the attacks on small-state ciphers.

Vorheriger Artikel Asymptotic existence results for primitive completely normal elements in extensions of Galois fields

Nächster Artikel Authentication codes based on resilient Boolean maps

Nur mit Berechtigung zugänglich

The branch number of a linear transformation is the minimum number of active/non-zero input and output words over all inputs with at least one active/non-zero word.

We do not claim attacks on Feistel-2 that have this type of round functions.

For linear function, the probability that a solution exists to the differential \(({\varDelta }_{I},{\varDelta }_{O})\) is about \(2^{|\#{\varDelta }_{I}-\#{\varDelta }_{O}|}\) (where \(\#X\) denotes the number of elements in X), which might be smaller than one.

Recall that this difference corresponds to an internal state difference for the plaintext pair \((m,m')\).

Less, as one evaluation of the round functions costs less than one encryption query.

When n and c are big enough, the constant factor in \(2^{n-2c+1}\) has limited impact. Ignoring the constant factor simplifies the evaluation and makes it easy to understand the intuition of generic attacks.

One may need additional data complexity or the additional access to the decryption oracle depending on what attack is used for attacking reduced rounds. However, the impact to the entire attack is rather limited compared to the last round subkey recovery.

The probability of satisfying an event with \(\mathrm{Pr}= 2^{-12}\) with \(2^{12}\) trials, with \(2^{13}\) trials, and with \(2^{14}\) trials is \(1-(1-2^{-12})^{2^{12}} \approx 63\,\%\), \(1-(1-2^{-12})^{2^{13}} \approx 86\,\%\), and \(1-(1-2^{-12})^{2^{14}} \approx 98\,\%\), respectively, which also matches our experiment.

Aoki K., Guo J., Matusiewicz K., Sasaki Y., Wang L.: Preimages for step-reduced SHA-2. In: Matsui M. (ed.) ASIACRYPT. LNCS, vol. 5912, pp. 578–597. Springer, Berlin (2009).

Aoki K., Ichikawa T., Kanda M., Matsui M., Moriai S., Nakajima J., Tokita T.: Camellia: a 128-bit block cipher suitable for multiple platforms—design and analysis. In: Stinson D.R., Tavares S.E. (eds.) Selected Areas in Cryptography. LNCS, vol. 2012, pp. 39–56. Springer, Berlin (2000).

Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013).

Biham E., Dunkelman O.: The SHAvite-3 hash function. Submission to NIST (Round 2) (2009).

CAST: Cryptographic algorithms approved for Canadian government use (2012).

Coppersmith D.: The data encryption standard (DES) and its strength against attacks. IBM J. Res. Dev. 38(3), 243–250 (1994).

Daemen J., Knudsen L.R., Rijmen V.: The block cipher square. In: Biham, E. (ed.) FSE. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997).

Demirci H., Selçuk A.A.: A meet-in-the-middle attack on 8-round AES. In: Nyberg K. (ed.) FSE. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008).

Derbez P., Fouque P.A., Jean J.: Improved key recovery attacks on reduced-round AES in the single-key setting. IACR Cryptology ePrint Archive 2012, 477 (2012).

10.

Derbez P., Fouque P.A., Jean J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: Johansson T., Nguyen P.Q. (eds.) EUROCRYPT. LNCS, vol. 7881, pp. 371–387. Springer, Heidelberg (2013).

11.

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. LNCS, vol. 7417, pp. 719–740. Springer, Heidelberg (2012).

12.

Dunkelman O., Keller N., Shamir A.: Improved single-key attacks on 8-round AES-192 and AES-256. In: Abe M. (ed.) ASIACRYPT. LNCS, vol. 6477, pp. 158–176. Springer, Heidelberg (2010).

13.

Feistel H., Notz W., Smith J.: Some cryptographic techniques for machine-to-machine data communications. Proc. IEEE. 63(11), 1545–1554 (1975).

14.

Gilbert H., Minier M.: A collision attack on 7 rounds of Rijndael. In: AES Candidate Conference, pp. 230–241 (2000).

15.

Guo J., Ling S., Rechberger C., Wang H.: Advanced meet-in-the-middle preimage attacks: first results on full tiger, and improved results on MD4 and SHA-2. In: Abe M. (ed.) ASIACRYPT. LNCS, vol. 6477, pp. 56–75 Springer, Heidelberg (2010).

16.

ISO/IEC: Information technology—security techniques—encryption algorithms—part 3: block ciphers (2010).

17.

Isobe T., Shibutani K.: All subkeys recovery attack on block ciphers: extending meet-in-the-middle approach. In: Knudsen LR, Wu H. (eds.) Selected Areas in Cryptography. LNCS, vol. 7707, pp. 202–221. Springer, Heidelberg (2012).

18.

Isobe T., Shibutani K.: Generic key recovery attack on feistel scheme. In: Sako K., Sarkar P. (eds.) ASIACRYPT (1). LNCS, vol. 8269, pp. 464–485. Springer, Heidelberg (2013).

19.

Knudsen L.R.: The security of feistel ciphers with six rounds or less. J. Cryptol. 15(3), 207–222 (2002).

20.

Luby M., Rackoff C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988).

21.

Merkle R.C., Hellman M.E.: On the security of multiple encryption. Commun. ACM 24(7), 465–467 (1981).

22.

Sasaki Y., Aoki K.: Finding preimages in full MD5 faster than exhaustive search. In: Joux A. (ed.) EUROCRYPT. LNCS, vol. 5479, pp. 134–152. Springer, Heidelberg (2009).

23.

Shibutani K., Bogdanov A.: Towards the optimality of Feistel ciphers with substitution-permutation functions. Des. Codes Cryptogr. 73(2), 667–682 (2014).

24.

Shibutani K., Isobe T., Hiwatari H., Mitsuda A., Akishita T., Shirai T.: Piccolo: an ultra-lightweight blockcipher. In: Preneel B., Takagi T. (eds.) CHES. LNCS, vol. 6917, pp. 342–357. Springer, Heidelberg (2011).

25.

Todo Y.: Upper bounds for the security of several feistel networks. In: Boyd C., Simpson L. (eds.) ACISP. LNCS, vol. 7959, pp. 302–317. Springer, Heidelberg (2013).

26.

Wu W., Zhang L.: LBlock: a lightweight block cipher. In: Lopez J., Tsudik G. (eds.) ACNS. LCNS, vol. 6715, pp. 327–344. Springer, Berlin (2011).

27.

Zhang L., Wu W., Wang Y., Wu S., Zhang J.: LAC: a lightweight authenticated encryption cipher. Submitted to the CAESAR competition (2014).

Titel: Extended meet-in-the-middle attacks on some Feistel constructions
verfasst von: Jian Guo
Jérémy Jean
Ivica Nikolić
Yu Sasaki
Publikationsdatum: 01.09.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2016
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-015-0120-4

Springer Professional

Extended meet-in-the-middle attacks on some Feistel constructions

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2016

Asymptotic existence results for primitive completely normal elements in extensions of Galois fields

Non-special subsets of the set of points of a curve defined over a finite field

Authentication codes based on resilient Boolean maps

Partial geometric designs with prescribed automorphisms

Meet-in-the-middle attacks on 10-round AES-256

Extended dual system group and shorter unbounded hierarchical identity based encryption

Premium Partner