[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

On Thu, Jun 26, 2014 at 2:47 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>
> On Jun 26, 2014, at 10:35 AM, Trevor Perrin <trevp at trevp.net> wrote:
>
>> On Wed, Jun 25, 2014 at 10:21 PM, Mike Hamburg <mike at shiftleft.org> wrote:
[Trevor]:
>> But it still seems odd to tie private key generation to a fixed hash
>> function.  If we start losing confidence in SHA512, do we throw away
>> all these keys?  If I'm building a system based on SHA3, do I have to
>> include SHA512 just for keygen?
>
> The Goldilocks code effectively defines two things:
> * The curve, and point operations on the curve
> * A library to do basic algorithms (currently encrypt and sign) using the curve.
>
> Perhaps the library should be factored differently from how it is, to aid people who are just using the curve.  But the current way is that if you’re using the library’s version of things, then your PRNG is ChaCha, your hash is SHA512, your point format is 1/sqrt(x), and your key storage format is either the full 144 bytes (sym,scalar,pub) or just the 32-byte sym.
>
> If you aren’t using the library, you aren’t bound to its keygen.  Take a random number and reduce it mod q, and you’re done.

I like that you're providing a full system, with good choices already
made.  Since the private key is connected to the nonce key, and nonce
hashing is connected to signature hashing, and signature hashing is
connected to the public key format, it makes sense to design things
together.

But it would also make sense for the design to allow hash agility and
arbitrary private keys, IMO.


>> What if Goldilocks keygen was simply:
>>
>>  private_scalar[56] = random_bytes(64) % q
>>
>> (where q is main subgroup order)
>>
>> Then people could use more conservative or context-specific choices for the RNG.
>
> I’m open to changing the library so that sym is used as a symmetric nonce, and the private key storage format is 56 or 112 bytes.  This is only kosher under some assumptions about the hash function (eg, it’s a random oracle), but I’m basically OK with that in the name of simplicity.

OK.  If you were to write this as a spec, what about recommending a
separate nonce key, but allowing the private scalar as a nonce key if
implementations don't want to store an extra key?

So overall advice like:

"""
nonce_key = either
 - random(32) generated as part of private key (preferred), OR
 - private_scalar

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

Where q is the main subgroup order, and HLEN is the output length of
the hash, which must be at least 64 bits greater than q (i.e. at least
510 bits for Goldilocks).

In rare situations, you can do either (BUT NOT BOTH!!!) of:
 (a) set the random bytes to zeros, for deterministic sigs or if
random is untrusted
 (b) omit the message, for large messages or precomputation (but only
if random is highly trusted)
"""

Separate but related: if you're using prefixes for distinct random
oracles, perhaps do the same for the signature hash?

sig_hash = HASH("signature" || R || pubkey || message)


>> What about:
>>
>> sig_nonce[56] = HMAC-HASH("signonce" || private_scalar, random(64) ||
>> message) % q
>
> I am happy to stir some randomness into the signonce process.  Is there a clear disadvantage to doing this, other than locking the RNG?

DJB brings up a malicious RNG that knows the message and private key,
but lacks any way to exfiltrate data except through the signature
nonce:

http://blog.cr.yp.to/20140205-entropy.html

I think that's pretty unlikely, and would rather have the
randomization in most cases.  But I could be wrong.


Trevor