[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

On Fri, Jun 27, 2014 at 10:20 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>
> On Jun 27, 2014, at 1:08 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> 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
>
> I think I prefer hashing the randomness, which is fine so long as the hash is entropy-preserving and the RNG is not malicious.

Not sure what you mean by "entropy-preserving" - if an attacker can
cause collisions or severe biases on a hash with unknown prefix then I
would guess that property is being violated, which is where XOR with
good RNG adds more robustness.


>  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.

If the hash is truly awful you're screwed for forgeries, but XOR with
good RNG still prevents your key from being revealed.

So when the RNG is good, I think XOR-the-RNG is clearly better.

If the RNG is omnisciently bad, like the DJB blog, then it can leak
your private key either way (by brute-forcing a bias, for example).
So I'm not sure there's a real difference here, except that XOR makes
it more obvious to implementors that the RNG can control the nonce -
which I think is good.

If the RNG is not omnisciently bad and the hash is good, then things
are fine - no difference.

The only argument for hash-the-RNG I see is that if the RNG is weak
*and* the hash is weak, *maybe* the RNG is at least good enough that
it "salts" the hash and improves it more than XOR would?

I think that's more fussy than even I'd go, but you could do both:

sig_nonce =
(random(HLEN) XOR HMAC-HASH("sig_nonce" || nonce_key, random(HLEN) ||
message)) % q


Trevor