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

Dmitry Belyavsky <beldmit@gmail.com> Mon, 05 August 2019 19:05 UTC

Return-Path: <beldmit@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 87D8B120152 for <cfrg@ietfa.amsl.com>; Mon, 5 Aug 2019 12:05:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 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, URIBL_BLOCKED=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 2g1R2OWQmMGx for <cfrg@ietfa.amsl.com>; Mon, 5 Aug 2019 12:05:30 -0700 (PDT)
Received: from mail-vs1-xe31.google.com (mail-vs1-xe31.google.com [IPv6:2607:f8b0:4864:20::e31]) (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 D25F81202F7 for <cfrg@irtf.org>; Mon, 5 Aug 2019 12:05:29 -0700 (PDT)
Received: by mail-vs1-xe31.google.com with SMTP id h28so56646649vsl.12 for <cfrg@irtf.org>; Mon, 05 Aug 2019 12:05:29 -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=Fhqj4NDOJdjieHYda9ZUpBdPyRO/cEILG1KLVqdiY3A=; b=HFqCtVvNfx8q5/mPdurgVUnCHKmlNCFxZOWJOLdNRjukD0LdpTmsEImb9Jap2yXe5j dXBxX7vdJ7NdtVE5XVLtlDJkxzE5SFFsNisWHORJppHTKOKqW1CJ21t/mrN4eRURomiM dOm719oj3KCICXDFwI2nJwrMQTlH38Nk6jbrFX8XH6/y4eoNiLhr34ES5wIJ/NE4twir ZyeCsAvaL3LMiP/ORyPI58C43+nlqZvTWr/e31uEk1OfIprPF5oxCtWA9O/dELpz0Yhu N9yOe5uCudAkLbRZKSalQ4gm6Qfy3/sD1SBxagC+kdJ8JrhyvwjMz2MdebJyLXP50zox 1NpQ==
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=Fhqj4NDOJdjieHYda9ZUpBdPyRO/cEILG1KLVqdiY3A=; b=Zb7djGWl4ycWyiCJ/mLc76qmonr1wPCXc9WMSuom1ISdeLA6s6fvxT3s9SppHFxmPN RZbYL4/zFnzqLPVE0NnSCTm1WuZj/j1KSAC2eQKcgbD5yWvPJfjejQAUkE/wX1k7aR4Z AdaPjTnCKVmOvdAGAHR3NNifTwl4EJxvWAAd2Zap+yMFnif52o57OhZLeZN46JxuEGN+ 3yS7LOoB9Y82EZ2uJze5GMXh/XLotinmARmF1e3bFisuZlFCY4ESnM+TBlqLnTPpv90O aASmhiQCnM3mii3RpSPXH1Nxd6g0Ciwutnnj+kfkySxtbiTfk5+hJCIWbGkh7ONWhxTn l6FQ==
X-Gm-Message-State: APjAAAW46AdlXPTdCvtXKM23FaPFwjOX6/WoMdy5yi9Jt0Vl5hk18UtY Ror+V0x/UjDuWpoo2sOP9xkikHKsT48OI4JkjNc2l7h/hek=
X-Google-Smtp-Source: APXvYqx0ub8+htsvr/m1FfEV3JU350nwlINQwByMGXujy9sP3d02Wo8wL1DQmFql9UI7A0nq4TNb3JHsTDxD9gDTKMU=
X-Received: by 2002:a67:cfc2:: with SMTP id h2mr94784646vsm.30.1565031928590; Mon, 05 Aug 2019 12:05:28 -0700 (PDT)
MIME-Version: 1.0
References: <1327417226.25659372.1565019306532.JavaMail.zimbra@inria.fr>
In-Reply-To: <1327417226.25659372.1565019306532.JavaMail.zimbra@inria.fr>
From: Dmitry Belyavsky <beldmit@gmail.com>
Date: Mon, 5 Aug 2019 22:05:17 +0300
Message-ID: <CADqLbz+2dbvxdaGKp_3XMprp4XMxDK=B=1GKCLmxkjThX9kPYg@mail.gmail.com>
To: Leo Perrin <leo.perrin@inria.fr>
Cc: cfrg <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000002a75ee058f6364d2"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/pRYcKWc_sPekvTZPqPJlMW--zWY>
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: Mon, 05 Aug 2019 19:05:44 -0000

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
> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>


-- 
SY, Dmitry Belyavsky