What order should COSEAlgorithms be in secure_algs and all_possible_algs?

[zacknewman]

While the example in RFC 9053 shows EdDSA curves as prioritized over ECDSA curves, it is not a formal recommendation let alone requirement. I cannot seem to find any RFC or other specification related to WebAuthn, CBOR, or JOSE that specifies what order of algorithms SHOULD/MUST be used yet.

WebAuthn Level 3 appears will have Ed25519, ES256, and RSA256; but that is not yet official.

I'd like to start a discussion around what should be the order of webauthn-rs-proto::cose::COSEAlgorithms in the returned alloc::vec::Vecs from COSEAlgorithm::secure_algs and COSEAlgorithm::all_possible_algs.

I believe—once my diff is merged—the order should follow this hypothetical spec if for no other reason forward compatibility. Even in the unlikely case the spec will not state what order algorithms should be preferred in, I still think the order should be as stated. Why?

• Most cryptographers would order those algorithms the same way by security; or at the very least, would not put Ed25519 after the other two (i.e., at worst, it's as good).
• Code is easier to write and read; thus less likely to have bugs and easier to audit.
• Client authenticators will ignore any unsupported algorithms, so any argument that relies on the popularity of an algorithm is irrelevant.
• The order aligns with the order of best performance and inversely with the size of signatures.
• There is no NIST/NSA connection with Ed25519.

Addressing perceived storage size concerns

YubiKey 5C firmware 5.4.3 algorithm storage comparison for security key (note RSA is not supported with this firmware) using patched versions of webauthn-rs 0.4.8, webauthn-rs-core 0.4.9, and webauthn-rs-proto 0.4.9:

Entire payload that relies on attestation, AAGUID, and platform type:

• Ed25519
  • {"cred":{"cred_id":"SPH4JpOewjA7cDMF8exK8cURnJwk8ZS8TP7y7mwqRY05iY1elOk-2b-dhfO7soT_kWvHtazb7AVIwfe9roAgBYOsKnqWQXjqIeyTgl2xszEhvqcTcm7TbVHTeVOif21esbQ3bwbWHmYqD0UptomBsV5IbwXRgy8VY7JGfmCsKzI","cred":{"type_":"EdDSA","key":{"EC_OKP":{"crv":"Ed25519","x":"h_aqenn11OFT1-jMQ727gIFarWVeYRkynOIDcYRGSOY"}}},"counter":3,"transports":null,"user_verified":true,"backup_eligible":false,"backup_state":false,"registration_policy":"discouraged","extensions":{"cred_protect":"NotRequested","hmac_create_secret":"NotRequested","appid":"NotRequested","cred_props":"Ignored"},"attestation":{"data":{"Basic":["MIIC2DCCAcCgAwIBAgIJAPkeEJBFzRXcMA0GCSqGSIb3DQEBCwUAMC4xLDAqBgNVBAMTI1l1YmljbyBVMkYgUm9vdCBDQSBTZXJpYWwgNDU3MjAwNjMxMCAXDTE0MDgwMTAwMDAwMFoYDzIwNTAwOTA0MDAwMDAwWjBuMQswCQYDVQQGEwJTRTESMBAGA1UECgwJWXViaWNvIEFCMSIwIAYDVQQLDBlBdXRoZW50aWNhdG9yIEF0dGVzdGF0aW9uMScwJQYDVQQDDB5ZdWJpY28gVTJGIEVFIFNlcmlhbCAyNjk0OTE5NjEwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAATxBlFac6ZCOTaesMSVQq-qRj_pCX5LiTu2t9QhAnsXkanB0XQM4d_lfJW_YIlWvegwqiDVb9IFIBOHWC5patxso4GBMH8wEwYKKwYBBAGCxAoNAQQFBAMFBAMwIgYJKwYBBAGCxAoCBBUxLjMuNi4xLjQuMS40MTQ4Mi4xLjcwEwYLKwYBBAGC5RwCAQEEBAMCBSAwIQYLKwYBBAGC5RwBAQQEEgQQ7ogoeXIcSROXdT38zpcHKjAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEBCwUAA4IBAQCocCl0EQ8Ke0ySq5k4TyiCmDNWPz8KRz8lg4Gpliwg4KuWfK3S7klIfaqDpEkYUtlYsZPfckEL-_0u0ldjNzG63NwmEmFmKmAA1fVYRRSTfhiY6eIWeikeEajFkatlckQ7apazTTxCx2oO53B7PoGVzznPb1BcUKyCClGzrJg703nbNuwxcnGx6A6ctOomTC3InptvVPkVsC7ekYiTgAPanPJw0jCDSjPEaLVVh3Y7U79siV9fGFoazCoCwDpJ0AusKEZ-9HgZ9nx-zBUaHyPgiLetfCIh6y-yX68Jhc1QaWXOfFro81TLwc3kzKQe83B16eILycdxFRZWOROW2YpK"]},"metadata":{"Packed":{"aaguid":"ee882879-721c-4913-9775-3dfcce97072a"}}},"attestation_format":"Packed"}}
  • 1679 bytes
• ES256
  • {"cred":{"cred_id":"Od9v8eovle9HgTY_MchbBP5_5wmrhhjFmnAq0oKryUIhvsuEYprXXdyO0ezka8WWS_frMPz0xr2KmU-jRnY0hw","cred":{"type_":"ES256","key":{"EC_EC2":{"curve":"SECP256R1","x":"M9Etc2vDxSiNsFNqm8AKvfUE6WUerF85EeAxGqUMluw","y":"fGU80eXX1XLN1Sci5TEp-ibb3Weh0z9CiACSMnpc0J8"}}},"counter":3,"transports":null,"user_verified":true,"backup_eligible":false,"backup_state":false,"registration_policy":"discouraged","extensions":{"cred_protect":"NotRequested","hmac_create_secret":"NotRequested","appid":"NotRequested","cred_props":"Ignored"},"attestation":{"data":{"Basic":["MIIC2DCCAcCgAwIBAgIJAPkeEJBFzRXcMA0GCSqGSIb3DQEBCwUAMC4xLDAqBgNVBAMTI1l1YmljbyBVMkYgUm9vdCBDQSBTZXJpYWwgNDU3MjAwNjMxMCAXDTE0MDgwMTAwMDAwMFoYDzIwNTAwOTA0MDAwMDAwWjBuMQswCQYDVQQGEwJTRTESMBAGA1UECgwJWXViaWNvIEFCMSIwIAYDVQQLDBlBdXRoZW50aWNhdG9yIEF0dGVzdGF0aW9uMScwJQYDVQQDDB5ZdWJpY28gVTJGIEVFIFNlcmlhbCAyNjk0OTE5NjEwWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAATxBlFac6ZCOTaesMSVQq-qRj_pCX5LiTu2t9QhAnsXkanB0XQM4d_lfJW_YIlWvegwqiDVb9IFIBOHWC5patxso4GBMH8wEwYKKwYBBAGCxAoNAQQFBAMFBAMwIgYJKwYBBAGCxAoCBBUxLjMuNi4xLjQuMS40MTQ4Mi4xLjcwEwYLKwYBBAGC5RwCAQEEBAMCBSAwIQYLKwYBBAGC5RwBAQQEEgQQ7ogoeXIcSROXdT38zpcHKjAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEBCwUAA4IBAQCocCl0EQ8Ke0ySq5k4TyiCmDNWPz8KRz8lg4Gpliwg4KuWfK3S7klIfaqDpEkYUtlYsZPfckEL-_0u0ldjNzG63NwmEmFmKmAA1fVYRRSTfhiY6eIWeikeEajFkatlckQ7apazTTxCx2oO53B7PoGVzznPb1BcUKyCClGzrJg703nbNuwxcnGx6A6ctOomTC3InptvVPkVsC7ekYiTgAPanPJw0jCDSjPEaLVVh3Y7U79siV9fGFoazCoCwDpJ0AusKEZ-9HgZ9nx-zBUaHyPgiLetfCIh6y-yX68Jhc1QaWXOfFro81TLwc3kzKQe83B16eILycdxFRZWOROW2YpK"]},"metadata":{"Packed":{"aaguid":"ee882879-721c-4913-9775-3dfcce97072a"}}},"attestation_format":"Packed"}}
  • 1648 bytes

≈ 1.019 times larger
Total impact on storage:
(1679x + 1648(t - x)) / 1648t = (31x + 1648t) / 1648t = 31x/1648t + 1 for t,x ∈ ℕ where t > 0, x ≤ t, t is total registrations, and x is total Ed25519 registrations. For example if 5% of authenticators support Ed25519, then 31/1648 x .05 + 1 = 1.000940534 times more storage will be used which is an increase of 0.0940534%.

Entire payload that does not rely on attestation, AAGUID, or platform type:

• Ed25519
  • {"cred":{"cred_id":"Eu1bpj-SFUPqY-AwoSWhl2n-7Q2Ji_-JfGGedxXIQhxQzpCaOaQ0fKIV4yTWmnsZiY8Jyj96cjfleyueTqBrBlxLBJcKzIAzj_qS1bvvlVKj-L-p0FzAiURm2i5iZnc3FGQoNx2vALqPmWaELJj4nfFj0ChxNb31A22Ikf2BWJM","cred":{"type_":"EdDSA","key":{"EC_OKP":{"crv":"Ed25519","x":"_i9Hh8wQSq-Aa4q_V2z9uTkR4ntO-BxavrjSn0FOZjE"}}},"counter":3,"transports":null,"user_verified":true,"backup_eligible":false,"backup_state":false,"registration_policy":"discouraged","extensions":{"cred_protect":"NotRequested","hmac_create_secret":"NotRequested","appid":"NotRequested","cred_props":"Ignored"},"attestation":{"data":"None","metadata":"None"},"attestation_format":"None"}}
  • 639 bytes
• ES256
  • {"cred":{"cred_id":"ciZIo6aPZRhA9Y-9dL-gZ_eWJpFaBY24duoAuCkYKZ4E519MoGOObGouaXJ29RANLPP8aa-Po8VU6DpYdLdsrQ","cred":{"type_":"ES256","key":{"EC_EC2":{"curve":"SECP256R1","x":"40_QHyoxf6UGOd-laguPdmMNsu6nbvBCeZBH0b4JcfI","y":"MF3jWGhEkR0GU2nqEsZ59NQZCOEBJDzag3KjRDbAUBk"}}},"counter":3,"transports":null,"user_verified":true,"backup_eligible":false,"backup_state":false,"registration_policy":"discouraged","extensions":{"cred_protect":"NotRequested","hmac_create_secret":"NotRequested","appid":"NotRequested","cred_props":"Ignored"},"attestation":{"data":"None","metadata":"None"},"attestation_format":"None"}}
  • 608 bytes

≈ 1.051 times larger
Total impact on storage:
(639x + 608(t - x)) / 608t = (31x + 608t) / 608t = 31x/608t + 1 for t,x ∈ ℕ where t > 0, x ≤ t, t is total registrations, and x is total Ed25519 registrations. For example if 5% of authenticators support Ed25519, then 31/608 x .05 + 1 = 1.002549342 times more storage will be used which is an increase of 0.2549342%.

CredentialID:

• Ed25519
  • SPH4JpOewjA7cDMF8exK8cURnJwk8ZS8TP7y7mwqRY05iY1elOk-2b-dhfO7soT_kWvHtazb7AVIwfe9roAgBYOsKnqWQXjqIeyTgl2xszEhvqcTcm7TbVHTeVOif21esbQ3bwbWHmYqD0UptomBsV5IbwXRgy8VY7JGfmCsKzI
  • 171 bytes
• ES256
  • EOd9v8eovle9HgTY_MchbBP5_5wmrhhjFmnAq0oKryUIhvsuEYprXXdyO0ezka8WWS_frMPz0xr2KmU-jRnY0hw
  • 86 bytes

≈ 1.988 times larger
Total impact on storage:
(171x + 86(t - x)) / 86t = (85x + 86t) / 86t = 85x/86t + 1 for t,x ∈ ℕ where t > 0, x ≤ t, t is total registrations, and x is total Ed25519 registrations. For example if 5% of authenticators support Ed25519, then 85/86 x .05 + 1 = 1.049418605 times more storage will be used which is an increase of 4.9418605%.

If/when serialization is changed to reduce the overall payload, then hopefully this will be revisited. Additionally a simplistic argument like "storage is twice the size" is not valid. To employ reductio ad absurdum, if only one byte was needed for ES256 and two bytes for Ed25519, you'd presumably allow it despite it still using twice the storage not to mention that if ES256 were twice the size of RSA it would still likely be included.

More generally, it's clear the goalposts are being shifted to fit the narrative. When one wants to have a logically consistent and unbiased argument, one comes up with the rules/axioms a priori and ensures each rule/axiom does not contradict another regardless of how deep you must delve into that point to discover the contradiction. Once these rules are established, you then let the chips fall where they may. I doubt any consideration of comparative storage size was done when deciding to implement ES256 or RSA. Furthermore storage size is but one component that should be considered in aggregate with other aspects. I don't see how an effective increase of less than 1% on storage is enough to discount all the other advantages.

Last the conclusion of forcing one to use webauthn-rs-core seems draconian. That crate explicitly states:

"⚠️ ⚠️ ⚠️ THIS IS UNSAFE. AVOID USING THIS DIRECTLY ⚠️ ⚠️ ⚠️

If possible, use the webauthn-rs crate, and it’s safe wrapper instead!

Webauthn as a standard has many traps that in the worst cases, may lead to bypasses and full account compromises. Many of the features of webauthn are NOT security policy, but user interface hints. Many options can NOT be enforced. webauthn-rs handles these correctly. USE webauthn-rs INSTEAD."

Why force one to violate what the crate states just because they want to use Ed25519? Couldn't a function/method be added to webauthn_rs::WebauthnBuilder that allows one to enable and prioritize Ed25519?

[yaleman]

For my part I'm not a fan of chasing draft specs, so adding things pre-emptively to chase possibilities feels like a waste of dev time.

[Firstyear]

We have support for things that we don't always advertise by default. There is precedent to support ed25519 in the core library and not to expose it by default so that we can ensure it works correctly.

[zacknewman]

So this means that it should not be added at all to secure_algs and that it should remain last in all_possible_algs?

[Firstyear]

Initially yes.

[yaleman]

And by "dev time", you mean 20 seconds.

This has already taken far more than 20 seconds.

[zacknewman]

I was referring to writing the code obviously. Again, I have 5 other reasons to support it even if one of them is not relevant (i.e., "chasing draft specs").

[Firstyear]

* Most cryptographers would order those algorithms the same way by security; or at the very least, would _not_ put Ed25519 after the other two (i.e., at worst, it's as good).

The primary difference is that ECDSA signatures require randomness during the signature process. Since authenticators have self contained high quality RNG for key generation in the first place, this is not vulnerable to the same issues as say a software implementation. Compromise of the RNG of a device would also compromise it's ed25519 keys.

* Code is easier to write and read; thus less likely to have bugs and easier to audit.

This is not true, the order doesn't affect this.

* Client authenticators will ignore any unsupported algorithms, so any argument that relies on the popularity of an algorithm is irrelevant.

Authenticators also don't use the supplied algorithm list in order either. They are free to pick and choose what they want to respond with. It is "best effort" https://w3c.github.io/webauthn/#dom-publickeycredentialcreationoptions-pubkeycredparams

* The order aligns with the order of best performance and inversely with the size of signatures.

This is subjective - not all crypto libraries impls have optimised implementations of these algorithms.

* There is no NIST/NSA connection with Ed25519.

We do not engage in conspiracy theories in this project.

The reality of the situation is that most authenticators do NOT support ed25519. The recommendations in w3c were made by one person to "encourage" future development of ed25519 - it is not about "security". Similar, there are plenty of other recommendations in w3c and the fido space that we simply ignore because they harm users.

Our policy is "correct, simple, fast.". Currently ecdsa is proven to be correct, secure and is the most widely supported authenticator key type. We see no reason to deviate from this.

[zacknewman]

The primary difference is that ECDSA signatures require randomness during the signature process. Since authenticators have self contained high quality RNG for key generation in the first place, this is not vulnerable to the same issues as say a software implementation. Compromise of the RNG of a device would also compromise it's ed25519 keys.

The algorithm is susceptible to more attacks than Ed25519 regardless of the entropy source or "randomness" used to construct the private key. ECDSA is also more susceptible to problems due to a poor RNG even more so than RSA and EdDSA.

* Client authenticators will ignore any unsupported algorithms, so any argument that relies on the popularity of an algorithm is irrelevant.

Authenticators also don't use the supplied algorithm list in order either. They are free to pick and choose what they want to respond with. It is "best effort" https://w3c.github.io/webauthn/#dom-publickeycredentialcreationoptions-pubkeycredparams

Of course they pick what algorithm, but this list is in order by preference:

This member lists the key types and signature algorithms the Relying Party supports, ordered from most preferred to least preferred. The client and authenticator make a best-effort to create a credential of the most preferred type possible. If none of the listed types can be created, the create() operation fails.

* The order aligns with the order of best performance and inversely with the size of signatures.

This is subjective - not all crypto libraries impls have optimised implementations of these algorithms.

It's statistically true. It's "subjective" that LeBron James could beat me in a game of basketball, but it's near 100% accurate. If you'd like, I can construct benchmarks using openssl.

* There is no NIST/NSA connection with Ed25519.

We do not engage in conspiracy theories in this project.

Not a conspiracy theory. NSA has made recommendations to NIST in the past about what primitives to use for the purposes of being able to more easily subvert the algorithm. The construction of curve P-256 was not justified and violates nothing up my sleeve.

The reality of the situation is that most authenticators do NOT support ed25519. The recommendations in w3c were made by one person to "encourage" future development of ed25519 - it is not about "security". Similar, there are plenty of other recommendations in w3c and the fido space that we simply ignore because they harm users.

Our policy is "correct, simple, fast.". Currently ecdsa is proven to be correct, secure and is the most widely supported authenticator key type. We see no reason to deviate from this.

Ed25519 is also proven to be correct and secure. Again, this is an argument of not supporting EdDSA at all.

[Firstyear]

Coming back to this. We aren't going to enable this by default for a very simple reason - eddsa credential id's are more than double the size of a ecdsa or rsa key.

Recently we implemented a fake credential ID generator that required us to investigate this. We found that apple key chain handles are 20 bytes, tpm rsa key handles are 32 bytes, yk ecdsa keys were 64 bytes, but yk eddsa keys are 128 and solokeys were more than 250 bytes.

This means that every "gain" in signature performance, is removed by the fact you double the storage requirements in your database. Suddenly this isn't zero-cost improvement - it's a very expensive one. This is supported by the fact we have users asking us to assist in reducing our credential storage footprint already.

For now, we will leave eddsa as an "opt in" via the rs-core interface, as there is no pressing need to enable it by default.