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).

[reaperhulk]

Yeah we're not going to take on additional C deps here. Requesting methods for this on the OpenSSL side is a good plan -- I'd suggest bringing a PR because if you do that quickly it might make it in 3.0.0. Otherwise you're going to be waiting at least a year.

[chrysn]

Tracked now as https://github.com/openssl/openssl/issues/13630.

For reference, in parallel I'm exploring a pure-Python conversion based on the ge25519 module. (A rather new project that seems to convert some components of sodium to Python; looks kind of OK but doesn't (yet?) give me the vibes I'd want from something to rely on for crypto primitives, but then again it's not too exposed).

Conversion looks like this:

def pk_to_curve25519(ed: ed25519.Ed25519PublicKey) -> x25519.X25519PublicKey:
    raw = ed.public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw,
            )

    # This is libsodium's crypto_sign_ed25519_pk_to_curve25519 translated into
    # the Pyton module ge25519.

    from ge25519 import ge25519, ge25519_p3
    from fe25519 import fe25519

    if ge25519.has_small_order(raw) != 0:
        raise RuntimeError("Doesn' thave small order")

    # frombytes in libsodium appears to be the same as
    # frombytes_negate_vartime; as ge25519 only implements the from_bytes
    # version, we have to do the root check manually.
    A = ge25519_p3.from_bytes(raw)
    if A.root_check:
        raise RuntimeError("Root check failed")

    if not A.is_on_main_subgroup():
        raise RuntimeError("It's on the main subgroup")

    one_minus_y = fe25519.one() - A.Y
    x = A.Y + fe25519.one()
    x = x * one_minus_y.invert()

    return x25519.X25519PublicKey.from_public_bytes(bytes(x.to_bytes()))

(Error handling has obvious room for improvement.)

[kwikwag]

FWIW I've copy+pasted the above examples into two working bits of code and a test, with just a few tweaks (functions receive and return bytes, raise ValueError rather than RuntimeError).

from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
from cryptography.hazmat.backends.openssl.backend import backend
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey, Ed25519PublicKey)
from cryptography.hazmat.primitives.asymmetric.x25519 import (
    X25519PrivateKey, X25519PublicKey)
from cryptography.hazmat.primitives.serialization import (
    Encoding, NoEncryption, PrivateFormat, PublicFormat)
from fe25519 import fe25519
from ge25519 import ge25519, ge25519_p3

def pbk_bytes(pbk):
    return pbk.public_bytes(Encoding.Raw, PublicFormat.Raw)

def pvk_bytes(pvk):
    return pvk.private_bytes(Encoding.Raw, PrivateFormat.Raw, NoEncryption())

def x25519_from_ed25519_private_bytes(private_bytes):
    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(private_bytes)
    h = bytearray(hasher.finalize())
    # curve25519 clamping
    h[0] &= 248
    h[31] &= 127
    h[31] |= 64

    return h[0:32]

def x25519_from_ed25519_public_bytes(public_bytes) -> X25519PublicKey:
    if not backend.x25519_supported():
        raise UnsupportedAlgorithm(
            "X25519 is not supported by this version of OpenSSL.",
            _Reasons.UNSUPPORTED_EXCHANGE_ALGORITHM,
        )

    # This is libsodium's crypto_sign_ed25519_pk_to_curve25519 translated into
    # the Pyton module ge25519.
    if ge25519.has_small_order(public_bytes) != 0:
        raise ValueError("Doesn't have small order")

    # frombytes in libsodium appears to be the same as
    # frombytes_negate_vartime; as ge25519 only implements the from_bytes
    # version, we have to do the root check manually.
    A = ge25519_p3.from_bytes(public_bytes)
    if A.root_check:
        raise ValueError("Root check failed")

    if not A.is_on_main_subgroup():
        raise ValueError("It's on the main subgroup")

    one_minus_y = fe25519.one() - A.Y
    x = A.Y + fe25519.one()
    x = x * one_minus_y.invert()

    return bytes(x.to_bytes())

def test_x25519_from_ed25519():
    x = b'01234567890123456789012345678901'
    for i in range(10):
        pvk_ed = Ed25519PrivateKey.from_private_bytes(x[i:] + x[:i])
        pbk_ed = pvk_ed.public_key()

        pvk_x = X25519PrivateKey.from_private_bytes(x25519_from_ed25519_private_bytes(pvk_bytes(pvk_ed)))
        pbk_x1 = pvk_x.public_key()
        pbk_x2 = X25519PublicKey.from_public_bytes(x25519_from_ed25519_public_bytes(pbk_bytes(pbk_ed)))

        assert pbk_bytes(pbk_x1) == pbk_bytes(pbk_x2)