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

[Dmitry Khovratovich <[e-mail]>]

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

>
> Hi Leo,
>
>
> On Feb 10, 2019, at 1:49 PM, Leo Perrin <[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]
>
> 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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>


-- 
Best regards,
Dmitry Khovratovich