CVE-2022-21449: Psychic Signatures in Java
The long-running BBC sci-fi show Doctor Who has a recurring plot device where the Doctor manages to get out of trouble by showing an identity card which is actually completely blank. Of course, this being Doctor Who, the card is really made out of a special “psychic paper“, which causes the person looking at it to see whatever the Doctor wants them to see: a security pass, a warrant, or whatever.
It turns out that some recent releases of Java were vulnerable to a similar kind of trick, in the implementation of widely-used ECDSA signatures. If you are running one of the vulnerable versions then an attacker can easily forge some types of SSL certificates and handshakes (allowing interception and modification of communications), signed JWTs, SAML assertions or OIDC id tokens, and even WebAuthn authentication messages. All using the digital equivalent of a blank piece of paper.
It’s hard to overstate the severity of this bug. If you are using ECDSA signatures for any of these security mechanisms, then an attacker can trivially and completely bypass them if your server is running any Java 15, 16, 17, or 18 version before the April 2022 Critical Patch Update (CPU). For context, almost all WebAuthn/FIDO devices in the real world (including Yubikeys*) use ECDSA signatures and many OIDC providers use ECDSA-signed JWTs.
If you have deployed Java 15, Java 16, Java 17, or Java 18 in production then you should stop what you are doing and immediately update to install the fixes in the April 2022 Critical Patch Update.
Update: the official announcement from Oracle also lists older versions of Java, including 7, 8 and 11. Although I’m not aware of the bug impacting those older implementations they did fix a similar bug in the (non-EC) DSA implementation at the same time, so it’s possible older versions are also impacted. There are also other security vulnerabilities reported in the same CPU, so (as always) it is worth upgrading even if you are running an older Java version. The OpenJDK advisory on the other hand lists only versions 15, 17, and 18 as affected by this specific issue (CVE-2022-21449).
Oracle have given this a CVSS score of 7.5, assigning no impact to Confidentiality or Availability. Internally, we at ForgeRock graded this a perfect 10.0 due to the wide range of impacts on different functionality in an access management context. ForgeRock customers can read our advisory about this issue for further guidance.
Background: ECDSA signatures
ECDSA stands for the Elliptic Curve Digital Signature Algorithm, and it is a widely used standard for signing all kinds of digital documents. Compared to the older RSA standard, elliptic curve keys and signatures tend to be much smaller for equivalent security, resulting in them being widely used in cases where size is at a premium. For example, the WebAuthn standard for two-factor authentication allows device manufacturers to choose from a wide range of signature algorithms, but in practice almost all of the devices manufactured to date support ECDSA signatures only (a notable exception being Windows Hello, which uses RSA signatures; presumably for compatibility with older TPM hardware).
Without getting too much into the technical details, an ECDSA signature consists of two values, called r and s. To verify an ECDSA signature, the verifier checks an equation involving r, s, the signer’s public key, and a hash of the message. If the two sides of the equation are equal then the signature is valid, otherwise it is rejected.
One side of the equation is r and the other side is multiplied by r and a value derived from s. So it would obviously be a really bad thing if r and s were both 0, because then you’d be checking that 0 = 0 ⨉ [a bunch of stuff], which will be true regardless of the value of [a bunch of stuff]! And that bunch of stuff is the important bits like the message and the public key. This is why the very first check in the ECDSA verification algorithm is to ensure that r and s are both >= 1.
Guess which check Java forgot?
That’s right. Java’s implementation of ECDSA signature verification didn’t check if r or s were zero, so you could produce a signature value in which they are both 0 (appropriately encoded) and Java would accept it as a valid signature for any message and for any public key. The digital equivalent of a blank ID card.
Here’s an interactive jshell session showing the vulnerable implementation accepting a completely blank signature as valid for an arbitrary message and public key:
| Welcome to JShell -- Version 17.0.1
| For an introduction type: /help intro
jshell> import java.security.*
jshell> var keys = KeyPairGenerator.getInstance("EC").generateKeyPair()
keys ==> java.security.KeyPair@626b2d4a
jshell> var blankSignature = new byte[64]
blankSignature ==> byte[64] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... , 0, 0, 0, 0, 0, 0, 0, 0 }
jshell> var sig = Signature.getInstance("SHA256WithECDSAInP1363Format")
sig ==> Signature object: SHA256WithECDSAInP1363Format<not initialized>
jshell> sig.initVerify(keys.getPublic())
jshell> sig.update("Hello, World".getBytes())
jshell> sig.verify(blankSignature)
$8 ==> true
// Oops, that shouldn't have verified...Note that the “InP1363Format” qualifier just makes it easier to demonstrate the bug. Signatures in ASN.1 DER format can be exploited in the same way, you just have to do a bit more fiddling with the encoding first, but note that JWTs and other formats do use the raw IEEE P1363 format.
A few technical details
If you go and look at the fine details of ECDSA on wikipedia, you’ll see that the right hand side of the equation is not multiplied by s but rather by its multiplicative inverse: s-1. If you know a little maths, you may be thinking “won’t calculating this inverse result in a division by zero?” But in elliptic curve cryptography, this inverse is being calculated modulo a large number, n, and for the curves typically used in ECDSA, n is a prime number so we can use the Little Theorem of Fermat (vandalizer of margins) to calculate the modular inverse:
xn = x1 = x (mod n)
x(n-1) = x0 = 1 (mod n)
x(n-2) = x-1 (mod n)
This is very efficient, and it’s exactly what Java does. However, it is only valid for when x is not zero, as zero doesn’t have a multiplicative inverse. When x is zero then 0(n-2) = 0: garbage in, garbage out.
The fact that arithmetic is carried out modulo n is also why you need to check that r and s are both < n too, because n = 0 (mod n) so setting r or s to n would have the same effect as setting them to 0.
Another check that should’ve saved Java is the check described in step 5 of the verification algorithm on Wikipedia: checking that a point calculated from r and s is not the “point at infinity”. If r and s are both zero, then the resulting point will in fact be the point at infinity and so this check will fail. But again, Java failed to perform this check.
Why did you just find this now?
You may be wondering why this is just coming to light now, when Java has had ECDSA support for a long time. Has it always been vulnerable?
No. This is a relatively recent bug introduced by a rewrite of the EC code from native C++ code to Java, which happened in the Java 15 release. Although I’m sure that this rewrite has benefits in terms of memory safety and maintainability, it appears that experienced cryptographic engineers have not been involved in the implementation. The original C++ implementation is not vulnerable to these bugs, but the rewrite was. Neither implementation appears to have very good test coverage, and even the most cursory reading of the ECDSA spec would surely suggest testing that invalid r and s values are rejected. I am not at all confident that other bugs aren’t lurking in this code.
What should we do about it?
First of all, if you are using Java 15 or later then please go and update to the latest version to get the fix for this issue.
In general, cryptographic code is very tricky to implement correctly and public key signature algorithms are some of the trickiest. ECDSA is itself one of the most fragile algorithms, where even a tiny amount of bias in one random value can allow complete recovery of your private key. On the other hand, we now have excellent resources like Project Wycheproof that provide test cases for known vulnerabilities. After I found this bug I updated a local copy of Wycheproof to run against Java 17 – it found this issue immediately. Hopefully the JDK team will adopt the Wycheproof test suite themselves to avoid any similar bugs slipping through the net in future.
If you are designing a protocol or application that you think needs to use digital signatures, consider if you really do – would a simpler mechanism work instead? Simple MAC algorithms like HMAC are incredibly hard to mess up compared to signature schemes. If you really need a signature then consider using a modern algorithm like EdDSA that avoids some of the pitfalls of ECDSA.
Timeline
11 Nov 2021 – Issue found and disclosed to OpenJDK vulnerability report email address.
11 Nov 2021 – Determined JDK change that introduced the bug in Java 15.
12 Nov 2021 – Initial acknowledgement from Oracle.
18 Nov 2021 – Oracle confirms the bug and indicates it will be patched in a future Critical Patch Update (CPU). It is assigned tracking ID S1559193.
18 Nov 2021 – ForgeRock issues a security advisory informing our customers not to deploy affected versions of Java into production.
14 Jan 2022 – Ask Oracle for status update. Told that the fix is targeting the April 2022 CPU, scheduled for 19th April.
25 Mar 2022 – Confirm again with Oracle that the fix will be in April CPU. Inform them that ForgeRock will proceed to full disclosure if the bug is not fixed by then.
19 Apr 2022 – Fix released by Oracle in April CPU.
19 Apr 2022 – Article published.
* Yubico is one of the few WebAuthn manufacturers that support the more secure EdDSA standard in addition to ECDSA. EdDSA signatures are less prone to the type of bug described here.