ECDSA support

[tarcieri]

With the simplified cryptographic scheme (#73) of Biscuit 2.0 (#72), it becomes possible to support other cryptographic algorithms.

I would like to make a suggestion to support ECDSA in conjunction with the NIST P-256 elliptic curve. Full disclosure I am a maintainer of the ecdsa and p256 Rust crates.

The main reason for supporting ECDSA/P-256 is compatibility with hardware tokens, smartcards, and SEPs. Notably the following devices support it, and don't support Ed25519:

• Yubikey 4/5 devices
• iOS/macOS Keychain + SEP

The use case would be registering the ECDSA public key associated with a hardware-backed private key and allowing a user to sign Biscuits with that hardware-backed private key.

ECDSA has a somewhat notorious past of sharp edges and implementation mistakes. The two biggest are:

• Dependence on a random scalar k which if selected in a biased manner leaks the private key. This is mitigated through using a pseudorandom scalar selected by rejection sampling as standardized in RFC6979, a method not too far off from how Ed25519 works
• Incomplete addition formulas were often used to implement the NIST curves, e.g. Jacobian formulas. I'll note that the p256 crate at least implements complete addition formulas for prime order elliptic curves. Other implementations may vary, although this is generally an issue impacting D-H/encryption rather than signatures

[Geal]

I'm wondering how that would play out with attenuation, where a new signature has to be made. Here are the possible scenarios:

• the signing algorithm can change on every block (ECDSA on one, Ed25519 on the next, etc). We would need a way to signal which algorithm should be used for the next signature (since the previous block chooses the key pair), and which algorithms should be used to verify each block, otherwise we'd try to verify a signature on P256 with the Ed25519 algorithm(are there possible issues when confusing curve algorithms there?). Unless there's a way from looking at the keys or signature to guess which kind they are?
• the signing algorithm is the same for the entire token. We still need a way to signal it. It can be done with a field like the root key id. That field does not need to be signed: the verifier could check that it matches the chosen root key

Apart from that field, the format would not change, keys and signatures are just byte arrays.

About the implementaton mistakes, do you think we can mandate the safer ways to sign?

[tarcieri]

I would suggest parameterizing each key with its algorithm, and leaving the signature itself opaque. The signature either verifies under a given key with a known algorithm or it doesn't.

As to whether or not you allow mix-and-match algorithms I could go either way. It seems useful in things like X.509 certificate chains to be able to use different signing algorithms, so for example you can upgrade CA certificates to new algorithms without all of their clients having to upgrade, and I suspect there are similar potential use cases here.

About the implementaton mistakes, do you think we can mandate the safer ways to sign?

The best I can suggest is documenting something to the effect of "Signers SHOULD use RFC6979 to select ECDSA ephemeral scalar k". You can also provide test vectors based on deterministic RFC6979, and mandate particular curve/digest combinations (e.g. ECDSA/P-256 w\ SHA-256, ECDSA/P-384 w\ SHA-384)

The problems with making RFC6979 a MUST are that if you want to support hardware tokens, they won't necessarily use RFC6979. Fully deterministic signature algorithms are problematic for hardware tokens due to fault attacks, so ones using RFC6979 would be best off supplementing it with added entropy. A fault attacker who is able to cause the device to produce the same k scalar for two different signatures can algebraically solve for the private key.

There's also no way for a verifier to check how k was selected, so it's really a "best practices" thing.

[Geal]

alright, it's starting with https://github.com/CleverCloud/biscuit/commit/f38c856c78c3e3792ff482b415b6c2501cc02a70 I'll try to integrate new algorithms next