[curves] XEdDSA specification

[Andy Isaacson]

I'm happy to announce that a spec for the "XEd25519" signature
algorithm used in Signal is available at [1].
Feedback is welcome, ...

Thanks for all your work on this, Trevor.

Is the source markup for this document in git somewhere? I'd put up
pull requests for these suggestions if it were.

Having two different values named A makes the document excessively
confusing to the non-expert. We can avoid some confusion if we rename
one of them, for example keep $A$ for the curve constant and use `Ak`
for the twisted Edwards point representation of the public key. (This
will be somewhat confusing with the `kB` notation used for
multiplication in `calculate_key_pair` so perhaps this also demands
writing multiplication `k * B`, which is unfortunate but perhaps not a
blocker.)

I'd be more comfortable if the pseudocode explicitly called out the
bytes-to-integer and integer-to-bytes conversion that's defined in 2.4;
as it stands, the document can only be read sequentially starting at the
beginnning, every time I need to refer to it, because the implicit
conversions are critical to understanding section 3 and xeddsa_verify.

Having one spec defining four different functions (XEd25519, VXEd25519,
XEd448, VXEd448) makes some of the definitions general enough to be hard
for the non-specialist reader to make concrete. I'd have an easier time
understanding XEd25519 in a standalone spec. But there's a tradeoff,
the symmetry in the specs is worth preserving, so maybe this spec should
remain general and once the standards are finalized, a more concrete
implementor's guide can be written.

There aren't any test vectors in the spec, and only one in
curve25519-java/android/jni/ed25519/tests/tests.c that I've found so
far. A few more wouldn't hurt.

It'd also be nice to have fully worked examples, but that definitely
doesn't belong in the spec; I'll see if I can generate an appropriate
document as part of my current project.

-andy

[Trevor Perrin]

Thanks for feedback,

This is timely because I'd like to update this spec in the next couple
weeks with feedback from Brian Smith and others, and some extensions.

Having two different values named A makes the document excessively confusing
to the non-expert.

It's hard because "A" is widely used for the Montgomery curve, but is
also the public key in most descriptions of Ed25519/EdDSA signatures.

Most other letters are taken, but with a little shuffling we could
probably use (K, k) for (public key, private key). And perhaps
subscripts like k_mont and k_ed could distinguish the original vs
converted values.

I'd be more comfortable if the pseudocode explicitly called out the
bytes-to-integer and integer-to-bytes conversion that's defined in 2.4; as
it stands, the document can only be read sequentially starting at the
beginnning, every time I need to refer to it, because the implicit
conversions are critical to understanding section 3 and xeddsa_verify.

I thought boldface to indicate byte strings nicely avoided the clutter
of byte-conversion functions. Sounds like it's not working for you?

There aren't any test vectors in the spec, and only one in
curve25519-java/android/jni/ed25519/tests/tests.c that I've found so far. A
few more wouldn't hurt.
It'd also be nice to have fully worked examples, but that definitely doesn't
belong in the spec; I'll see if I can generate an appropriate document as
part of my current project.

Sure, good ideas. Giving test vectors for intermediate values would
make sense in an appendix, I think, if you feel like generating that
(and sending to me, there's no github for this at the moment).

Trevor

[Andy Isaacson]

Post by Trevor Perrin

Post by Andy Isaacson
I'd be more comfortable if the pseudocode explicitly called out the
bytes-to-integer and integer-to-bytes conversion that's defined in 2.4; as
it stands, the document can only be read sequentially starting at the
beginnning, every time I need to refer to it, because the implicit
conversions are critical to understanding section 3 and xeddsa_verify.

I thought boldface to indicate byte strings nicely avoided the clutter
of byte-conversion functions. Sounds like it's not working for you?

Agreed, explicit byte conversion routines will add some clutter.

I'd missed that the bold was semantically significant -- the bold isn't
stronly visually different on my browser setup (firefox, debian testing,
hi-dpi monitor), it's more visually distinctive in the PDF version.

My use case for the document here is that I've read the spec carefully
several months ago and am now returning to it with implementation in
mind, so I just skimmed the preamble and dug into the pseudocode and
textual specification, then stumbled several times on these issues.

Re-reading with the bold in mind, I immediately stumble on
<bold>M</bold> which is just a byte sequence (the message) rather than
the byte-representation-of-a-point.

I think my conclusion is that I'm way out of practice reading math. :)

Post by Trevor Perrin

Post by Andy Isaacson
There aren't any test vectors in the spec, and only one in
curve25519-java/android/jni/ed25519/tests/tests.c that I've found so far. A
few more wouldn't hurt.
It'd also be nice to have fully worked examples, but that definitely doesn't
belong in the spec; I'll see if I can generate an appropriate document as
part of my current project.

Sure, good ideas. Giving test vectors for intermediate values would
make sense in an appendix, I think, if you feel like generating that
(and sending to me, there's no github for this at the moment).

I'll try to squeeze this in, but I can't make a solid commitment due to
some resource competition on my end.

-andy