[tor-dev] X25519 ←→ Ed25519 key conversions and specs [was: Bridge Bandwidth Scanner Internship]

[isis agora lovecruft]

Hey Isis,
I have a few crypto questions for you. The bonus question is purely out
of interest (I searched for the answer, but didn't get a
good/understandable answer, if you are busy don't worry about it).

Hey Jake!

I'm CCing the conversation to tor-dev, since these are all really good
questions. (Also you found another problem in our specs!)

Q1. What does the bit argument in the the ntor-onion-key-crosscert field
do?
The following is an example ntor-onion-key-crosscert field. The bit
argument is the "1" following ntor-onion-key-crosscert keyword.

ntor-onion-key-crosscert 1
-----BEGIN ED25519 CERT-----
AQoABl2EAdjttTuvK9jQzdyi+Mh46ky1Jk9+Hw+FJ6eos5zUxcBDAJF+TGU6oZij
DOToeg+/lIaEkv0RwIrl5aJta/jf2EdTgHRfCsMOLEWMfqjOA6pmkwc3jnWvWNms
7NVBzUcMWgA=
-----END ED25519 CERT-----

Q2. The following sentence is the bit argument's documentation from the
dir-spec. Could you possibly explain to me what this means? What is a
public key's "sign"?

Bit must be "0" or "1". It indicates the sign of the ed25519 public key corresponding to the ntor onion key.

The following paragraph is also in the dir-spec, I know that it is
relevant, but I don't understand what it means.

C. Converting a curve25519 public key to an ed25519 public key
Given a curve25519 x-coordinate (u), we can get the y coordinate
of the ed25519 key using
y = (u-1)/(u+1)
and then we can apply the usual ed25519 point decompression
algorithm to find the x coordinate of the ed25519 point to check
signatures with.
Note that we need the sign of the X coordinate to do this
operation; otherwise, we'll have two possible X coordinates that
might have correspond to the key. Therefore, we need the 'sign'
of the X coordinate, as used by the ed25519 key expansion
algorithm.
To get the sign, the easiest way is to take the same private key,
feed it to the ed25519 public key generation algorithm, and see
what the sign is.

BONUS. What is the difference between a curve25519 public key and an
ed25519 public key? Why would you want to convert back and forth between
the two?

Okay, this is going to be a long answer. Let me know if parts don't make
sense.

Bit must be "0" or "1". It indicates the sign of the ed25519
public key corresponding to the ntor onion key.
To compute the ed25519 public key corresponding to a
curve25519 key, see appendix C.

There are a few different representations of the curve over the Galois field
GF(2²⁵⁵ - 19) called curve25519. The (arguably) most useful is the twisted
Edwards form of the curve (see our Rust documentation [1] for further
details on point forms and more literature) defined for affine points
P = (x,y) by the equation

-x²+y² = 1 + dx²y² (1)

where

d = - 121665/121666

This is due to the fact that efficient, complete formulae (meaning that the
same formulae, e.g. for point addition, can be used for all points, so you
don't have messy if/then statements to deal with exceptional points) exist
for Edwards curves. (Recently, complete formulae for Weierstrass curves and
other prime-order curves have also been described. [2] However, they are
still slightly less-efficient for most tasks.)

There's a useful technique called a Montgomery ladder, which is an approach
to constant-time (if implemented in a sane manner) point multiplication
(i.e. computing nP by taking the point P and adding it to itself n times).
This is particularly useful for elliptic curve Diffie-Hellman (ECDH)
implementations, but it requires first converting a point from a certain
representation (a.k.a. within a specific spatial coordinate system), usually
"extended homogeneous twisted Edwards coordinates" (see Hişil's thesis [3],
which is the explanation of all the different forms and group laws), into
the affine point Q = (u,v) as it would lie on the Montgomery form of the
curve:

bv² = u³ + au² + u (2)

where

a = 486662
b = 1

The conversion is rather straighforward, as you can see from mine and Henry
de Valence's code [4], but there's a problem in that the compressed form
(i.e. "give me the serialised version that is just an array of 32 bytes") of
points on the Montgomery curve are just the u-coordinate. You can use this
u-coordinate to recover the v-coordinate, [5] and then use both u and v to
recover the original Edwards x-coordinate, [6] but there's two possible
x-coordinates, one positive and one negative.

So, if you want to be able to use a key for both purposes, then, when using
Montgomery form (e.g. an X25519 key a.k.a. a "curve25519 key") then you have
to also pass around the sign of x. It's kind of icky.

In this case, the "ntor-onion-key-crosscert" is an Ed25519 signature (so the
public key is a point in twisted Edwards form) of the relay's public master
identity key, computed using the "ntor-onion-key" (which is an X25519 key,
so a point in Montgomery form). The verifier knows the "ntor-onion-key",
but needs to know the sign of x in order to be able to convert it into the
Edwards-form public key to check this signature.

Following through the code tor is using, it appears that if "Bit" is "0",
then x will be positive. If "Bit" is "1" then x will be negative. Tor's
behaviour w.r.t. the sign bit (using either curve25519-donna [7] or ref10
[8]) appears to be identical to other implementations, namely Open
Whispersystems' code [9] and curve25519-dalek. [10]

It appears it isn't specified anywhere what the "Bit" is supposed to mean in
terms of parsing the ntor-onion-cert into an Ed25519 key though. :( I made
an attempt at specifying it better. [11]

As for the question of why one would want to convert back and forth between
the two
 normally, you wouldn't want to do this. There's nothing concretely
horribly wrong or insecure about it, but there are plenty of more
theoretical concerns regarding any type of key reuse for different
protocols, primarily because it removes any sense of domain separation, such
that an attack on one protocol might be assisted by or contribute to
attacking the other. With separate keys for separate purposes, you can
breathe a lot easier knowing that if, e.g. your ECDH keys were compromised,
that your signing key (being a totally different key) is (probably)
unaffected. The only time where is does make sense to share a key between
two protocols is what Nick's design for the cross-certifications,
i.e.:

a) Prove that you control the private part of an encryption key by
converting it to a signing key, then signing the public master identity
key, and
b) Authenticate the signature by using the master identity key to sign the
entire document (including the other signature).

Thanks for all the help, I hope that you are having a nice day and...
Happy Hacking.
- Jake

No worries! Thanks for the excellent questions and catching more bugs in
our specs!

[0]: https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt?id=ce09d266#n536
[1]: https://docs.rs/curve25519-dalek/0.10.0/curve25519_dalek/curve/index.html
[2]: https://ellipticnews.wordpress.com/2016/05/30/complete-group-laws-for-prime-order-elliptic-curves-a-step-towards-safer-implementations-of-standard-curves/
[3]: https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20mathematics/elliptic%20curve%20cryptography/Elliptic%20Curves%2C%20Group%20Law%2C%20and%20Efficient%20Computation%20(2010)%20[thesis]%20-%20Hi%C5%9Fil.pdf
[4]: https://github.com/isislovecruft/curve25519-dalek/blob/f2883028d/src/curve.rs#L175
[5]: https://github.com/isislovecruft/curve25519-dalek/blob/f2883028d/src/curve.rs#L235
[6]: https://github.com/isislovecruft/curve25519-dalek/blob/f2883028d/src/curve.rs#L270
[7]: https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519/donna/ed25519_tor.c?id=2032b9b1#n324
[8]: https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519/ref10/keyconv.c?id=2032b9b1b1#n6
[9]: https://github.com/WhisperSystems/curve25519-java/blob/master/android/jni/ed25519/additions/ge_montx_to_p3.c#L35
[10]: https://github.com/isislovecruft/curve25519-dalek/blob/f2883028d/src/curve.rs#L253
[11]: https://gitweb.torproject.org/torspec.git/commit/?id=2395f34affbe97c19d7bb9e3e288bc20d2249edd

Best,