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.

ECDSA

So what is Elliptic Curve DSA algorithm and how does it work? Wikipedia comes to rescue and provides the definitions.

The Signature Algorithm:

  1. Calculate \( e = HASH(m) \),
  2. Let \( z\) be the \( L_n \) leftmost bits of e,
  3. Pick a random \( k \in [1, n-1]\),
  4. Calculate \( (x_1, y_1 ) = k \times G\),
  5. Calculate \( r = x_1 (mod\ n)\), if \(r = 0 \), pick another \( k\),
  6. Calculate \( s = k^{-1} (z + rd_A)\ (mod\ n) \). If \( s=0\), pick another \( k\),
  7. 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?

  1. Verify that \( r,s \in [1,n-1]\)
  2. Calculate \( e = HASH(m) \),
  3. Let \( z\) be the \( L_n \) leftmost bits of e,
  4. Calculate \( u_1 = zs^{-1} = 0\ (mod\ n)\) and \(u_2 = rs^{-1} =0\ (mod\ n)\)
  5. 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.
  6. 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.