On April 19, 2022, information about a severe vulnerability in recent versions of Java shook up the security community. News got out about a serious implementation flaw of the Elliptic Curve Digital Signature Algorithm (ECDSA), which would allow a malicious user to trivially construct an ECDSA signature such that signature validation is successful although this adversary does not have access to the private signing key. This could for example be easily exploited to forge authorization tokens or TLS handshakes. Or worse, it could declare a legally binding qualified electronic signature as valid even though it is not.
This vulnerability, labelled CVE-2022-21449 and also dubbed “Psychic Signatures” or simply “Bug of 2022”, had been reported to Oracle in November 2021 by ForgeRock security researcher Neil Madden. It affects Java 15 through 18. On the Common Vulnerability Scoring System (CVSS), Oracle had given it a score of 7.5 out of 10 although this may well be understated given its impacts.
First off: the Fix
On April 19, 2022, Oracle resolved the vulnerability in its Java April 2022 Critical Patch Update. Anybody deploying Java 15, 16, 17, or 18 has been urged to immediately update their Java versions to install those fixes.
ECDSA is the elliptic curve analogue of the Digital Signature Algorithm (DSA), and is widely used in a variety of authentication processes, such as SSL/TLS handshakes, JSON Web Tokens, SAML assertions, and OIDC tokens. It is the signature algorithm of choice especially in resource-constrained environments where key size and power consumption matter. Being able to pass the ECDSA signature verification algorithm without knowledge of a user’s private signing key means that an adversary is able to assume that user’s identity and act on their behalf!
How it Works
Exploiting the CVE-2022-21449 vulnerability is trivial!
An ECDSA signature is a pair of integers (r,s), both between 1 and n-1 where n is a large prime (256 bits or more) that is part of the algorithm’s public parameters. Such a signature (r,s) is generated using the signer’s private key and the hash H(m) of the message m that is to be signed. Now, the security of ECDSA is based on the assumption that the so-called Elliptic Curve Discrete Logarithm Problem is computationally intractable, and on the assumption that the hash function H is cryptographically secure (that is, collision resistant and pre-image resistant). Under these assumptions, an ECDSA signature (r,s) on a message m passes the validation algorithm only if the signer’s private key was used in the signing process. This property is exactly what makes a signature algorithm suitable for authentication purposes.
What goes wrong in the faulty Java 15 - 18 implementations of the ECDSA signature verification algorithm is that the property that both r and s are non-zero is not being checked, and the verification algorithm accepts (r,s) = (0,0) as a valid ECDSA signature on any message m.
This way, a signature forgery or authentication bypass is trivial to implement. As a Proof of Concept, security researcher Khaled Nassar published an example involving a vulnerable client that accepts an invalid signature from a malicious TLS server, thereby allowing for a TLS handshake.
How Did This Happen?
As indicated in Neil Madden’s excellent initial article, this implementation flaw got introduced when rewriting the ECDSA code from native C++ code to Java for the Java 15 release. That this bug went undetected suggests that insufficient testing and oversight of the code was applied.
It must be emphasized that there is nothing wrong with ECDSA. All what needs to be done for an ECDSA implementation to meet its security claims, is to implement the parameter generation, signature generation, and signature verification algorithms exactly as described in the standards, such as ANSI X9.62, FIPS 186-2, IEEE 1363-2000, or ISO/IEC 15946-2. Indeed, in each of these standards, the first line of the signature verification algorithm is something like “Verify that r and s are integers in the interval [1, n-1].” It is textbook knowledge that this check must not be omitted, and that things can go very wrong if just one of r or s is allowed to be zero.
CVE-2022-21449 is a fine example that a cryptographic algorithm is experiencing a vulnerability not because of a flaw in the algorithm itself, but because of human error in its implementation.
By the way, Cryptomathic has analyzed the impact of CVE-2022-21449 on their own products using signature validation when using ECDSA. We determined that they were not affected and that no Cryptomathic software updates are required.
Want to know how we can help ?
Get in touch to better understand how our solutions secure ecommerce and billions of transactions worldwide.