Analysis of CVE-2022-21449: Bypass Java’s ECDSA Signature Check by (0,0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

public class ECDSAOperations {
	// ...

	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);
    }

    // ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

public class ECDSAOperations {
    // ...

	public boolean verifySignedDigest(byte[] digest, byte[] sig, ECPoint pp) {

        IntegerFieldModuloP field = ecOps.getField();
        IntegerFieldModuloP orderField = ecOps.getOrderField();
        BigInteger mod = orderField.getSize();
        int length = (mod.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);
        }

        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);
        // 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();
        b2a(result, orderField, temp1);
        return MessageDigest.isEqual(temp1, r);
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Verify verifies the signature in r, s of hash using the public key, pub. Its
// return value records whether the signature is valid. Most applications should
// use VerifyASN1 instead of dealing directly with r, s.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
	c := pub.Curve
	N := c.Params().N

	if r.Sign() <= 0 || s.Sign() <= 0 {
		return false
	}
	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
		return false
	}
	return verify(pub, c, hash, r, s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class DssSigScheme(object):
    # ...
	def verify(self, msg_hash, signature):
        """Check if a certain (EC)DSA signature is authentic.
        Args:
          msg_hash (hash object):
            The hash that was carried out over the message.
            This is an object belonging to the :mod:`Crypto.Hash` module.
            Under mode ``'fips-186-3'``, the hash must be a FIPS
            approved secure hash (SHA-2 or SHA-3).
          signature (``bytes``):
            The signature that needs to be validated.
        :raise ValueError: if the signature is not authentic
        """

        if not self._valid_hash(msg_hash):
            raise ValueError("Hash is not sufficiently strong")

        if self._encoding == 'binary':
            if len(signature) != (2 * self._order_bytes):
                raise ValueError("The signature is not authentic (length)")
            r_prime, s_prime = [Integer.from_bytes(x)
                                for x in (signature[:self._order_bytes],
                                          signature[self._order_bytes:])]
        else:
            try:
                der_seq = DerSequence().decode(signature, strict=True)
            except (ValueError, IndexError):
                raise ValueError("The signature is not authentic (DER)")
            if len(der_seq) != 2 or not der_seq.hasOnlyInts():
                raise ValueError("The signature is not authentic (DER content)")
            r_prime, s_prime = Integer(der_seq[0]), Integer(der_seq[1])

        if not (0 < r_prime < self._order) or not (0 < s_prime < self._order):
            raise ValueError("The signature is not authentic (d)")

        z = Integer.from_bytes(msg_hash.digest()[:self._order_bytes])
        result = self._key._verify(z, (r_prime, s_prime))
        if not result:
            raise ValueError("The signature is not authentic")
        # Make PyCrypto code to fail
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int ossl_ecdsa_simple_verify_sig(const unsigned char *dgst, int dgst_len,
                                 const ECDSA_SIG *sig, EC_KEY *eckey)
{
	// 初始化变量

    if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
        BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
        BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
        ERR_raise(ERR_LIB_EC, EC_R_BAD_SIGNATURE);
        ret = 0;                /* signature is invalid */
        goto err;
    }

    // 验签运算
}