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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure

verfasst von : Alex Biryukov, Léo Perrin

Erschienen in: Advances in Cryptology -- CRYPTO 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box F of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of F are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box’s DDT.

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 Links Among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis
Nächstes Kapitel Capacity and Data Complexity in Multidimensional Linear Attack
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The fact that Browning works at the NSA shows that this agency values theoretical considerations, which makes the simplicity of F all the stranger.
 
2
An anonymous member of sci.crypt posted what they claimed to be Skipjack at a time when this algorithm was still classified [25]. Although the algorithm described, “S-1”, turned out to be different from Skipjack as we know it, it used similar notations — the S-Box is called “F-Table” — and the key-schedule leads to identical round keys being used every 5 rounds, just like in the actual Skipjack.
 
3
One can also notice that linear operations do not alter the DDT profile of the permutation and thus one has to recompute the metric only after non-linear operations.
 
4
A formula in Conjunctive Normal Form is the conjunction of multiple clauses, each of them being the disjunction of some possibly negated variables.
 
5
The PC used for the experiments has a Intel(R) Core(TM) i7-3770 CPU (3.40GHz) for a cpu and 8 Go of RAM.
 
6
This experiment was performed on a single core of a dedicated server with 500 Go of RAM.
 
7
The pictures obtained in this fashion have a strong abstract feel to them, hence a name refering to the painter Jackson Pollock for this algorithm.
 
8
As will be explained later, this algorithm works by drawing the image to embed point after point just like in a pointillist painting, hence the name of the painter who invented this method.
 
Literatur
1.
2.
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994) CrossRef
3.
Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields Appl. 32, 120–147 (2015). Special Issue: Second Decade of FFAMathSciNetCrossRef
4.
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) CrossRef
5.
Nyberg, K.: Linear approximation of block ciphers. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995) CrossRef
6.
Barreto, P., Rijmen, V.: The whirlpool hashing function. In: First open NESSIE Workshop, Leuven, Belgium, vol. 13, p. 14 (2000)
7.
Barreto, P., Rijmen, V.: The khazad legacy-level block cipher. Primitive submitted to NESSIE 97 (2000)
8.
Grosso, V., Leurent, G., Standaert, F.-X., Varıcı, K.: LS-Designs: bitslice encryption for efficient masked software implementations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 18–37. Springer, Heidelberg (2015)
9.
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
10.
Daemen, J., Rijmen, V.: The Design of Rijndael: AES-the Advanced Encryption Standard. Springer, Heidelberg (2002) CrossRef
11.
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)
12.
U.S. DEPARTMENT: OF COMMERCE/National Institute of Standards and Technology: Data encryption standard. Publication, Federal Information Processing Standards (1999)
13.
National Security Agency, N.S.A.: SKIPJACK and KEA Algorithm Specifications (1998)
14.
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The simon and speck families of lightweight block ciphers. IACR Cryptology ePrint Archive 2013, 404 (2013)
15.
Coppersmith, D.: The Data Encryption Standard (DES) and its strength against attacks. IBM J. Res. Dev. 38(3), 243–250 (1994)MathSciNetCrossRefMATH
16.
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394–405. Springer, Heidelberg (2001)
17.
Patarin, J.: Luby-Rackoff: 7 rounds are enough for formula \(2^{n(1-\epsilon )}\) security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 513–529. Springer, Heidelberg (2003) CrossRef
18.
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. J. Cryptology 18(4), 291–311 (2005)MathSciNetCrossRefMATH
19.
Knudsen, L.R., Robshaw, M., Wagner, D.: Truncated differentials and skipjack. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 165–180. Springer, Heidelberg (1999) CrossRef
20.
21.
Browning, K., Dillon, J., McQuistan, M., Wolfe, A.: An apn permutation in dimension six. Finite Fields: Theory Appl. 518, 33–42 (2010)MathSciNet
22.
Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Math. Cryptology JMC 1(3), 221–242 (2007)MathSciNetMATH
23.
O’Connor, L.: Properties of linear approximation tables. In: Preneel, B. (ed.) FSE 1995. LNCS, vol. 1008, pp. 131–136. Springer, Heidelberg (1995)CrossRef
24.
Brickell, E.F., Denning, D.E., Kent, S.T., Maher, D.P., Tuchman, W.: Skipjack review: Interim report (1993)
25.
26.
27.
Gilbert, H., Chassé, G.: A statistical attack of the FEAL-8 cryptosystem. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 22–33. Springer, Heidelberg (1991)
28.
Tardy-Corfdir, A., Gilbert, H.: A known plaintext attack of FEAL-4 and FEAL-6. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 172–182. Springer, Heidelberg (1992)
29.
Matsui, M., Yamagishi, A.: A new method for known plaintext attack of FEAL cipher. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 81–91. Springer, Heidelberg (1993) CrossRef
30.
Patarin, J.: Generic attacks on feistel schemes. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 222–238. Springer, Heidelberg (2001) CrossRef
31.
Wernsdorf, R.: The round functions of RIJNDAEL generate the alternating group. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 143–148. Springer, Heidelberg (2002) CrossRef
32.
Blondeau, C., Canteaut, A., Charpin, P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010)MathSciNetCrossRefMATH
33.
Jean-Charles, F., Perret, L.: An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography. J. Symbolic Comput. 44(12), 1676–1689 (2009)MathSciNetCrossRefMATH
34.
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH
35.
Patarin, J.: New results on pseudorandom permutation generators based on the DES scheme. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 301–312. Springer, Heidelberg (1992)
36.
Patarin, J.: Security of random feistel schemes with 5 or more rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004) CrossRef
37.
Een, N., Sörensson, N.: Minisat: A sat solver with conflict-clause minimization. Sat 5 (2005)
38.
Biryukov, A., Leurent, G., Perrin, L.: ESC 2015 S-box Reverse-Engineering Challenge. In: Early Symmetric Crypto, ESC 2015, pp. 104–107 (2015)
39.
Canteaut, A.: Analyse et Conception de Chiffrements à Clef Secrète. Habilitation à diriger des recherches, Institut National de Recherche en Informatique et Automatique, Rocquencourt, September 2006
40.
Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-Bit blockcipher CLEFIA (extended abstract). In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 181–195. Springer, Heidelberg (2007) CrossRef
41.
Massey, J.L.: Safer k-64: A byte-oriented block-ciphering algorithm. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 1–17. Springer, Heidelberg (1994) CrossRef
42.
Metadaten
Titel
On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure
verfasst von
Alex Biryukov
Léo Perrin
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology -- CRYPTO 2015

Print ISBN: 978-3-662-47988-9

Electronic ISBN: 978-3-662-47989-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-47989-6_6