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:
Tightly CCA-Secure Encryption Without Pairings Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1

verfasst von : Alex Biryukov, Léo Perrin, Aleksei Udovenko

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

The Russian Federation’s standardization agency has recently published a hash function called Streebog and a 128-bit block cipher called Kuznyechik. Both of these algorithms use the same 8-bit S-Box but its design rationale was never made public.
In this paper, we reverse-engineer this S-Box and reveal its hidden structure. It is based on a sort of 2-round Feistel Network where exclusive-or is replaced by a finite field multiplication. This structure is hidden by two different linear layers applied before and after. In total, five different 4-bit S-Boxes, a multiplexer, two 8-bit linear permutations and two finite field multiplications in a field of size \(2^{4}\) are needed to compute the S-Box.
The knowledge of this decomposition allows a much more efficient hardware implementation by dividing the area and the delay by 2.5 and 8 respectively. However, the small 4-bit S-Boxes do not have very good cryptographic properties. In fact, one of them has a probability 1 differential.
We then generalize the method we used to partially recover the linear layers used to whiten the core of this S-Box and illustrate it with a generic decomposition attack against 4-round Feistel Networks whitened with unknown linear layers. Our attack exploits a particular pattern arising in the Linear Approximations Table of such functions.

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 Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning
Nächstes Kapitel Complete Addition Formulas for Prime Order Elliptic Curves
Fußnoten
1
The version submitted to the next round, referred to as “stribobr2” and “whirlbob” [21], uses the S-Box of the Whirlpool hash function [22] whose design criteria and structure are public. In fact, the secrecy surrounding the S-Box of Streebog was part of the motivation behind this change [23].
 
2
Except of course in position (0, 0) where the bias is equal to the maximum of 128.
 
3
It is obtained by setting \(b=b_0=a=0\) in the statement of the original proposition and renaming the functions used.
 
5
Note that the LAT of \(\hat{\pi }\) is not exactly the same as \(\mathcal {L}_{\pi }'\) which is given in Fig. 4 because e.g. of a nibble swap.
 
6
We used Synopsys design_compiler (version J-2014.09-SP2) along with digital library SAED_EDK90_CORE (version 1.11).
 
7
More precisely, the multiplexer is moved after the left side is input to \(\phi \). This does not change the output: when the output of \(\nu _{0}\) is selected, the right branch is equal to 0 and the input of \(\sigma \) is thus 0 regardless of the left side.
 
8
Note that our proof actually only requires \(F_{1}\) and \(F_{2}\) to be permutations. The pattern would still be present if the first and/or last Feistel functions had inner-collisions.
 
9
We make some definitions with transpose to simplify later notations.
 
Literatur
1.
Daemen, J., Rijmen, V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and Cryptography. Springer, Heidelberg (2002)CrossRefMATH
2.
3.
Tardy-Corfdir, A., Gilbert, H.: A known plaintext attack of FEAL-4 and FEAL-6. In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO 1992. LNCS, vol. 576, pp. 172–182. Springer, Berlin Heidelberg (1992)
4.
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
5.
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
6.
Suzaki, T., Minematsu, K., Morioka, S., Kobayashi, E.: TWINE : A lightweight block cipher for multiple platforms. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 339–354. Springer, Heidelberg (2013)CrossRef
7.
U.S. Department: OF COMMERCE/National Institute of Standards and Technology: Data encryption standard. Publication, Federal Information Processing Standards (1999)
8.
Coppersmith, D.: The data encryption standard (DES) and its strength against attacks. IBM J. Res. Develop. 38(3), 243–250 (1994)MathSciNetCrossRefMATH
9.
National Security Agency, N.S.A.: SKIPJACK and KEA AlgorithmSpecifications (1998)
10.
Biryukov, A., Perrin, L.: On reverse-engineering s-boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015. LNCS, vol. 9215, pp. 116–140. Springer, Berlin, Heidelberg (2015)CrossRef
11.
12.
Guo, J., Jean, J., Leurent, G., Peyrin, T., Wang, L.: The usage of counter revisited: second-preimage attack on new russian standardized hash function. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 195–211. Springer International Publishing, Switzerland (2014)CrossRef
13.
AlTawy, R., Youssef, A.M.: Watch your constants: malicious streebog. IET Inf. Secur. 9(6), 328–333 (2015)CrossRef
14.
15.
Biryukov, A., Perrin, L., Udovenko, A.: Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr 1. Cryptology ePrint Archive, report 2016/071 (2016). http://​eprint.​iacr.​org/​
16.
Shishkin, V., Dygin, D., Lavrikov, I., Marshalko, G., Rudskoy, V., Trifonov, D.: Low-weight and hi-end: draft russian encryption standard. In: Preproceedings of CTCrypt 2014, 05–06 June 2014, Moscow. Russia, pp. 183–188 (2014)
17.
18.
19.
20.
Saarinen, M.J.O.: STRIBOB: Authenticated encryption from GOST R 34.11-2012 LPS permutation. In: https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-49890-3_15/MediaObjects/420599_1_En_15_Figd_HTML.gif [Mathematical Aspects of Cryptography]. vol.6(2), pp. 67–78. Steklov Mathematical Institute ofRussian Academy of Sciences (2015)
21.
Saarinen, M.J.O., Brumley, B.B.: WHIRLBOB, the whirlpool based variant of STRIBOB. In: Buchegger, S., Dam, M. (eds.) NordSec 2015. LNCS, vol. 9417, pp. 106–122. Springer International Publishing, Cham (2015)CrossRef
22.
Barreto, P., Rijmen, V.: The whirlpool hashing function. In: First open NESSIE Workshop, Leuven, Belgium. vol. 13, p. 14 (2000)
23.
24.
25.
Knudsen, L.R., Robshaw, M.J., Wagner, D.: Truncated differentials and skipjack. In: Wiener, M. (ed.) Advances in Cryptology-CRYPTO 1999. LNCS, vol. 1666, pp. 165–180. Springer, Heidelberg (1999)
26.
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, p. 362. Springer, Heidelberg (1999)CrossRef
27.
28.
Kazymyrov, O., Kazymyrova, V.: Algebraic aspects of the russian hash standard GOST R 34.11-2012. In: IACR Cryptology ePrint Archive 2013 556 (2013)
29.
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) Advances in Cryptology - EUROCRYPT 2001. LNCS, vol. 2045, pp. 395–405. Springer, Berlin Heidelberg (2001)CrossRef
30.
Dinur, I., Dunkelman, O., Kranz, T., Leander, G.: Decomposing the ASASA block cipher construction. In: Cryptology ePrint Archive, report 2015/507 (2015). http://​eprint.​iacr.​org/​
31.
Minaud, B., Derbez, P., Fouque, P.A., Karpman, P.: Key-Recovery attacks on ASASA. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology – ASIACRYPT 2015. LNCS, vol. 9453, pp. 3–27. Springer, Heidelberg (2015)CrossRef
32.
Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel networks with secret round functions. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS. Springer International Publishing, Heidelberg (2015)
33.
Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Math. Crypt. JMC 1(3), 221–242 (2007)MathSciNetMATH
34.
Blondeau, C., Canteaut, A., Charpin, P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010)MathSciNetCrossRefMATH
35.
Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis, Katholieke Universiteit Leuven (1993)
36.
37.
Canright, D.: A very compact S-Box for AES. In: Rao, J., Sunar, B. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2005. LNCS, vol. 3659, pp. 441–455. Springer, Berlin Heidelberg (2005)CrossRef
38.
Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) Advances in Cryptology - ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Berlin Heidelberg (2012)CrossRef
39.
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
40.
Standaert, F.X., Piret, G., Rouvroy, G., Quisquater, J.J., Legat, J.D.: ICEBERG : An involutional cipher efficient for block encryption in reconfigurable hardware. In: Roy, B., Meier, W. (eds.) Fast Software Encryption. LNCS, vol. 3017, pp. 279–298. Springer, Berlin Heidelberg (2004)CrossRef
41.
Barreto, P., Rijmen, V.: The Khazad legacy-level block cipher. In: Primitive submitted to NESSIE 97 (2000)
42.
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
43.
Grosso, V., Leurent, G., Standaert, F.X., Varıcı, K.: LS-designs: Bitslice encryption for efficient masked software implementations. In: Fast Software Encryption (2014)
44.
Canteaut, A., Duval, S., Leurent, G.: Construction of lightweight s-boxes using feistel and MISTY structures. In: Dunkelman, O., Keliher, L. (eds.) Selected Areas in Cryptography - SAC 2015. LNCS, vol. 8731. Springer International Publishing, Heidelberg (2015)
45.
Matsui, M.: New block encryption algorithm MISTY. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 54–68. Springer, Berlin, Heidelberg (1997)CrossRef
46.
Metadaten
Titel
Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1
verfasst von
Alex Biryukov
Léo Perrin
Aleksei Udovenko
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – EUROCRYPT 2016

Print ISBN: 978-3-662-49889-7

Electronic ISBN: 978-3-662-49890-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49890-3_15

Premium Partner

    Bildnachweise