Psychic Signatures in Java

This is the huge item ever!

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.

“Looks legit to me. Hic!“

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
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
Read More
Share this on knowasiak.com to discuss with people on this topicSign up on Knowasiak.com now if you’re not registered yet.