[curves] Sig nonce generation

[Trevor Perrin]

On Sun, Jul 27, 2014 at 8:35 PM, Jon Callas <jon at callas.org> wrote:
> On Jul 27, 2014, at 8:24 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
>
>> What's wrong with deterministic signatures ala Ed25519 and RFC 6979?
>> All these questions about untrusted RNGs are easily solved for
>> signatures.
>
> Thank you. You got to the point I was making badly. If you use deterministic DSA, it doesn't matter what your RNG does.


Deterministic DSA and Schnorr are a little different:

x = private key

DSA
----
m = hash(msg)
k = HMAC(x, m) # deterministic nonce
r = g^k
s = (k^-1)(m + rx)
signature = (r,s)

Schnorr
--------
k = HMAC(x, msg) # deterministic nonce
r = g^k
m = hash(r || msg)
s = k + mx
signature = (r,s) or (m,s)

With DSA, if you can find a hash collision (msg1, msg2) you can submit
msg1 to forge a signature on msg2.

With Schnorr, you can't do that as easily since the HMAC and hash are
randomized.  But with deterministic Schnorr if you can find a (msg1,
msg2) which produce a nonce collision _despite_ the secret HMAC key,
and which don't also produce a collision on m, then the private key
can be calculated from the two signatures.

That's unlikely, but if you calculate the nonce as:

k = HMAC(x, msg || random())

then it's more unlikely.

If the hash is so weak this matters the attacker can probably still
forge signatures via collisions on m, but that's less damaging than
stealing the private key.

If the RNG is malicious and knows x it can bias k so as to leak x.  A
malicious RNG can also do "covert channel" signalling.  But I'd argue
those are unlikely threat models.

Maybe I'm down a rathole, but private keys are important, leaking them
is the end of the world, isn't that worth extra care?

Trevor