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

["D. J. Bernstein" <[e-mail]>]

Nico Williams writes:
> replacing M with H(M) in the second hash

This makes the signature scheme vulnerable to collisions in H. This
_shouldn't_ be a problem, since the community puts a lot of effort into
designing hash functions for which finding collisions seems to be
extremely difficult; but it's safer to build collision-resilient
signature systems, using collisions as an early-warning mechanism.

Of course, it's up to the user what to sign with a collision-resilient
signature system. In particular, instead of signing m, the user is free
to sign H(m). This throws away collision-resilience, but it can improve
cost in some applications: specifically, if H is one-pass while the
signature system isn't, then the whole procedure of signing H(m) is
one-pass, and this saves time when m doesn't fit into fast RAM. But this
combination clearly shouldn't be the default: security is job #1, and
the number of passes is irrelevant to most applications.

Similarly, the user is free to use a deterministic signature system to
sign (r,m), where r is chosen randomly for each message. This type of
randomization can in some situations reduce the cost of protecting
against, e.g., EM attacks. But again this shouldn't be the default: it
makes testing harder for everybody, raises kleptographic questions, etc.

Here's a related excerpt from http://blog.cr.yp.to/20140323-ecdsa.html:

   _Maximum security_. Ed25519 actually generates k by hashing the
   secret key together with the entire message. Very fast "PRFs" used to
   authenticate messages, such as VMAC, are safe here, but Ed25519
   simply uses SHA-512 since it's quite rare for this to be a noticeable
   bottleneck. Using an RNG wouldn't break interoperability, but the
   safest option is the default. Using Ed25519 to sign H(m), rather than
   m, would mean hashing m only once (at the expense of collision
   resilience), but again the safest option is the default.

---Dan