[curves] Generating nonces for Schnorr signatures

[Samuel Neves]

On 06/29/2014 05:06 AM, Trevor Perrin wrote:
> 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).

If history teaches us anything is that RNGs fail more often that hash functions's PRF property; even MD4 is fairly OK as
far as HMAC is concerned (I'm aware of [1, 2], but compare that to generating collisions by hand on the same function).
You need a truly pathological hash function for this to become a problem.

Therefore I would give priority to hashing rather than the RNG. Additionally, the RNG enables a covert channel to
transmit information to the outside world. I don't mean this in the bruteforcing sense, as suggested before; I mean
something much simpler.

Suppose an attacker can send messages to be signed at will: if the RNG wants to send a 0, it'll output all-zeros, and
this will result in a deterministic signature, which is easily detected by signing the same message twice. If it wants
to send a 1, it will generate random bytes as usual. This does not even need to be the result of a malicious RNG --- it
could be something else acting on the system (say, malware), which disturbs the normal functioning of the RNG. For
example, RDRAND can be made to output all-zero (if the carry flag is left unchecked) by running it in all CPU threads
simultaneously.

[1] http://eprint.iacr.org/2006/187
[2] http://www.di.ens.fr/~fouque/pub/crypto07b.pdf