Paper 2016/071

Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version)

Alex Biryukov, Léo Perrin, and Aleksei Udovenko


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.

Note: Fixed bibliography and added an alternative decomposition.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Reverse-EngineeringS-BoxStreebogKuznyechikSTRIBOBr1White-BoxLinear Approximation TableFeistel Network
Contact author(s)
leo perrin @ uni lu
2016-02-18: revised
2016-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Biryukov and Léo Perrin and Aleksei Udovenko},
      title = {Reverse-Engineering the S-Box of Streebog, Kuznyechik and {STRIBOBr1} (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/071},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.