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

Introduction

前几天看到了一个有关于Cryptography密码学的漏洞CVE-2022-21449 ,是一个ECDSA签名绕过的漏洞,漏洞原理似乎很简单,就稍微看了一下。

比较遗憾的是,网上大多都是一些高度概括性的文章 ,没有深入到代码细节的分析。

好奇心驱使,很想刨根究底弄个明白,就自己去找了点源码看了下,看完后确实加深了一些理解;此外,还顺便横向对比了一下其他密码库的实现,有一点点思考和收获。故此,开篇博客记录下。

ECDSA Signature

ECDSA 是一个常用的签名算法,基于椭圆曲线上的离散对数难题,相较于RSA签名算法 ,可以在安全性保持不变的情况下,拥有更小的密钥空间;但也因为需要一个随机的nonce来保障安全性而备受吐槽(nonce reuse attackbiased-k lattice attack )。而后起之秀EdDSA 签名算法,同样基于椭圆曲线上的离散对数难题,却可以无需nonce(miuse-resistant)+更短的公钥+更快的运算效率。

这个漏洞是有关于ECDSA的,我们首先来看一下ECDSA数字签名算法的具体操作步骤,签名算法包含有2个部分:生成签名和验证签名。(这部分主要参考wiki

Signature Generation

假设现在Alice想要给Bob发送一条带签名的消息,最开始,他俩要先协商好签名所需的一些椭圆曲线参数。

参数包括:

  • CURVE:椭圆曲线方程$y^2 = x^3 + ax + b$,即选系数$a, b$,一般都有几个特定的曲线可以选
  • $G$:椭圆曲线上的基点(这个基点可以生成一个秩为大素数$n$的子群)
  • $n$:基点$G$的秩,即$n \times G = O$,其中$O$是无穷远点(即单位元)
  • $d_A$:Alice的私钥,是一个在[1, n-1]之间随机选取的数
  • $Q_A$:Alice的公钥,通过$Q_A = d_A \times G$计算得出

以及

  • $m$:Alice想要发送的原始消息

协商完参数,就可以开始生成消息$m$所对应的签名了。

步骤如下:

  1. 计算$e = HASH(m)$,其中$HASH$一般都是SHA-2哈希函数
  2. 取$z$为$e$的最左边$L_n$位,其中$L_n$是群阶数$n$的二进制位数(也就是把$e$给截断到跟$n$的位数相同,方便后续$\bmod{n}$的模运算)
  3. 在[1, n-1]的范围内选取一个密码学安全的随机数$k$,即nonce(这也就是ECDSA最遭人诟病的一步了,在具体代码实现的时候也要千分万分地小心)
  4. 将$k$作为一个标量,可以得到一个椭圆曲线上得点$P_k = (x_1, y_1) = k \times G$
  5. 取横坐标为一个签名值$r \equiv x_1 \pmod{n}$,在这一步要校验是否有$r=0$,如果$r$等于0,则退回到第3步(这一道check在实际中几乎不可能发生,但还是要follow)
  6. 再计算另外一个签名值$s \equiv k^{-1}(z+rd_A) \pmod{n}$,同样要校验是否有$s=0$,如果$s$等于0,则退回到第3步
  7. 最终的签名即为组合$sig = (r, s)$

Alice随后就可以将带有签名的消息$m’ = (sig, m)$发送给Bob。

Signature Verification

Bob收到Alice发来的带有签名的消息$m’ = (sig, m)$后,他可以根据验签的结果来判断出这个消息的真实性+合法性+完整性。

此外,Bob还需要收到Alice的公钥信息$Q_A$,并对$Q_A$进行一些基础性的检测,这个不是很重要,就略过了。

我们着重来看验签,步骤如下:

  1. 检查两个签名值$r, s$是否都在[1, n-1]的范围内,如果不在,则说明签名无效(根据签名生成的过程也可以看出来,正常的签名值肯定都在这个范围内。这个漏洞就是因为少了这一层校验而导致的,使得攻击者可以用双零的签名(0,0)来通过签名检测)
  2. 计算$e = HASH(m)$
  3. 取$z$为$e$的最左边$L_n$位(第2、3步都和签名生成步骤一致)
  4. 计算两个中间值$u_1 \equiv zs^{-1} \pmod{n}$和$u_2 \equiv r s^{-1} \pmod{n}$
  5. 根据两个中间值,计算出一个椭圆曲线上的点$P_k’ = (x_1’,y_1’) = u_1 \times G + u_2 \times Q_A$,如果这个点是无穷远点$O$,则说明签名无效
  6. 若$r \equiv x_1’ \pmod{n}$,则签名正确

为什么最后$r \equiv x_1’ \pmod{n}$,就说明签名正确呢?

我们可以来验证一下:

实际上,验签的第4和第5步,就是要把签名生成中第4步里的$P_k$给计算出来。要计算$P_k$,肯定绕不开$k$,而$k$又还在$s \equiv k^{-1}(z+rd_A) \pmod{n}$这个式子里出现过。

我们就可以对这个式子变形一下,把$s$除到等式右边去,再把$k$乘到等式左边去,这样$k$就单独在一边: $$ k \equiv zs^{-1} + rs^{-1} \cdot d_A \pmod{n} $$ 等式右边里,$zs^{-1}$即为中间值$u_1$,$rs^{-1}$即为中间值$u_2$;从而,等式变为了: $$ k \equiv u_1 + u_2 \cdot d_A \pmod{n} $$ 在这个等式里,$u_1, u_2$以及模数$n$均为已知量,未知量仅为$k, d_A$。对于验签的一方,私钥$d_A$肯定是不知道的。

那怎么办呢?我们有关于私钥$d_A$的另外的信息就是公钥$Q_A = d_A \times G$。

我们可以借助点的标量乘法,来把$d_A$带上,即我们可以在等式两边同时乘上基点$G$: $$ k \times G \equiv u_1 \times G + u_2 \cdot d_A \times G \pmod{n} $$

注意这里的点乘和叉乘是两个完全不一样的乘法运算,点乘$\cdot$是标量和标量的乘法,而叉乘则是椭圆曲线上标量和点的乘法。

从而等式右边就变为了: $$ P_k’ \equiv u_1 \times G + u_2 \times Q_A $$ 我们只需要验证这个通过$z, r, s$计算得出的$P_k’$是否为原先的$P_k$即可。如何验证?判断两个点的横坐标是否相等即可,也就是:$r \equiv x_1’ \pmod{n}$


值得注意的一点是,签名(0,0)也是可以满足上述证明的运算的,在这种情况下,$r= s=0$,则$u_1 = u_2 = 0$,从而导致$P_k’ = O$,而无穷远点的横坐标则默认为0,0==r。

所以在验签的过程中,必须要有第1步和第5步最后的校验,防止一些非法的签名值绕过了整个验签逻辑。

What’s going wrong with Java?

我们来看看Java在实现ECDSA的时候到底出现了什么问题?

Vulnerability

根据漏洞的描述,可知Java15-18版本全军覆没了。

我们可以去找一下Java的jdk源码 来看看,到底发生了什么。

找到GitHub上的代码仓库: https://github.com/openjdk/jdk

切换tag至jdk-15+36分支: https://github.com/openjdk/jdk/tree/jdk-15+36

这里以jdk15为例,jdk15、16、17、18都是一样的

然后一头钻进源码里。

不是很好找,但是可以借助一下GitHub的文件搜索功能,搜一下ECDSA

image-20220429024823284

test开头的文件直接不用看,只看src开头的,点开了几个,然后搜verify,在ECDSAOperations.java里找到了内部具体的实现,代码位于:

https://github.com/openjdk/jdk/blob/4a588d89f01a650d90432cc14697a5a2ae2c97d3/src/jdk.crypto.ec/share/classes/sun/security/ec/ECDSAOperations.java#L199-L254

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

可以看到,在从sig里取出r, s之后,并没有任何第1步有关于$r, s$范围的校验,第5步拿到点p1之后也没有校验是否为无穷远点,从而导致可以利用(0,0)签名来通过整个验签的运算。。。

Fix

在漏洞报给Oracle之后,Oracle对其进行了修复,修复后的代码在最新的master分支里,具体位置为: https://github.com/openjdk/jdk/blob/master/src/jdk.crypto.ec/share/classes/sun/security/ec/ECDSAOperations.java#L201-L262

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

可以看到,多了一段if语句的范围校验,从而修补了之前的漏洞。(但是第5步最后那个判断p1是否为无穷远点$O$的校验还是没加上???)

Reproduction

那么这个漏洞有什么危害呢?

首先,利用这个漏洞,可以绕过ECDSA的签名校验。

而现实世界中,有非常多的应用的安全性都依赖于这一道校验,例如TLS协议的证书签名校验、JWT的鉴权等等。

再联想到世界上几百上千万台设备是运行的Java代码,这危害可想而知。。

官方Oracle给这个漏洞CVSS评分为7.5,说实话,确实给少了,漏洞发现者认为实际危害甚至可以达到10.0(核弹)级别。。。

网上有个demo可以来证明这个漏洞的危害到底有多大。

demo :伪装成google


在这个demo中,攻击者将伪装成google,用自己伪造的(0,0)签名证书来绕过用户端的TLS证书签名校验。

server端:

  • 作者魔改了golang的标准库源码,把里面一些签名校验的check给patch掉了
  • 并且自己生成了一个假的google证书(签名为(0,0))
  • 然后在本地127.0.0.1起了一个http+tls=https服务。

client端:

  • 运行java -jar vulnclient.jar会使用存在漏洞的jdk,去向两个指定的网站发起请求,并且把两个请求的响应log出来

  • 第一次运行,两个请求都是访问的外网的服务,响应正常;而且,用curl(无签名漏洞)访问google是正常的,google返回的证书是可以通过curl内置的证书签名校验的

  • 第二次运行之前,作者先把hosts文件改了一下,把google.com域名指向了本地回环地址127.0.0.1,即模拟了一下DNS污染,这样第二次运行的https://www.google.com/hello就会访问本地的443端口的服务。

  • 第二次运行,按理说,由于作者是没有google合法的证书的,所以访问https://www.google.com/hello返回的响应理应会报证书错误(正如使用curl命令得到的结果所示);但是并没有,因为作者伪造的证书签名(0,0)成功通过了jdk的签名校验,,使得本地虚假的google.com服务会被client信任

通过这种demo,说明攻击者可以利用此漏洞,冒充伪造成任何高信誉域名,从而严重危害到用户的网络安全。

How About Others?

这是Java的情况,那我们再来看看其他语言的密码库做的如何呢?能不能举一反三,找到其他类似的漏洞?

golang

Go语言的标准库中实现了各种常用的密码算法和协议,即golang.org/x/crypto

其中,就有ECDSA数字签名算法的实现,代码位于:

https://github.com/golang/go/blob/master/src/crypto/ecdsa/ecdsa.go#L296-L301

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

在正式进入验签verify运算之前,先check了一下两个签名的取值范围,如果不在[1, order-1]里面,就return fasle,表示签名有问题。

pycryptodome

pycryptodome是一个常用的Python密码库,CTFer选手对这个Crypto库应该非常熟悉了。

我们来看看Crypto库里的ECDSA签名算法的验签逻辑,Crypto库的签名算法封装在DssSigScheme类中,具体代码位于: https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Signature/DSS.py#L156-L157

 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

同样的,在调用self._key._verify验签运算之前,首先有一段if语句的check,如果范围不在(0, order)里面,就直接raise一个error。

openssl

openssl的ecdsa的签名函数找起来比较绕。。。

跟了一会儿代码,没找到,换一种思路,用全局搜索。

结合签名时用到的一个高辨识度的变量u1,全局搜索u1关键字,并且限制搜索文件范围为ec*.c,再裁剪掉一些无关的文件*.pem,就能直接找到对应的代码位置。

image-20220429003146407VS Code全局搜索

代码位于: https://github.com/openssl/openssl/blob/master/crypto/ec/ecdsa_ossl.c#L400-L406

 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;
    }
    
    // 验签运算
}

同样的,在验签运算之前,也有一段if的check,两个签名r和s都不能在(0, order)范围之外。

看来其他密码库的实现,都还挺安全的。

Conclusion

一开始看这个洞的时候,只是看了一下漏洞发现者的那篇高度概括的博客,似懂非懂。

后来,仔细深入看具体代码之后,对这个洞的理解就加深了一大截,深入钻研还有很有趣的呀~


那么既然漏洞原理其实挺简单的,为什么到现在才爆出来呢?

原因在于:Java近期把C++实现的ECC密码相关代码重新改写为了Java原生实现,在代码重写的过程中,才引入了这样一个问题。

思路延伸一下,一个可以深入挖掘方向:(既然这个developer安全意识不咋地的情况下)重写的Java代码还有没有可能存在其他的问题?


经验教训就是,一些check也是很关键的,如果漏掉了一个,可能整体的安全性就完全丧失了。。