eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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.