[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

On Sat, Jun 28, 2014 at 7:51 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On 6/28/2014 1:47 PM, Trevor Perrin wrote:
>>
>> 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
>
> Doing both is almost certainly not better than just XORing, since XORing is
> going to fail only if the hash is bad and the RNG is soso; or if the RNG is
> stupidly malicious.

Even with XOR, I'd consider doing both in the case where the user
wants to omit hashing the message (due to message size or a desire for
precomputing the scalar mult).  I.e. replace nonce = RNG() xor
PRF(message) with nonce = RNG() xor PRF(RNG()), so you'd survive a
biased-but-nonrepeating RNG.


> I dunno.  I'm convinced that a proper PRF should be used (HMAC or SHAKE or
> something) and that the RNG should be used by default, but I think the order
> doesn't matter much -- any issue there is way down the threat list.

Not much, but I do think XOR has a better redundancy argument: if
either the hash or RNG fails independently, the private scalar will
not be revealed.  (And that's true even if the private scalar is a
direct input to the nonce hashing, which is a convenience I think
should be allowed.)

Aside from security, I think the clarity of the XOR would help
implementors reason about it (what happens if we omit the RNG?  what
happens if it's malicious?  what happens if the hash is bad? - these
are simpler to answer with XOR).


Trevor