Re: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization

["Stanislav V. Smyshlyaev" <[e-mail]>]

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).

We believe that there really cannot be a higher level of "proven
randomness" than using d with a known hash preimage (regarding to
properties of hash function, of course).

The only one option to get a "backdoored" curve with our method that I
understand is the existence of some large publicly unknown class of "bad"
("backdoored", subverted) curves. But if such a class exists, who can
guarantee that any of your generated curves doesn't belong to this class?..

P.S.:
Nevertheless, for that exact twisted Edwards curve we have also a preimage
value of first 512 bits of W (we did this only to organize process of
candidate curve generation in parallel, without too much need also though),
but I had to mention this (pretty useless) fact.

Best regards,
Stanislav V. Smyshlyaev, Ph.D.,
Head of Information Security Department, CryptoPro LLC


2015-01-28 16:28 GMT+03:00 Alyssa Rowan <[e-mail]>:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> On 27 January 2015 15:57:40 GMT+00:00, "Станислав Смышляев" <
> [e-mail]> wrote:
>
> >The curve parameters have been generated using random nonce W in such way
> that e = 1, d = hash(W), where hash() is Russian national standard GOST R
> 34.11-2012 hash function (also known as “Streebog”,
> https://www.streebog.net/en/). The seed value W is equal to:
> >W = 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F6 A5
> AF 09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2 5E
> AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7E
> D6 D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,
>
> ...and the million-rouble question, if I may be the first to ask:
>
> How was that seed W generated, and under what criteria?
>
> There is now a strong preference for open curve generation processes whose
> criteria are all explicitly shown, chosen for clearly-defined "rigid"
> reasons, and whose generation can be replicated and verified.
>
> I can't see the procedure you show here has that property, due to the
> unexplained seed; a property it shares with the US standard NIST curves
> we've been asked to replace, so I'm not too sure as to the merits of your
> curve?
>
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
> Version: APG v1.1.1
>
> iQI3BAEBCgAhBQJUyOPlGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
> jtkWi2t6rbAP/0/Cz+7r1IIf8spVLUVeAxtrgdsuKvtRt6Dpz5vkNiiS/pwRXpVF
> /70MbeBQA4M2ak7enzYGnRI/I2hGAv6nV6ybTwwnPDjq33iBS6F16sV7KsBaLRcy
> 7KmUTYKIT7oTncTWTDO0zlgo2k+/Hy1G/ChmnOLBFH6peKSwgt8OJgEPe0rZbg8E
> pTukrmr8lDw18MiGPhoqnj7Ug46ydJhqqZkP0aT3xtSF8Y+lVEpn7O36QV03QnAU
> d/0oQCQHkHJBfcI9w2W6tiyI6iHFH40U3c78kdASLdWjHyOfYZ/P00BasQudWcvD
> kgqYVGrZMXkrIQvn1JnMt5PD5Wl+XN6/6csAkeUOBr9oTwwWnX9xmvT+Ly14TFw2
> fw5/WaMKYht9K//qPh0hQLHCZuG0NEx/0pcoTTgYSGyXOIlAx19gDSbybmd/+ssj
> 9/ttSN+t9eENghr1IcXRMCrPcxbwnQRS2dQYGzCmqohf0ZS3DIzYAI2ChMT5eLNl
> lD9iSluaf7ss2/qlzwu+4kw25qDR/JwgKL8gmC0jhDE1ID4e8P4/ovpj3EwlW47S
> 2tRBD1XhRR0L1ZLiA5za+LLHPg9kUgFVnZ9kMhpm0ATE/bZzAujwFG1rlHmhLxiC
> RsU3euvrcb8QPcdLkNLunoCv71QSiCyABeUIG0jFKdU+oA4VoTkP+LWV
> =BuQY
> -----END PGP SIGNATURE-----
>
>