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

[Alyssa Rowan <[e-mail]>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 28/01/2015 14:14, Stanislav V. Smyshlyaev wrote:

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

Even a _partial_ second-preimage presents a significant problem here,
which is the big problem with the SEC1/NIST approach - and unless I'm
misunderstanding of course, the one you've taken?

A simple brute force partial second-preimage search lets you cook a
seed which yields a hash (even with a theoretical perfect hash
function) with as many bits as you can brute-force (64, no problem;
70-80, maybe for some?), and thus covertly select curves with
properties one desires (and perhaps, which we don't desire!) even down
to, say, p=1/(2^63).

Now I wouldn't characterise those properties as "very probable" to
occur by random chance at all, or indeed a large class - but it's
definitely a totally feasible condition to force for anyone who gets
to freely choose the seed.

That's why our draft rigid generation process doesn't use seeds - and
why anyone who does use seeds needs to be incredibly careful to the
extent to which anyone _can_ choose them (BADA55 being a demonstration
that a 'verifiably pseudo-random' process needs to be careful too, as
the mere choice of primitives and constants in the process may allow
enough of a degree of freedom to affect the outcome to force a
one-in-a-million choice).

So… who did choose W? Or, if W is a hash output itself, who chose the
seed for that? (The attack still works on iterated hash functions.)

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJUySSsAAoJEOyEjtkWi2t6HKIP/1OfbTbsADv0gUI2cywXmINM
2WTc3ulsMMEPDI/LIp15Dg8BEZJHQAiUWpZGcRGAvPyX6X27Uo+Jol2+Ab2G/EAh
zRLkw0HKnaACGpJftLKDoOZmwa2myLJWjVANz3YhRqu9HOee+IbPO1nelQMVJn89
hEg7h/JcPHQT65/PuXDE5ZVCwbJSfth3/LxS0bmkLeC1hGdr+bHuhPvf298vtk+d
ZlcmL5oiexCs+2Io63U6CTL9+XT881su75aMfMK+8cW9SphV6IASocSmhPotAJns
blYCnvBxAKNZD5cgHlgx7TV/9bhO14n8AT7ausUT6cwLzRj6kJT6fsBreeiNZagy
SC2j6WOFYgThyGbUz6xoot/bHpmP0zGVxeQwKmTIVjlD4IHmSA7dpf2wCCJSkkhI
DYfc7bAPKOl2+DXn43DRJ6uyGAOfpU+/oKkzUzyIklhP/7B17F1PBNMKVIgySKtC
ccozug5LNcwHfuzxpJVITDR9YvAwxDkcGuD0dVetaH4wY/F/4n2YWqhqQd7PTZgk
NtO0HhsoL610CpfVrB1PsIHvPWRwt8pAzi3k0oJMxjg7PB1bmVMj6Xv/BctvA4ki
BDiMKr9k9ZCSgwlFxkQR3568v993g72vUh6NwbSfChqxvZBcKnx1MayF8wQhjC96
FtOdtZJ9NDzZlO0QNbvw
=gvRr
-----END PGP SIGNATURE-----