Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DDD421286E7 for ; Sun, 10 Feb 2019 13:49:51 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -6.9 X-Spam-Level: X-Spam-Status: No, score=-6.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LW9HieDbWq9q for ; Sun, 10 Feb 2019 13:49:49 -0800 (PST) Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D67FB129524 for ; Sun, 10 Feb 2019 13:49:48 -0800 (PST) X-IronPort-AV: E=Sophos;i="5.58,356,1544482800"; d="scan'208,217";a="368776167" Received: from zcs-store2.inria.fr ([128.93.142.29]) by mail2-relais-roc.national.inria.fr with ESMTP; 10 Feb 2019 22:49:46 +0100 Date: Sun, 10 Feb 2019 22:49:46 +0100 (CET) From: Leo Perrin To: cfrg@irtf.org Message-ID: <47911132.8757406.1549835386894.JavaMail.zimbra@inria.fr> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="=_1e0344b1-bac1-4e72-99c3-eaca4caae44f" X-Originating-IP: [46.193.64.114] X-Mailer: Zimbra 8.7.11_GA_3706 (ZimbraWebClient - FF65 (Linux)/8.7.11_GA_3706) Thread-Index: M2cDHlAHTYJlvIzXfPp0nyBHxhmcpw== Thread-Topic: Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801) Archived-At: Subject: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801) X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 10 Feb 2019 21:49:52 -0000 --=_1e0344b1-bac1-4e72-99c3-eaca4caae44f Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Dear CFRG Participants,=20 My name is L=E9o Perrin, I am a post-doc in symmetric cryptography at Inria= , and I would like to bring recent results of mine to your attention. They = deal with the last two Russian standards in symmetric crypto, namely RFC 78= 01 (Kuznyechik, a block cipher) and RFC 6986 (Streebog, a hash function). M= y conclusion is that their designers purposefully used (and did not disclos= e) a very specific structure to build their S-box. The knowledge of this st= ructure demands a renewed analysis of their algorithms in its light. While = I do not have an attack at the moment, these results lead me to urge cautio= n about using these algorithms.=20 Let me summarize my results.=20 Both algorithms use the same 8-bit S-box, pi, which is only specified via i= ts lookup table. The designers never disclosed their rationale for their ch= oice and never disclosed the structure they used. I have managed to identif= y what I claim to be the structure purposefully used by its designers to co= nstruct pi. The corresponding paper was accepted at ToSC and is already on = eprint: [ https://eprint.iacr.org/2019/092 | https://eprint.iacr.org/2019/0= 92 ]=20 With my then colleagues from the university of Luxembourg, we previously fo= und two different structures in this component and published them a couple = years ago [1,2]. However, we were not satisfied with these results as the s= tructures we found were bulky and just plain weird. The one I just found is= much simpler and has both previous decompositions as side effects---in fac= t, we conjectured the existence of such a nicer structure in [2]. Much more= importantly, this new decomposition highlights some very specific (and, in= my opinion, worrying) properties of pi that were not known before.=20 In a nutshell, pi is actually defined over the finite field GF(2^8) in such= a way as to map multiplicative cosets of GF(2^4) to additive cosets of GF(= 2^4). Furthermore, the restriction of the permutation to each multiplicativ= e coset is always the same. Also, the linear layer of Streebog---specified = via a 64x64 binary matrix by its designers, including in RFC 6986---is in f= act an 8x8 matrix defined over GF(2^8) using the same irreducible polynomia= l as in the S-box. Thus, at least in the case of Streebog, both the linear = layer and the S-box interact in a highly structured way with two partitions= of GF(2^8) and one of those is its partition into additive cosets of the s= ubfield (this will be important later).=20 This situation is unlike anything else in the literature. For example, whil= e the inverse in GF(2^8) preserves the partition into multiplicative cosets= of GF(2^8), the AES designers composed it with an affine mapping breaking = the GF(2^8) structure. It is not the case here. On the other hand, Arnaud B= annier proved in his PhD (see also [3]) that an S-box preserving a partitio= n of the space into additive cosets in such a way that it interacts with th= e linear layer was necessary to build some specific backdoors.=20 Still, at the moment, I don't know of any attack leveraging my new decompos= ition as the partition in the input is the partition in multiplicative cose= ts (and not additive ones). Nevertheless, I can't think of a good reason fo= r the designers of these algorithms to use this structure and, worse, to ke= ep this fact secret; especially since the presence of such properties deman= ds a specific analysis to ensure that the algorithms are safe.=20 I felt I had to bring these results to the attention of the CFRG. If you ha= ve any questions I'd be happy to answer them!=20 Best regards,=20 /L=E9o Perrin=20 [1] Alex Biryukov, L=E9o Perrin, Aleksei Udovenko. "Reverse-Engineering the= S-Box of Streebog, Kuznyechik and STRIBOBr1". Eurocrypt'16, available onli= ne: https://eprint.iacr.org/2016/071=20 [2] L=E9o Perrin, Aleksei Udovenko. "Exponential S-Boxes: a Link Between th= e S-Boxes of BelT and Kuznyechik/Streebog ". ToSC'16. Available online: htt= ps://tosc.iacr.org/index.php/ToSC/article/view/567=20 [3] Arnaud Bannier, Nicolas Bodin, =C9ric Filiol. "Partition-based trapdoor= ciphers". https://eprint.iacr.org/2016/493=20 --=_1e0344b1-bac1-4e72-99c3-eaca4caae44f Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Dear CFRG Participants,

My name is L=E9o P= errin, I am a post-doc in symmetric cryptography at Inria, and I would like= to bring recent results of mine to your attention. They deal with the last= two Russian standards in symmetric crypto, namely RFC 7801 (Kuznyechik, a = block cipher) and RFC 6986 (Streebog, a hash function). My conclusion is th= at their designers purposefully used (and did not disclose) a very specific= structure to build their S-box. The knowledge of this structure demands a = renewed analysis of their algorithms in its light. While I do not have an a= ttack at the moment, these results lead me to urge caution about using thes= e algorithms.

= Let me summarize my results.

Both algorithms use the same 8-bit S-box, p= i, which is only specified via its lookup table. The designers never disclo= sed their rationale for their choice and never disclosed the structure they= used. I have managed to identify what I claim to be the structure purposef= ully used by its designers to construct pi. The corresponding paper was acc= epted at ToSC and is already on eprint: https://eprint.iacr.org/2019/092
With my then colleagues from the university of Luxembourg, we = previously found two different structures in this component and published t= hem a couple years ago [1,2]. However, we were not satisfied with these res= ults as the structures we found were bulky and just plain weird. The one I = just found is much simpler and has both previous decompositions as side eff= ects---in fact, we conjectured the existence of such a nicer structure in [= 2]. Much more importantly, this new decomposition highlights some very spec= ific (and, in my opinion, worrying) properties of pi that were not known be= fore.

In a nutshell, pi is actually defined over the finite field GF(2^8) in su= ch a way as to map multiplicative cosets of GF(2^4) to additive cosets of G= F(2^4). Furthermore, the restriction of the permutation to each multiplicat= ive coset is always the same. Also, the linear layer of Streebog---specifie= d via a 64x64 binary matrix by its designers, including in RFC 6986---is in= fact an 8x8 matrix defined over GF(2^8) using the same irreducible polynom= ial as in the S-box. Thus, at least in the case of Streebog, both the linea= r layer and the S-box interact in a highly structured way with two partitio= ns of GF(2^8) and one of those is its partition into additive cosets of the= subfield (this will be important later).

This situation is unlike anything else in the literature.= For example, while the inverse in GF(2^8) preserves the partition into mul= tiplicative cosets of GF(2^8), the AES designers composed it with an affine= mapping breaking the GF(2^8) structure. It is not the case here. On the ot= her hand, Arnaud Bannier proved in his PhD (see also [3]) that an S-box pre= serving a partition of the space into additive cosets in such a way that it= interacts with the linear layer was necessary to build some specific backd= oors.

Still, at the mom= ent, I don't know of any attack leveraging my new decomposition as the part= ition in the input is the partition in multiplicative cosets (and not addit= ive ones). Nevertheless, I can't think of a good reason for the designers o= f these algorithms to use this structure and, worse, to keep this fact secr= et; especially since the presence of such properties demands a specific ana= lysis to ensure that the algorithms are safe.

I felt= I had to bring these results to the attention of the CFRG. If you have any= questions I'd be happy to answer them!

=
Best regards,
/L=E9o Perrin

[1] A= lex Biryukov, L=E9o Perrin, Aleksei Udovenko. "Reverse-Engineering the S-Bo= x of Streebog, Kuznyechik and STRIBOBr1". Eurocrypt'16, available online: h= ttps://eprint.iacr.org/2016/071
[2] L=E9= o Perrin, Aleksei Udovenko. "Exponential S-Boxes: a Link Between the S-Boxe= s of BelT and Kuznyechik/Streebog ". ToSC'16. Available online: https://tos= c.iacr.org/index.php/ToSC/article/view/567
[3] Arnaud Bannier, Nicolas Bodin, =C9ric Filiol. "Partition-based trapd= oor ciphers". https://eprint.iacr.org/2016/493
--=_1e0344b1-bac1-4e72-99c3-eaca4caae44f--