Convert Ed25519 to Curve25519 keys

[chrysn]

Keys generally used for signing can be also used for derivation of a shared secret -- they have to be converted from the Twisted Edwards to the Montgomery form for that, though.

One application for this is OSCORE group communication, where keys that are mostly used for signing are used for static-static key derivation (https://tools.ietf.org/html/draft-ietf-core-oscore-groupcomm-10#section-2.3.1 the paragraph starting "If EdDSA asymmetric keys are used,").

It would be nice to have that functionality in cryptography.

Right now I can perform most steps of this using the cryptography module, but the coordinate conversion process is not available, and as a workaround I'm reaching into the NaCl library just to do that. Example code:

from cryptography.hazmat.primitives.asymmetric import x25519
from cryptography.hazmat.primitives.asymmetric import ed25519
import nacl.signing, nacl.public

private1 = bytes.fromhex('397CEB5A8D21D74A9258C20C33FC45AB152B02CF479B2E3081285F77454CF347')
private2 = bytes.fromhex('70559B9EECDC578D5FC2CA37F9969630029F1592AFF3306392AB15546C6A184A')
shared_reference = bytes.fromhex('4546babdb9482396c167af11d21953bfa49eb9f630c45de93ee4d3b9ef059576')


# These keys would regularly be used like this:
cpriv1 = ed25519.Ed25519PrivateKey.from_private_bytes(private1)

# Importing the key in NaCl
npriv1 = nacl.signing.SigningKey(seed=private1, encoder=nacl.encoding.RawEncoder)
npriv2 = nacl.signing.SigningKey(seed=private2, encoder=nacl.encoding.RawEncoder)

# Use NaCl to convet to Montgomery form
npriv1_mont = npriv1.to_curve25519_private_key()
npriv2_mont = npriv2.to_curve25519_private_key()

# Import the converted keys back into Cryptography
k1 = x25519.X25519PrivateKey.from_private_bytes(npriv1_mont._private_key)
k2 = x25519.X25519PrivateKey.from_private_bytes(npriv2_mont._private_key)
shared_1_2 = k1.exchange(k2.public_key())
shared_2_1 = k2.exchange(k1.public_key())
assert shared_1_2 == shared_2_1
assert shared_1_2 == shared_reference

(Keys and reference value stem from the test vectors used during the IETF hackathon)

If a conversion function existed, the NaCl code could bre replaced with

k1 = cpriv1.to_x25519()

where the to_x25519 documentation would say something like:

Converts the Ed25519 key (which is a point on the Edwards curve) to a key usable for X25519 key exchanges (and thus a point on the Montgomery curve).

[reaperhulk]

An explicit method to do this conversion would be fine by me, but OpenSSL (to my knowledge) doesn't currently have APIs for conversion between edwards and montgomery forms.

[chrysn]

The conversion itself is probably rather straightforward (I just don't want to see it in application code, especially, not without some cryptography library review). It should be doable with some bigint arithmetic (a hardcoded constant for sqrt(-486664), a bitflip, an inversion, a few additions and multiplications); would that be within the scope of what cryptography accepts to do internally?

[reaperhulk]

The math for conversion of public keys is pretty straightforward, but we do have the complexity of X25519 -> ed25519 being ambiguous due to X25519 not preserving sign. Conversion of the private scalar is just a hash + standard clamping (https://github.com/jedisct1/libsodium/blob/927dfe8e2eaa86160d3ba12a7e3258fbc322909c/src/libsodium/crypto_sign/ed25519/ref10/keypair.c#L70), so implementing that is very straightforward as well.

I'd be more inclined to support conversion Ed25519 -> X25519 for private keys only as a first pass if you're interested in submitting a PR since that's unambiguous and easy to do (modulo determining the best way to rigorously test it).

[chrysn]

Edwards to Montgomery is the conversion that's being specified for oscore-groupcomm; if going back is tricky, going forth is a sane starting point, and doing the private side first is fine with me.

I'll give it a try, but may have questions as to the preferred methods coming up during that.

[reaperhulk]

I'm still not sure whether we want to put this as a supported API, but this code will convert

        hasher = hashes.Hash(hashes.SHA512())
        hasher.update(data)
        h = bytearray(hasher.finalize())
        # curve25519 clamping
        h[0] &= 248
        h[31] &= 127
        h[31] |= 64
       x25519_private_scalar = h[0:32]

You could patch X25519PrivateKey with this then:

    @classmethod
    def from_ed25519_private_bytes(cls, data):
        from cryptography.hazmat.primitives import hashes
        from cryptography.hazmat.backends.openssl.backend import backend

        if not backend.x25519_supported():
            raise UnsupportedAlgorithm(
                "X25519 is not supported by this version of OpenSSL.",
                _Reasons.UNSUPPORTED_EXCHANGE_ALGORITHM,
            )

        hasher = hashes.Hash(hashes.SHA512())
        hasher.update(data)
        h = bytearray(hasher.finalize())
        # curve25519 clamping
        h[0] &= 248
        h[31] &= 127
        h[31] |= 64

        return backend.x25519_load_private_bytes(h[0:32])

[chrysn]

Thanks for coming up with this, I had lost this out of sight.

The proposed code works well in my application, and both test vectors and random input data comparison with the nacl-based workaround that worked during previous interoperability tests.

API-wise I'm not using this to start from a raw key but from an Ed25519PrivateKey; I think this gives better usability (by having more visibility of what is what in the types). If, however, future backends are envisioned where private keys would lock themselves in (not have a .private_bytes() method at all), implementing it this way would become unfeasible.

[chrysn]

I've now looked into which OpenSSL components would be involved in doing the public side there. Tracing the steps of the sodium code and looking for the OpenSSL equivalents indicates that not only are these not exposed in cryptography, the're even static in OpenSSL.

While having private key conversion is already a good start, in the end a Group OSCORE implementation will need both conversions (from ed to curve; for the other direction it's become obvious that it's not possible for the generic backend case that may need the key in its original seed form). I didn't find a feature request in OpenSSL equivalent to this yet, so it's probably most straightforward that I ask there first. (I'm working on alternatives in parallel, but I don't suppose a dependency to anything low-level that's not one of the existing backends would not go over too well here).