[curves] Generating nonces for Schnorr signatures

[Mike Hamburg]

On 6/28/2014 1:47 PM, Trevor Perrin wrote:
> 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.
That's a good point.  I was thinking that the fresh randomness is 
somehow superior to the key... which it probably is, but probably only 
after the point where you lose anyway.

Keccak is entropy-preserving in that the state cannot lose entropy, 
because the update function is a permutation.  This means that if the 
state is random at some time, it cannot be made less random, though I 
suppose that if it doesn't have the full 1600 bits of entropy an 
attacker might theoretically be able to "herd" the entropy into one part 
of the state or another.

Likewise, one might hope that H(anything||r) would have 
not-too-much-less entropy than r.  So hashing randomly at the end might 
be better than at the beginning.  Maybe.
>>   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.
Sure.
>
> 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.
Maybe.  I was thinking of cases where the RNG is malicious but ignorant, 
and can see what it's being XOR'd into but can't do big computations.  
When RDRAND was integrated into /dev/random there was some concern about 
this model.  But pretty much any of these models is really unlikely.
> 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
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.

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.

-- Mike