[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

On Wed, Jun 25, 2014 at 10:21 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On Wed, Jun 25, 2014 at 4:37 PM, Trevor Perrin <trevp at trevp.net> wrote:
>> So Ed25519 and Goldilocks are similar in generating the private scalar
>> and signing nonce from a "master key":
>>
>> Ed25519
>> --------
>> private_scalar[32], nonce_key[32] = SHA512(master_key[32])
>> sig_nonce[32] = SHA512(nonce_key[32] || message) % q
>>
>> Goldilocks
>> --------
>> private_scalar[56] = SHA512("derivepk" || masterkey[32])
>> sig_nonce[56] = SHA512("signonce" || masterkey[32] || message ||
>> masterkey[32]) % q
>>
>>
>> Qs
>> * Is it weird that the range for Goldilocks private scalar and nonce
>> is size 2^256, rather than the size of the main subgroup (~2^446)?
[...]
>
> 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]).

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?

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

 * 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

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

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