[curves] Generating nonces for Schnorr signatures

[Michael Hamburg]

On Jun 27, 2014, at 1:08 PM, Trevor Perrin <trevp at trevp.net> wrote:

> On Thu, Jun 26, 2014 at 2:47 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>> 
>> On Jun 26, 2014, at 10:35 AM, Trevor Perrin <trevp at trevp.net> wrote:
>>> 
>>> * A pair of messages that produce a collision for signing nonce (but
>>> not for Schnorr hash) would leak the private key.  I assume finding
>>> collisions with a hidden prefix is much harder than finding general
>>> collisions (is there a name for this?).  But against such a thing,
>>> deterministic Schnorr would be *less* resilient than ECDSA (for which
>>> collisions forge signatures but don't leak the key).
>> 
>> This seems like a pretty unlikely attack.
> 
> Probably.  But another risk is that messages could be chosen to force
> a few known bits in the nonce, which might leak the key (e.g. [1]).
> 
> To modify last suggestion, what about XOR'ing the PRNG contribution,
> instead of mixing it into the hash?
> 
> """
> nonce_key = either
> - random(32) generated as part of private key (preferred), OR
> - private_scalar
> 
> sig_nonce = (random(HLEN) XOR HMAC-HASH("sig_nonce" || nonce_key, message)) % q
> """
> 
> This makes it easier for DJB's malicious RNG to steer the nonce, but a
> malicious RNG can brute-force a bias and leak the private key anyways,
> so we might as well make the risk obvious.
> 
> Going the other way, no matter how bad the hash, the nonce will be
> good if the RNG is.
> 
> ?
> 
> Trevor
> 
> 
> [1] http://eprint.iacr.org/2013/346.pdf

I think I prefer hashing the randomness, which is fine so long as the hash is entropy-preserving and the RNG is not malicious.  Because if the hash is truly awful then you’re screwed anyway, but if the RNG is straightforwardly malicious, then it could bias bits through the XOR.  Not that either of these is at all likely.

— Mike