Security Concerns Surrounding WebAuthn: Don't Implement ECDAA (Yet) - Paragon Initiative Enterprises Blog


Earlier this year, the World Wide Web Consortium (W3C) and FIDO Alliance shared their latest drafts for a standard Web Authentication API called WebAuthn.

For context (present and historical): The current version (as of this writing) of the WebAuthn specification lives here, and the most up-to-date version can be found here.

Our security team took an interest to this proposal since WebAuthn would be used in conjunction hardware two-factor authentication devices. Hardware 2FA has proven to be far more resilient against phishing attacks than HOTP or TOTP (meanwhile, SMS-based 2FA is essentially security theater; avoid like the plague).

Despite the importance of WebAuthn to web security for the years to come, our analysis of the standard reveals a lot of concerns that almost any cryptographer should have been able to identify and remedy earlier in the design phase.

Regardless of whether this was a failure of the W3C and/or FIDO Alliance to enlist the aid of cryptography engineers, or of the cryptography community to be more proactive in preventing the deployment of error-prone cryptographic designs, there is only one path forward; and that is to fix the design of WebAuthn before it's set in stone.

WebAuthn Security Risk Overview

WebAuthn employs a standard called COSE (RFC 8152), which builds on the error-prone JOSE standards.

In the COSE Algorithm Registrations section of the WebAuthn specification, it notes that RSASSA-PKCS1-v1_5 is already registered by COSE and then registers two additional COSE algorithm identifiers for use in WebAuthn, based on the FIDO Alliance's ECDAA algorithm.

Bleichenbacher's Monster Returns

As a consequence of its COSE legacy, WebAuthn specifically requires ongoing support for RSA with PKCS1v1.5 padding. Much has been written about the past twenty years of padding oracle and signature forgery vulnerabilities inherent to PKCS1v1.5 padding.

If you're not familiar with RSA with PKCS1v1.5 padding, just know that a team of researchers won a prestigious information security award at the Black Hat conference this year for discovering that systems are still vulnerable to decades-old vulnerabilities simply because they still support RSA PKCS1v1.5 padding.

As we covered in a previous blog post, it is possible to implement PKCS1v1.5 securely, but this requires an application-layer mitigation; your library can't do it for you.

If you didn't explicitly write your RSA-based protocol to side-step these PKCS1v1.5 vulnerabilities (and, instead, you just used whatever API your version of OpenSSL and/or programming language gave you), you're vulnerable! (Unless you don't use this padding mode, of course.)

So while support for RSA with PKCS1v1.5 padding is explicitly required in the FIDO2 server requirements, we implore nobody to ever actually allow this padding mode to be used.

In short: PKCS1v1.5 is bad. The exploits are almost old enough to legally drink alcohol in the United States. Don't use it!

ECDAA: Exceedingly Concerning Decisions About Authentication

To fully appreciate the security concerns with the FIDO Alliance's ECDAA specification, it's worth skimming over the past two decades of research into elliptic curve cryptography.

A Brief History of Real World Elliptic Curve Cryptography

In the year 2000, Biehl, et al. publishes a paper on Differential Fault Attacks on Elliptic Curve Cryptosystems (PDF), presented at CRYPTO 2000. This paper laid the groundwork for a class of active attacks against elliptic curve cryptosystems called invalid curve attacks. As recently as 2017, invalid curve attacks have threatened ECDH-ES in the JOSE standards.

In 2010 at the Chaos Communication Congress, fail0verflow exploits a k-value reuse to steal Sony's ECDSA secret key.

Cryptographers argued for a while about who to blame for this ECDSA failure, then Thomas Pornin published RFC 6797: Deterministic (EC)DSA in 2013 to prevent k-value reuse in ECDSA implementations (without breaking backwards compatibility). However, cryptographers arguing about the ECDSA failure wasn't a fruitless effort.

In 2013, Daniel J. Bernstein and Tanja Lange published SafeCurves, a website that evaluated a lot of popular elliptic curve designs on very rigorous criteria: It isn't sufficient for an elliptic curve cryptography algorithm to be secure against ECDLP attacks, there are a lot more requirements for making these algorithms secure in real world ECC. SafeCurves takes these requirements into account.

In 2016, the Crypto Forum Research Group approves the publication of RFC 7748 and RFC 8032.

These RFCs were the result of years of bikeshedding over the subtleties of elliptic curve designs and parameter choices: Weierstrass vs Montgomery vs Edwards curves, cofactors, twists, the tradeoffs of 1 mod 4 versus 3 mod 4, etc.

CFRG discussions are very intense, deeply technical, and at many points heated.

At some point the mounting tension in the CFRG was briefly broken by someone vigorously demanding feedback for their homemade cipher "Crystalline", to which renowned security expert and nocoiner Tony Arcieri eventually obliged.

Takeaway

  1. Invalid curve attacks leak your secret key
  2. Nonce reuse in ECDSA leaks your secret key
  3. Elliptic Curve Cryptography parameter choice is a very complicated issue best left to experts (who will still take years to arrive at a satisfactory answer)
  4. Don't roll your own crypto

ECDAA Considered Harmful

Out of all the hard-won ECC security lessons one could glean from the past two decades of real world security failures, ECDAA seems to have learned precisely none of them.

ECDAA Specifies Uncompressed Points

There are two schools of thought for preventing Invalid Curve Attacks:

  1. Tell implementors to verify that any points they receive are on the curve, and hope they remember to do so consistently.
  2. Use point compression and make it not their problem.

Point compression means sending only the X or Y coordinate, and the sign (positive or negative) of the other coordinate.

Point compression is widely regarded among cryptographers and cryptography engineers as the preferred mitigation strategy for preventing invalid curve attacks.

ECDAA explicitly specifies using uncompressed points (ECDAA specification, section 3.1.2 and WebAuthn, section 8.6), which allows an attacker to choose an (x,y) pair that isn't on the curve.

Point compression, by contrast, is not allowed per the current ECDAA specification; nor is it mentioned anywhere.

ECDAA Specifies Non-Deterministic Signatures

Section 3.5 of the ECDAA specification contains several invocations of randomness (i.e. $RAND(p)$).

As we saw in the history of real world ECC security section of this post, randomly generated k-values have historically led to security disaster (i.e. revealing the secret keys for the ECDSA signatures that helped secure the PlayStation 3). The correct way to use ECDSA is with deterministic signatures.

Further, it is worth noting that the ECDAA specification's definition of $RAND(x)$ does not include any cryptographic security requirements. It is incredibly likely that developers would implement this using a Linear Congruent Generator or Mersenne Twister, rather than the kernel's CSPRNG.

Therefore, it is very likely that continuing to rely on randomness in ECDAA signing will lead to more ECC security disasters.

ECDAA in WebAuthn is Specified over Barreto-Naehrig (BN) Curves

WebAuthn specifies two ECDSA algorithms: ED256 (TPM_ECC_BN_P256 with SHA256) and ED512 (ECC_BN_ISOP512 with SHA512). These are both Barreto-Naehrig curves used for pairing-based cryptography, and suffer from a pretty serious security reduction.

Generally, if you have an elliptic curve with a prime of magnitude $2^{n}$, you have roughly $\frac{n}{2}$ bits of security against the Elliptic Curve Discrete Logarithm Problem (ECDLP). Therefore:

  • 128-bit curves should offer 64 bits of ECDLP security.
  • 256-bit curves should offer 128 bits of ECDLP security.
  • 512-bit curves should offer 256 bits of ECDLP security.

However, due to advancements in cryptanalysis, 256-bit BN curves "no longer offer 128 bits of security, but perhaps closer to 96 or so". This is a speedup factor of 32 bits (roughly 4 billion).

The ill consequences of this curve choice are exacerbated by several ECC security deficits inherent to BN curves.

The FIDO Alliance Rolled Their Own Crypto

To round off the list of takeaways that ECDAA failed to take into consideration, the FIDO Alliance designed their own cryptography standard for anonymous attestations (using pairing-based cryptography over elliptic curves).

That puts us at 0 for 4 on learning from history so we're not doomed to repeat it.

In an interesting twist of fate, according to someone familiar with ECDAA and the FIDO Alliance, they hadn't yet implemented ECDAA themselves (mirrored).

While this is really weird to hear (why would anyone attempt to standardize a cryptography protocol they hadn't implemented, let alone tested, yet?), it does present to us an opportunity to fix the standard before it's burdened by backward compatibility requirements and we end up with an echo of POODLE.

Recommendations

Developers: Please, do NOT implement ECDAA in your WebAuthn libraries.

At least, not yet.

It might sound like a tremendous amount of work to shore up the security of ECDAA but two of the three proposed fixes are very simple.

Fix #1: Require (Or, At Least Allow) Point Compression

This recommendation should be obvious at this point. Read about point compression above, if you haven't already done so.

With point compression, you'll be eliminating an entire class of active attacks and preventing a long tail of implementation error.

Fix #2: Use Deterministic Nonces

There are two (good, but different) approaches to ensuring deterministic signatures:

  1. Implement an HMAC-based approach, similar to RFC 6797 for DSA and ECDSA
  2. Use a hash of the message (with optional domain separation) instead of a random integer.

For example, there are two points in EcdaaSign that random values are being generated.

These could easily be replaced by $H(c1 || msg)$ and $H(c2 || msg)$, where $c1$ is the byte 0xF1 repeated a number of times equal to the block size of the hash function (32 for SHA256, 64 for SHA512), and $c2$ is the byte 0xD0 repeated the same number of times.

(The constants 0xF1 and 0xD0 were chosen as a visual nod to the FIDO Alliance when represented in hexadecimal.)

The motivation to use a domain-separated hash function instead of HKDF or HMAC is that ECDAA is going to be implemented in hardware, and since a hash function is already being used, the overhead for this change is minimal.

Fix #3: Reconsider BN Curves

In light of the BN curve security reduction mentioned previously, an alternative curve for pairing-based cryptography should be considered.

When we shared our initial criticism of ECDAA with the FIDO Alliance, we CC'd Tony Arcieri (mentioned in the history section above) and he suggested looking at BLS12-381 ("JubJub") as an alternative to BN_P256.

Fix #4: Hire Cryptographers to Review Your Designs and Implementations

Cryptography code is hard. Mistakes happen. Misunderstandings are everywhere.

While not everyone who works with cryptography is on board, there is a large community of computer security experts and cryptographers that prioritize solutions over blame, and that wants to see projects like W3C's WebAuthn succeed.

If anyone wants to design a novel cryptography standard, reach out to cryptography experts. The CFRG is probably not the worst place to find one.

If yours is a commercial product, contract or hire at least one cryptographer to review your design and suggest changes, then implement them.

That being said, it cannot be the case that an alliance consisting of large companies and hardware security token vendors that advocates for improved web security fails to learn from the past two decades of real world cryptographic security research. Nobody wins in this scenario, except the attackers.