Re: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801)

Dmitry Khovratovich <> Tue, 12 February 2019 11:55 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D919B12D826 for <>; Tue, 12 Feb 2019 03:55:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.01
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id LkHHIvSZjC6A for <>; Tue, 12 Feb 2019 03:55:32 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::82c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E6879124C04 for <>; Tue, 12 Feb 2019 03:55:31 -0800 (PST)
Received: by 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;; 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;; 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: <> <>
In-Reply-To: <>
From: Dmitry Khovratovich <>
Date: Tue, 12 Feb 2019 12:55:17 +0100
Message-ID: <>
To: Paul Lambert <>
Cc: Leo Perrin <>,
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-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

Even more interesting is that the Belorussian Sbox has the same
nonlinearity value of 102, despite all the differences introduced by

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éo 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 of
> this structure 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
> 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 and
> is already on eprint:
> <>
> 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 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]. Much 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 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, including
> 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
> 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 hand,
> 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 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 the 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; especially since the
> presence of such properties demands a specific analysis 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!
> Interesting work … looking at the walsh function based non-linearity of
> Streebog, it is non-optimal (compared to AES and SMS4):
> AES non-linearity  (min, max) =  (112.0, 112.0)
> sms4 non-linearity (min, max) =  (112.0, 112.0)
> Streebog non-linearity  (min, max) =  (102.0, 110.0)
> This was using:
> Paul
> Best regards,
> /Léo Perrin
> [1] Alex Biryukov, Léo Perrin, Aleksei Udovenko. "Reverse-Engineering the
> S-Box of Streebog, Kuznyechik and STRIBOBr1". Eurocrypt'16, available
> online:
> [2] Léo Perrin, Aleksei Udovenko. "Exponential S-Boxes: a Link Between the
> S-Boxes of BelT and Kuznyechik/Streebog ". ToSC'16. Available online:
> [3] Arnaud Bannier, Nicolas Bodin, Éric Filiol. "Partition-based trapdoor
> ciphers".
> _______________________________________________
> Cfrg mailing list
> _______________________________________________
> Cfrg mailing list

Best regards,
Dmitry Khovratovich