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

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 <bascule@gmail.com>:

> On Sun, Feb 10, 2019 at 1:50 PM Leo Perrin <leo.perrin@inria.fr> 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 <smyshsv@gmail.com>
> 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 <akr@akr..io <akr@akr.io>>, cfrg@irtf.org <cfrg@irtf.org>
>
>
> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>