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 D919B12D826 for ; Tue, 12 Feb 2019 03:55:34 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.01 X-Spam-Level: X-Spam-Status: No, score=-0.01 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com 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 LkHHIvSZjC6A for ; Tue, 12 Feb 2019 03:55:32 -0800 (PST) Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E6879124C04 for ; Tue, 12 Feb 2019 03:55:31 -0800 (PST) Received: by mail-qt1-x82c.google.com with SMTP id v10so2523384qtp.8 for ; Tue, 12 Feb 2019 03:55:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=oc+FrI59UQjkTKpdeR6czBPlaSdSaoP6kz47S5oBDwY=; b=lcP0nDcTBeVBjJio2tD0oQ7g9P3ihkFA5WQYf9LPikO/pJ9LIrrNElTV2wUontIPu5 K3jClBC03q54yLEAEFo2KDUL4m9+xnsQ6/+G6Td/H6ETbJogr9tAilM2IWXUS9slUilF 6UnKiPFXxjml+5B8tiGB+HFwYgOWQmjkBEBbXRXw6kbzacUA894Mj7zbGvSafzFCt7H8 9lewj3ngqy0iK+YuMcCCswitsO1fGmnMVa2J2IapI//eVf+IlMrSAYP+FGUbb3nGIamR mYZ1VbSAKWtYKFHnFAC+JjnTLcbJikhk+WoI3r18aMfG/3WwGrR/aySbmP2+EoE2OH1O 9p9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=oc+FrI59UQjkTKpdeR6czBPlaSdSaoP6kz47S5oBDwY=; b=XoooQ6xW7AefrnJ+jYyXN/x0AoV4s8WEow0zAwX/irTf6fWB7oRXMTCnXgqCVUnd5l kEf7NlM+fJgRzsAuXp7TvB74935HQtc2sakg6FCfeQJXvoYsf0kA3V6yH1GCgjO3j2L7 olc3gczY04gUTUduQdhZXz48KWnn8FugaX+oOL6WDi6MYPO6SgKAzF+pDkubxQ/pTSZX 1z8TeCUGHg/5RyAD8O+E/pXZ/5C+G9XrVT+nkm36XKM1mLp5rseA5474lrV7raH0KNYh vwH3hLvhvwDuJRvl0ycliamSHwTUwBtGSAwSae7hVzE1X9hBb31rKfVq6fvAJzZDMaeH 4F0A== X-Gm-Message-State: AHQUAub3Q5d9z7dBGEv9wOP0fvGtbM0+EK8aslNsOLal4mwCHKuZ5Uof At2uCUmvcYQ7V+69xx3wwwciVLhIMLCbUhkH4Ho= X-Google-Smtp-Source: AHgI3IYPGotfBhEeNYzf4wJEvnD6lvyUzx62UnVLbDFNfigwK5VOnGGPDFU70565b1AGuZpeLTx5bEtX2Kp4sD+9Ebs= X-Received: by 2002:a0c:a5a2:: with SMTP id z31mr2365621qvz.108.1549972530732; Tue, 12 Feb 2019 03:55:30 -0800 (PST) MIME-Version: 1.0 References: <47911132.8757406.1549835386894.JavaMail.zimbra@inria.fr> <1CE71837-B6F4-4A55-9B1B-21053E6ABD97@usfca.edu> In-Reply-To: <1CE71837-B6F4-4A55-9B1B-21053E6ABD97@usfca.edu> From: Dmitry Khovratovich Date: Tue, 12 Feb 2019 12:55:17 +0100 Message-ID: To: Paul Lambert Cc: Leo Perrin , cfrg@irtf.org Content-Type: multipart/alternative; boundary="0000000000001b2a1c0581b11a05" Archived-At: Subject: Re: [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: Tue, 12 Feb 2019 11:55:35 -0000 --0000000000001b2a1c0581b11a05 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Even more interesting is that the Belorussian Sbox has the same nonlinearity value of 102, despite all the differences introduced by Russians. On Tue, Feb 12, 2019 at 2:16 AM Paul Lambert wrote: > > Hi Leo, > > > On Feb 10, 2019, at 1:49 PM, Leo Perrin wrote: > > Dear CFRG Participants, > > My name is L=C3=A9o 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 > 7801 (Kuznyechik, a block cipher) and RFC 6986 (Streebog, a hash function= ). > My conclusion is that their designers purposefully used (and did not > disclose) a very specific structure to build their S-box. The knowledge o= f > this structure demands a renewed analysis of their algorithms in its ligh= t. > While I do not have an attack at the moment, these results lead me to urg= e > caution about using these algorithms. > > Let me summarize my results. > > Both algorithms use the same 8-bit S-box, pi, which is only specified via > its lookup table. The designers never disclosed their rationale for their > choice and never disclosed the structure they used. I have managed to > identify what I claim to be the structure purposefully used by its > designers to construct pi. The corresponding paper was accepted at ToSC a= nd > 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 them a > couple years ago [1,2]. However, we were not satisfied with these results > as the structures we found were bulky and just plain weird. The one I jus= t > found is much simpler and has both previous decompositions as side > effects---in fact, we conjectured the existence of such a nicer structure > in [2]. Much more importantly, this new decomposition highlights some ver= y > specific (and, in my opinion, worrying) properties of pi that were not > known before. > > 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 > multiplicative coset is always the same. Also, the linear layer of > Streebog---specified via a 64x64 binary matrix by its designers, includin= g > in RFC 6986---is in fact an 8x8 matrix defined over GF(2^8) using the sam= e > irreducible polynomial 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 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 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 han= d, > Arnaud Bannier proved in his PhD (see also [3]) that an S-box preserving = a > partition of the space into additive cosets in such a way that it interac= ts > with the linear layer was necessary to build some specific backdoors. > > Still, at the moment, I don't know of any attack leveraging my new > decomposition as the partition in the input is the partition in > multiplicative cosets (and not additive ones). Nevertheless, I can't thin= k > of a good reason for the designers of these algorithms to use this > structure and, worse, to keep this fact secret; especially since the > presence of such properties demands a specific analysis to ensure that th= e > 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! > > > Interesting work =E2=80=A6 looking at the walsh function based non-linear= ity of > Streebog, it is non-optimal (compared to AES and SMS4): > AES non-linearity (min, max) =3D (112.0, 112.0) > sms4 non-linearity (min, max) =3D (112.0, 112.0) > Streebog non-linearity (min, max) =3D (102.0, 110.0) > > This was using: > https://github.com/nymble/cryptopy/blob/master/analysis/sbox_nonlinearity= .py > > > Paul > > > > Best regards, > /L=C3=A9o Perrin > > [1] Alex Biryukov, L=C3=A9o Perrin, Aleksei Udovenko. "Reverse-Engineerin= g the > S-Box of Streebog, Kuznyechik and STRIBOBr1". Eurocrypt'16, available > online: https://eprint.iacr.org/2016/071 > [2] L=C3=A9o Perrin, Aleksei Udovenko. "Exponential S-Boxes: a Link Betwe= en the > S-Boxes of BelT and Kuznyechik/Streebog ". ToSC'16. Available online: > https://tosc.iacr.org/index.php/ToSC/article/view/567 > [3] Arnaud Bannier, Nicolas Bodin, =C3=89ric Filiol. "Partition-based tra= pdoor > ciphers". https://eprint.iacr.org/2016/493 > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > > https://urldefense.proofpoint.com/v2/url?u=3Dhttps-3A__www.irtf..org_mail= man_listinfo_cfrg&d=3DDwICAg&c=3DqgVugHHq3rzouXkEXdxBNQ&r=3DoIg4FfS8P761Blh= MPJ2ys3IvSyH4XQ12Mbj_mXrCAJs&m=3DS0H637y57cjgJ_W4QG8e2TIQ0lLL3cDdmc5Lf8_Mxf= I&s=3DCbZRt6CVbiJLCAXEFyRawO2y5_gU6tsBtlsT9gxbQ14&e=3D > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > --=20 Best regards, Dmitry Khovratovich --0000000000001b2a1c0581b11a05 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Even more interesting is that the Belorussian Sbox has the= same nonlinearity value of 102, despite all the differences introduced by = Russians.

On Tue, Feb 12, 2019 at 2:16 AM Paul Lambert <plambert@usfca.edu> wrote:

Hi Leo,


On Feb 10, 2019, at 1:49 PM, Leo Perrin <leo.perrin@inria.fr> wrote:

D= ear CFRG Participants,

My name is L=C3=A9o Per= rin, I am a post-doc in symmetric cryptography at Inria, and I would like t= o bring recent results of mine to your attention. They deal with the last t= wo Russian standards in symmetric crypto, namely RFC 7801 (Kuznyechik, a bl= ock cipher) and RFC 6986 (Streebog, a hash function). My conclusion is that= their designers purposefully used (and did not disclose) a very specific s= tructure to build their S-box. The knowledge of this structure demands a re= newed analysis of their algorithms in its light. While I do not have an att= ack at the moment, these results lead me to urge caution about using these = algorithms.

Let me summarize my re= sults.

Both algorithms use the same 8-bit S= -box, pi, which is only specified via its lookup table. The designers never= disclosed their rationale for their choice and never disclosed the structu= re they used. I have managed to identify what I claim to be the structure p= urposefully used by its designers to construct pi. The corresponding paper = was accepted at ToSC and is already on eprint: https://eprint.iacr.org/2019/092

With my then colleagues from the university of Luxembourg, we previ= ously found 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 structures 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 fact, we conjectured the existence of such a nicer structure in [2]. M= uch more importantly, this new decomposition highlights some very specific = (and, in my opinion, worrying) properties of pi that were not known before.=

In a nutshell, pi is actually defined over th= e 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 per= mutation to each multiplicative coset is always the same. Also, the linear = layer of Streebog---specified via a 64x64 binary matrix by its designers, i= ncluding in RFC 6986---is in fact an 8x8 matrix defined over GF(2^8) using = the same irreducible polynomial 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 stru= ctured way with two partitions 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 liter= ature. For example, while the inverse in GF(2^8) preserves the partition in= to 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 Bannier proved in his PhD (see also [3]) that an S-b= ox preserving a partition of the space into additive cosets in such a way t= hat it interacts with the linear layer was necessary to build some specific= backdoors.

Still, at the moment, I don'= t know of any attack leveraging my new decomposition as the partition in th= e input is the partition in multiplicative cosets (and not additive ones). = Nevertheless, I can't think of a good reason for the designers of these= algorithms to use this structure and, worse, to keep this fact secret; esp= ecially since the presence of such properties demands a specific analysis t= o ensure that the algorithms are safe.

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

Interesting work =E2=80=A6 looking at the walsh function= based non-linearity of Streebog, it is non-optimal (compared to AES and SM= S4):
AES non-linearity=C2=A0=C2=A0(min, max= ) =3D=C2=A0=C2=A0(112.0, 112.0)
sms4 non-linearity= (min, max) =3D=C2=A0=C2=A0(112.0, 112.0)
Streebog= non-linearity=C2=A0=C2=A0(min, max) =3D=C2=A0=C2=A0(102.0, 110.0)


Paul



Best regards,
/= L=C3=A9o Perrin

[1] Alex Biryukov, L=C3=A9o Pe= rrin, Aleksei Udovenko. "Reverse-Engineering the S-Box of Streebog, Ku= znyechik and STRIBOBr1". Eurocrypt'16, available online: https://eprint.iacr= .org/2016/071
[2] L=C3=A9o Perrin, Aleksei Udovenko. &quo= t;Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/St= reebog ". ToSC'16. Available online: https://tosc.iacr.or= g/index.php/ToSC/article/view/567
[3] Arnaud Bannier, Nic= olas Bodin, =C3=89ric Filiol. "Partition-based trapdoor ciphers".= https://epr= int.iacr.org/2016/493
______________________= _________________________
Cfrg mailing list
Cfrg@irtf.org
https://urldefense.proofpoint.com/v2/url?u=3Dhttps-3A__www.irtf..org_ma= ilman_listinfo_cfrg&d=3DDwICAg&c=3DqgVugHHq3rzouXkEXdxBNQ&r=3Do= Ig4FfS8P761BlhMPJ2ys3IvSyH4XQ12Mbj_mXrCAJs&m=3DS0H637y57cjgJ_W4QG8e2TIQ= 0lLL3cDdmc5Lf8_MxfI&s=3DCbZRt6CVbiJLCAXEFyRawO2y5_gU6tsBtlsT9gxbQ14&= ;e=3D

_____________________= __________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg


--
Best regards,
Dmitry Khovratovich=
--0000000000001b2a1c0581b11a05--