[curves] Generating nonces for Schnorr signatures
trevp at trevp.net
Thu Jun 26 10:35:33 PDT 2014
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":
>> private_scalar, nonce_key = SHA512(master_key)
>> sig_nonce = SHA512(nonce_key || message) % q
>> private_scalar = SHA512("derivepk" || masterkey)
>> sig_nonce = SHA512("signonce" || masterkey || message ||
>> masterkey) % q
>> * 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 ).
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 = 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 , 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.
sig_nonce = 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
In unusual situations, you could choose to omit *either* the random
(deterministic signatures), or message (for large messages, where you
trust your RNG).
* 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?
More information about the Curves