Add EdDSA capabilities

[zacknewman]

It would be nice if EdDSA curves were properly supported; and once supported, webauthn_rs_proto::cose::COSEAlgorithm::secure_algs added COSEAlgorithm::EDDSA to the returned Vec. Personally I would even like a way to prioritize such curves (e.g., Ed25519). I think that could be done in a "safe" way with something like webauthn_rs::WebauthnBuilder::prefer_edwards_curves which would allow developers to not have to specify specific curves.

[Firstyear]

It's not possible today. There are no rust cryptography libraries that are high quality enough, portable, and support the needed key hydration options.

Optimally we want to stay within the openssl ecosystem, and that sadly doesn't allow recovering ed25519 keys from points. (rather, it allows recovery from points, but it's not the same point axis).

I think that could be done in a "safe" way with something like webauthn_rs::WebauthnBuilder::prefer_edwards_curves

We already support the ability to set what algorithms you accept, so we don't need this flag.

Finally, almost no keys support ed25519. The exceptions are the FIPS validated yubikeys, and solokey/nitrokey. However, both solokey and nitrokey have security issues, meaning I don't consider their use "serious" for security purposes so any discussions of algorithms is completely pointless when your key is fundamentally flawed.

As a result, we see no reason to implement ed25519 support at this time, nor do we feel a need to rush to support it.

[zacknewman]

It's not possible today. There are no rust cryptography libraries that are high quality enough, portable, and support the needed key hydration options. Optimally we want to stay within the openssl ecosystem, and that sadly doesn't allow recovering ed25519 keys from points. (rather, it allows recovery from points, but it's not the same point axis).

ed25519_dalek does not work? I find it to be high quality, and I believe it is portable. One can serialize the Y coordinate; and if for some reason you need the superflous X coordinate to be serialized, then you can derive it manually from the Y coordinate. What am I missing here?

Finally, almost no keys support ed25519. The exceptions are the FIPS validated yubikeys, and solokey/nitrokey. However, both solokey and nitrokey have security issues, meaning I don't consider their use "serious" for security purposes so any discussions of algorithms is completely pointless when your key is fundamentally flawed.

Non-FIPS YubiKeys have supported Ed25519 since firmware 5.2.3 (the current firmware is 5.4.3). I have been using sk-ssh-ed25519@openssh.com on every SSH server I maintain for a while now with both the resident and non-resident key option with my YubiKey 5C (not FIPS-validated).

[Firstyear]

It's not possible today. There are no rust cryptography libraries that are high quality enough, portable, and support the needed key hydration options. Optimally we want to stay within the openssl ecosystem, and that sadly doesn't allow recovering ed25519 keys from points. (rather, it allows recovery from points, but it's not the same point axis).

ed25519_dalek does not work? I find it to be high quality, and I believe it is portable.

We prefer openssl because of various compliance reasons that our library consumers have.

One can serialize the Y coordinate; and if for some reason you need the superflous X coordinate to be serialized, then you can derive it manually from the Y coordinate. What am I missing here?

That nothing magically supports that out of the box.

Finally, almost no keys support ed25519. The exceptions are the FIPS validated yubikeys, and solokey/nitrokey. However, both solokey and nitrokey have security issues, meaning I don't consider their use "serious" for security purposes so any discussions of algorithms is completely pointless when your key is fundamentally flawed.

Non-FIPS YubiKeys have supported Ed25519 since firmware 5.2.3 (the current firmware is 5.4.3). I have been using sk-ssh-ed25519@openssh.com on every SSH server I maintain for a while now with both the resident and non-resident key option with my YubiKey 5C (not FIPS-validated).

Still, the point is there is very little compelling reason to prefer ed25519 over ecdsa today, and it's a large amount of work that has little gain for us.

I think right now this feature request is in "PR's welcome" - until we have a user with a strict compliance reason for it, then we might consider it but I doubt that will occur.

[zacknewman]

Your initial argument was that "almost no keys" supported it then when on to name a few that had "security issues" without evidence and then was corrected about the most popular security key of them all, YubiKey, supporting Ed25519 for quite some time. You also said "optimally we want to stay within the openssl ecosystem" (emphasis added), but now it sounds more like a hard requirement.

There are some admittedly niche cases where Ed25519 is more secure in addition to the whole NIST-NSA stuff. Fortunately the beautiful thing about open-source code is one can write it themselves which I will probably do. I would offer a PR instead, but I will likely use ed25519_dalek and only store the Y coordinate which sounds like nonstarters for this project.

[zacknewman]

Re-opening this since I want to walk back my assumption that a PR will likely not be accepted. A cursory read of the source code seems to indicate that a reasonable amount of the "infrastructure" needed to get Ed25519 support exists, and I believe it will be easy to stay within the confines of the openssl crate.

The notion that openssl won't allow recovery from the necessary points is incorrect. Despite the nomenclature used by RFC 9053 for the parameter names, the parameters in the Octet Key Pair (OKP) type don't reflect their actual meaning. In particular "x" is simply the "public key " (i.e., it is not an "X coordinate"). The RFC even explicitly states to not assume any additional meaning based on the parameter names:

Do not assume that keys using this type are elliptic curves. This key type could be used for other curve types (for example, mathematics based on hyper-elliptic surfaces).

As a result when dealing with a "crv" value of "Ed25519", "x" is actually the compressed-Y coordinate as defined by RFC 8032. Why does this matter? It's even easier to create the public key from OKP information than it is to create the public key from the EC2 key information:

use base64urlsafedata::Base64UrlSafeData;
use openssl::error::ErrorStack;
use openssl::pkey::{Id, PKey, Public};
#[derive(Clone, Copy)]
pub enum EDDSACurve {
    ED25519 = 6,
    ED448 = 7,
}
impl From<EDDSACurve> for Id {
    fn from(value: EDDSACurve) -> Self {
        match value {
            EDDSACurve::ED25519 => Self::ED25519,
            EDDSACurve::ED448 => Self::ED448,
        }
    }
}
pub struct COSEOKPKey {
    pub curve: EDDSACurve,
    /// The compressed Y coordinate.
    pub x: Base64UrlSafeData,
}
impl TryFrom<&COSEOKPKey> for PKey<Public> {
    type Error = ErrorStack;
    fn try_from(value: &COSEOKPKey) -> Result<Self, Self::Error> {
        Self::public_key_from_raw_bytes(value.x.0.as_slice(), value.curve.into())
    }
}

That is a single line vs. the 7 lines for COSEEC2Key. While there is surely a lot of work to do, this instills confidence that a PR will be accepted.

[Firstyear]

I did say PR's would be welcome. Yes most of the infrastructure is already there, and there are even test vectors in the repo, that currently just expect errors since we don't support this type.

So provided you can do this with openssl, then no problem.

My point was there was nothing compelling our team right now to pursue this feature on our own time, not that we wouldn't accept it.

It's disappointing to learn about the confusing nature of the values in the specifications - this confusion was the very thing that trapped us in the past from implementing this type.

[zacknewman]

You did, but your first response focused on not enough devices supporting it and openssl's inability for "key hydration" as the reasons Ed25519 was not compelling. While I knew YubiKeys have supported it for over 4 years, I took the openssl thing on face value which is why I assumed a PR would not be accepted.

I am super pumped that openssl will support it no problem. Curve25519 and its birationally equivalent twisted Edwards curve are the "gold standard" of elliptic curves that are easier to implement well (e.g., suffer from fewer side-channel attacks) than curves like NIST P-256.

For PRs, is it fine that I host my own Git repos; or do you require the use of GitHub?

[Firstyear]

Github PR's are preferred, but if needed I'll accept a git format-patch output.

[zacknewman]

I e-mailed the diff. A few comments on it:

• I fixed a few clippy complaints about explicit use of return and unused imports that were unrelated to the EdDSA support.
• I chose to spell EdDSA, Ed25519, and Ed448 to align with how RFC 9053 spells them.
• I removed webauthn-rs-core::crypto::ECDSACurve::to_openssl_nid since the logic of that function already exists via openssl::nid::Nid's implementation of core::convert::From<&webauthn-rs-core::interface::ECDSACurve> in webauthn-rs-core::interface.
  • There are a few other places where unnecessary code duplication occurs that I didn't address. Such duplication complicates code audits though.
• I reordered webauthn_rs_proto::cose::COSEAlgorithms such that COSEAlgorithm::EdDSA is first in any sequence to align with RFC 9053 (e.g., COSEAlgorithm::secure_algs[0] == COSEAlgorithm::EdDSA).
• I added id_to_curve, cbor_ed25519, and cbor_ed448 test functions to webauthn-rs-core::crypto::tests.
• I largely left alone any tests related to "invalid CBOR" for SoloKeys in webauthn-rs-core::core.
• I only tested the code on a YubiKey 5C with firmware 5.4.3.
• For non-ephemeral types that are lightweight, deriveing Copy is the norm especially when such types derive Clone. This makes using them more efficient and more importantly more ergonomic. For that reason webauthn-rs-core::interface::EdDSACurve implements Copy despite the bizarre choice for not implementing Copy on ECDSACurve.
  • A consequence of this is that openssl::pkey::Id implements From<EdDSACurve> instead of From<&EdDSACurve> à la Nid does for &ECDSACurve.
• I did not audit most of the code.
  • For example there are a few comments talking about RFC 8152; however that RFC has been obsolete for over a year by RFCs 9052 and 9053.

[Firstyear]

I reordered webauthn_rs_proto::cose::COSEAlgorithms such that COSEAlgorithm::EdDSA is first in any sequence to align with RFC 9053 (e.g., COSEAlgorithm::secure_algs[0] == COSEAlgorithm::EdDSA).

Where are you seeing this in rfc9053? It appears to make no recomendation for algorithm order preference.

[zacknewman]

I didn't say "recommendation". The example it shows has EdDSA curves ahead:

[
 [-8 / EdDSA /,
   [1 / OKP key type /],
   [
     [1 / OKP /, 6 / Ed25519 / ],
     [1 /OKP/, 7 /Ed448 /]
   ]
 ],
 [-7 / ECDSA with SHA-256/,
   [2 /EC2 key type/],
   [
     [2 /EC2/, 1 /P-256/],
     [2 /EC2/, 3 /P-521/]
   ]
 ],

Additionally, I think I read somewhere it was actually recommended ahead; but I'll have to find it.

[Firstyear]

As mentioned in the email, re-ordering the algos is a separate discussion.

[zacknewman]

Adding this for future reference:

https://github.com/w3c/webauthn/issues/1757#issuecomment-1321203084

That's not an RFC, but it was used to justify putting EdDSA at the top by W3C themselves; furthermore the next comment by @Firstyear was not correct as openssl was supporting EdDSA even then. But I'll table prioritizing EdDSA for a separate discussion that I'll link to here.