Categories
Cryptography

Guidance for Choosing an Elliptic Curve Signature Algorithm in 2022

A cartoon wild canid on the Internet provides general guidance on elliptic curve cryptography parameter choices.

Earlier this year, Cendyne published A Deep Dive into Ed25519 Signatures, which covered some of the different types of digital signature algorithms, but mostly delved into the Ed25519 algorithm. Truth in advertising.

This got me thinking, “Why isn’t there a better comparison of different elliptic curve signature algorithms available online?”

Art: LvJ

Most people just defer to SafeCurves, but it’s a little dated: We have complete addition formulas for Weierstrass curves now, but SafeCurves doesn’t reflect that.

For the purpose of simplicity, I’m not going to focus on a general treatment of Elliptic Curve Cryptography (ECC), which includes pairing-based cryptography, Elliptic-Curve Diffie-Hellman, and (arguably) isogeny cryptography.

Instead, I’m going to focus entirely on elliptic curve digital signature algorithms.

Note: The content of this post is a bit lower-level than most programmers ever need to be concerned with. If you’re a programmer and interested in learning cryptography, start here. If you’re looking for library recommendations, libsodium is a good safe default.

Compliance Rules Everything Around Me

If you have to meet some arbitrary compliance requirements (i.e. FIPS 140-3, CNSA, etc.), your decision is already made for you, and you shouldn’t waste your time reading blogs like this that will only get your hopes up about the options available to you.

Choose the option your compliance officer demands, and hope it’s good enough.

“Sure, let me check that box.”
Art: LvJ

Elliptic Curves for Signature Algorithms

Let’s start with the same curve Cendyne analyzed: Ed25519.

Ed25519 (EdDSA, Curve25519)

Ed25519 is one of the two digital signature algorithms today that use the EdDSA algorithm framework. The other is Ed448, which targets a higher security level (224-bit vs 128-bit) but is also slower and uses SHAKE256 (which is overkill and not great for performance).

Ed25519 is a safe default choice for most applications where a digital signature is appropriate, for many reasons:

  1. Ed25519 uses deterministic nonces, which means you’re severely unlikely to ever reproduce the Sony ECDSA k-reuse bug in your system.

    The deterministic nonce is calculated from the SHA512 hash of the secret key and message. Two invocations to crypto_sign_ed25519() with the same message and secret key will produce the same signature, but the intermediate nonce value is never revealed to an attacker.
  2. Ed25519 includes the public key in the data hashed to produce the signature (more specifically s from the (R,s) pair). This offers a property that ECDSA lacks: Exclusive Ownership. I’ve written about this property before.

    Without Exclusive Ownership, it’s possible to create a single signature value that’s valid for multiple different (message, public key) pairs.

Years ago, there would have an additional list item: Ed25519 uses Edward Curves, which have complete addition formulas and are therefore safer to implement in constant-time than Weierstrass curves (i.e. the NIST curves). However, we now have complete addition formulas for Weierstrass curves, so this has become a moot point (assuming your implementation uses complete addition formulas).

Ed25519 targets the 128-bit security level.

Why Not Use Ed25519?

There is one minor pitfall of Ed25519 that makes it unsuitable for esoteric uses (say, Ring Signature Schemes or zero-knowledge proofs): Ed25519 is not a prime-order group; it has a cofactor h = 8. This detail famously created a double-spend vulnerability in all CryptoNote-based cryptocurrencies (including Monero).

For systems that want the security of Ed25519 and its various well-studied implementations, but still need a prime-order group for their protocol, cryptographers have developed the Ristretto Group to meet your needs.

If you’re working on embedded systems, the determinism inherent to EdDSA might be undesirable due to the possibility of fault attacks. You can use a hedged variant of Ed25519 to mitigate this risk.

Additionally, Ed25519 is not approved for many government applications, although it did make the latest draft revision of FIPS 186 in 2019. If you care about compliance (see above), you cannot use Ed25519. Yet.

A niche Internet meme for cryptography engineers

Guidance for Ed25519

Unless legally prohibited, Ed25519 should be your default choice, unless you need a prime-order group. In that case, build your desired protocol atop Ristretto255.

If you’re not sure if you need a prime-order group, you probably don’t. It’s a specialized requirement for uncommon use cases (ring signatures, password authenticated key exchange protocols, zero-knowledge proofs, etc.).

Art: LvJ

The Bitcoin Curve (ECDSA, secp256k1)

Secp256k1 is a Koblitz curve, which is a special case of Weierstrass curves that are more performant when used in binary fields, of the form, y^2=x^3 + 7. This curve is almost exclusively used in cryptocurrency software.

There is no specified reason why Bitcoin chose secp256k1 over another elliptic curve at the time of its inception, but we can speculate:

The author was a pseudonymous contributor to the Metzdowd mailing list for cypherpunks, and probably didn’t trust the NIST curves. Since Ed25519 didn’t exist at the time, the only obvious choice for a hipster elliptic curve parameter selection was to rely on the SECG recommendations, which specify the NIST and Koblitz curves. If you cross the NIST curves off the list, only the Koblitz curves remained.

Therefore, the selection of secp256k1 is likely an artefact of computer history and not a compelling reason to select secp256k1 in new designs. Please look elsewhere.

Fact: Imgflip didn’t have a single secp256k1 meme until I made this one.

Secp256k1 targets the 128-bit security level.

Guidance for secp256k1

Don’t bother, there are better options. (i.e. Ed25519)

If you’re writing software for a cryptocurrency-related project, and you feel compelled to use secp256k1 for the sake of reducing your code footprint, please strongly consider the option of burning everything to the proverbial ground.

Soatok angrily grasping computer monitor
Cryptocurrency sucks!
Art: Swizz

Cryptocurrency Aside, Why Avoid Secp256k1?

As we noted above, secp256k1 isn’t widely used outside of cryptocurrency.

As a direct consequence of this (as we’ll discuss in the NIST P-256 section), most cryptography libraries don’t offer optimized, side-channel-resistant implementations of secp256k1; even if they do offer optimized implementations of NIST P-256.

(Meanwhile, Ed25519 is designed to be side-channel and misuse-resistant, partly due to its Schnorr construction and constant-time ladder for scalar multiplication, so any library that implements Ed25519 is overwhelmingly likely to be constant-time.)

Therefore, any secp256k1 library for most programming languages that isn’t an FFI wrapper for libsecp256k1 will have worse performance than the other 256-bit curves.

Additionally, secp256k1 implementations are often a source of exploitable side-channels that permit attackers to pilfer your secret keys.

The previously linked article was about BouncyCastle’s implementation (which covers Java and .NET), but there’s still plenty of secp256k1 implementations that don’t FFI libsecp256k1.

From a quick Google Search:

  • Python (uses EEA rather than Binary GCD for modular inverse)
  • Go (uses Numbers, which weren’t designed for cryptography)
  • PHP (uses GMP, which isn’t constant-time)
  • JavaScript (calls here, which uses bn.js, which isn’t constant-time)

If you’re using secp256k1, and you’re not basing your choice on cybercash-interop, you’re playing with fire at the implementation and ecosystem levels–even if there are no security problems with the Koblitz curve itself.

You are much better off choosing any different curve than secp256k1 if you don’t have a Bitcoin/Ethereum/etc. interoperability requirement.

“No thanks, I use Ed25519.”
Art: LvJ

NIST P-256 (ECDSA, secp256r1)

NIST P-256 is the go-to curve to use with ECDSA in the modern era. Unlike Ed25519, P-256 uses a prime-order group, and is an approved algorithm to use in FIPS-validated modules.

Most cryptography libraries offer optimized assembly implementations of NIST P-256, which makes it less likely that your signing operations will leak timing information or become a significant performance bottleneck.

P-256 targets the 128-bit security level.

Why Not Use P-256?

Once upon a time, P-256 was riskier than Ed25519 (for signatures) and X25519 (for Diffie-Hellman), due to the incomplete addition formulas that led to timing-leaky implementations.

If you’re running old software, you may still be vulnerable to timing attacks that can recover your ECDSA secret key. However, there is a good chance that you’re on a modern and secure implementation in 2022, especially if you’re outsourcing this to OpenSSL or its derivatives.

ECDSA requires a secure randomness source to sign data. If you don’t have one available, and you sign anything, you’re coughing up your secret key to any attacker capable of observing multiple signatures.

Guidance for P-256

P-256 is an acceptable choice, especially if you’re forced to cope with FIPS and/or the CNSA suite requirements when using cryptography.

Of course, if you can get away with Ed25519, use Ed25519 instead.

If you use P-256, make sure you’re using it with SHA-256. Some implementations may default to something weaker (e.g. SHA-1).

If you’re also going to be performing ECDH with P-256, make sure you use compressed points. There used to be a patent; it died in 2018.

If you can afford it, make sure you use deterministic ECDSA (RFC 6979) or hedged signatures (if fault attacks are relevant to your threat model).

Art: LvJ

NIST P-384 (ECDSA, secp384r1)

NIST P-384 has a larger field than the curves we’ve previously examined, which allows P-384 to target the 192-bit security level. That’s the primary reason why anyone would choose P-384.

Naturally, elliptic curve security is more complicated than merely security against the Elliptic Curve Discrete Logarithm Problem (ECDLP).

P-384 is most often paired with SHA-384, which is the most widely used flavor of the SHA-2 family hash functions that isn’t susceptible to length-extension attacks. (There are also truncated SHA-512 variants specified later, but that’s also what SHA-384 is under-the-hood.)

If you’re aiming to build a “secure-by-default” tool for a system that the US government might one day become a customer of, with minimal cryptographic primitive choice, using NIST P-384 with SHA-384 makes for a reasonably minimalistic bundle.

Why Not Use P-384?

Unlike P-256, most P-384 implementations don’t use constant-time, optimized, and/or formally verified assembly code. (Notable counter-examples: AWS-LC and Go x/crypto.)

Like P-256, P-384 also requires a secure randomness source to sign data. If you aren’t providing one, expect your signing key to end up on fail0verflow one day.

Guidance for P-384

If you use P-384, make sure you’re using it with SHA-384.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art by Kyume
Art: Kyume

NIST P-521 (ECDSA, secp521r1)

Biggest curve is best curve! — the clueless

Systems that choose P-521 often have an interesting threat model, even though said threat model is rarely formally specified.

It’s overwhelmingly likely that what eventually breaks the 256-bit elliptic curves will also break P-521 in short order: Cryptography Relevant Quantum Computers.

The only thing P-521 does against CRQCs that P-256 doesn’t is require more quantum memory. If you’re worried about QRQCs, you might want to look into hybrid post-quantum signature schemes.

If you’re choosing P-521 in your designs, you’re basically saying, “I want to have 256 bits of asymmetric cryptographic security, come hell or high water!” even though the 128-bit security level is likely just fine for your actual threats.

Aside: P-521 and 512-bit ECC Security

P-521 is not a typo, although people sometimes think it is. P-521 uses the Mersenne prime 2^{521}-1 instead of a 512-bit near-Mersenne prime.

This has led to an unfortunate trend in cryptography media to map ECC key sizes to symmetric security levels that misleads people as to the relationship between the two. For example:

Regrettably, this is misleading, because plotting the ECC Key Size versus equivalent Symmetric Security isn’t a how ECDLP security works. The ratio of the exponents involved is totally linear; it doesn’t suddenly increase beyond 384-bit curves for a mysterious mathematical reason.

  • 256-bit Curves target the 128-bit security level
  • 384-bit Curves target the 192-bit security level
  • 512-bit Curves target the 256-bit security level
  • 521-bit Curves actually target the 260-bit security level, but that meets or exceeds the 256-bit security level, so that’s how the standards are interpreted

The reason for this boils down entirely to the best attack against the Elliptic Curve Discrete Logarithm Problem: Pollard’s Rho, which recovers the secret key from an n-bit public key (which has a 2^{n} search space) in \sqrt{2^{n}} guesses.

Taking the square root of a number is the same as halving its exponent, so the security level is half: \sqrt{2^{n}} = 2^{n/2}.

Takeaway: If someone tells you that you need a 521-bit curve to meet the 256-bit security level, they are mistaken and it’s not their fault.

Art: Harubaki

Why Not Use P-521?

It’s slow. Much slower than P-256 and Ed25519. Modestly slower than P-384.

Unlike P-384, you’re less likely to find an optimized, constant-time P-521 implementation.

Guidance for P-521

First, make a concerted effort to figure out the motivation for P-521 in your designs. Chances are, someone is putting too much emphasis on the wrong things for security.

If you use P-521, make sure you’re using it with SHA-512.

The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.

Art: LvJ

Ed448 (EdDSA, Curve448)

Ed448 is the P-521 of the Edwards curves: It mostly exists to give standards committees a psychological comfort for the unlikely event that 256-bit ECC is desperately broken but ECC larger than 384 bits is somehow still safe.

The very concept of having multiple “security levels” for raw cryptography primitives is mostly an artefact of the historical military roots of cryptography, rather than a serious consideration in the modern world.

Unfortunately, this leads to implementations that prioritize runtime algorithm selection negotiation, which maximizes the risk of protocol-level vulnerabilities. See also: JWT.

Ed448 was specified to use SHAKE256, which is a needlessly conservative decision which leads to an unnecessary performance bottleneck.

Why Not Use Ed448?

Aside from the performance hit mentioned previously, there’s no compelling reason to avoid Ed448 that isn’t also true of either Ed25519 or P-384.

Guidance for Ed448

If you want more speed, go with Ed25519. In addition to being faster, Ed25519 is also very widely supported.

If you need a prime-order field, use Decaf with Ed448 or consider P-384.

The Brainpool Curves

The main motivation for the Brainpool curves is that the NIST curves were not generated in a “verifiable pseudo-random way”.

The only reasons you’d ever want to support the Brainpool curves include:

  1. You think the NIST curves are somehow backdoored by the NSA
  2. You don’t appreciate small attack surfaces in cryptography libraries
  3. The German government told you to (see: compliance)

Most of the advice for the NIST Curves at each security level can be copy/pasted for the Brainpool curves, with one important caveat:

When considering real-world implementations, Brainpool curves are more likely to use the general purpose Big Number procedures (which aren’t always constant-time), rather than optimized assembly code, than the NIST curves are.

Therefore, my general guidance for the Brainpool curves is simply:

  1. Proceed at your own peril
  2. Consider hiring a cryptography engineer to study the implementation you’re relying on, especially with regard to timing attacks
Me when I hear “brainpool”
Art: LvJ

Re-Examining the SafeCurves Criteria

Here’s a 2022 refresh of the SafeCurves criteria for all of the curves considered by this blog post.

SafeCurve CriteriaRelevance to the Curves Listed Above
FieldsAll relevant curves satisfy the requirements
EquationsAll relevant curves satisfy the requirements
Base PointsAll relevant curves satisfy the requirements
RhoAll relevant curves satisfy the requirements
TransfersAll relevant curves satisfy the requirements
DiscriminantsOnly secp256k1 doesn’t satisfy the requirements (out of the curves listed in this blog post)
RigidityThe NIST curves do not meet this requirement.

If you care about whether or not the standards were manipulated to insert a backdoor, rigidity matters to you. Otherwise, it’s not a deal-breaker.
LaddersWhile a Montgomery ladder is beneficial for speed and implementation security, it isn’t strictly speaking required.

This is an icing-on-the-cake consideration.
TwistsThe only curve listed above that doesn’t meet the requirement is the 256-bit Brainpool curve (brainpoolp256t1).
CompletenessAll relevant curves satisfy the requirements, as of 2015.

SafeCurves is out of date here.
IndistinguishabilityAll relevant curves satisfy the requirements, as of 2014.

SafeCurves continues to be a useful resource, especially if you stray from the guidance on this page.

For example: You wouldn’t want to use pairing-friendly curves for general purpose ECC digital signatures, because they’re suitable for specialized problems. SafeCurves correctly recommends not using BN(2,254).

However, SafeCurves is showing its age in 2022. BN curves still end up in digital signature protocol standards even though BLS-12-381 is clearly a better choice.

The Internet would benefit greatly for an updated SafeCurves that focuses on newer elliptic curve algorithms.

Art: Scruff

TL;DR

Ed25519 is great. NIST P-256 and P-384 are okay (with caveats). Anything else is questionable, and their parameter selection should come with a clear justification.

19 replies on “Guidance for Choosing an Elliptic Curve Signature Algorithm in 2022”

Hi,

This is the first time I’m commenting, so first of all, thank you for all the great content on this blog!

If I may nit-pick a bit:

– I think “a special case of Weierstrass curves that can be used in binary fields” is a bit misleading, I think it would be more accurate to say that they have special properties that can be used to boost performance especially over binary fields (which is what the linked source says, btw). One point is, working on binary fields is nothing specific to Koblitz curves. The other point is Koblitz curves on prime fields use a different equation than Koblitz curves on binary fields, so they’re not that directly related (Koblitz curves on prime fields just try to transfer to the prime field case one trick that happens to be quite important in the case of binary fields, that’s all). In particular, it would be wrong to think you can somehow take secp256k1 and “use it in binary fields”, while I think that’s one reasonable intepretation of your wording.

– I’m not seeing anything wrong with the table you show at the beginning of section “Aside: P-521 and 512-bit ECC Security”. I don’t think it’s “plotting the ECC Key Size versus equivalent Symmetric Security”, but ECC key size vs equivalent RSA key size. The ratio explodes because “The ratio of the exponents [between ECDLP and symmetric] is totally linear” as you say, but it famously isn’t the case for RSA, where sub-exponential attacks exist. I agree with the general point that the reason we have 521 instead of 512 here is because of the Mersenne prime, which was chosen for performance and not because we would need the extra 9 bits to reach the 512-bit level for some mysterious reason. But I just don’t see what that has to do with the quoted table.

– “Unlike Ed25519, P-256 uses a prime-order field” I think that’s a typo an you mean group here.

That’s it, sorry for picking on details, and again thanks for al the great content!

With regards to FIPS it is possible to include non-NIST curvs. There is an Implementation Guidance (https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Module-Validation-Program/documents/fips140-2/FIPS1402IG.pd and https://csrc.nist.gov/CSRC/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf) that allows the use of non-NIST curves for FIPS 140-2 and FIPS 140-3 under the CMVP. IG A.2 (-2) and IG C.A (-3) explicitly permit the use of non-NIST-recommended curves in a module’s Approved mode of operation.

There are also two draft publications (FIPS 186-5 and SP 800-186) that (when published) will formally recognize the curves in Section 3.5 as FIPS Approved. Public comment period closed in January 2020. Section 7.1 in the draft of FIPS 186-5 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft.pdf) identifies Edwards-curve Digital Signature Algorithms and considers them Approved (as long as the “shall” statements are met). Curve25519 is identified in Section 4.2 of SP 800-186 (https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf). ACVP validation testing (https://usnistgov.github.io/ACVP/) for these algorithms should follow once FIPS 186-5 and SP 800-186 are published. Until ACVP testing is available a these functions can be included in the module’s Approved mode of operation as “vendor affirmed”.

I know it’s, strictly speaking, “possible”. But in practice, nobody I’ve ever worked with wanted to rock the compliance boat by deviating from the well-tread path. FIPS certifications are already severely backlogged due to COVID-19 (by at least 3 months).

Additional nitpick: the following is incorrect.

“Indistinguishability: Only Ed25519 and Ed448 satisfy this requirement.”

All curves satisfy this requirement, at least as of 2014. See the Elligator Squared paper (eprint 2014/043) and its follow-ups.

One thing I didn’t see mentioned is how curve/signature algorithm affects privacy. NIST curves and ECDSA allow the public key to be recovered from the signature (section 4.1.6 of http://www.secg.org/sec1-v2.pdf), which can act as a tracking identifier. I’m not aware of Ed25519 having this vulnerability. But, this info is from several years ago so it may no longer be relevant.

You need one additional bit to recover the public key from a signature, otherwise you recover two candidate public keys and cannot distinguish one from the other. I’ve not heard of this “feature” existing in EdDSA, either, but I could be missing something.

Very interesting and very much applicable to my requirements, which include FIPS compliance. I was wondering if you could comment on the “sect” (versus “secp”) curves as well? My requirements dictate 384-bit or better, so I’m thinking that I’ll stick with just secp384r1 and potentially allow secp521r1 but from your article, it seems like I don’t really gain much from doing so. But this morning I saw “sect” curves mentioned (on the ActiveMQ mailing list) and so I was wondering if you had any thoughts on that? Thanks.

I would advise against binary curves unless you have a specific need to support them. “sect” are elliptic curves over binary fields rather than prime fields.

Bark My Way

This site uses Akismet to reduce spam. Learn how your comment data is processed.