[prev in list] [next in list] [prev in thread] [next in thread]
List: cfrg
Subject: Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and Kuznyechik
From: Leo Perrin <leo.perrin () inria ! fr>
Date: 2019-08-06 15:04:11
Message-ID: 1887277869.25916502.1565103851198.JavaMail.zimbra () inria ! fr
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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" <smyshsv@gmail.com>
> À: "Leo Perrin" <leo.perrin@inria.fr>, "Stephen Farrell"
> <stephen.farrell@cs.tcd.ie>
> Cc: "cfrg" <cfrg@irtf.org>, "Dmitry Belyavsky" <beldmit@gmail.com>
> Envoyé: Mardi 6 Août 2019 15:14:43
> Objet: Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and
> Kuznyechik
> 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 |
> 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
> backdoors/vulnerabilities.
> Best regards,
> Stanislav
> пн, 5 авг. 2019 г. в 22:07, Dmitry Belyavsky < [ mailto:beldmit@gmail.com |
> beldmit@gmail.com ] >:
> > 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 < [ mailto:leo.perrin@inria.fr |
> > leo.perrin@inria.fr ] > 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/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.
> > 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] [
> > > https://mailarchive.ietf.org/arch/msg/cfrg/4PmssKzCBsxTmLCieDgqD7Nynwg?fbclid=IwAR3JIGXt1_6aFwNOjDb-p7oC3ezHRuEEreznt-atyY7Clah2QZU_uU7FKS8
> > > |
> > > 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 | https://eprint.iacr.org/2019/528 ]
> > > _______________________________________________
> > > Cfrg mailing list
> > > [ mailto:Cfrg@irtf.org | Cfrg@irtf.org ]
> > > [ https://www.irtf.org/mailman/listinfo/cfrg |
> > > https://www.irtf.org/mailman/listinfo/cfrg ]
> > --
> > SY, Dmitry Belyavsky
> > _______________________________________________
> > Cfrg mailing list
> > [ mailto:Cfrg@irtf.org | Cfrg@irtf.org ]
> > [ https://www.irtf.org/mailman/listinfo/cfrg |
> > https://www.irtf.org/mailman/listinfo/cfrg ]
[Attachment #5 (text/html)]
<html><body><div id="zimbraEditorContainer" style="font-family: arial, helvetica, \
sans-serif; font-size: 12pt; color: #000000" class="31"><div>Hello \
everyone,<br></div><div><br data-mce-bogus="1"></div><div>There are two issues which \
should not be mistaken for one another.<br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>1. Do the specifics \
of the decomposition I found lead to an attack?<br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div>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).<br></div><div><br \
data-mce-bogus="1"></div><div>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.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div>2. Why did the designers provide wrong information to \
the ISO cryptographers?<br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div>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].<br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div>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.<br data-mce-bogus="1"></div><div><br \
data-mce-bogus="1"></div><div><div>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.</div><div><br data-mce-bogus="1"></div><div>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.</div><div><br \
data-mce-bogus="1"></div><div>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?<br data-mce-bogus="1"></div><div><br></div></div><div>/Léo<br \
data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>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.<br \
data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>[1] \
https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/final-lwc-submission-requirements-august2018.pdf<br \
data-mce-bogus="1"></div><div>[2] <span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT515_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT520_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT414_com_zimbra_url"><a \
href="https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf" \
target="_blank" data-mce-href="https://cdn.virgilsecurity.com/assets/docs/memo-on-kuzn \
yechik-s-box.pdf">https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf</a></span></span></span><br></div><div><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object">[3] \
https://eprint.iacr.org/2019/528<br \
data-mce-bogus="1"></span></span></span></div><div><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object"><br \
data-mce-bogus="1"></span></span></span></div><div><br data-mce-bogus="1"></div><hr \
id="zwchr" data-marker="__DIVIDER__"><div data-marker="__HEADERS__"><blockquote \
style="border-left:2px solid \
#1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:norm \
al;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><b>De: \
</b>"Stanislav V. Smyshlyaev" <smyshsv@gmail.com><br><b>À: </b>"Leo Perrin" \
<leo.perrin@inria.fr>, "Stephen Farrell" \
<stephen.farrell@cs.tcd.ie><br><b>Cc: </b>"cfrg" <cfrg@irtf.org>, "Dmitry \
Belyavsky" <beldmit@gmail.com><br><b>Envoyé: </b>Mardi 6 Août 2019 \
15:14:43<br><b>Objet: </b>Re: [Cfrg] On the (non-)randomness of the S-box of Streebog \
and Kuznyechik<br></blockquote></div><div data-marker="__QUOTED_TEXT__"><blockquote \
style="border-left:2px solid \
#1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:norm \
al;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div \
dir="ltr">Dear Stephen and Leo,<br><br>>> Does the structure you've discovered \
also exist in GOST R 34.11-94?<br>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.<br><br>>> 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…<br>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.<br>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. <br>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).<br>If Leo had a result like Ferguson and Shumow in 2007 (<a \
href="https://rump2007.cr.yp.to/15-shumow.pdf" \
target="_blank">https://rump2007.cr.yp.to/15-shumow.pdf</a>, 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.<div><br>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". <br>Leo, many thanks for that clarification of yours; you've been absolutely \
honest, I've found this in your papers:</div><div><i>- "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]"</i></div><div><i>- "Open Problem 1. Is there a way to leverage the \
partition-preserving property of \uD835\uDF0B to mount an attack against \
Streebog?"</i></div><div><br>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..<br><br><div>Best \
regards,<br>Stanislav</div></div></div><br><div class="gmail_quote"><div dir="ltr" \
class="gmail_attr">пн, 5 авг. 2019 г. в 22:07, Dmitry Belyavsky <<a \
href="mailto:beldmit@gmail.com" \
target="_blank">beldmit@gmail.com</a>>:<br></div><blockquote class="gmail_quote" \
style="margin:0px 0px 0px 0.8ex;border-left:1px solid \
rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">Dear Leo, dear \
CFRG members,</div><div dir="ltr"><br></div><div>Many thanks for your efforts in \
analysis of Russian GOST crypto algorithms. </div><div dir="ltr">I am not a \
cryptographer myself, but one of the implementors of Russian \
cryptography.<br></div><br><div class="gmail_quote"><div dir="ltr" \
class="gmail_attr">On Mon, Aug 5, 2019 at 6:35 PM Leo Perrin <<a \
href="mailto:leo.perrin@inria.fr" target="_blank">leo.perrin@inria.fr</a>> \
wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div \
style="font-family:arial,helvetica,sans-serif;font-size:12pt;color:rgb(0,0,0)"><div><div>Dear \
CFRG members,<br></div><br><div>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).<br></div><div>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:<br></div><div>- <span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT515_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT520_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT414_com_zimbra_url"><a \
href="https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf" \
target="_blank">https://cdn.virgilsecurity.com/assets/docs/memo-on-kuznyechik-s-box.pdf</a></span></span></span><br></div><div>- \
<span class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT516_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT521_com_zimbra_url"><span \
class="gmail-m_-3515335629100444058gmail-m_1835156983088108477Object" \
id="gmail-m_-3515335629100444058gmail-m_1835156983088108477OBJ_PREFIX_DWT415_com_zimbra_url"><a \
href="https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf" \
target="_blank">https://cdn.virgilsecurity.com/assets/docs/meeting-report-for-the-discussion-on-kuznyechik-and-streebog..pdf</a></span></span></span><br></div><div>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].</div><br><div>That is hardly possible. Let us see why.</div><br><div>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].<br></div><br><div>In light of this argument, only two possibilities are \
left:<br></div><div>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<br></div><div>2. they used a TKlog \
deliberately but decided to hide it, the TKlog being the structure I identified in \
Cfrg mailing list<br>
<a href="mailto:Cfrg@irtf.org" target="_blank">Cfrg@irtf.org</a><br>
<a href="https://www.irtf.org/mailman/listinfo/cfrg" rel="noreferrer" \
target="_blank">https://www.irtf.org/mailman/listinfo/cfrg</a><br> \
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" \
class="gmail-m_-3515335629100444058gmail_signature">SY, Dmitry Belyavsky</div></div> \
_______________________________________________<br> Cfrg mailing list<br>
<a href="mailto:Cfrg@irtf.org" target="_blank">Cfrg@irtf.org</a><br>
<a href="https://www.irtf.org/mailman/listinfo/cfrg" rel="noreferrer" \
target="_blank">https://www.irtf.org/mailman/listinfo/cfrg</a><br> \
</blockquote></div><br></blockquote></div></div></body></html>
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic