[curves] Sig nonce generation

[Michael Hamburg]

On Jul 27, 2014, at 6:52 PM, Jon Callas <jon at callas.org> wrote:

> 
> On Jul 27, 2014, at 4:32 PM, Trevor Perrin <trevp at trevp.net> wrote:
> 
>> 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?
> 
> Ages ago, in PGP, when we started using DSA, we were concerned about RNG issues. We hashed together the secret key along with the RNG output, as a keyed hash with the secret key as the key. These days, the stylish thing to do would be to HMAC the RNG output with the secret DSA key as the HMAC key.
> 
> I'd recommend keeping it simple and not gild the lily too much. If your hash function is good, it doesn't matter what you throw in. But the attacker has complete control of the message, and I'd be wary of throwing it in. You can safely assume the attacker doesn't have control of the private key (because if they do, then they can just do anything they want). So you'd want to come up with a reason why your construct is better than simply hashing/HMACing the RNG output with the private key.
> 
> 	Jon


The reason to include the message is that if the nonce repeats and the message does not, then you leak the secret key.  This only matters if you’re worried about the RNG repeating, but it seems like a valid concern.

Cheers,
— Mike