[curves] Generating nonces for Schnorr signatures
Trevor Perrin
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":
>>
>> 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
More information about the Curves
mailing list