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
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Differential Analysis and Meet-in-the-Middle Attack Against Round-Reduced TWINE Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE

verfasst von : Patrick Derbez, Léo Perrin

Erschienen in: Fast Software Encryption

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as possible using attacks which are usually impractical despite being faster than brute-force, the challenge invites cryptographers to find practical attacks and encourages them to actually implement them. In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the 6 and 8-round categories — the highest for which winners were identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher. We also describe heuristic methods we used to find practical SAT-based and differential attacks.
Finally, we also present an analysis of the cycle structure of the internal rounds of PRINCE leading both to a low complexity distinguisher for 4-round PRINCE-core and an alternative representation of the cipher valid in particular contexts and which highlights, in this cases, a poor diffusion.

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 Security of the AES with a Secret S-Box
Nächstes Kapitel Linear Distinguishers in the Key-less Setting: Application to PRESENT
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
A clause is the logical OR of several variables, e.g. \(a \vee b\), a, \(\overline{a} \vee b \vee \overline{c}\) where \(\overline{x}\) is the negation of x.
 
2
Actually, a structure of size \(2^{12}\) where the first three nibbles take all values contains 64 right families with probability about \(2^{-5.9}\). If we reduce these to form the structures of \(2^{9}\) plaintext/ciphertext encryptions we described, only some of these 64 families are still present, hence the presence of either 0 or several right families in a structure.
 
3
Each structure yields \(2^{9-3}=2^6\) families for each of the \(4^3\) interesting input differences so that we consider the families by groups of \(2^{12}\). This implies that a collision has a probability of about \({2^{12} \atopwithdelims ()2} \cdot 2^{-64} \approx 2^{-41}\).
 
4
While there are some cycles which do not have this structure, they are a small minority: for \(f_{0}\), 256 elements out of 65536 are on such cycles, 64 for \(f_{1}\), 8 for \(f_{2}\) and 194 for \(f_{3}\).
 
5
Recall that the probability for x to be on a cycle of length \(\ell \) for a permutation of \([0, N-1]\) is equal to 1 / N. Hence, the probability that the length is smaller than \(2^{15}\) for a permutation of \([0, 2^{64}-1]\) is \(\sum _{\ell =1}^{2^{15}} 2^{-64} = 2^{-49}\).
 
6
In each column, 16 bits from the corresponding column of \(k_{1}\) are used as well as 16 bits from the corresponding column of \(SR^{-1}(k_{1})\). Since the top nibble of these two sets is the same, we are left with \(32-4=28\) bits.
 
Literatur
1.
2.
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) CrossRef
3.
Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-round AES. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008) CrossRef
4.
5.
Borghoff, J., Canteaut, A., Güneysu, T., Kavun, E.B., Knezevic, M., Knudsen, L.R., Leander, G., Nikov, V., Paar, C., Rechberger, C., Rombouts, P., Thomsen, S.S., Yalçın, T.: 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
6.
7.
8.
Jean, J., Nikolić, I., Peyrin, T., Wang, L., Wu, S.: Security analysis of PRINCE. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 92–111. Springer, Heidelberg (2014)
9.
10.
Canteaut, A., Fuhr, T., Gilbert, H., Naya-Plasencia, M., Reinhard, J.R.: Multiple differential cryptanalysis of round-reduced PRINCE (full version). Cryptology ePrint Archive, Report 2014/089 (2014). http://​eprint.​iacr.​org/​
11.
12.
Dunkelman, O., Keller, N., Shamir, A.: Improved single-key attacks on 8-round AES-192 and AES-256. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 158–176. Springer, Heidelberg (2010) CrossRef
13.
Derbez, P., Fouque, P.: Exhausting Demirci-Selçuk meet-in-the-middle attacks against reduced-round AES. In: Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, 11–13 March 2013, pp. 541–560 (2013). Revised Selected Papers
14.
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 2013. LNCS, vol. 7881, pp. 371–387. Springer, Heidelberg (2013) CrossRef
15.
Mironov, I., Zhang, L.: Applications of SAT solvers to cryptanalysis of hash functions. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 102–115. Springer, Heidelberg (2006) CrossRef
16.
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004) CrossRef
17.
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, p. 394. Springer, Heidelberg (2001)
18.
Abed, F., List, E., Lucks, S.: On the security of the core of prince against biclique and differential cryptanalysis. Cryptology ePrint Archive, Report 2012/712 (2012). http://​eprint.​iacr.​org/​
19.
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
20.
Moore, J.H., Simmons, G.J.: Cycle structure of the DES with weak and semi-weak keys. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 9–32. Springer, Heidelberg (1987)
21.
Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the even-mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012) CrossRef
Metadaten
Titel
Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE
verfasst von
Patrick Derbez
Léo Perrin
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Fast Software Encryption

Print ISBN: 978-3-662-48115-8

Electronic ISBN: 978-3-662-48116-5

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48116-5_10

Premium Partner

    Bildnachweise