### Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and Kuznyechik

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Tue, 06 August 2019 13:14 UTC

Return-Path: <smyshsv@gmail.com>

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 53F5A120191
for <cfrg@ietfa.amsl.com>; Tue, 6 Aug 2019 06:14:24 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.998

X-Spam-Level:

X-Spam-Status: No, score=-1.998 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,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, 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 TMH51zoMWuTW for <cfrg@ietfa.amsl.com>;
Tue, 6 Aug 2019 06:14:21 -0700 (PDT)

Received: from mail-lj1-x231.google.com (mail-lj1-x231.google.com
[IPv6:2a00:1450:4864:20::231])
(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 1FEB9120182
for <cfrg@irtf.org>; Tue, 6 Aug 2019 06:14:21 -0700 (PDT)

Received: by mail-lj1-x231.google.com with SMTP id d24so82193607ljg.8
for <cfrg@irtf.org>; Tue, 06 Aug 2019 06:14:21 -0700 (PDT)

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=QplEwc3nqdNyqYEwNqbNomBcEpCUnZ/V8du0ZuQ9UlI=;
b=AlxBrHgIfBiclKmqSNTmWyEbyMimZIB2KXidCgmCfAMKqCmUqR7prb/n3WO3RJnub7
xkjHb0h1ynEilahLlNQi1/wWRTnshlTNLZfnE+5ZIuPuoywqGHp7QTErGh+z3M831Rqy
saov40eiZM6N6k9tQnmwoh/ek+40vWtuUL4FZOiAFtI45W5IXfjqk3FgaX4X8ddY/KYF
2mEoRCpTcgu7PVu4NCvI9nTzUbKCwqO5E//FYgPjTGjheUPsKV5saP023/XGOqIFFJcC
/CKIhahlpR8v4X6ojAJJ1CQ2ynV60FttXJvAZjJz29Q8ZlxfUsHMEfdlK/XiMdAxt0Em
+Jkw==

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=QplEwc3nqdNyqYEwNqbNomBcEpCUnZ/V8du0ZuQ9UlI=;
b=b59GMqHnkJ5EKCLmh/W962n8AIBr7QVivldUNDB9AuEv9/WG/cwplVMkbAzJHZ6R5x
lEFQMDeGbGizx8jrLKa6Bb4iPEL7bHTGs/iWy0AW1B6UMEcsXSq1eOJzUZYxQ23tM/kv
YgfpgFlcWnZwrKyc+0rkVWRhULfmGbQkhnkSpv+El/mxExNbz4IhJtEyaVIduxXoPi80
TXG3BHPHhp+U0PkqbFaFGXXEM3uirtgXcVSnPJkCELKpq7wTI3eqMhtIfegSC5YnDFpG
NQMtA2DzZMVV4VILC9y2dAS39H/sxnteqJMe+gBe/jlP8fnMnB07umQc/m59JTEZHeSe
Lh8g==

X-Gm-Message-State: APjAAAUBt660DK1Hsvtibe3QWWkeWJEapKcz1+RE11pOPK4YngxUq7BS
XN7i4LKwzbahfPlCX1kd8WuqetlAOYItcWt6KQU=

X-Google-Smtp-Source: APXvYqyc8tMl4YuQIi7RAB0rJHAYqd4PcVfl6frGJDkNmWCxyfpZcuTT5g48MeAOOwk7omG0GsBvb35YNmco/JifhXc=

X-Received: by 2002:a2e:98d7:: with SMTP id s23mr1744578ljj.179.1565097259089;
Tue, 06 Aug 2019 06:14:19 -0700 (PDT)

MIME-Version: 1.0

References: <1327417226.25659372.1565019306532.JavaMail.zimbra@inria.fr>
<CADqLbz+2dbvxdaGKp_3XMprp4XMxDK=B=1GKCLmxkjThX9kPYg@mail.gmail.com>

In-Reply-To: <CADqLbz+2dbvxdaGKp_3XMprp4XMxDK=B=1GKCLmxkjThX9kPYg@mail.gmail.com>

From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>

Date: Tue, 6 Aug 2019 16:14:43 +0300

Message-ID: <CAMr0u6kGAPRoS70uqqOPJzv30tBR0pgMKLSrBO0eksWrB5Pi8w@mail.gmail.com>

To: Leo Perrin <leo.perrin@inria.fr>,
Stephen Farrell <stephen.farrell@cs.tcd.ie>

Cc: cfrg <cfrg@irtf.org>, Dmitry Belyavsky <beldmit@gmail.com>

Content-Type: multipart/alternative; boundary="0000000000002ac7da058f729a17"

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/C5S7LmI7foZh71kt126OX36q_rY>

Subject: Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and
Kuznyechik

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Tue, 06 Aug 2019 13:14:24 -0000

Dear Stephen and Leo, >> Does the structure you've discovered also exist in GOST R 34.11-94? Stephen, GOST R 34.11-94 is built using a completely different construction, so (Leo will correct me, if I am mistaken) the discovered properties are not related to GOST R 34.11-94. I’d also like to clarify that this GOST R 34.11-94 is an old hash function, which has been deprecated for about 7 years in Russia. >> In general I would support CFRG deprecating any algorithms for which there is significant doubt. I have not myself verified that the structure Leo has found is real… First of all, I’d like to express my sincere appreciation to Leo for his deep study of Streebog/Kuznyechik S-Box properties. I am not a designer of those algorithms, but my company (software development: digital signature servers, VPN solutions etc.) uses them in those software products which are intended for usage with governmental applications inside Russia (they must be used for such applications). Hence, I am definitely interested in having as much research of those algorithms as possible: they are obviously worth being studied. Leo’s results about structures of those S-Boxes are very interesting and important for understanding the properties of the algorithms themselves and for optimization of their implementations (which is interesting for all software developers implementing them). I sincerely wish that Leo continues your research – Leo, please continue this study, you’re doing a great work. Leo has discovered a very interesting property of the S-Boxes, a very curious structure of representing them, but there is a certain contrast between high level of the Leo’s scientific part of work and the lack of ground (so far, at least) for conclusions and accusations about possible vulnerabilities in the algorithms. At the CFRG session in Montreal there was a discussion on this issue, it is important to continue the research when some new properties are found in any crypto, but we can’t “deprecate” something deployed (at least, there are many cases when they are used in Russian part of Internet) “just in case”, just because there are some new properties found (without any results of how they could lead to a vulnerability or to a backdoor, despite the fact that Leo has obviously been working on finding such for at least one year). If Leo had a result like Ferguson and Shumow in 2007 ( https://rump2007.cr.yp.to/15-shumow.pdf, when they showed that the knowledge of certain parameter – discrete logarithm in that case – allows to mount an attack on predicting Dual EC DRBG outputs with low complexity), then, of course, it would be definitely a reason for significant doubts in those algorithms (and, particularly, for an I-D about the found attacks) – in international and national organizations and technical committees. But, as Leo stresses himself, he does not have any (even preliminary) results of this kind. During the discussion at the CFRG session Leo claimed that he stressed in his papers explicitly, that he hasn’t found any methods for mounting the attacks or conditional results like “if the designers know a certain parameter X, then they can mount the following attack”. Leo, many thanks for that clarification of yours; you’ve been absolutely honest, I’ve found this in your papers: *- “Kuznyechik seems to be in the second situation [although the S-Box and linear layer are defined over similar structures, a small function was added with the explicit purpose of breaking this similarity (case of the AES and the affine permutation used in its S-Box]”* *- “Open Problem 1. Is there a way to leverage the partition-preserving property of 𝜋 to mount an attack against Streebog?“* Once more, Leo, your research is extremely interesting – I personally ask you to continue. But it will be correct to underline that currently it’s only an ongoing research, without any reasons for statements about backdoors/vulnerabilities. Best regards, Stanislav пн, 5 авг. 2019 г. в 22:07, Dmitry Belyavsky <beldmit@gmail.com>;: > Dear Leo, dear CFRG members, > > Many thanks for your efforts in analysis of Russian GOST crypto > algorithms. > I am not a cryptographer myself, but one of the implementors of Russian > cryptography. > > On Mon, Aug 5, 2019 at 6:35 PM Leo Perrin <leo.perrin@inria.fr>; wrote: > >> Dear CFRG members, >> >> I would like to follow up on the short talk I gave several days ago. That >> talk was itself a follow-up to a previous e-mail [0] which presented a >> strange structure I found in pi, a component (S-box) which is shared by >> both Streebog (RFC 6986) and Kuznyechik (RFC 7801). >> At the time of writing this previous e-mail, I did not know that the >> designers of these algorithms were still claiming that they had generated >> their S-box randomly. However, they do! Here are links to relevant ISO >> documents that were leaked: >> - https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf >> - >> https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog..pdf >> <https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf> >> As we can see in the first one, the designers of pi did claim that they >> obtained this component by generating many random S-boxes and then choosing >> the best according to some (fair and usual) criteria. In fact, as we can >> see in the second, they insisted that they used this method even *after* >> the publication of my latest results [1]. >> >> That is hardly possible. Let us see why. >> >> There are 2^{L+1}-1 bitstrings of length at most L. Thus, the total >> number of permutations with an implementation fitting in at most L bits in >> a given language (e.g. in C) is upper bounded by 2^{L+1}. The shortest >> implementation of pi in C we are aware of was found by ceilingcat [2] who >> improved a previous implementation by Xavier Bonnetain. That implementation >> is 139 ASCII characters long, i.e. 973 bits long. Thus, there are fewer >> than 2^{974} permutations with an implementation this simple. As there are >> 256! = 2^{1684} permutations operating on 8 bits, we easily conclude that >> the probability that a random permutation has a C implementation at most >> 973 bits long is smaller than 2^{974-1684} = 2^{-710}, which is beyond >> negligible. If we look at languages more compact than C (see [2]) then we >> can deduce even lower probabilities. In other words, the set of the >> permutations as simple as pi for a very broad definition of simplicity is >> extremely small, and thus the probability that we fall into it by chance is >> negligible. More detailed explanations are available at [3]. >> >> In light of this argument, only two possibilities are left: >> 1.. the designers of pi really used a random process to generate their >> S-box, they were just lucky enough to find one of the very (very very very) >> few permutations with a short implementation, or >> 2. they used a TKlog deliberately but decided to hide it, the TKlog being >> the structure I identified in [1]. >> The probability that the first one is true can be upper bounded using the >> discussion above: it is at most 2^{-710}. For comparison, there are about >> 10^80 = 2^266 atoms in the universe. The only reasonable conclusion is then >> that we are in the second case: the use of the TKlog is a deliberate choice >> by its designers. Note that this reasoning is based purely on the >> simplicity of the TKlog structure. It does not take into account its very >> peculiar interactions with the finite field, nor does it consider the fact >> that the finite field used to define it is the same as the one used in the >> linear layer of Streebog. It is also unlikely that the differential and >> linear properties of pi can be encountered in a feasibly large set of >> random S-boxes [4]. >> >> Because of these observations, I insist that the designers of these >> algorithms have provided cryptanalysts with misleading information. There >> cannot be any good reason for this, which is why I think these algorithms >> cannot be trusted, and thus that RFC 6986 and 7801 should be deprecated. >> >> Cheers, >> >> /Léo >> >> PS: Remember that the golfed implementations listed in [2] are only >> intended to be small. They are *not* intended to be secure! Their running >> time in CPU cycles is directly proportionnal to the discrete logarithm of >> their input, meaning that they are the opposite of constant time. An >> implementation using them would be trivially vulnerable to some side >> channel attacks. >> > > You say that you have arguments that the designers may have said > controversial declarations about some details of the construction in the > ISO, but this doesn’t seem to correspond to attack. > > Could you please clarify how does the existence of a compact code for > generation of the S-box imply a possibility of attack? > > Currently, I don't see even a performance optimization as a consequence of > the compact representation of the S-box. > The most widespread open-source implementation ( > https://github.com/gost-engine/engine/tree/openssl_1_1_0) > of Streebog and Kuznyechik does not use the Pi transformations as a > separate step — they use a combined process. > > >> [0] >> https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg?fbclid=IwAR3JIGXt1_6aFwNOjDb-p7oC3ezHRuEEreznt-atyY7Clah2QZU_uU7FKS8 >> [1] https://tosc.iacr.org/index.php/ToSC/article/view/7405 >> [2] >> https://codegolf.stackexchange.com/questions/186498/proving-that-a-russian-cryptographic-standard-is-too-structured >> [3] https://who.rocq.inria.fr/Leo.Perrin/code-golf.html >> <https://who.rocq.inria.fr/Leo.Perrin/code-golf..html> >> [4] https://eprint.iacr.org/2019/528 <https://eprint..iacr.org/2019/528> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> https://www.irtf.org/mailman/listinfo/cfrg >> > > > -- > SY, Dmitry Belyavsky > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >

- [Cfrg] On the (non-)randomness of the S-box of ... Leo Perrin
- Re: [Cfrg] On the (non-)randomness of the S-box... Stephen Farrell
- Re: [Cfrg] On the (non-)randomness of the S-box... Dmitry Belyavsky
- Re: [Cfrg] On the (non-)randomness of the S-box... Stanislav V. Smyshlyaev
- Re: [Cfrg] On the (non-)randomness of the S-box... Stephen Farrell
- Re: [Cfrg] On the (non-)randomness of the S-box... Stanislav V. Smyshlyaev
- Re: [Cfrg] On the (non-)randomness of the S-box... Dmitry Belyavsky
- Re: [Cfrg] On the (non-)randomness of the S-box... Stephen Farrell
- Re: [Cfrg] On the (non-)randomness of the S-box... Dmitry Belyavsky
- Re: [Cfrg] On the (non-)randomness of the S-box... Stephen Farrell
- Re: [Cfrg] On the (non-)randomness of the S-box... Jonathan Hoyland
- Re: [Cfrg] On the (non-)randomness of the S-box... Stanislav V. Smyshlyaev
- Re: [Cfrg] On the (non-)randomness of the S-box... Leo Perrin