[curves] XEdDSA specification

[Trevor Perrin]

On Fri, Oct 28, 2016 at 12:47 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Fri, Oct 28, 2016 at 2:40 AM, Brian Smith <brian at briansmith.org> wrote:
> [...]
>> Consider this "best of both worlds" scheme:
>>
>>      r = hash1(a || [first half of Z] || M || [second half of Z])

Samuel Neves mentioned (off-list) that with SHA512's 128-byte block
size, a and M would still be mingled together in the first block.

So I'm thinking about this:

  a || Z || pad || M

where "pad" adds zero bytes to fill the hash block (so 32 bytes with
25519 and SHA512, since |a|=32 and |Z|=64).

Rationale:
 (1) In the Random Oracle Model, this is no different from hashing "a
|| M || Z".
 (2) Processing the secret inputs (a and Z) in a separate block (or
blocks) from M seems cleaner
 (3) Mixing the secret key with secret random data (Z) prior to mixing
it with known input (M) is better for resisting physical sidechannels
(power, EM).
 (4) The prior rationale for hashing Z at the end was weak:  It might
help protect a very weak hash where the attacker was able to choose M
to force biases or collisions, even with unknown and randomized
prefix.  But I think the sidechannel threat is more plausible.
 - We could consider a || Z1 || pad || M || Z2, but the risk of (4) is
low enough that I doubt that's worth the complexity

Thoughts?

Trevor