[curves] Generating nonces for Schnorr signatures

[Mike Hamburg]

On 6/25/2014 5:56 PM, Samuel Neves wrote:
> On 26-06-2014 00:37, Trevor Perrin wrote:
>>   * Goldilocks uses envelope-MAC for the nonce, Ed25519 doesn't care
>> about length extension.  I can't think of a reason length extension
>> matters?
>>
>>   * Seems like it would be more traditional for nonce derivation to pad
>> the secret key out to a full SHA512 block (128 bytes), HMAC-style.
> I was under the impression that envelope-MAC, by definition, required at least the prefix to be block-sized [1]. But the
> message should also be padded to block-size, to avoid some largely impractical attacks that result from the suffix key
> possibly overlapping into 2 separate blocks. [2, Section 6] has a good overview on the history and padding issues of
> envelope-MAC.
Yeah, you're right.  Goldilocks' not-quite-envelope-MAC is basically a 
placeholder for "some hash-based PRF", and is sloppily done.  I think 
it's on the TODO list, but if not, it should be.

>
> I don't think any of this has much relevance to the nonce generation setting. Neither does length extension: if we are
> able to mount a length-extension attack, we must already have some way to recover the nonce (that is, the SHA-512
> state), a far more devastating attack.
Not in practice, but I'd like to use a PRF because that's Obviously The 
Right Thing.  For key generation and obliterating bad state, a 
fixed-length PRF is good enough, though maybe using the same PRF for 
both things (with a suitable diversifier) would be a good idea before 
flipping the switch from experimental to stable.

Is there a standard way to use SHA3 as a keyed hash?  Is it sufficient 
just to prefix the message with the key?  I'm not tied to SHA2, I just 
had an implementation lying around so it was easy.
> [1] G. Tsudik. "Message Authentication with One-Way Hash Functions", 1992, https://www.ics.uci.edu/~gts/pubs.html
> [2] N. Koblitz and A. Menezes, " Another Look at Security Theorems for 1-Key Nested MACs", 2013,
> http://eprint.iacr.org/2013/248
Thanks for the refs,
-- Mike