# OpenSSL CVE-2016-0701私钥恢复攻击漏洞分析

**Author:au2o3t @360 Cloud Security Team**

0x00 前言
=======

* * *

2016年1月28日，OpenSSL官方发布了编号为 CVE-2016-0701 的漏洞。该漏洞发生在OpenSSL 1.0.2 版本中(OpenSSL 1.0.2f和以后版本不受影响)，在使用DH算法时对不同客户端使用了相同私钥和不安全的大素数，导致攻击者可以通过降阶的攻击方式(或者是秘钥恢复估计)来获取服务器端的私钥，从而解密tls。

360云安全团队的au2o3t对官网和发现者Antonio Sanso提供的实现存在疑惑，并提供了一份我们认为是正确的漏洞分析(欢迎反馈)。

hf

0x01 分析
=======

* * *

![p1](http://drops.javaweb.org/uploads/images/ae0e8fc3d80e7f2d101f851b15df2b0ce8020ed0.jpg)^领导说了必须得有图^

看了CVE-2016-0701 发现者Antonio Sanso的博文(参考1)， 对其中的攻击步骤“`calculate yb = g*xa (mod p) * B`”和“`yb^xa * B^xa (mod p)`”的由来百思而始终不得其解，并且一直对文档中以及openssl官方中所描述需要“多次握手”颇有疑惑（参考2）。

经过一番研究，总算实现了攻击并找到了理论证明。

事实上，攻击者并不需要多次握手。只要握手一次，获得服务器公钥即可。

而Antonio Sanso文中出现的“`calculate yb = g*xa (mod p) * B`”和“`yb^xa * B^xa (mod p)`”依旧不知所云，似是毫无用处。   所谓私钥恢复攻击，实质上是对不安全素数的降阶攻击。

安全素数也叫苏菲·姬曼（Sophie Germain）素数，如果 p1 是素数，p2 = p1*2+1 也是素数，那么 p2 就是安全素数，反之则是不安全的。   DH密钥交换算法的安全性基于有限域上离散对数的难解性，而其保障正是强素数模。   服务器随机产生私钥 xb，计算公钥 yb = g^xb mod p （DH中，素数 p 和 g 是公开的）。

若其中 p 不够强（不是安全素数），则 p-1 可被分解为若干素因子，这正是攻击者可利用之处。

攻击者已知 g，p，yb 的情况：

若p-1可被因式分解为若干小因子，则可进行降阶攻击。   原式（yb = g^xb mod p）中，由于 orb(g) 值很大，难以暴力破解。

但 p-1 可分解的情况，可对其降阶：

令 g’ = g^((p-1)/q) mod p，其中 q 是 p-1 的一个素因子，则 g’ 的阶降低为 q，

那么 g’^xb mod p = g’^(xb mod q) mod p = yb^((p-1)/q)。   至多 q 次，可以暴力得到 x’ = xb mod q 值（其实至多 q^(1/2)次可得）,   按此法，若能得到 p-1 的若干素因子 q1，q2，q3。。。

则同理可得，g1，g2，g3。。。及 y1，y2，y3。。。

即可以较低复杂度计算出 x1 = xb mod q1，x2 = xb mod q2，x3 = xb mod q3。。。   于是由中国剩余定理可得：

`xb = （ x1*q1’*q2*q3*...+ x2*q1*q2’*q3*...+ x3*q1*q2*q3’...+ ... ） mod q1*q2*q3*....`

（`q1’*q2*q3*...= 1 mod q1，q1*q2’*q3*... = 1 mod q2 ...` 见“中国剩余定理”）

实现攻击的时间复杂度取决于 p-1 分解出的最大素因子长度。

**验证：**

为方便快速验证原理，不妨取一较小 p 值，如 p = 192271，g = 2。

易知，p-1 可分解为 `2 * 3 * 5 * 13 * 17 * 29`。   假设服务器取随机私钥 xb = 34567，那么其公钥 yb = 2^34566 mod 192271 = 44402。  

则攻击方已知量为 p = 192271，g = 2， yb = 44402，由此3量我们来尝试计算其私钥 xb：   由于 p-1 可分解为 `2 * 3 * 5 * 13 * 17 * 29`，

设 q1 = 2，q2 = 3，q3 = 5，q4 = 13，q5 = 17，q6 = 29。   依上面公式 g’ = g^((p-1)/q) mod p，可计算：

```
g1 = g^((p-1)/q1) mod p = 2^(192270/2) mod 192271 = 1，同理：
g2 = 2^(192270/3) mod 192271 = 136863，
g3 = 2^38454 mod 192271 = 118548，
g4 = 2^14790 mod 192271 = 95011，
g5 = 2^11310 mod 192271 = 141591，
g6 = 2^6630 mod 192271 = 148926，

```

    同样计算 y’ = yb^((p-1)/q) 可得：

```
y1 = 1，
y2 = 136863，
y3 = 156372，
y4 = 1，
y5 = 188120，
y6 = 190612，

```

    根据 g’^(xb mod q) mod p = yb^((p-1)/q) 即：

```
g1^(xb mod q1) mod p = y1，
g2^(xb mod q2) mod p = y2，
g3^(xb mod q3) mod p = y3，
……

```

  即可算出：

```
x1 = xb mod 2 = 1,
x2 = xb mod 3 = 1,
x3 = xb mod 5 = 2,
x4 = xb mod 13 = 0,
x5 = xb mod 17 = 6,
x6 = xb mod 29 = 28,

```

    由中国剩余定理：

```
xb = x1*q1’*q2*q3*q4*q5*q6 + x2*q1*q2’*q3*q4*q5*q6 + x3*q1*q2*q3’*q4*q5*q6 + x4*q1*q2*q3*q4’*q5*q6 + x5*q1*q2*q3*q4*q5’*q6 + x6*q1*q2*q3*q4*q5*q6′ mod (q1*q2*q3*q4*q5*q6）

```

  易算得：

```
q1’=1，
q2’=1，
q3’=4，
q4’=3，
q5’=7，
q6’=21，

```

  则 xb = 1*96135 + 1*64090 + 2*4*38454 + 0 + 6*7*11310 + 28*21*6630 mod 192270  
= 4841317 mod 192270  
= 34567

即实现了已知 p，g，yb，求 xb。

0x02 写在最后
=========

* * *

如前言所述，我们在坚信自己认为是正确的路上前进着。

gl

0x03 参考
=======

* * *

1.  [http://intothesymmetry.blogspot.com/2016/01/openssl-key-recovery-attack-on-dh-small.html](http://intothesymmetry.blogspot.com/2016/01/openssl-key-recovery-attack-on-dh-small.html)
2.  [https://openssl.org/news/secadv/20160128.txt](https://openssl.org/news/secadv/20160128.txt)