Support for EdDSA (Ed25519 & Ed448)

[jas4711]

EdDSA is a public-key digital signature system, instantiated with common parameters as Ed25519 and Ed448. It would be nice to have this implemented in OpenSSL, both at the crypto API level and at the TLS level.

Crypto: https://tools.ietf.org/html/draft-irtf-cfrg-eddsa
TLS: https://tools.ietf.org/html/draft-ietf-tls-rfc4492bis

I'm sure people are thinking and working this, but I did not find a good place to follow progress about this, so I'm hoping a wishlist like this will help to make the status of this work public.

/Simon

[ghedo]

I don't think anyone is actually working on this. There's also https://rt.openssl.org/Ticket/Display.html?id=4077 tracking this (that you created as well), with just one reply from @richsalz https://mta.openssl.org/pipermail/openssl-dev/2015-October/003010.html (that went only to the mailing list and not RT, so I'm guessing you haven't seen it).

It kinda seemed like you were interested in working on this, or at least finding a suitable implementation that could be used by OpenSSL, but maybe I got the wrong idea.

[richsalz]

Has CFRG concluded yet? It's pretty clear only "deterministic DSA" right?

[dol]

You might profit from the work of boringssl:
https://boringssl.googlesource.com/boringssl/+/4fb0dc4b031df7c9ac9d91fc34536e4e08b35d6a

[ladar]

It sure would be nice if someone was working on it. :)

[alex]

@richsalz just so this is canonicalized here, CFRG isn't done yet, but the Ed25519 portion is pretty solid at this point: https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-02

[richsalz]

Yes, we're aware. We'll have to see. It might be hard to get it into 1.1; a PR with source doc and test would help :)

[alex]

I figured you were aware, just wanted to make sure anyone viewing this PR had an answer :-)

[richsalz]

The answer is: send code, else I think it's doubtful. My opinion.

[ghost]

Please support Ed511187.

[richsalz]

@stas730 please open a separate issue.

[HLFH]

@stas730 Your Ed511187 does not exist.

[ghost]

Why I see it in a some library? Library name CoCryl.

[ghost]

Sorry for Google link.
http://www.google.com.ua/url?q=http://www.cyberens.fr/wp-content/uploads/2016/04/COCryl_doc.pdf&sa=U&ved=0ahUKEwiCus7_8_LMAhVkJ5oKHaf9DfgQFggPMAA&usg=AFQjCNEPOvZGcNK5fzSdM_a4dLRCOn_kqw

[ghost]

UPD: Normal link
http://www.cyberens.fr/wp-content/uploads/2016/04/COCryl_doc.pdf

[ghost]

M-511 is this Curve.
But E-521 is better… if it supported in EdDSA.

[ladar]

Linked below is a gist/patch file that will add support for Ed25519 to OpenSSL 1.0.2j. The effort isn't perfect, by any means, but hopefully it will tide me (and others) over till a) EdDSA is fully supported officially, b) v1.1.1 is released (assuming Ed25519 makes the cut for 1.1.1, and c) several years pass, bugs are fixed, and confidence is gained in v1.1.1 and migrations are made.

This patch bolts the boringssl Ed25519 and X25519 functions onto OpenSSL v1.0.2. Note that master already has X25519 functions but the interfaces are slightly different, so I felt it was easier to take the whole boringssl package rather than mix and match interfaces.

Unfortunately none of the implementations (boringssl or master) add support for Ed25519 to the EVP interfaces, so you'll have to use the raw interfaces:

void ED25519_keypair(uint8_t out_public_key[32],
                                    uint8_t out_private_key[64]);

int ED25519_sign(uint8_t out_sig[64], const uint8_t *message,
                                size_t message_len,
                                const uint8_t private_key[64]);

int ED25519_verify(const uint8_t *message, size_t message_len,
                                  const uint8_t signature[64],
                                  const uint8_t public_key[32]);

I plan to cleanup a few minor things when time allows, so if anyone notices an issue let me know and I'll see what I can do.

https://gist.github.com/ladar/04bf594b793e957e6b576633e00467c0

[ladar]

Since curve25519 and ed25519 use different derivation logic when going from a private seed value to a public exponent, I added the function ED25519_public_from_private() to the patch. There is already an X25519 function for this purpose.

void ED25519_public_from_private(uint8_t out_public_key[32],
                                const uint8_t private_key[32]);

https://gist.github.com/ladar/e45e893901f30f480dd49265ba3c42c0

[richsalz]

Suggest you post this to openssl-users so more people will see what you’ve got.

[ladar]

The patch links above have been updated to use the ED25519_keypair_from_seed() nomenclature/prototype as discussed on the boringssl change review linked below. I updated the patch to reflect the API change so the two remain consistent with each other.

https://boringssl-review.googlesource.com/#/c/12040/

P.S. @richsalz I haven't had time to post the patch to the dev/users mailing lists yet. Feel free to share them for me if you think others would be interested.

[Darkspirit]

New: RFC8080: Edwards-Curve Digital Security Algorithm (EdDSA) for DNSSEC (Ed25519 and Ed448)

(I have powerdns in mind.)

Edit: I would switch from P-384 only to Ed448. (Special use)

[NahualTeraB]

Could anyone clarify if OpenSSL will fully support Ed25519 and Ed448 anytime soon?
Since BIND9 developers will consider to implement RFC 8080 when EdDSA and the 2 selected Edwards Curves (Ed25519 and Ed448) will be supported by OpenSSL.

PS: Would the Ed448-Goldilocks implementation by Mike Hamburg that is currently licensed under the MIT license be suiteable for OpenSSL?
https://eprint.iacr.org/2015/625.pdf
https://github.com/coruus/ed448-goldilocks

[richsalz]

In my personal opinion, I doubt it would happen before Q3, and might not show up in release until 2018. The team is working mainly on other things, especially TLS 1.3

A PR that worked and fit into the EVP API would speed things up tremendously.

[Habbie]

New: RFC8080: Edwards-Curve Digital Security Algorithm (EdDSA) for DNSSEC (Ed25519 and Ed448)

(I have powerdns in mind.)

PowerDNS already supports Ed25519 via libsodium.

[snhenson]

Update: I'm working on Ed25519 support. I should have an initial WIP PR soon.

[MaggieLplus]

Ed25519 support (#3503) and Ed25519 TLS support (#3585) have been merged to OpenSSL master

[romen]

@snhenson @richsalz regarding the new API, after #3503

• Am I correct saying that Ed25519 can be used only through the EVP_DigestSign/EVP_DigestVerify and there is no way to call it through the EVP_PKEY_sign/EVP_PKEY_verify API?
• For a given EVP_PKEY *key is it currently possible to discern if the underlying EVP_PKEY_METHOD supports sign/verify or only digestsign/digestverify?
  • Should we add signals e.g. to EVP_PKEY_METHOD->ctrl to check what interface the method supports?
• Are we missing EVP_PKEY_meth_set_digestsign/EVP_PKEY_meth_set_digestverify functions in evp.h to externally manipulate the vtable to provide alternative implementations of the new API?

[davidben]

In other key types, EVP_PKEY_sign and EVP_PKEY_verify sign a pre-hashed digest rather than an unhashed message. There isn't an analogous operation in Ed25519, so EVP_PKEY_sign doesn't work. EVP_DigestSign and EVP_DigestVerify sign an unhashed message, so that works analogously for both.

See #487 (comment). It's unfortunate that the API gives names are the opposite of what one would expect here ("sign" is sign digest and "DigestSign" is sign message), but so it goes. :-/

[romen]

@davidben

In other key types, EVP_PKEY_sign and EVP_PKEY_verify sign a pre-hashed digest rather than an unhashed message.

Is that really so? In my understanding EVP_PKEY_sign and EVP_PKEY_verify are agnostic on what is being given to sign, just a pointer to a buffer and its length.

Other key types call these two functions after pre-hashing, but nowhere the documentation states that EVP_PKEY_sign and EVP_PKEY_verify must receive a pre-hashed message and cannot be used for Ed25519.

But this is not really the point of my questions: currently Ed25519, and one day Ed448 or other EdDSA implementations, have their own API for sign/verify and need to be treated differently from any other EVP_PKEY providing a digital signature scheme. Moreover it seems like there is no way to programmatically assess, given any EVP_PKEY object, which API should be used to perform signing or verification. This is a problem for third party developers that want to use OpenSSL to develop a client app to sign/verify stuff given any key supported by OpenSSL, but also internally e.g. in the openssl dgst command that cannot currently be used to sign/verify messages given an Ed25519 key, or in the openssl speed command to benchmark (I'm currently working on some changes to enable the speed command to use the EVP API for signatures).

Not having EVP_PKEY_meth_set_digestsign/EVP_PKEY_meth_set_digestverify stops third party developers to manipulate the vtables, and since 1.1.0 made internal structures opaque, there is currently no way to implement e.g. an ENGINE providing an alternative implementation for Ed25519.

[ghost]

@romen If I understood your comment correctly, there is no EC_KEY_* support for the primitives Ed25519 uses, despite its support in the EVP_PKEY_* API?

[romen]

@R030t1 I was not pointing at that but what you say is also true: X25519 and Ed25519 are implemented at the EVP_PKEY_ level as a separate ECX_ module instead of through the lower level EC_ API_.

What I wanted to point out is that external libraries or programs (end even the builtin apps in openssl accessible from the openssl command line utility), since the introduction of changes for ED25519, apparently lack a unified API way to sign/verify, as some methods require to use digestsign/digestverify instead of the sign/verify function and there is no programmatic way of querying a method to discover which function should be used.

[davidben]

You should always use the digestsign/digestverify functions for signing messages. That's your unified API.

To answer your earlier question, EVP_PKEY_sign and EVP_PKEY_verify have fine type signatures for either, but signing a prehashed digest and signing a raw message typically have the same type signature anyway. But if you're writing code that acts on a key uniformly, the existing semantics of those functions matter too, not just their type signatures. The existing semantics are that they sign a prehashed digest. If you tried to sign a message with ECDSA or RSA with EVP_PKEY_sign, you won't get the right answer. Ed25519 does not use those functions precisely so there is a unified API.

[ghost]

@davidben If the end result is that I can't perform certain operations with a signature system then I am not sure the API is unified.

[kaduk]

Ed25519 landed in #3585 and friends, so moving the Ed448 issue out into #5049 and closing this one.

[kriskwiatkowski]

It seems it's not possible to create eddsa certificates via command line. Do you plan to add support for that ?

[mattcaswell]

It is perfectly possible to create EdDSA certs from the command line. E.g.:

$ openssl genpkey -algorithm Ed25519 -out ed25519key.pem
$ openssl req -x509 -key ed25519key.pem -out cert.pem -days 365

[kriskwiatkowski]

Thank you, @mattcaswell . Indeed it works with openssl compiled from master branch

[kriskwiatkowski]

I'm trying to generate a key in different way and getting following error

openssl req -config openssl.cnf -x509 -passin pass:test123 -key private/ed25519.key -out csr/ed25519.csr -subj "/CN=www.cert_testing.com" 
0:error:1010F08A:elliptic curve routines:pkey_ecd_ctrl:invalid digest type:crypto/ec/ecx_meth.c:783:

It's a bit weird, because same command works for RSA and ECDSA

[mattcaswell]

What's in openssl.cnf?

[kriskwiatkowski]

I do have

default_md        = sha256

but commenting this line doesn't change anything. That's my full file:

[ ca ]
# `man ca`
default_ca = CA_default

[ CA_default ]
# Directory and file locations.
dir               = .
certs             = $dir/certs
crl_dir           = $dir/crl
new_certs_dir     = $dir/newcerts
database          = $dir/index.txt
serial            = $dir/serial
RANDFILE          = $dir/private/.rand

# The root key and root certificate.
private_key       = $dir/root.key
certificate       = $dir/root.pem

# For certificate revocation lists.
crlnumber         = $dir/crlnumber
crl               = $dir/crl/intermediate.crl.pem
crl_extensions    = crl_ext
default_crl_days  = 30

# SHA-1 is deprecated, so use SHA-2 instead.
default_md        = sha256

name_opt          = ca_default
cert_opt          = ca_default
default_days      = 9999
preserve          = no
policy            = policy_loose

[ policy_strict ]
# The root CA should only sign intermediate certificates that match.
# See the POLICY FORMAT section of `man ca`.
countryName             = match
stateOrProvinceName     = match
organizationName        = match
organizationalUnitName  = optional
commonName              = supplied
emailAddress            = optional

[ policy_loose ]
# Allow the intermediate CA to sign a more diverse range of certificates.
# See the POLICY FORMAT section of the `ca` man page.
countryName             = optional
stateOrProvinceName     = optional
localityName            = optional
organizationName        = optional
organizationalUnitName  = optional
commonName              = supplied
emailAddress            = optional

[ req ]
# Options for the `req` tool (`man req`).
default_bits        = 4096
distinguished_name  = req_distinguished_name
string_mask         = utf8only
default_md          = sha384

[ req_distinguished_name ]
countryName                     = Country Name (2 letter code)
stateOrProvinceName             = State or Province Name (full name)
localityName                    = Locality Name (eg, city)
organizationalUnitName          = Organizational Unit Name (eg, section)
commonName                      = Common Name

stateOrProvinceName_default     = PACA
countryName_default             = FR
localityName_default            = Cagnes sur Mer
organizationalUnitName_default  = Cert Testing Organization
commonName_default              = Cert Testing Organization
commonName_max                  = 64

[ v3_ca ]
# Extensions for a typical CA (`man x509v3_config`).
subjectKeyIdentifier        = hash
authorityKeyIdentifier      = keyid:always,issuer
basicConstraints            = critical, CA:true
keyUsage                    = critical, digitalSignature, cRLSign, keyCertSign

[ v3_intermediate_ca ]
# Extensions for a typical intermediate CA (`man x509v3_config`).
subjectKeyIdentifier        = hash
authorityKeyIdentifier      = keyid:always,issuer
basicConstraints            = critical, CA:true, pathlen:0
keyUsage                    = critical, digitalSignature, cRLSign, keyCertSign

[ usr_cert ]
# Extensions for client certificates (`man x509v3_config`).
basicConstraints        = CA:FALSE
nsCertType              = client, email
nsComment               = 'Cert Testing Intermediate - Client'
subjectKeyIdentifier    = hash
authorityKeyIdentifier  = keyid,issuer
keyUsage                = critical, nonRepudiation, digitalSignature, keyEncipherment
extendedKeyUsage        = clientAuth, emailProtection

[ server_cert ]
# Extensions for server certificates (`man x509v3_config`).
basicConstraints        = CA:FALSE
nsCertType              = server
nsComment               = 'Cert Testing Intermediate - Server'
subjectKeyIdentifier    = hash
authorityKeyIdentifier  = keyid,issuer:always
keyUsage                = critical, digitalSignature, keyEncipherment
extendedKeyUsage        = serverAuth
subjectAltName          = @alt_names

[ crl_ext ]
# Extension for CRLs (`man x509v3_config`).
authorityKeyIdentifier  = keyid:always

[ ocsp ]
# Extension for OCSP signing certificates (`man ocsp`).
basicConstraints        = CA:FALSE
subjectKeyIdentifier    = hash
authorityKeyIdentifier  = keyid,issuer
keyUsage                = critical, digitalSignature
extendedKeyUsage        = critical, OCSPSigning

[alt_names]
DNS.1   = *.cert_testing.com
IP.1    = 127.0.0.1

[mattcaswell]

As well as the line you pointed out, you also have a second similar one in the req section:

default_md          = sha384

What happens if you comment that out?

[kriskwiatkowski]

Ahh, I've missed that one.
Everything works OK if I comment sha384.
Thank you

[mattcaswell]

Great! I wonder what should happen in that scenario? Do we do the right thing by complaining? Or should we ignore a default md in that case?

[kriskwiatkowski]

I'm not sure what would be better codewise, but I think I would vote for ignore, my arguments:

1. As far as I can see hash in Ed25519 is fixed to SHA-512/256, so choosing this algorithm implies choosing sha-512 anyway
2. If it's ignored than I can use same configuration file for creating ECDSA, RSA and EdDSA and I don't have to align hash to eddsa.