[curves] Generating nonces for Schnorr signatures

[Michael Hamburg]

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:
>> 
>> The curve is designed to be ~2^223 secure.  If the scalar and nonce are
>> chosen by a pseudorandom generator and function, respectively, with ~2^256
>> security, then they are indistinguishable from random for an attacker acting
>> within the security estimate.
> 
> With that argument I'd expect HMAC (or at least pad-key-to-blocksize,
> so it could be analyzed similar to [1]).

It should be HMAC or pad-key-to-blocksize.  The lousy not-quite-envelope-MAC is a placeholder.

> 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.

> 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.

> ---
> 
> I still wonder if the Goldlocks/Ed25519 signing-nonce scheme could be improved:
> 
> * The entire message is hashed twice (once for signing nonce, once
> for Schnorr hash).  That could be costly for large messages.  DJB
> suggests signing Hash(message) for large messages [2], but this loses
> collision-resilience, one of the main benefits of Schnorr signatures.
> 
> * A pair of messages that produce a collision for signing nonce (but
> not for Schnorr hash) would leak the private key.  I assume finding
> collisions with a hidden prefix is much harder than finding general
> collisions (is there a name for this?).  But against such a thing,
> deterministic Schnorr would be *less* resilient than ECDSA (for which
> collisions forge signatures but don't leak the key).

This seems like a pretty unlikely attack.

> * It assumes private keys generated from a master key, so is not
> obviously compatible with private keys generated other ways.
> 
> 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?

> (where HASH outputs >= 512 bits, to follow NIST advice by reducing a
> value at least 64 bits larger than q - your 448-bit values fit nicely
> here).
> 
> In unusual situations, you could choose to omit *either* the random
> (deterministic signatures), or message (for large messages, where you
> trust your RNG).

Or for precomputing signatures, if we care about that.  Sure.

> Benefits:
> * Supports different hash algorithms
> * Supports arbitrary private keys
> * "signonce" prefix helps in RO analysis (e.g. joint DH/signatures)
> * HMAC is most-studied PRF-from-hash construction
> * randomizes each nonce hash, which I assume helps collision resistance?
> 
> Trevor
> 
> [1] http://cseweb.ucsd.edu/~mihir/papers/hmac-new.pdf
> [2] http://blog.cr.yp.to/20140323-ecdsa.html

Cheers,
— Mike