×

Reverse-engineering the S-Bbox of Streebog, Kuznyechik and Stribobr1. (English) Zbl 1385.94016

Fischlin, Marc (ed.) et al., Advances in cryptology – EUROCRYPT 2016. 35th annual international conference on the theory and applications of cryptographic techniques, Vienna, Austria, May 8–12, 2016. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-49889-7/pbk; 978-3-662-49890-3/ebook). Lecture Notes in Computer Science 9665, 372-402 (2016).
Summary: 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.
For the entire collection see [Zbl 1339.94004].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI