Paper 2016/071

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

Alex Biryukov, Léo Perrin, and Aleksei Udovenko

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.

Note: Fixed bibliography and added an alternative decomposition.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
Reverse-EngineeringS-BoxStreebogKuznyechikSTRIBOBr1White-BoxLinear Approximation TableFeistel Network
Contact author(s)
leo perrin @ uni lu
History
2016-02-18: revised
2016-01-26: received
See all versions
Short URL
https://ia.cr/2016/071
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/071,
      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{https://eprint.iacr.org/2016/071}},
      url = {https://eprint.iacr.org/2016/071}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.