[curves] XEdDSA specification

[Trevor Perrin]

Thanks for good feedback, responses below:


On Thu, Oct 27, 2016 at 2:08 AM, Brian Smith <brian at briansmith.org> wrote:
>
> In the motivation for the randomized scheme, the document says "However, if
> the same message is signed repeatedly, a glitch that affects the calculation
> of h could cause this to happen (an observation due to Benedikt Schmidt)."
> Could you provide a reference to a paper/message that explains what is being
> referred to here, and/or add a description of the issue to the paper?

Sure, what do you think needs to be clarified, exactly?  The math
seems clear, I'm guessing you think "glitch" attacks need to be
defined?

Benedikt points out this is more relevant to hashing large messages;
it's also more revelant to VXEdDSA, where "h" is encoded as part of
the signature, so those seem like good points to add.


> In xeddsa_sign, why set:
>
>       r = hash1(a || M || Z)
>
> instead of one of:
>
>       r = hash1(Z || a || m)
>       r = hash1(a || Z || M)?
>
> It seems like it would be better to incorporate the randomness into the
> state of the hash function as early as possible to reduce risk of some
> (non-timing) differential side-channel attacks on the hashing step.

I don't think it matters much.

But if an attacker could choose M to cause a collision between M1 and
M2 or biased output, even with unknown/randomized prefix, then hashing
Z at the end might be better [1].

That's an unlikely scenario.  But hashing Z at the end also makes the
design look like EdDSA a little more, as the first two inputs are
secret key, then message, same as EdDSA.

You mention "differential" side-channel attacks against the secret key
"a", but adding randomness before the secret key would make those
attacks easier if the randomness leaks (e.g. a predictable RNG), so
that's not obviously an improvement with respect to side-channels.


> Why is Z fixed at 64 bytes? That is, why is its length not a function of the
> size of the key and/or the digest function output length?

Ed25519 was specified to reduce a 512-bit hash output to produce its
nonce, so it seemed most consistent to add 512 bits of entropy.  Since
these values/sizes are also suitable for 448, we don't bother changing
them.

512 bits of hash output / entropy is overkill in all these cases, but
it's simple to specify and easy to implement.   Taking 64 bytes from
the RNG might add some defense in depth if the RNG is slightly weak.


> Do you have any suggestions for how one would mark a key as to whether it is
> intended to be used for X25519 and/or EdDSA and/or XEdDSA and/or VXEdDSA?

You can use X25519 or X448 keys for any of these algorithms.  If you
want to keep them separate that's traditionally a higher-level thing
(e.g. keyUsage bits).


>
> The security considerations say that the caller "must pass in a new secret
> and random 64 byte value each time the signing function is called." I
> suggest s/64 byte value/**Z**/. Also, it would be nice to clarify the extent
> of the badness if a Z value were to be reused.

OK, will note to clarify.


> Would you be open to using a different name than `q` for the order of the
> base point? `q` is commonly used in code and specifications to refer to what
> this paper calls `p`. Another name would be less confusing. The EdDSA RFC
> uses `L`, IIRC.


For "plain" DSA (i.e. non-elliptic-curve DSA), it's pretty
conventional to use "p" for the field prime and "q" for the subgroup
order (e.g. FIPS 186, Wikipedia, RFCs 6979, 3279).

Some math is "mod p", and some is "mod q", so (p,q) make a good pair,
and that was loose inspiration for the XEdDSA choice.

For EC-DSA (not EdDSA) the SEC1 and FIPS-186 standards use "p" for the
field prime, but "n" for subgroup order.  Bitcoin follows that (p,n)
but I don't think "n" is any better than "q".

The Ed25519 and EdDSA papers use "q" for field prime and "l" for
subgroup order.  Not sure why "l" was chosen, it's a problem character
(looks like "1" and "I").  There's a CFRG Draft that uses (p,L) but
XEdDSA uses lower-case for integers, and I think that's a good
convention I want to stick to.

So I think "p" and "q" are good choices, considering?


> Section 2.5 says "since the first |p| bits encode an integer greater than
> p." I think it would be useful to add a clarification such as "(This is why
> it is required 2**|p| - 1 - i > p.)" or otherwise clarify the motivation for
> that precondition.

OK, I was hoping that was clear, but will try to clarify.

Trevor

[1] https://moderncrypto.org/mail-archive/curves/2014/0002