[curves] Sig nonce generation

[Trevor Perrin]

On Fri, Jul 25, 2014 at 10:56 AM, Michael Hamburg <mike at shiftleft.org> wrote:
> I was conveying the results of our signature nonce generation discussion to CFRG, and I realized a problem with PRF(message) xor random().
>
> If your random number generator is broken, it might have near-collisions.  Near-collisions lead to near-colliding nonces, which leaks the key.


Good point, I was wrong there.

To recap: we want to generate a Schnorr signature nonce which is
uniformly random for each message.

Obvious options are to use an RNG, or to use a PRF (such as
HMAC-SHA512) with a secret associated with the private scalar (or
derived from the private scalar), and with the message as input.

We're considering resilience against failures of varying plausibility:

 (A) A bad RNG that produces low-entropy outputs [1].

 (B) A malicious RNG that can "see" how its output will be used so is
able to bias the nonce and leak the private key [2].

 (C) A malicious RNG that exfiltrates data via a "covert channel" by
switching between random output and a constant when the same message
is signed repeatedly [3].

 (D) A PRF so weak an attacker could submit a pair of messages which
produce a nonce collision, thus leaking the private key [4].

Samuel Neves suggests avoiding (A) through (C) by avoiding RNGs, and
hedging (D) by combining two different PRFs, e.g. one based on
HMAC-SHA512 and one based on AES, though combining them in a way that
maximizes security isn't trivial [5].

Mike Hamburg has suggested applying the PRF to both the message and
RNG output, e.g.:

nonce =
  HMAC-SHA512("nonce" || private_scalar, message || RNG()) % q

This resists (A) provided the PRF is good, and resists (D) under the
(reasonable?) assumption that "H(anything||r would have
not-too-much-less entropy than r" [6].

Questions:
 - For the 2 PRFs, which would people choose and what's the best combiner?
 - For either approach, is it OK to use the private scalar for the PRF
vs an independent key like in Ed25519 [7]?
 - For the HMAC(MSG||RNG) approach, is there a difference in hashing
the MSG before or after the RNG?

Trevor


[1] https://moderncrypto.org/mail-archive/curves/2014/000254.html
[2] http://blog.cr.yp.to/20140205-entropy.html
[3] https://moderncrypto.org/mail-archive/curves/2014/000240.html
[4] https://moderncrypto.org/mail-archive/curves/2014/000218.html
[5] https://moderncrypto.org/mail-archive/curves/2014/000255.html
[6] https://moderncrypto.org/mail-archive/curves/2014/000227.html
[7] https://moderncrypto.org/mail-archive/curves/2014/000212.html