Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Yoav Nir <[e-mail]>]

> On May 3, 2015, at 2:14 PM, Alexey Melnikov <[e-mail]> wrote:
> 
> CFRG chairs are starting discussion of the next topic.
> 
> The consensus view of the mailing list was that NIST compliance of our selected
> signature scheme is not necessary, opening up the opportunity for us to
> consider a rich class of signature schemes beyond ECDSA.
> 
> Most if not all signature schemes defined over elliptic curves can be
> de-randomised by generating the "random" value used during signing in a
> pseudorandom manner from the message to be signed. This ameliorates some
> catastrophic failure modes for these schemes. The generation could involve
> using a PRF such as HMAC with a key designed solely for this purpose
> (resulting in an augmented private (signing) key). An alternative could be
> to hash a string consisting of a concatenation of the private (signing)
> key with the message to be signed. There are other possibilities too.
> Several methods are described in detail in RFC 6979
> (http://tools.ietf.org/html/rfc6979 <http://tools.ietf.org/html/rfc6979>).
> 
> To determine the way forward, we are going to conduct a poll to determine
> how we should tackle the question of de-randomisation. Please pick one of the
> options specified below:
> 
> 1. CFRG should stick to randomised signature schemes only.
> 
> 2. CFRG should adopt deterministic signature scheme only.
> 
> 3. De-randomisation should be an optional feature for implementers to
> decide upon (i.e. both choices 1 and 2 allowed).

#2.

Random number generation is one of the weak spots of a lot of cryptographic libraries. Either they get the PRNG/DRBG wrong, or even when they get it right, they rely on a problematic source for seeding. 

Things might work fine on regular servers, then lose their entropy when running in a virtualized environment. Very often the entropy comes from a source that is outside the control of the cryptographic library and may or may not be reliable depending on the running environment. 

Deterministic works for everybody. Randomized works not for everybody. Better go with #2.

Of course de-randomizing doesn’t buy you much if you use the signature as part of a protocol such as TLS that requires random bytes, but removing one thing that relies on the RNG is better than not doing it.

Yoav