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

Paul Lambert <> Tue, 12 February 2019 01:16 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 427D51293B1 for <>; Mon, 11 Feb 2019 17:16:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.612
X-Spam-Status: No, score=-0.612 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_LOW=-0.7, 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 BcayBxm6fYdG for <>; Mon, 11 Feb 2019 17:16:10 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 3A7751276D0 for <>; Mon, 11 Feb 2019 17:16:10 -0800 (PST)
Received: from pps.filterd ( []) by ( with SMTP id x1C1FR6i022174 for <>; Mon, 11 Feb 2019 17:16:10 -0800
Received: from ( []) by with ESMTP id 2qkfyw9j15-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for <>; Mon, 11 Feb 2019 17:16:09 -0800
Received: by with SMTP id y2so787693plr.8 for <>; Mon, 11 Feb 2019 17:16:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=sTJdVMMMmGuF2r4ZOCnUpDxOble6SmBcXQ77Oj9Ac8U=; b=qXVO44YZHdZuaIAwFbr2Muyalh3zspWaU34Cmvwdb6BclgsonqBSOn9rZL8uWQSTHv y/TgpSXa8zrrQuGt3Kvp0uCqirE8h8NZan6h3CcdwptXHYu8GY0uwCI/UpYBxTdBaw3c dmlUW4yC7Tw0XkoLrK5dZPFmpGWydWTqMVMm/qR8s4uo9IL+VfaomtPnE7uj3m5huRWo CveHPBMo1cs41/dogY5fvcDeKa9p5SwDcpBkZqDKBIAH4oIDPSMaszfFzbXjg9lX0r/Z Avlu+8u1bn2z19gPLgvAwP4i9RpD0IXDzy9IFk15Yw1s/vfIFLg3dCtvD6qQ46Bvturm Jyyw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=sTJdVMMMmGuF2r4ZOCnUpDxOble6SmBcXQ77Oj9Ac8U=; b=HbQad+jrWeOkfPjjgufeZwcRFtfDyRKg4sKZYBR0dIZN6rlKYRgXPiI1uPu1sLhn7o YQK1619RXn1IXv0QU4pWwI7gGnK/1+ZLZ3SEbZFiZnQCxr7nHYuFIRtLxvxUl4gWNxFA NPM4pqgbgQ9jOSOXbP3LhSmW4pwhCQNI9XwD2NA8OpFZrYS21dmgugSCiBGyHw2KoH5B ktKh2p6Bb+y2g82k6ULx9k4kmcUiwh+jDYKJWVXWK9eAN2iCKqA7SUEcJE1DglvOM7+r g95CuzdbdSvsk1yYQfpAbXbiirIIaNhwxQ/f1KNkOEbJQVUJBusrMdZorCzCUItxZSbC LQCA==
X-Gm-Message-State: AHQUAua4/TxWjhkcEMXwsHAQ0bCKwo1Lq+xM0wKqlZiBA1PEDhf/9BSU 6p8MjslRCudUnsDtqNieMx2wL2yZd4EfHCdD2RdPZw0pux0qIzxmX93tnaFuv9A06T/cZV7dpOw JCS6Q
X-Received: by 2002:a17:902:8643:: with SMTP id y3mr1315391plt.80.1549934169121; Mon, 11 Feb 2019 17:16:09 -0800 (PST)
X-Google-Smtp-Source: AHgI3IbJTsEEdx6iyhWZXWA4Kze4ZiqLDX4B9VTTyPFYVey26YM9NdT/9sbOnJ+lYYAi+SwF4Jf8TA==
X-Received: by 2002:a17:902:8643:: with SMTP id y3mr1315365plt.80.1549934168767; Mon, 11 Feb 2019 17:16:08 -0800 (PST)
Received: from [] ( []) by with ESMTPSA id f67sm17729301pfc.141.2019. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 11 Feb 2019 17:16:08 -0800 (PST)
From: Paul Lambert <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_EA67DABE-4769-4DD0-A119-33F54863E941"
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Date: Mon, 11 Feb 2019 17:16:25 -0800
In-Reply-To: <>
To: Leo Perrin <>
References: <>
X-Mailer: Apple Mail (2.3445.102.3)
X-MailRoute: Internal
X-Proofpoint-Spam-Reason: safe
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 01:16:14 -0000

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: 


> 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