Cryptology ePrint Archive: Report 2016/071

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

Alex Biryukov and 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.

Category / Keywords: Reverse-Engineering, S-Box, Streebog, Kuznyechik, STRIBOBr1, White-Box, Linear Approximation Table, Feistel Network

Original Publication (with major differences): IACR-EUROCRYPT-2016

Date: received 26 Jan 2016, last revised 18 Feb 2016

Contact author: leo perrin at uni lu

Available format(s): PDF | BibTeX Citation

Note: Fixed bibliography and added an alternative decomposition.

Version: 20160218:165932 (All versions of this report)

Short URL: ia.cr/2016/071

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]