[curves] Sig nonce generation
trevp at trevp.net
Sun Jul 27 16:32:20 PDT 2014
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 .
(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 .
(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 .
(D) A PRF so weak an attacker could submit a pair of messages which
produce a nonce collision, thus leaking the private key .
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 .
Mike Hamburg has suggested applying the PRF to both the message and
RNG output, e.g.:
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" .
- 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 ?
- For the HMAC(MSG||RNG) approach, is there a difference in hashing
the MSG before or after the RNG?
More information about the Curves