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

[Sergey Agievich <[e-mail]>]

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 <[e-mail]> от имени Paul Lambert <[e-mail]>
Отправлено: 12 февраля 2019 г. 4:16
Кому: Leo Perrin
Копия: [e-mail]
Тема: 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 <[e-mail]<mailto:[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://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):
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



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
_______________________________________________
Cfrg mailing list
[e-mail]<mailto:[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=