Psychic Signatures in Java OpenJDK
If you have any OpenJDK version from 15 to 18 in production, read on.
Psychic Signatures in Java OpenJDK
Introduction
This was a surprise I must admit. Did not name it either. Never thought I’ll see such a flaw in a signature algorithm. If you have any OpenJDK version from 15 to 18 in production, read on.
ECDSDA
So what is Elliptic Curve DSA algorithm and how does it work? Wikipedia comes to rescue and provides the definitions.
- \(G\): base point on the curve (Please, let the point be on the curve :) )
- \(n\): order of G s.t. \( nG = O \) and no \( m \lt n \) s.t. \( mG = O \), \( n,m \in \mathbb{Z} \)
- \( d_A \), \( Q_A \): private, public key of A
- \( m \): message to send
The Signature Algorithm:
- Calculate \( e = HASH(m) \),
- Let \( z\) be the \( L_n \) leftmost bits of e,
- Pick a random \( k \in [1, n-1]\),
- Calculate \( (x_1, y_1 ) = k \times G\),
- Calculate \( r = x_1 (mod\ n)\), if \(r = 0 \), pick another \( k\),
- Calculate \( s = k^{-1} (z + rd_A)\ (mod\ n) \). If \( s=0\), pick another \( k\),
- The signature is \( (r,s) \).
So the above works for any elliptic curve but efficiency depends on the nature of the curve and security depends on the number of rationals points.
The signature (0,0)
You might have noticed there are two seperate checks on this algorithm for a particular value of \(k\). First one verifies that r is non-zero, the other one verifies s is non-zero. What happens if we remove those checks? Let’s verify the signature \( (0,0) \) without those checks, shall we?
Verify that\( r,s \in [1,n-1]\)- Calculate \( e = HASH(m) \),
- Let \( z\) be the \( L_n \) leftmost bits of e,
- Calculate \( u_1 = zs^{-1} = 0\ (mod\ n)\) and \(u_2 = rs^{-1} =0\ (mod\ n)\)
- Calculate \( (x_1, y_1) = u_1 \times G + u_2 \times Q_A = O \). If \( (x_1, y_1) = O \)
then the signature is invalid. - The signature is valid if \( r \equiv x_1\ (mod\ n) \)
It boils down to that (0,0) is valid for any private, public keypair so it is possible to bypass signature checks. But \( \frac{1}{0} = 0^{-1} \) is undefined right?
Multiplicative Inverses in Finite Fields
Say that you have a prime \( p \in \mathbb{Z} \) and a finite field \( \mathbb{F}_q \) where \(q=p^n\) for a positive integer n. Then for every non-zero element \( \alpha \in \mathbb{F}_q^* \), the following holds:
\[ \alpha^{q-1} = 1\]Moreover, the inverses can be seen in the following equation:
\[ \alpha^{q-2} \alpha = 1\]Therefore, the inverse of \( \alpha \) is basically \( \alpha^{q-2} \). Obviously, this is true for any non-zero \( \alpha \). But what about if we omit the check \( \alpha = 0 \)?
\[ \alpha^{q-2} = 0^{q-2} = 0 \]Huh? The multiplicative inverse of zero is zero? This should not be true right since
\[ 0^{q-2}\ 0 = 0 \neq 1 \]The Algebraist
Still not convinced? Let’s see it in action one more time, shall we?
\[ = O \] \[ = 0 \times O + 0 \times O \] \[ = z0 \times O + rd_A 0 \times O\] \[ = z0 \times G + rd_A 0 \times G\] \[ = z0 \times G + r0 \times Q_A\] \[ = zs^{-1} \times G + rs^{-1} \times Q_A \] \[ = \frac{zk}{z+rd_A} \times G + \frac{rk}{z+rd_A} \times Q_A \] \[ = \frac{zk}{z+rd_A} \times G + \frac{rk}{z+rd_A} \times d_A G \] \[ = \frac{zk +rkd_A}{z+rd_A} \times G \] \[ = k \frac{z +rd_A}{z+rd_A} \times G \] \[ = k \times G \]So, unless \( n \mid k \) this equation is incorrect. Since we pick \( k \in [1,n-1] \) it leads to a contradiction. Oh hai! If we omit that check, we can have a similar bug by just selecting \( k = mn \) for some \(m \in \mathbb{Z} \). Great.
The OpenJDK Case
Enough of theory? Show me the code!
The codebase of OpenJDK is kept at java.net. I’ve found a copy on GitHub. The committer of this patch is wangweij, dated back Feb 2020. Let’s look into the details. In ECDSAOperations.java
public boolean verifySignedDigest(byte[] digest, byte[] sig, ECPoint pp) {
IntegerFieldModuloP field = ecOps.getField();
IntegerFieldModuloP orderField = ecOps.getOrderField();
int length = (orderField.getSize().bitLength() + 7) / 8;
byte[] r;
byte[] s;
int encodeLength = sig.length / 2;
if (sig.length %2 != 0 || encodeLength > length) {
return false;
} else if (encodeLength == length) {
r = Arrays.copyOf(sig, length);
s = Arrays.copyOfRange(sig, length, length * 2);
} else {
r = new byte[length];
s = new byte[length];
System.arraycopy(sig, 0, r, length - encodeLength, encodeLength);
System.arraycopy(sig, encodeLength, s, length - encodeLength, encodeLength);
}
ArrayUtil.reverse(r);
ArrayUtil.reverse(s);
IntegerModuloP ri = orderField.getElement(r);
IntegerModuloP si = orderField.getElement(s);
// z
int lengthE = Math.min(length, digest.length);
byte[] E = new byte[lengthE];
System.arraycopy(digest, 0, E, 0, lengthE);
ArrayUtil.reverse(E);
IntegerModuloP e = orderField.getElement(E);
IntegerModuloP sInv = si.multiplicativeInverse();
ImmutableIntegerModuloP u1 = e.multiply(sInv);
ImmutableIntegerModuloP u2 = ri.multiply(sInv);
AffinePoint pub = new AffinePoint(field.getElement(pp.getAffineX()),
field.getElement(pp.getAffineY()));
byte[] temp1 = new byte[length];
b2a(u1, orderField, temp1);
byte[] temp2 = new byte[length];
b2a(u2, orderField, temp2);
MutablePoint p1 = ecOps.multiply(basePoint, temp1);
MutablePoint p2 = ecOps.multiply(pub, temp2);
ecOps.setSum(p1, p2.asAffine());
IntegerModuloP result = p1.asAffine().getX();
result = result.additiveInverse().add(ri);
b2a(result, orderField, temp1);
return ECOperations.allZero(temp1);
}
In this method, the following is executed to get field elements:
ArrayUtil.reverse(r);
ArrayUtil.reverse(s);
IntegerModuloP ri = orderField.getElement(r);
IntegerModuloP si = orderField.getElement(s);
It can be observed, there are no checks on either r or s. The situation is remedied in a following patch.
BigInteger rb = new BigInteger(1, r);
BigInteger sb = new BigInteger(1, s);
if (rb.signum() == 0 || sb.signum() == 0
|| rb.compareTo(mod) >= 0 || sb.compareTo(mod) >= 0) {
return false;
}
ArrayUtil.reverse(r);
ArrayUtil.reverse(s);
IntegerModuloP ri = orderField.getElement(r);
IntegerModuloP si = orderField.getElement(s);
Checks for the interval \( [1,n−1] \) are added to fix the issue. So
far so good yet I really want to see a fix to
si.multiplicativeInverse()
. I’ve found the relevant code in
IntegerModuleP.java:
/**
* Compute the multiplicative inverse of this field element.
*
* @return the multiplicative inverse (1 / this)
*/
default ImmutableIntegerModuloP multiplicativeInverse() {
return pow(getField().getSize().subtract(BigInteger.valueOf(2)));
}
Unfortunately, OpenJDK still thinks the multiplicative inverse of zero
is zero. All I can say is, I am not going to get frustrated next time
there is a bug in OpenJDK that depends on calculating the inverse of
zero. One nice thing is the pow()
implementation:
/**
* Calculate the power this^b and return the result.
*
* @param b the exponent
* @return the value of this^b
*/
default ImmutableIntegerModuloP pow(BigInteger b) {
//Default implementation is square and multiply
MutableIntegerModuloP y = getField().get1().mutable();
MutableIntegerModuloP x = mutable();
int bitLength = b.bitLength();
for (int bit = 0; bit < bitLength; bit++) {
if (b.testBit(bit)) {
// odd
y.setProduct(x);
}
x.setSquare();
}
return y.fixed();
}
This implementation follows the Repeated Squaring Algorithm and is a polynomial time algorithm where the number of squarings is less than \( \lceil log_2(p) \rceil \). What about side-channels?
Conclusion
Checks in the cryptographic algorithms are crucial as in this. If an implementation omits some of the checks, then it might be vulnerable to certain attacks with or without raising any exceptions in the code. This bug existed since since Java 15.It shows that it is better to read and verify the soundness of the implementation before employing it in any project. You might say nobody does it nevertheless here we are.