Subject: [Cfrg] Verifiably hard-to-find random curves (Was: ECC reboot)

From: David Leon Gil <[email-masked]>
Date: Tue, 21 Oct 2014 14:21:40 -0400

On Tue, Oct 21, 2014 at 9:12 AM, Alyssa Rowan <[email-masked]> wrote:
>
> Perhaps I'm confused, or perhaps there's a language barrier? The position paper you posted says that Brainpool wants pseudorandom prime curves, whose description *exactly* matches those of the existing Brainpool curves, but generated via some (unspecified, yet assumed trusted) new process; that you want these alongside special curves; and you want the PSR curves to be mandatory to implement.

There are some problems with the current Brainpool curves; in
particular, brainpoolP256t1 has a very insecure twist.

--

But I agree: It is hard to generate random numbers by consensus.

1. I tend to think that CFRG/Brainpool/someone should recommend -- for
applications that *need* random curves -- a new process to generate
verifiably random primes and curves starting from a seed that meet the
SafeCurves+Brainpool conditions.

2. There is, however, another possibility; suggested by djb's BADA55
exercise (especially for special primes):

a. Require, as in BADA55, that the high order bits of the curve
parameter are equal to something simple and pseudorandom. E.g.,
Salsa20(k=0,n=0,0)[0:64].

b. Find a matching (safe) curve. (Starting from a public "verifiable"
seed, if you like.)

c. Suppose that fewer than 2^-32 of curves are weak; an adversary will
require 2^96 trials to find a weak curve that satisfies this
condition.

This only requires agreement that prescribing a pseudo-random
bitpattern is not likely to be correlated with curve weakness.

(I still dislike this idea, as compared to a rigid choice, and see
little point in doing it.[**] But it seems better than trying to
specify a new seed/generation procedure, where there are many
choices.)

- dlg

[*] Is the list of reasonable choices longer than, e.g.:
- {Salsa,ChaCha}20(k=0*256, n=0*8)
- SHAx-x('')
- AES-x[k=0*x](0*128)
- {BLAKE,blake2{b,s}}('')

This is still << than 2^8 choices for the adversary.

[**] In particular, it is a purely linear difficulty tradeoff.