[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

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