Subject: [Cfrg] On the (non-)randomness of the S-box of Streebog and Kuznyechik

From: Leo Perrin <[email-masked]>
Date: Mon, 5 Aug 2019 17:35:06 +0200 (CEST)

Dear CFRG members, 

I would like to follow up on the short talk I gave several days ago. That talk was itself a follow-up to a previous e-mail [0] which presented a strange structure I found in pi, a component (S-box) which is shared by both Streebog (RFC 6986) and Kuznyechik (RFC 7801). 
At the time of writing this previous e-mail, I did not know that the designers of these algorithms were still claiming that they had generated their S-box randomly. However, they do! Here are links to relevant ISO documents that were leaked: 
- [ https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf | https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf ] 
- [ https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf | https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf ] 
As we can see in the first one, the designers of pi did claim that they obtained this component by generating many random S-boxes and then choosing the best according to some (fair and usual) criteria. In fact, as we can see in the second, they insisted that they used this method even *after* the publication of my latest results [1]. 

That is hardly possible. Let us see why. 

There are 2^{L+1}-1 bitstrings of length at most L. Thus, the total number of permutations with an implementation fitting in at most L bits in a given language (e.g. in C) is upper bounded by 2^{L+1}. The shortest implementation of pi in C we are aware of was found by ceilingcat [2] who improved a previous implementation by Xavier Bonnetain. That implementation is 139 ASCII characters long, i.e. 973 bits long. Thus, there are fewer than 2^{974} permutations with an implementation this simple. As there are 256! = 2^{1684} permutations operating on 8 bits, we easily conclude that the probability that a random permutation has a C implementation at most 973 bits long is smaller than 2^{974-1684} = 2^{-710}, which is beyond negligible. If we look at languages more compact than C (see [2]) then we can deduce even lower probabilities. In other words, the set of the permutations as simple as pi for a very broad definition of simplicity is extremely small, and thus the probability that we fall into it by chance is negligible. More detailed explanations are available at [3]. 

In light of this argument, only two possibilities are left: 
1. the designers of pi really used a random process to generate their S-box, they were just lucky enough to find one of the very (very very very) few permutations with a short implementation, or 
2. they used a TKlog deliberately but decided to hide it, the TKlog being the structure I identified in [1]. 
The probability that the first one is true can be upper bounded using the discussion above: it is at most 2^{-710}. For comparison, there are about 10^80 = 2^266 atoms in the universe. The only reasonable conclusion is then that we are in the second case: the use of the TKlog is a deliberate choice by its designers. Note that this reasoning is based purely on the simplicity of the TKlog structure. It does not take into account its very peculiar interactions with the finite field, nor does it consider the fact that the finite field used to define it is the same as the one used in the linear layer of Streebog. It is also unlikely that the differential and linear properties of pi can be encountered in a feasibly large set of random S-boxes [4]. 

Because of these observations, I insist that the designers of these algorithms have provided cryptanalysts with misleading information. There cannot be any good reason for this, which is why I think these algorithms cannot be trusted, and thus that RFC 6986 and 7801 should be deprecated. 

Cheers, 

/Léo 

PS: Remember that the golfed implementations listed in [2] are only intended to be small. They are *not* intended to be secure! Their running time in CPU cycles is directly proportionnal to the discrete logarithm of their input, meaning that they are the opposite of constant time. An implementation using them would be trivially vulnerable to some side channel attacks. 

[0] https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg?fbclid=IwAR3JIGXt1_6aFwNOjDb-p7oC3ezHRuEEreznt-atyY7Clah2QZU_uU7FKS8 
[1] [ https://tosc.iacr.org/index.php/ToSC/article/view/7405 | https://tosc.iacr.org/index.php/ToSC/article/view/7405 ] 
[2] [ https://codegolf.stackexchange.com/questions/186498/proving-that-a-russian-cryptographic-standard-is-too-structured | https://codegolf.stackexchange.com/questions/186498/proving-that-a-russian-cryptographic-standard-is-too-structured ] 
[3] [ https://who.rocq.inria.fr/Leo.Perrin/code-golf.html | https://who.rocq.inria.fr/Leo.Perrin/code-golf.html ] 
[4] https://eprint.iacr.org/2019/528

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 5 Aug 2019 19:02:37 +0100

Hiya,

On 05/08/2019 16:35, Leo Perrin wrote:
> Because of these observations, I insist that the designers of these
> algorithms have provided cryptanalysts with misleading information.
> There cannot be any good reason for this, which is why I think these
> algorithms cannot be trusted, and thus that RFC 6986 and 7801 should
> be deprecated.
Actually, this might need to be (at least partly) handled outside
CFRG by the IETF, as there is at least one standards track DNSSEC
RFC (RFC8624 [1]) with a normative reference to 6986.

There are also other documents with references to these RFCs, you
can see which documents reference 6986 at [2] and 7801 at [3]. (I
didn't check any of the others of those out myself though.)

However, the DNSSEC situation may be less bad than it seems, as
8624 says:

"
   GOST R 34.11-94 has been superseded by GOST R 34.11-2012 in
   [RFC6986].  GOST R 34.11-2012 has not been standardized for use in
   DNSSEC.
"

Does the structure you've discovered also exist in GOST R 34.11-94?

If it did, then there'd be a good case (IMO) to further deprecate use
of DNSSEC hash function #3, but if not, then perhaps the correct thing
is some kind of erratum to the effect that 6986 really ought not be
a normative reference in 8624 but rather RFC5831 ought be what's
referenced.

There is a similar statement about the related signature algorithm
(code point #12) defined in RFC7091 that also has a normative
reference to 6986.

Complicating matters a bit more, both code points are defined
with a "MUST NOT" implementation recommendation (which I don't
really understand;-) in RFC8624.

In general I would support CFRG deprecating any algorithms for
which there is significant doubt. I have not myself verified that
the structure Leo has found is real, but assuming it is then IMO
that'd be sufficient reason to deprecate these algorithms. But, I
think deprecating algorithms ought be done taking into account
existing deployments as well as the severity of the issue with
the algorithm. I'm not familiar with how widely these algorithms
are deployed.

For Leo: if you think these algorithms ought be deprecated then
writing an I-D to that effect would be what you'd want to do. If
you wanted help from someone more familiar with IETF/IRTF process
crap, I'd be happy to try help as needed.

Cheers,
S.

[1] https://tools.ietf.org/html/rfc8624
[2] https://datatracker.ietf.org/doc/rfc6986/referencedby/
[3] https://datatracker.ietf.org/doc/rfc7801/referencedby/

---

From: Dmitry Belyavsky <[email-masked]>
Date: Mon, 5 Aug 2019 22:05:17 +0300

Dear Leo, dear CFRG members,

Many thanks for your efforts in analysis of Russian GOST crypto algorithms.
I am not a cryptographer myself, but one of the implementors of Russian
cryptography.

On Mon, Aug 5, 2019 at 6:35 PM Leo Perrin <[email-masked]> wrote:

> Dear CFRG members,
>
> I would like to follow up on the short talk I gave several days ago. That
> talk was itself a follow-up to a previous e-mail [0] which presented a
> strange structure I found in pi, a component (S-box) which is shared by
> both Streebog (RFC 6986) and Kuznyechik (RFC 7801).
> At the time of writing this previous e-mail, I did not know that the
> designers of these algorithms were still claiming that they had generated
> their S-box randomly. However, they do! Here are links to relevant ISO
> documents that were leaked:
> - https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf
> -
> https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf
> As we can see in the first one, the designers of pi did claim that they
> obtained this component by generating many random S-boxes and then choosing
> the best according to some (fair and usual) criteria. In fact, as we can
> see in the second, they insisted that they used this method even *after*
> the publication of my latest results [1].
>
> There are 2^{L+1}-1 bitstrings of length at most L. Thus, the total number
> of permutations with an implementation fitting in at most L bits in a given
> language (e.g. in C) is upper bounded by 2^{L+1}. The shortest
> implementation of pi in C we are aware of was found by ceilingcat [2] who
> improved a previous implementation by Xavier Bonnetain. That implementation
> is 139 ASCII characters long, i.e. 973 bits long. Thus, there are fewer
> than 2^{974} permutations with an implementation this simple. As there are
> 256! = 2^{1684} permutations operating on 8 bits, we easily conclude that
> the probability that a random permutation has a C implementation at most
> 973 bits long is smaller than 2^{974-1684} = 2^{-710}, which is beyond
> negligible. If we look at languages more compact than C (see [2]) then we
> can deduce even lower probabilities. In other words, the set of the
> permutations as simple as pi for a very broad definition of simplicity is
> extremely small, and thus the probability that we fall into it by chance is
> negligible. More detailed explanations are available at [3].
>
> 1. the designers of pi really used a random process to generate their
> S-box, they were just lucky enough to find one of the very (very very very)
> few permutations with a short implementation, or
> The probability that the first one is true can be upper bounded using the
> discussion above: it is at most 2^{-710}. For comparison, there are about
> 10^80 = 2^266 atoms in the universe. The only reasonable conclusion is then
> that we are in the second case: the use of the TKlog is a deliberate choice
> by its designers. Note that this reasoning is based purely on the
> simplicity of the TKlog structure. It does not take into account its very
> peculiar interactions with the finite field, nor does it consider the fact
> that  the finite field used to define it is the same as the one used in the
> linear layer of Streebog. It is also unlikely that the differential and
> linear properties of pi can be encountered in a feasibly large set of
> random S-boxes [4].
>
> algorithms have provided cryptanalysts with misleading information. There
> cannot be any good reason for this, which is why I think these algorithms
> cannot be trusted, and thus that RFC 6986 and 7801 should be deprecated.
>
> Cheers,
>
> /Léo
>
> PS: Remember that the golfed implementations listed in [2] are only
> intended to be small. They are *not* intended to be secure! Their running
> time in CPU cycles is directly proportionnal to the discrete logarithm of
> their input, meaning that they are the opposite of constant time. An
> implementation using them would be trivially vulnerable to some side
> channel attacks.
>

You say that you have arguments that the designers may have said
controversial declarations about some details of the construction in the
ISO, but this doesn’t seem to correspond to attack.

Could you please clarify how does the existence of a compact code for
generation of the S-box imply a possibility of attack?

Currently, I don't see even a performance optimization as a consequence of
the compact representation of the S-box.
The most widespread open-source implementation (
https://github.com/gost-engine/engine/tree/openssl_1_1_0)
of Streebog and Kuznyechik does not use the Pi transformations as a
separate step — they use a combined process.

> [0]
> https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg?fbclid=IwAR3JIGXt1_6aFwNOjDb-p7oC3ezHRuEEreznt-atyY7Clah2QZU_uU7FKS8
> [1] https://tosc.iacr.org/index.php/ToSC/article/view/7405
> [2]
> https://codegolf.stackexchange.com/questions/186498/proving-that-a-russian-cryptographic-standard-is-too-structured
> [3] https://who.rocq.inria.fr/Leo.Perrin/code-golf.html
> <https://who.rocq.inria.fr/Leo.Perrin/code-golf..html>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
SY, Dmitry Belyavsky

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 6 Aug 2019 16:14:43 +0300

Dear Stephen and Leo,

>> Does the structure you've discovered also exist in GOST R 34.11-94?
Stephen, GOST R 34.11-94 is built using a completely different
construction, so (Leo will correct me, if I am mistaken) the discovered
properties are not related to GOST R 34.11-94. I’d also like to clarify
that this GOST R 34.11-94 is an old hash function, which has been
deprecated for about 7 years in Russia.

>> In general I would support CFRG deprecating any algorithms for which
there is significant doubt. I have not myself verified that the structure
Leo has found is real…
First of all, I’d like to express my sincere appreciation to Leo for his
deep study of Streebog/Kuznyechik S-Box properties. I am not a designer of
those algorithms, but my company (software development: digital signature
servers, VPN solutions etc.) uses them in those software products which are
intended for usage with governmental applications inside Russia (they must
be used for such applications). Hence, I am definitely interested in having
as much research of those algorithms as possible: they are obviously worth
being studied.
Leo’s results about structures of those S-Boxes are very interesting and
important for understanding the properties of the algorithms themselves and
for optimization of their implementations (which is interesting for all
software developers implementing them). I sincerely wish that Leo continues
your research – Leo, please continue this study, you’re doing a great work.
Leo has discovered a very interesting property of the S-Boxes, a very
curious structure of representing them, but there is a certain contrast
between high level of the Leo’s scientific part of work and the lack of
ground (so far, at least) for conclusions and accusations about possible
vulnerabilities in the algorithms. At the CFRG session in Montreal there
was a discussion on this issue, it is important to continue the research
when some new properties are found in any crypto, but we can’t “deprecate”
something deployed (at least, there are many cases when they are used in
Russian part of Internet) “just in case”, just because there are some new
properties found (without any results of how they could lead to a
vulnerability or to a backdoor, despite the fact that Leo has obviously
been working on finding such for at least one year).
If Leo had a result like Ferguson and Shumow in 2007 (
https://rump2007.cr.yp.to/15-shumow.pdf, when they showed that the
knowledge of certain parameter – discrete logarithm in that case – allows
to mount an attack on predicting Dual EC DRBG outputs with low complexity),
then, of course, it would be definitely a reason for significant doubts in
those algorithms (and, particularly, for an I-D about the found attacks) –
in international and national organizations and technical committees. But,
as Leo stresses himself, he does not have any (even preliminary) results of
this kind.

During the discussion at the CFRG session Leo claimed that he stressed in
his papers explicitly, that he hasn’t found any methods for mounting the
attacks or conditional results like “if the designers know a certain
parameter X, then they can mount the following attack”.
Leo, many thanks for that clarification of yours; you’ve been absolutely
honest, I’ve found this in your papers:
*- “Kuznyechik seems to be in the second situation [although the S-Box and
linear layer are defined over similar structures, a small function was
added with the explicit purpose of breaking this similarity (case of the
AES and the affine permutation used in its S-Box]”*
*- “Open Problem 1. Is there a way to leverage the partition-preserving
property of 𝜋 to mount an attack against Streebog?“*

Once more, Leo, your research is extremely interesting – I personally ask
you to continue. But it will be correct to underline that currently it’s
only an ongoing research, without any reasons for statements about
backdoors/vulnerabilities.

Best regards,
Stanislav

пн, 5 авг. 2019 г. в 22:07, Dmitry Belyavsky <[email-masked]>:

>> https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog..pdf
>> <https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf>
>> There are 2^{L+1}-1 bitstrings of length at most L. Thus, the total
>> number of permutations with an implementation fitting in at most L bits in
>> a given language (e.g. in C) is upper bounded by 2^{L+1}. The shortest
>> 1.. the designers of pi really used a random process to generate their
>> [4] https://eprint.iacr.org/2019/528 <https://eprint..iacr.org/2019/528>

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 6 Aug 2019 14:33:36 +0100

Hiya,

> deprecated for about 7 years in Russia.

So that sounds like an erratum may be worthwhile
for each of 8624 and 7901? I guess the code points
defined for DNSSEC are really for the old algorithms
and ought not point to the RFCs for the new ones?
Those'd be valid errata I reckon, as it was a bit
of a mistake (though entirely understandable) to
refer to the new RFCs when the code points are for
the old algorithms. Those errata would just say
that the normative references to the new RFC were
wrong and should've been to the old RFC. And that
hasn't really got anything to do with the meat of
Leo's findings - it's just that his work flagged
up the erroneous references.

As to whether to deprecate the algorithms due to
Leo's findings, I agree that the existence of
deployments that'd be affected needs to be taken
into account in terms of the timing of when that
might reasonably be done. And the fact that the
algorithms in question are national standards is
also a relevant point, though of course deprecating
the RFCs has no formal effect on such national
standards.

Personally though, I think discovery of undeclared
and unexplained structure such as this in a crypto
algorithm ought be taken as a negative, even if there
is no known attack at present, so I'd be for moving
to deprecate when that is practical, in this case,
as I would in any other similar case.

Cheers,
S.

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 6 Aug 2019 16:57:19 +0300

Dear Stephen,

>> So that sounds like an erratum may be worthwhile for each of 8624 and
7901? I guess the code points defined for DNSSEC are really for the old
algorithms and ought not point to the RFCs for the new ones?
>> And that hasn't really got anything to do with the meat of Leo's
findings - it's just that his work flagged up the erroneous references.
Personally, I agree that it would be good to do the updates here. But, as
for DNSSEC, I hope that the authors of RFC 5933 (or, maybe, Dmitry
Belyavsky) can comment better.

---

From: Dmitry Belyavsky <[email-masked]>
Date: Tue, 6 Aug 2019 17:09:20 +0300

Dear Stephen,

RFC 7091 seems to be a translation of the corresponding GOST standard.

RFC 8624 contains a reference to RFC5933, where the GOST algorithms for
DNSSec were introduced.
The reference is correct, the reference to the superseding algorithms is
correct too.

So it seems that no errata required here.

-- 
SY, Dmitry Belyavsky

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 6 Aug 2019 15:13:16 +0100

Hiya,

> The reference is correct, the reference to the superseding algorithms is

I'm not getting it. Why does 8624 need a normative
reference to 6986 and an informative reference to
5933 when the code points refer to the algorithms
defined in 5933?

S.

---

From: Dmitry Belyavsky <[email-masked]>
Date: Tue, 6 Aug 2019 17:20:08 +0300

> 5933 when the code points refer to the algorithms

In fact, the reference to 5933 is normative (in part of  DNSSec).

Then we have reference to the superseding algorithms which personally I
tend to treat as informative.
It explains why the GOST algorithms have the status MUST NOT for
signing/delegation.

> >> вт, 6 авг. 2019 г. в 16:33, Stephen Farrell <[email-masked]
> >:
> >>
> >>>
> >>> Hiya,
> >>>

-- 
SY, Dmitry Belyavsky

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 6 Aug 2019 15:23:31 +0100

Sorry, I must be confusing something...

> In fact, the reference to 5933 is normative (in part of  DNSSec).

I'm looking at 8624 now and the reference
to 6986 is in section 7.1 "normative references" [1]
whereas the reference to 5933 is in 7.2 which
are the informative references. [2]

An errata that just said to swap those would make
sense and seems to match what you say below.

Cheers,
S.

[1] https://tools.ietf.org/html/rfc8624#section-7.1
[2] https://tools.ietf.org/html/rfc8624#section-7.2

---

From: Jonathan Hoyland <[email-masked]>
Date: Tue, 6 Aug 2019 15:31:37 +0100

Hi all,

Obviously not as a practical suggestion, but just to clarify my
understanding of the issue at hand, would creating a new S-box lookup table
from a verifiably random source completely ameliorate Leo's concerns?
If the S-box was created with no pattern in mind, as stated, then any other
randomly generated lookup table should be equally sound, and would be
immensely unlikely to have this curious structure.
Say we used a distributed randomness beacon to seed a permutation of the
S-box, such that anyone can verify for themselves that the S-box was
generated randomly, would everyone be satisfied that the new version was at
least as secure as the old?

Regards,

Jonathan

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 6 Aug 2019 17:39:00 +0300

Dear Jonathan,

All found properties are only about the particular S-Box (so, yes, "a new
S-box lookup table from a verifiably random source completely ameliorate
Leo's concerns"), but just picking a random S-Box can provide a weak one
(due to known and well-understood attacks, not to some "probably possible"
ones), since there are many properties (to be short, resistance to known
methods of cryptanalysis) that are taken into account when picking an S-Box
for a block cipher.

Best regards,
Stanislav

вт, 6 авг. 2019 г. в 17:32, Jonathan Hoyland <[email-masked]>:

> If the S-box was created with no pattern in mind, as stated, then any
> other randomly generated lookup table should be equally sound, and would be

---

From: Leo Perrin <[email-masked]>
Date: Tue, 6 Aug 2019 17:04:11 +0200 (CEST)

Hello everyone, 

There are two issues which should not be mistaken for one another. 

1. Do the specifics of the decomposition I found lead to an attack? 

As far as I know the answer is no, though I haven't looked at this very much since I found the TKlog decomposition about a year ago. I cannot speak for the whole secret key community but I know the same is true for many of us as we have been busy with the NIST lightweight standardization. It is not accurate to say that I have been looking at ways to exploit these properties for a year---or that anyone else has (as far as I know). 

I personnally really don't like the properties I found but it is fair to say that it is merely my intuition. I like to think it is an informed intuition as I have spent *a lot* of time looking at S-boxes, but the fact is that it is only an intuition. Talking about backdoors and such would only be speculations at that point, although I would definitely welcome investigations on this topic. 

2. Why did the designers provide wrong information to the ISO cryptographers? 

When publishing a cryptographic algorithm, it is expected that all its part are properly explained. For example, if we look at the NIST call for lightweight algorithms [1], it is explicitly stated that "The submitter *shall* explain the provenance of any constants or tables used in the algorithm." In other words, having unexplained constants or S-boxes is a deal breaker from the start, regardless of the other properties of the cipher. That was the situation in which the Russian algorithms were before 2018: they had an unexplained S-box. At that point, when asked for explanations by ISO, its authors "provided" the missing information in the form of [2]. 

What I claim, and what motivates my call for deprecation, is that this information is wrong: it describes an S-box generation process which is tremendously unlikely to produce anything that remotely resembles their S-box. Further, I disagree with Dmitry when he describes this as "controversial declarations about some details of the construction". It is factually wrong declarations, not controversial ones; and it is not about some details of the algorithms, it is about half of the round function; the only non-linear part of both algorithms in fact. 

The point of the short implementations is only to prove my claim above. The existence of a short implementation is not a problem in itself---the AES S-box has ~equally short implementations in golf languages. What matters is that it utterly disproves the explanations provided by the algorithm authors. 

Let me put it differently. Right now, the CFRG is looking for PAKE candidates. If a candidate relied on an elliptic curve claimed to be generated randomly but which actually turns out to have a very strong and new mathematical structure which cannot happen by chance, I think it would be kicked out without further analysis. 

Ultimately, cryptography is about trust. How can there be trust in an algorithm when all the evidence points towards their designers acting in bad faith? 

/Léo 

PS: To answer Jonathan proposal of verifiable randomness: Yes, as far as I am concerned, that could be a way forward. I am personnally not a fan of random S-boxes but our main conclusion in [3] is that the properties of a random S-box are basically always the same: they have no structure and have mediocre differential/linear properties with overwhelming probability that would probably be good enough here. 

[1] https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/final-lwc-submission-requirements-august2018.pdf 
[2] [ https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf | https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf ] 
[3] https://eprint.iacr.org/2019/528 

> De: "Stanislav V. Smyshlyaev" <[email-masked]>
> À: "Leo Perrin" <[email-masked]>, "Stephen Farrell"
> <[email-masked]>
> Cc: "cfrg" <[email-masked]>, "Dmitry Belyavsky" <[email-masked]>
> Envoyé: Mardi 6 Août 2019 15:14:43
> Objet: Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and
> Kuznyechik

> Stephen, GOST R 34.11-94 is built using a completely different construction, so
> (Leo will correct me, if I am mistaken) the discovered properties are not
> related to GOST R 34.11-94. I’d also like to clarify that this GOST R 34.11-94
> is an old hash function, which has been deprecated for about 7 years in Russia.

>>> In general I would support CFRG deprecating any algorithms for which there is
>>> significant doubt. I have not myself verified that the structure Leo has found
> >> is real…
> First of all, I’d like to express my sincere appreciation to Leo for his deep
> study of Streebog/Kuznyechik S-Box properties. I am not a designer of those
> algorithms, but my company (software development: digital signature servers,
> VPN solutions etc.) uses them in those software products which are intended for
> usage with governmental applications inside Russia (they must be used for such
> applications). Hence, I am definitely interested in having as much research of
> those algorithms as possible: they are obviously worth being studied.
> important for understanding the properties of the algorithms themselves and for
> optimization of their implementations (which is interesting for all software
> developers implementing them). I sincerely wish that Leo continues your
> research – Leo, please continue this study, you’re doing a great work.
> Leo has discovered a very interesting property of the S-Boxes, a very curious
> structure of representing them, but there is a certain contrast between high
> level of the Leo’s scientific part of work and the lack of ground (so far, at
> least) for conclusions and accusations about possible vulnerabilities in the
> algorithms. At the CFRG session in Montreal there was a discussion on this
> issue, it is important to continue the research when some new properties are
> found in any crypto, but we can’t “deprecate” something deployed (at least,
> there are many cases when they are used in Russian part of Internet) “just in
> case”, just because there are some new properties found (without any results of
> how they could lead to a vulnerability or to a backdoor, despite the fact that
> Leo has obviously been working on finding such for at least one year).
> If Leo had a result like Ferguson and Shumow in 2007 ( [
> https://rump2007.cr.yp.to/15-shumow.pdf |
> https://rump2007.cr.yp.to/15-shumow.pdf ] , when they showed that the knowledge
> of certain parameter – discrete logarithm in that case – allows to mount an
> attack on predicting Dual EC DRBG outputs with low complexity), then, of
> course, it would be definitely a reason for significant doubts in those
> algorithms (and, particularly, for an I-D about the found attacks) – in
> international and national organizations and technical committees. But, as Leo
> stresses himself, he does not have any (even preliminary) results of this kind.

> During the discussion at the CFRG session Leo claimed that he stressed in his
> papers explicitly, that he hasn’t found any methods for mounting the attacks or
> conditional results like “if the designers know a certain parameter X, then
> they can mount the following attack”.
> Leo, many thanks for that clarification of yours; you’ve been absolutely honest,
> I’ve found this in your papers:
> - “Kuznyechik seems to be in the second situation [although the S-Box and linear
> layer are defined over similar structures, a small function was added with the
> explicit purpose of breaking this similarity (case of the AES and the affine
> permutation used in its S-Box]”
> - “Open Problem 1. Is there a way to leverage the partition-preserving property
> of \uD835\uDF0B to mount an attack against Streebog?“

> Once more, Leo, your research is extremely interesting – I personally ask you to
> continue. But it will be correct to underline that currently it’s only an
> ongoing research, without any reasons for statements about

> пн, 5 авг. 2019 г. в 22:07, Dmitry Belyavsky < [ mailto:[email-masked] |
> [email-masked] ] >:

>> On Mon, Aug 5, 2019 at 6:35 PM Leo Perrin < [ mailto:[email-masked] |
>> [email-masked] ] > wrote:

>>> I would like to follow up on the short talk I gave several days ago. That talk
>>> was itself a follow-up to a previous e-mail [0] which presented a strange
>>> structure I found in pi, a component (S-box) which is shared by both Streebog
>>> (RFC 6986) and Kuznyechik (RFC 7801).
>>> At the time of writing this previous e-mail, I did not know that the designers
>>> of these algorithms were still claiming that they had generated their S-box
>>> randomly. However, they do! Here are links to relevant ISO documents that were
>>> leaked:
>>> - [ https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf |
>>> https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf ]
>>> - [
>>> |
>>> ]
>>> As we can see in the first one, the designers of pi did claim that they obtained
>>> this component by generating many random S-boxes and then choosing the best
>>> according to some (fair and usual) criteria. In fact, as we can see in the
>>> second, they insisted that they used this method even *after* the publication
>>> of my latest results [1].

>>> There are 2^{L+1}-1 bitstrings of length at most L. Thus, the total number of
>>> permutations with an implementation fitting in at most L bits in a given
>>> language (e.g. in C) is upper bounded by 2^{L+1}. The shortest implementation
>>> of pi in C we are aware of was found by ceilingcat [2] who improved a previous
>>> implementation by Xavier Bonnetain. That implementation is 139 ASCII characters
>>> long, i.e. 973 bits long. Thus, there are fewer than 2^{974} permutations with
>>> an implementation this simple. As there are 256! = 2^{1684} permutations
>>> operating on 8 bits, we easily conclude that the probability that a random
>>> permutation has a C implementation at most 973 bits long is smaller than
>>> 2^{974-1684} = 2^{-710}, which is beyond negligible. If we look at languages
>>> more compact than C (see [2]) then we can deduce even lower probabilities. In
>>> other words, the set of the permutations as simple as pi for a very broad
>>> definition of simplicity is extremely small, and thus the probability that we
>>> fall into it by chance is negligible. More detailed explanations are available
>>> at [3].

>>> 1.. the designers of pi really used a random process to generate their S-box,
>>> they were just lucky enough to find one of the very (very very very) few
>>> permutations with a short implementation, or
>>> discussion above: it is at most 2^{-710}. For comparison, there are about 10^80
>>> = 2^266 atoms in the universe. The only reasonable conclusion is then that we
>>> are in the second case: the use of the TKlog is a deliberate choice by its
>>> designers. Note that this reasoning is based purely on the simplicity of the
>>> TKlog structure. It does not take into account its very peculiar interactions
>>> with the finite field, nor does it consider the fact that the finite field used
>>> to define it is the same as the one used in the linear layer of Streebog. It is
>>> also unlikely that the differential and linear properties of pi can be
>>> encountered in a feasibly large set of random S-boxes [4].

>>> Because of these observations, I insist that the designers of these algorithms
>>> have provided cryptanalysts with misleading information. There cannot be any
>>> good reason for this, which is why I think these algorithms cannot be trusted,
>>> and thus that RFC 6986 and 7801 should be deprecated.

>>> PS: Remember that the golfed implementations listed in [2] are only intended to
>>> be small. They are *not* intended to be secure! Their running time in CPU
>>> cycles is directly proportionnal to the discrete logarithm of their input,
>>> meaning that they are the opposite of constant time. An implementation using
>>> them would be trivially vulnerable to some side channel attacks.

>> You say that you have arguments that the designers may have said controversial
>> declarations about some details of the construction in the ISO, but this
>> doesn’t seem to correspond to attack.

>> Could you please clarify how does the existence of a compact code for generation
>> of the S-box imply a possibility of attack?

>> Currently, I don't see even a performance optimization as a consequence of the
>> compact representation of the S-box.
>> The most widespread open-source implementation ( [
>> https://github.com/gost-engine/engine/tree/openssl_1_1_0 |
>> https://github.com/gost-engine/engine/tree/openssl_1_1_0 ] )
>> of Streebog and Kuznyechik does not use the Pi transformations as a separate
>> step — they use a combined process.

>>> [0] [
>>> |
>>> ]
>>> [1] [ https://tosc.iacr.org/index.php/ToSC/article/view/7405 |
>>> https://tosc.iacr.org/index.php/ToSC/article/view/7405 ]
>>> [2] [
>>> |
>>> ]
>>> [3] [ https://who.rocq.inria.fr/Leo.Perrin/code-golf..html |
>>> https://who.rocq.inria.fr/Leo.Perrin/code-golf.html ]
>>> [4] [ https://eprint..iacr.org/2019/528 | https://eprint.iacr.org/2019/528 ]
>>> [ mailto:[email-masked] | [email-masked] ]
>>> [ https://www.irtf.org/mailman/listinfo/cfrg |
>>> https://www.irtf.org/mailman/listinfo/cfrg ]

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