Léo Perrin
email: leo.perrin@inria.fr@lpp_crypto

Streebog and Kuznyechik Inconsistencies in the Claims of their Designers

Keywords: Boolean functions, Kuznyechik, Streebog, Reverse-Engineering, Partitions, Cosets, TKlog

Streebog and Kuznyechik are the latest symmetric cryptographic primitives standardized by the Russian GOST. They share the same S-Box, 𝜋, whose design process was not described by its authors. In previous works, Biryukov, Perrin and Udovenko recovered two completely different decompositions of this S-Box. We revisit their results and identify a third decomposition of 𝜋. It is an instance of a fairly small family of permutations operating on 2𝑚 bits which we call TKlog and which is closely related to finite field logarithms. Its simplicity and the small number of components it uses lead us to claim that it has to be the structure intentionally used by the designers of Streebog and Kuznyechik. The 2𝑚-bit permutations of this type have a very strong algebraic structure: they map multiplicative cosets of the subfield GF(2𝑚)* to additive cosets of GF(2𝑚)*. Furthermore, the function relating each multiplicative coset to the corresponding additive coset is always essentially the same. To the best of our knowledge, we are the first to expose this very strong algebraic structure. We also investigate other properties of the TKlog and show in particular that it can always be decomposed in a fashion similar to the first decomposition of Biryukov et al., thus explaining the relation between the two previous decompositions. It also means that it is always possible to implement a TKlog efficiently in hardware and that it always exhibits a visual pattern in its LAT similar to the one present in 𝜋. While we could not find attacks based on these new results, we discuss the impact of our work on the security of Streebog and Kuznyechik. To this end, we provide a new simpler representation of the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define 𝜋. We deduce that this matrix interacts in a non-trivial way with the partitions preserved by 𝜋.

Introduction

Many symmetric primitives rely on S-Boxes as their unique source of non-linearity, including the AES [AES01]. Such objects are small functions mapping F𝑚 2 to F𝑛 2 which are often specified via their look-up tables.

Their choice is crucial as both the security and the efficiency of the primitive depends heavily on their properties. For example, a low differential uniformity [Nyb94] implies a higher resilience against differential attacks [BS91a, BS91b]. On the other hand, the existence of a simple decomposition greatly helps with an efficient bitsliced or hardware implementation [LW14, CDL16]. Thus, algorithm designers are expected to provide detailed explanation about their choice of S-Box. Each cipher that was published at a cryptography or security conference has provided such explanations.

There are two prominent S-Boxes for which this information has not been provided. The first is the so-called "F-

The ByteSub S-box

The design criteria for the S-box are inspired by differential and linear cryptanalysis on the one hand and attacks using algebraic manipulations, such as interpolation attacks, on the other: 1. Invertibility; 2. Minimisation of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits;

3. Minimisation of the largest non-trivial value in the EXOR table ;   4. Complexity of its algebraic expression in GF(2 8 );

5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For invertible S-boxes operating on bytes, the maximum input/output correlation can be made as low as 2 -3 and the maximum value in the EXOR table can be as low as 4 (corresponding to a difference propagation probability of 2 -6 ).

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the mapping x ⇒ x -1 in GF(2 8 ).

By definition, the selected mapping has a very simple algebraic expression. This enables algebraic manipulations that can be used to mount attacks such as interpolation attacks [JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible affine transformation. This affine transformation does not affect the properties with respect tot the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the 'inverse' mapping. It can be seen as modular polynomial multiplication followed by an addition:

7 6 2 7 6 5 4 8 b x x + x x + x) a x (x + x x + x 1 mod x + 1 ( ) ( = + + ( ) + + )
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box(a) = a) and no 'opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an Sbox that is "average" in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

�������� ������� ��

The ByteSub S-box

The design criteria for the S-box are inspired by differential and linear cryptanalysis on the one hand and attacks using algebraic manipulations, such as interpolation attacks, on the other: 1. Invertibility; 2. Minimisation of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits;

3. Minimisation of the largest non-trivial value in the EXOR table ;   4. Complexity of its algebraic expression in GF(2 8 );

5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For invertible S-boxes operating on bytes, the maximum input/output correlation can be made as low as 2 -3 and the maximum value in the EXOR table can be as low as 4 (corresponding to a difference propagation probability of 2 -6 ).

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the mapping x ⇒ x -1 in GF(2 8 ).

By definition, the selected mapping has a very simple algebraic expression. This enables algebraic manipulations that can be used to mount attacks such as interpolation attacks [JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible affine transformation. This affine transformation does not affect the properties with respect tot the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the 'inverse' mapping. It can be seen as modular polynomial multiplication followed by an addition:

7 6 2 7 6 5 4 8 b x x + x x + x) a x (x + x x + x 1 mod x + 1 ( ) ( = + + ( ) + + )
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box(a) = a) and no 'opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an Sbox that is "average" in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

�������� ������� �� ����� �������� ����� ��/��

The ByteSub S-box

The design criteria for the S-box are inspired by differential and linear cryptanalysis on the one hand and attacks using algebraic manipulations, such as interpolation attacks, on the other: 1. Invertibility; 2. Minimisation of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits;

3. Minimisation of the largest non-trivial value in the EXOR table ;   4. Complexity of its algebraic expression in GF(2 8 );

5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For invertible S-boxes operating on bytes, the maximum input/output correlation can be made as low as 2 -3 and the maximum value in the EXOR table can be as low as 4 (corresponding to a difference propagation probability of 2 -6 ).

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the mapping x ⇒ x -1 in GF(2 8 ).

By definition, the selected mapping has a very simple algebraic expression. This enables algebraic manipulations that can be used to mount attacks such as interpolation attacks [JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible affine transformation. This affine transformation does not affect the properties with respect tot the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the 'inverse' mapping. It can be seen as modular polynomial multiplication followed by an addition:

7 6 2 7 6 5 4 8 b x x + x x + x) a x (x + x x + x 1 mod x + 1 ( ) ( = + + ( ) + + )
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box(a) = a) and no 'opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an Sbox that is "average" in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

�������� ������� ��

The ByteSub S-box

The design criteria for the S-box are inspired by differential and linear cryptanalysis on the one hand and attacks using algebraic manipulations, such as interpolation attacks, on the other: 1. Invertibility; 2. Minimisation of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits;

3. Minimisation of the largest non-trivial value in the EXOR table ;   4. Complexity of its algebraic expression in GF(2 8 );

5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For invertible S-boxes operating on bytes, the maximum input/output correlation can be made as low as 2 -3 and the maximum value in the EXOR table can be as low as 4 (corresponding to a difference propagation probability of 2 -6 ).

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the mapping x ⇒ x -1 in GF(2 8 ).

By definition, the selected mapping has a very simple algebraic expression. This enables algebraic manipulations that can be used to mount attacks such as interpolation attacks [JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible affine transformation. This affine transformation does not affect the properties with respect tot the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the 'inverse' mapping. It can be seen as modular polynomial multiplication followed by an addition:

7 6 2 7 6 5 4 8 b x x + x x + x) a x (x + x x + x 1 mod x + 1 ( ) ( = + + ( ) + + )
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box(a) = a) and no 'opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an Sbox that is "average" in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

�������� ������� ��

The ByteSub S-box

The design criteria for the S-box are inspired by differential and linear cryptanalysis on the one hand and attacks using algebraic manipulations, such as interpolation attacks, on the other: 1. Invertibility; 2. Minimisation of the largest non-trivial correlation between linear combinations of input bits and linear combination of output bits;

3. Minimisation of the largest non-trivial value in the EXOR table ;   4. Complexity of its algebraic expression in GF(2 8 );

5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For invertible S-boxes operating on bytes, the maximum input/output correlation can be made as low as 2 -3 and the maximum value in the EXOR table can be as low as 4 (corresponding to a difference propagation probability of 2 -6 ).

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the mapping x ⇒ x -1 in GF(2 8 ).

By definition, the selected mapping has a very simple algebraic expression. This enables algebraic manipulations that can be used to mount attacks such as interpolation attacks [JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible affine transformation. This affine transformation does not affect the properties with respect tot the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the 'inverse' mapping. It can be seen as modular polynomial multiplication followed by an addition:

7 6 2 7 6 5 4 8 b x x + x x + x) a x (x + x x + x 1 mod x + 1 ( ) ( = + + ( ) + + )
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box(a) = a) and no 'opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an Sbox that is "average" in this respect is likely to provide enough resistance against differential and linear cryptanalysis.

�������� ������� ��

Common ground

Both are standards in Russia.

They were designed by the TC26 (supervised by the FSB).

Their RFCs come from the independent stream (̸ = CFRG)

Both use the same 8-bit S-Box, π. 165 ASCII characters that fit on 7 bits: this program is 1155-bit long An AMD64 binary implementation fits 2 on 78 bytes, i.e. 624 bits. Many more short implementations have been found by code golfers! 3

π          F 2 8 → F 2 8 0 → κ(0) , (α 2 m +1 ) j → κ(2 m -j), for 1 ≤ j ≤ 2 m -1 , α i+(2 m +1)j → κ(2 m -i) ⊕ ( α 2 m +1 ) s(j) , for 0 < i, 0 ≤ j < 2 m -1 .
The probability that a random S-box is that simple is completely negligible (≤ 2 -1059 ). This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design. This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! =⇒ These algorithms cannot be trusted and I believe they should be deprecated.

vs.

This claim and this fact cannot be reconciled.

In my opinion, the designers of these algorithms have provided misleading information for the external analysis of their design.

Security analysis is hard enough with proper information: there is no good reason to complicate it further with wrong data! =⇒ These algorithms cannot be trusted and I believe they should be deprecated.

{0} V α × V α 2 × V ...

Feb. 2019

 2019 Kuznyechik at ISO: decision post-poned ISO Sep. 2019 Kuznyechik at ISO: decision must be taken! ISO Outline Standards and S-boxes On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion The Russian S-box Screen capture of the specification of Kuznyechik (2015). 8 / 11 Standards and S-boxes On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion How Was it Generated? According to the designers (April 2018) [...] Source: https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf See also the discussion summary: https://cdn.virgilsecurity.com/assets/docs/ meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf How Was it Generated? According to the designers (April 2018) [...] Source: https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf See also the discussion summary: https://cdn.virgilsecurity.com/assets/docs/ meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf What I proved (IACR ToSC 2019)

1 Bonnetain,

 1 Perrin, Tian. Anomalies and Vector Space Search: Tools for S-Box Reverse-Engineering. https://ia.cr/2019/528 2 Credit to @odzhan on stackexchange. 3 https://codegolf.stackexchange.com/questions/186498/ proving-that-a-russian-cryptographic-standard-is-too-structured On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Outline Standards and S-boxes On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Conclusion vs. This claim and this fact cannot be reconciled. 11 / 11 Standards and S-boxes On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Conclusion vs.

  On the S-box of RFC 6986 and 7801The Core Issue: the S-Box Generation Process Conclusion Conclusion vs.

  box (https://ia.cr/2016/493)λ(0) ⊕ V λ(15) ⊕ V λ(14) ⊕ V ... κ(0) ⊕ W κ(15) ⊕ W κ(14) ⊕ W ...

  table" of Skipjack [U.S98], a lightweight block cipher designed 8}) which can be specified via its lookup table.

	Transactions in Symmetric The Core Issue: the S-Box Generation Process The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Outline On the S-box of RFC 6986 and 7801 Outline On the S-box of RFC 6986 and 7801 On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Life Cycle of a Cryptographic Primitive Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Breaking the Pipeline Design Public Analysis Deployment Small teams Academic community Industry Breaking the Pipeline Design Public Analysis Deployment Small teams Academic community Industry On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Breaking the Pipeline Design Public Analysis Deployment Small teams Academic community Industry S-Boxes Definition (S(ubstitution)-box) An S-box S : F n 2 → F n 2 is a small non-linear function operating on a small On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Specifying the AES S-box block size (typically n ∈ {4, Standards and S-boxes �������� The Rijndael Block Cipher AES Proposal The Rijndael Block Cipher The The Rijndael Rijndael Block Block Cipher Cipher ���� ������ ������� ������	Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion Conclusion
	Cryptology, Volume 2019, No. 1, pp. 302-329. Best paper award! What is this result? The Core Issue: the S-Box Generation Process Standards and S-boxes On the S-box of RFC 6986 and 7801 Standards and S-boxes On the S-box of RFC 6986 and 7801 Design choices Design choices Design choices Design choices Design choices Well-studied Design choices Well-studied ...unless a new ...unless a new Design choices Well-studied ...unless a new ...unless a new The Core Issue: the S-Box Generation Process Scope statement Algorithm specification Scope statement Algorithm specification Scope statement Algorithm specification Try and break published algorithms Scope statement Algorithm specification Try and break published algorithms Scope statement Algorithm specification Try and break published algorithms Scope statement Algorithm specification Try and break published algorithms Implements algorithms in actual products... Implements algorithms in actual products... ??? Scope Try and break statement published Implements Implements Algorithm specification algorithms algorithms in actual products... algorithms in actual products... Hidden defect?
	Conclusion Security Security Security Security Security Security Security Conclusion justifications justifications justifications justifications justifications justifications justifications	eventually trusted eventually trusted eventually trusted algorithms are algorithms are algorithms are	Why is it inconsistent with the claims of the designers of these attack is found attack is found attack is found attack is found
	analysis analysis analysis analysis analysis analysis analysis			algorithms?
	Licensed under Creative Commons License CC-BY 4.0. IACR Transactions on Symmetric Cryptology ISSN 2519-173X, Vol. 2019, No. 1, pp. 302-329 DOI:10.13154/tosc.v2019.i1.302-329 Publication Publication Publication Publication Publication Publication Publication Publication Publication	Standardization Standardization Standardization Standardization Standardization Standardization Standardization Standardization Standardization	time time time time time time time time time time
	Conf., competition Conf., competition Conf., competition Conf., competition Conf., competition	NIST, ISO, IETF... NIST, ISO, IETF... NIST, ISO, IETF... NIST, ISO, IETF... NIST, ISO, IETF...

Conf., competition NIST, ISO, IETF... Conf., competition NIST, ISO, IETF... Conf., competition NIST, ISO, IETF... Conf., competition NIST, ISO, IETF...

IACR ToSC 2016

	On the S-box of RFC 6986 and 7801 On the S-box of RFC 6986 and 7801 On the S-box of RFC 6986 and 7801 On the S-box of RFC 6986 and 7801	The Core Issue: the S-Box Generation Process The Core Issue: the S-Box Generation Process The Core Issue: the S-Box Generation Process The Core Issue: the S-Box Generation Process	Conclusion Conclusion Conclusion Conclusion
	Timeline Timeline Timeline Timeline
	July GOST standardization of Streebog July GOST standardization of Streebog July 2012 GOST standardization of Streebog July 2012 GOST standardization of Streebog	GOST GOST GOST GOST
	Aug. RFC for Streebog (RFC 6986) Aug. RFC for Streebog (RFC 6986) Aug. 2013 RFC for Streebog (RFC 6986) Aug. 2013 RFC for Streebog (RFC 6986)	IETF IETF IETF IETF
	June GOST standardization of Kuznyechik June GOST standardization of Kuznyechik June 2015 GOST standardization of Kuznyechik June 2015 GOST standardization of Kuznyechik	GOST GOST GOST GOST
	Mar. RFC for Kuznyechik (RFC 7801) Mar. RFC for Kuznyechik (RFC 7801) Mar. 2016 RFC for Kuznyechik (RFC 7801) Mar. 2016 RFC for Kuznyechik (RFC 7801)	IETF IETF IETF IETF
	May Publication of the first decomposition May 2016 Publication of the first decomposition May 2016 Publication of the first decomposition	IACR IACR IACR
	Biryukov, Perrin, Udovenko. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. EUROCRYPT'16 Biryukov, Perrin, Udovenko. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. EUROCRYPT'16 Biryukov, Perrin, Udovenko. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. EUROCRYPT'16
	Mar. Publication of the second decomposition Mar. 2017 Publication of the second decomposition Mar. 2017 Publication of the second decomposition	IACR IACR IACR
	Oct. 2018 ISO standardization of Streebog (ISO 10118-3)	ISO

Perrin, Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog. Perrin, Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog.

IACR ToSC 2016

	On the S-box of RFC 6986 and 7801	The Core Issue: the S-Box Generation Process	Conclusion
	Timeline
	July 2012 GOST standardization of Streebog	GOST GOST
	Aug. 2013 RFC for Streebog (RFC 6986) Aug. 2013 RFC for Streebog (RFC 6986)	IETF IETF
	June 2015 GOST standardization of Kuznyechik June 2015 GOST standardization of Kuznyechik	GOST GOST
	Mar. 2016 RFC for Kuznyechik (RFC 7801) Mar. 2016 RFC for Kuznyechik (RFC 7801)	IETF IETF
	May 2016 Publication of the first decomposition May 2016 Publication of the first decomposition	IACR IACR
	Biryukov, Perrin, Udovenko. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. EUROCRYPT'16 Biryukov, Perrin, Udovenko. Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. EUROCRYPT'16
	Mar. 2017 Publication of the second decomposition Mar. 2017 Publication of the second decomposition	IACR IACR
	Perrin, Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog. IACR ToSC 2016 Perrin, Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog. IACR ToSC 2016
	Oct. 2018 ISO standardization of Streebog (ISO 10118-3) Oct. 2018 ISO standardization of Streebog (ISO 10118-3) Oct. 2018 ISO standardization of Streebog (ISO 10118-3)	ISO ISO ISO
	Jan. 2019 Publication of the final decomposition Jan. 2019 Publication of the final decomposition Jan. 2019 Publication of the final decomposition	IACR IACR IACR
	Perrin. Partitions in the S-box of Streebog and Kuznyechik. IACR ToSC 2019. Perrin. Partitions in the S-box of Streebog and Kuznyechik. IACR ToSC 2019. Perrin. Partitions in the S-box of Streebog and Kuznyechik. IACR ToSC 2019.
	Feb. 2019 Kuznyechik at ISO: decision post-poned	ISO

  On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Such a Structure is Beyond Unlikely Lemma (more details available online 1 ) On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Such a Structure is Beyond Unlikely Lemma (more details available online 1 ) There are 256! ≈ 2 1684 different 8-bit permutations, meaning you need at least 1684 bits to represent all of them in any language.

	On the S-box of RFC 6986 and 7801	The Core Issue: the S-Box Generation Process	Conclusion
	Such a Structure is Beyond Unlikely
	Lemma (more details available online 1 )
	There are 256! ≈ 2 1684 different 8-bit permutations, meaning you need at
	least 1684 bits to represent all of them in any language.

1 Bonnetain, Perrin, Tian. Anomalies and Vector Space Search: Tools for S-Box Reverse-Engineering. https://ia.cr/2019/528 2 Credit to @odzhan on stackexchange. 3 https://codegolf.stackexchange.com/questions/186498/ proving-that-a-russian-cryptographic-standard-is-too-structured There are 256! ≈ 2 1684 different 8-bit permutations, meaning you need at least 1684 bits to represent all of them in any language. 165 ASCII characters that fit on 7 bits: this program is 1155-bit long 1 Bonnetain, Perrin, Tian. Anomalies and Vector Space Search: Tools for S-Box Reverse-Engineering. https://ia.cr/2019/528 2 Credit to @odzhan on stackexchange. 3 https://codegolf.stackexchange.com/questions/186498/ proving-that-a-russian-cryptographic-standard-is-too-structured There are 256! ≈ 2 1684 different 8-bit permutations, meaning you need at least 1684 bits to represent all of them in any language.

165 ASCII characters that fit on 7 bits: this program is 1155-bit long An AMD64 binary implementation fits 2 on 78 bytes, i.e. 624 bits. Many more short implementations have been found by code golfers! 3 On the S-box of RFC 6986 and 7801 The Core Issue: the S-Box Generation Process Conclusion Such a Structure is Beyond Unlikely Lemma (more details available online 1 )

  On the S-box of RFC 6986 and 7801The Core Issue: the S-Box Generation Process Conclusion

	Conclusion
	vs.

https://csrc.nist.gov/csrc/media/projects/ cryptographic-standards-and-guidelines/documents/ aes-development/rijndael-ammended.pdf1 Clear design goals

Perrin, Udovenko. Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog. IACR ToSC 2016

July 2012 GOST standardization of Streebog