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

[Leo Perrin <[e-mail]>]

Hi, 

The S-box of the standard from Belarus was built using a much more classical structure, essentially a "regular" discrete logarithm mapping GF(2^8) to Z/2^8Z. In fact, its design was explained by its designers, although in a somewhat hard to find paper in a Russian speaking journal (the reference is in the ToSC'16 paper I co-authored with Udovenko). In contrast, the Russian S-box was never explained (including in Russian speaking sources) and it uses a strange variant of the logarithm mapping GF(2^8) to itself. Since the linear layers of the corresponding algorithms are also defined in GF(2^8), we have an "alignment" which I find worrying---especially since it involves a partition of the space into additive cosets of a vector subspace. 

The non-linearity (deduced from the maximum coefficient in the Linear Approximations Table) and the differential uniformity (maximum coefficient in the Difference Distribution Table) of the Russian S-box are the same as those of the usual discrete logarithm. A random S-box has worse differential and linear properties than a log-based S-box with overwhelmingly high probability (I estimate those probabilities in my paper). Still, the multiplicative inverse is far better from both a differential and a linear standpoint which is why both the AES and the SMS4 S-boxes fare better than the Russian S-box in this regard. A more careful analysis of the differential and linear properties finds them to be a tiny bit worse in pi than in a "normal" discrete logarithm. Hence, the justification for the structure used by the Russians cannot be an improvement of those quantities. 

If you are interested in this kind of statistical analysis, I recommend chapter 9 of my PhD thesis [1]. 

Cheers, and thanks for your interest 
/Léo 

[1] http://orbilu.uni.lu/handle/10993/31195 

> De: "Dmitry Khovratovich" <[e-mail]>
> À: "Paul Lambert" <[e-mail]>
> Cc: "Leo Perrin" <[e-mail]>, "cfrg" <[e-mail]>
> Envoyé: Mardi 12 Février 2019 12:55:17
> Objet: Re: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986,
> RFC 7801)

> 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 < [ mailto:[e-mail] |
> [e-mail] ] > wrote:

>> Hi Leo,

>>> On Feb 10, 2019, at 1:49 PM, Leo Perrin < [ mailto:[e-mail] |
>>> [e-mail] ] > 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: [
>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__eprint.iacr..org_2019_092&d=DwMFAw&c=qgVugHHq3rzouXkEXdxBNQ&r=oIg4FfS8P761BlhMPJ2ys3IvSyH4XQ12Mbj_mXrCAJs&m=S0H637y57cjgJ_W4QG8e2TIQ0lLL3cDdmc5Lf8_MxfI&s=uVblnQv8g31qEeLvM80bundiG3ewh95591JrcjZKvGQ&e=
>>> | 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 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: [
>> https://github.com/nymble/cryptopy/blob/master/analysis/sbox_nonlinearity.py |
>> https://github.com/nymble/cryptopy/blob/master/analysis/sbox_nonlinearity.py ]

>> 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: [
>>> https://eprint.iacr.org/2016/071 | https://eprint.iacr.org/2016/071 ]
>>> [2] Léo Perrin, Aleksei Udovenko. "Exponential S-Boxes: a Link Between the
>>> S-Boxes of BelT and Kuznyechik/Streebog ". ToSC'16. Available online: [
>>> https://tosc.iacr.org/index.php/ToSC/article/view/567 |
>>> https://tosc.iacr.org/index.php/ToSC/article/view/567 ]
>>> [3] Arnaud Bannier, Nicolas Bodin, Éric Filiol. "Partition-based trapdoor
>>> ciphers". [ https://eprint.iacr.org/2016/493 | https://eprint.iacr.org/2016/493
>>> ]
>>> _______________________________________________
>>> Cfrg mailing list
>>> [ mailto:[e-mail] | [e-mail] ]
>>> [
>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf..org_mailman_listinfo_cfrg&d=DwICAg&c=qgVugHHq3rzouXkEXdxBNQ&r=oIg4FfS8P761BlhMPJ2ys3IvSyH4XQ12Mbj_mXrCAJs&m=S0H637y57cjgJ_W4QG8e2TIQ0lLL3cDdmc5Lf8_MxfI&s=CbZRt6CVbiJLCAXEFyRawO2y5_gU6tsBtlsT9gxbQ14&e=
>>> |
>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf..org_mailman_listinfo_cfrg&d=DwICAg&c=qgVugHHq3rzouXkEXdxBNQ&r=oIg4FfS8P761BlhMPJ2ys3IvSyH4XQ12Mbj_mXrCAJs&m=S0H637y57cjgJ_W4QG8e2TIQ0lLL3cDdmc5Lf8_MxfI&s=CbZRt6CVbiJLCAXEFyRawO2y5_gU6tsBtlsT9gxbQ14&e=
>>> ]

>> _______________________________________________
>> Cfrg mailing list
>> [ mailto:[e-mail] | [e-mail] ]
>> [ https://www.irtf.org/mailman/listinfo/cfrg |
>> https://www.irtf.org/mailman/listinfo/cfrg ]

> --
> Best regards,
> Dmitry Khovratovich