[en] 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.
Disciplines :
Computer science
Author, co-author :
Biryukov, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Perrin, Léo Paul ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Udovenko, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
no
Language :
English
Title :
Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1
Publication date :
28 April 2016
Event name :
35th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Event organizer :
International Association for Cryptologic Research (IACR)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and Cryptography. Springer, Heidelberg (2002)
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Crypt. 4(1), 3–72 (1991)
Tardy-Corfdir, A., Gilbert, H.: A known plaintext attack of FEAL-4 and FEAL-6. In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO 1992. LNCS, vol. 576, pp. 172–182. Springer, Berlin Heidelberg (1992)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Suzaki, T., Minematsu, K., Morioka, S., Kobayashi, E.: TWINE: A lightweight block cipher for multiple platforms. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 339–354. Springer, Heidelberg (2013)
U.S. Department: OF COMMERCE/National Institute of Standards and Technology: Data encryption standard. Publication, Federal Information Processing Standards (1999)
Coppersmith, D.: The data encryption standard (DES) and its strength against attacks. IBM J. Res. Develop. 38(3), 243–250 (1994)
National Security Agency, N.S.A.: SKIPJACK and KEA AlgorithmSpecifications (1998)
Biryukov, A., Perrin, L.: On reverse-engineering s-boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015. LNCS, vol. 9215, pp. 116–140. Springer, Berlin, Heidelberg (2015)
Federal Agency on Technical Regulation and Metrology: GOST R34.11-2012: Streebog hash function (2012). https://www.streebog.net/
Guo, J., Jean, J., Leurent, G., Peyrin, T., Wang, L.: The usage of counter revisited: second-preimage attack on new russian standardized hash function. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 195–211. Springer International Publishing, Switzerland (2014)
AlTawy, R., Youssef, A.M.: Watch your constants: malicious streebog. IET Inf. Secur. 9(6), 328–333 (2015)
Biryukov, A., Perrin, L., Udovenko, A.: Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr 1. Cryptology ePrint Archive, report 2016/071 (2016). http://eprint.iacr.org/
Shishkin, V., Dygin, D., Lavrikov, I., Marshalko, G., Rudskoy, V., Trifonov, D.: Low-weight and hi-end: draft russian encryption standard. In: Preproceedings of CTCrypt 2014, 05–06 June 2014, Moscow. Russia, pp. 183–188 (2014)
Federal Agency on Technical Regulation and Metrology: Block ciphers (2015). http://www.tc26.ru/en/standard/draft/ENG GOSTRbsh.pdf
AlTawy, R., Youssef, A.M.: A meet in the middle attack on reduced round Kuznyechik. Cryptology ePrint Archive, report 2015/096 (2015). http://eprint.iacr.org/
Dolmatov, V.: GOST 28147–89: Encryption, decryption, and message authentication code (MAC) algorithms, RFC 5830, March 2010. http://www.rfc-editor.org/rfc/rfc5830.txt
Saarinen, M.J.O.: STRIBOB: Authenticated encryption from GOST R 34.11-2012 LPS permutation. In: [Mathematical Aspects of Cryptography]. vol.6(2), pp. 67–78. Steklov Mathematical Institute ofRussian Academy of Sciences (2015)
Saarinen, M.J.O., Brumley, B.B.: WHIRLBOB, the whirlpool based variant of STRIBOB. In: Buchegger, S., Dam, M. (eds.) NordSec 2015. LNCS, vol. 9417, pp. 106–122. Springer International Publishing, Cham (2015)
Barreto, P., Rijmen, V.: The whirlpool hashing function. In: First open NESSIE Workshop, Leuven, Belgium. vol. 13, p. 14 (2000)
Saarinen, M.J.O.: STRIBOBr 2 availability. Mail to the CAESAR mailing list. https://groups.google.com/forum/#!topic/crypto-competitions/zgi54-NEFM
Knudsen, L.R., Robshaw, M.J., Wagner, D.: Truncated differentials and skipjack. In: Wiener, M. (ed.) Advances in Cryptology-CRYPTO 1999. LNCS, vol. 1666, pp. 165–180. Springer, Heidelberg (1999)
Biham, E., Biryukov, A., Dunkelman, O., Richardson, E., Shamir, A.: Initial observations on skipjack: cryptanalysis of skipjack-3XOR. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, p. 362. Springer, Heidelberg (1999)
Knudsen, L., Wagner, D.: On the structure of Skipjack. Discrete Appl. Math. 111(1), 103–116 (2001)
Kazymyrov, O., Kazymyrova, V.: Algebraic aspects of the russian hash standard GOST R 34.11-2012. In: IACR Cryptology ePrint Archive 2013 556 (2013)
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) Advances in Cryptology - EUROCRYPT 2001. LNCS, vol. 2045, pp. 395–405. Springer, Berlin Heidelberg (2001)
Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel networks with secret round functions. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS. Springer International Publishing, Heidelberg (2015)
Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Math. Crypt. JMC 1(3), 221–242 (2007)
Blondeau, C., Canteaut, A., Charpin, P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010)
Preneel, B.: Analysis and design of cryptographic hash functions. Ph.D. thesis, Katholieke Universiteit Leuven (1993)
The Sage Developers: Sage Mathematics Software (Version 6.8) (2015). http://www.sagemath.org
Canright, D.: A very compact S-Box for AES. In: Rao, J., Sunar, B. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2005. LNCS, vol. 3659, pp. 441–455. Springer, Berlin Heidelberg (2005)
Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) Advances in Cryptology - ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Berlin Heidelberg (2012)
Gérard, B., Grosso, V., Naya-Plasencia, M., Standaert, F.-X.: Block ciphers that are easier to mask: how far can we go? In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 383–399. Springer, Heidelberg (2013)
Standaert, F.X., Piret, G., Rouvroy, G., Quisquater, J.J., Legat, J.D.: ICEBERG: An involutional cipher efficient for block encryption in reconfigurable hardware. In: Roy, B., Meier, W. (eds.) Fast Software Encryption. LNCS, vol. 3017, pp. 279–298. Springer, Berlin Heidelberg (2004)
Barreto, P., Rijmen, V.: The Khazad legacy-level block cipher. In: Primitive submitted to NESSIE 97 (2000)
Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-Bit blockcipher CLEFIA (Extended Abstract). In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 181–195. Springer, Heidelberg (2007)
Canteaut, A., Duval, S., Leurent, G.: Construction of lightweight s-boxes using feistel and MISTY structures. In: Dunkelman, O., Keliher, L. (eds.) Selected Areas in Cryptography - SAC 2015. LNCS, vol. 8731. Springer International Publishing, Heidelberg (2015)
Matsui, M.: New block encryption algorithm MISTY. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 54–68. Springer, Berlin, Heidelberg (1997)
Specification of the 3GPP Confidentiality and Integrity Algorithms 128- EEA3 & 128-EIA3. Document 4: Design and Evaluation Report, Technical report, ETSI/Sage, September 2011. http://www.gsma.com/aboutus/wp-content/uploads/2014/12/EEA3EIA3DesignEvaluationv20.pdf