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

From: Leo Perrin <[email-masked]>
Date: Sun, 10 Feb 2019 22:49:46 +0100 (CET)

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://eprint.iacr.org/2019/092 | 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! 

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 
[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 
[3] Arnaud Bannier, Nicolas Bodin, Éric Filiol. "Partition-based trapdoor ciphers". https://eprint.iacr.org/2016/493

---

From: Tony Arcieri <[email-masked]>
Date: Sun, 10 Feb 2019 22:29:29 -0800

On Sun, Feb 10, 2019 at 1:50 PM Leo Perrin <[email-masked]> wrote:

> This situation is unlike anything else in the literature. [...] 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.
>

Streebog was used as the hash function for the elliptic curve generation
procedure for 512-bit Edwards curves standardized in GOST R 34.10-2012. I'm
curious, even hypothetically, if this attack could be combined with an
attacker-controlled hash input (W) to maliciously influence curve parameter
selection.

Thread:
https://mailarchive.ietf.org/arch/msg/cfrg/1L7W2lPu4MtcHOfjoTFn_mmGPG4

A selected email below with an interesting passage highlighted...

---------- Forwarded message ---------
From: Stanislav V. Smyshlyaev <[email-masked]>
Date: Wed, Jan 28, 2015 at 6:14 AM
Subject: Re: [Cfrg] 512-bit twisted Edwards curve and curve generation
methods in Russian standardization
To: Alyssa Rowan <[email-masked]>, [email-masked] <[email-masked]>

Dear Alyssa,

As we believe (and as it has been mentioned earlier during discussion at
CFRG), the initital seed value doesn't have to be chosen explicitly in case
of trust in basic hash function properties – to gain some "backdoor-type"
properties of the curve with d = hash(W), one has either to *combine such
algebraic properties of a curve with properties of a hash function* (for a
trivial example, to have an ability to obtain a hash preimage) or to choose
a very probable "backdoor-type" property of a curve (such that it is
possible to obtain by random choice of a curve).

-- 
Tony Arcieri

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 11 Feb 2019 09:42:43 +0300

Dear Tony,

In response to your tweet
https://mobile.twitter.com/bascule/status/1094832386271932416
and this message of yours.

I am not able to comment anything on the principles of the generation of
Streebog and Kuznyechik S-Boxes - I've always been working in a commercial
company that develops software and was never invlolved in synthesis of
Russian cryptoprimitives.

But I can tell you everything about the process of generation of Edwards
curves, since my colleagues and I were the ones who generated them (and
later proposed for standardization in addition to older Weierstrass ones) –
since we needed to increase performance of digital signatures used in our
products.

You are totally right that W had not been selected according to modern good
principles of deterministic (and verifiable) search of suitable parameters.
It would be better if it was, but most of the curves that existed that time
were not even generated with parameters equal to hash values of some data
(with "verifiable pseudo-random" parameters).

But those curves were generated in 2012 - they reflected best practices and
state-of-the-art of that time. And Streebog was used for the obvious reason
- it was a new hash function that was standardized in Russia (as a part of
GOST R 34.11-2012 standard) and available for me and my colleagues.

Best regards,
Stanislav

пн, 11 февр. 2019 г. в 09:30, Tony Arcieri <[email-masked]>:

>> This situation is unlike anything else in the literature. [....] 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
> To: Alyssa Rowan <akr@akr..io <[email-masked]>>, [email-masked] <[email-masked]>
>
>
> Dear Alyssa,
>
> algebraic properties of a curve with properties of a hash function* (for
> a trivial example, to have an ability to obtain a hash preimage) or to
> choose a very probable "backdoor-type" property of a curve (such that it is
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 11 Feb 2019 13:49:17 -0800

On Sun, Feb 10, 2019 at 10:44 PM Stanislav V. Smyshlyaev <[email-masked]>
wrote:

> But those curves were generated in 2012 - they reflected best practices
> and state-of-the-art of that time. And Streebog was used for the obvious
> reason - it was a new hash function that was standardized in Russia (as a
> part of GOST R 34.11-2012 standard) and available for me and my colleagues.
>

I'm not accusing you of acting in bad faith (and to the extent I may have
done that in my tweet regarding Streebog in general I apologize, it was
moderately out of proportion).

That said, one of the main goals of the CFRG in selecting new elliptic
curves was to have a set of "rigid" selection guidelines (a.k.a. "nothing
up my sleeve"). A series of circumstances like this is the exact reason why
it's nice for the curve parameter selection process to be beyond reproach,
and if nothing else serves as an illustrative example of what could go
wrong in a standardization process which doesn't follow this approach.

-- 
Tony Arcieri

---

From: Paul Lambert <[email-masked]>
Date: Mon, 11 Feb 2019 17:16:25 -0800

Hi Leo,

> On Feb 10, 2019, at 1:49 PM, Leo Perrin <[email-masked]> wrote:
> 
> Dear CFRG Participants,
> 
> 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://eprint.iacr.org/2019/092 <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=>
> 

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 

Paul

> 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=

---

From: Dmitry Khovratovich <[email-masked]>
Date: Tue, 12 Feb 2019 12:55:17 +0100

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 <[email-masked]> wrote:

> 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.
>
> 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://eprint.iacr.org/2019/092
> <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=>
>
> 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):
> This was using:
> 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
> [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
> [3] Arnaud Bannier, Nicolas Bodin, Éric Filiol. "Partition-based trapdoor
> ciphers". https://eprint.iacr.org/2016/493
> 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=
>
>

-- 
Best regards,
Dmitry Khovratovich

---

From: Leo Perrin <[email-masked]>
Date: Tue, 12 Feb 2019 15:22:48 +0100 (CET)

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" <[email-masked]>
> À: "Paul Lambert" <[email-masked]>
> Cc: "Leo Perrin" <[email-masked]>, "cfrg" <[email-masked]>
> 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:[email-masked] |
> [email-masked] ] > wrote:

>>> On Feb 10, 2019, at 1:49 PM, Leo Perrin < [ mailto:[email-masked] |
>>> [email-masked] ] > wrote:

>>> 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.

>>> 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
>>> 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!

>> 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 ]

>>> [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 ]
>>> 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 ]
>>> ciphers". [ https://eprint.iacr.org/2016/493 | https://eprint.iacr.org/2016/493
>>> ]
>>> [ mailto:[email-masked] | [email-masked] ]
>>> [
>>> |
>>> ]

>> [ mailto:[email-masked] | [email-masked] ]
>> [ https://www.irtf.org/mailman/listinfo/cfrg |
>> https://www.irtf.org/mailman/listinfo/cfrg ]

---

From: Sergey Agievich <[email-masked]>
Date: Tue, 12 Feb 2019 18:20:14 +0000

Hi all,

1. I looked at Paul's code. There is a misunderstanding. He calculated the nonlinearity of the Belt S-box, not the Streebog one.

2. Let me explain the nonlinearity of H, the S-box of the Belt block cipher. H permutes bytes. In the context of Belt, where the addition modulo 2^32 is extensively used, we need to consider not only H itself but also the cascades H_k: x -> H(x + k), where + is the addition modulo 256 and k runs over bytes. In our case, the minimum nonlinearity over the cascades is even lower than 102, it equals 96. Exactly this nonlinearity was under control. We could not find H with larger min_k nl(H_k). The detailed characteristics of H can be found here: https://github.com/agievich/GF2/blob/master/test/test.cpp#L100.

3. The design of H was announced at the very beginning (2002). We used exponentiation in GF(2^8) (see https://eprint.iacr.org/2004/024.pdf) to achieve reasonably good cryptographic characteristics. Here is the code for generating H: https://github.com/agievich/bee2/blob/master/test/crypto/belt-test.c#L47.

4. Indeed, multiplicative inversion in GF(2^8) gives better nonlinearity and DDT than exponentiation. But inverse S-boxes have a drawback: the connection between their inputs and outputs can be described by only quadratic multivariate polynomials. Such an easy algebraic description provides a basis for algebraic attacks.

5. The main characteristics of S-boxes are deg (algebraic degree), nl (nonlinearity), dc (maximum entry in DDT), ai (algebraic immunity). For example, for AES, (deg, nl, dc, ai) = (7,112,4,2). The last coordinate indicates the presence of mentioned quadratic relations between inputs and outputs. If we require ai = 3 (the maximum), what can we expect from other characteristics? The current record known to me is (deg, nl, dc, ai) = (7, 108, 6, 3). It was achieved in several ways presented at the CTCrypt conferences. The interesting question is whether this is the final frontier.

Best regards,
Sergey Agievich

________________________________
От: Cfrg <[email-masked]> от имени Paul Lambert <[email-masked]>
Отправлено: 12 февраля 2019 г. 4:16
Кому: Leo Perrin
Копия: [email-masked]
Тема: Re: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801) [bayes][faked-from]

Hi Leo,

On Feb 10, 2019, at 1:49 PM, Leo Perrin <[email-masked]<mailto:[email-masked]>> wrote:

Dear CFRG Participants,

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://eprint.iacr.org/2019/092<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=>

Paul

Best regards,
/Léo Perrin

[email-masked]<mailto:[email-masked]>