OpenSSL CVE-2016-0701私钥恢复攻击漏洞分析 | WooYun知识库
source link:
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
OpenSSL CVE-2016-0701私钥恢复攻击漏洞分析
Author:[email protected]
0x00 前言
2016年1月28日，OpenSSL官方发布了编号为 CVE-2016-0701 的漏洞。该漏洞发生在OpenSSL 1.0.2 版本中(OpenSSL 1.0.2f和以后版本不受影响)，在使用DH算法时对不同客户端使用了相同私钥和不安全的大素数，导致攻击者可以通过降阶的攻击方式(或者是秘钥恢复估计)来获取服务器端的私钥，从而解密tls。
360云安全团队的au2o3t对官网和发现者Antonio Sanso提供的实现存在疑惑，并提供了一份我们认为是正确的漏洞分析(欢迎反馈)。
hf
0x01 分析
^领导说了必须得有图^
看了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,
由中国剩余定理：
#!bash
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 参考
Recommend
-
10
Android平台下二维码漏洞攻击杂谈 路人甲
-
13
Redis漏洞攻击植入木马逆向分析 阿里云安全
-
8
OpenSSH CVE-2016-0777私钥窃取技术分析 360安全卫士...
-
19
关于OpenSSL“心脏出血”漏洞的分析 Fish ·...
-
6
CVE-2014-6352漏洞及定向攻击样本分析 360安全卫士
-
10
Openssl多个安全补丁简易分析危害及修复方案 livers
-
12
Hacking Team攻击代码分析Part 4: Flash 0day漏洞 CVE-2015-5122 3...
-
7
OpenSSL-CVE-2015-1793漏洞分析 360安全卫士
-
15
如何发现 NTP 放大攻击漏洞 心伤的胖子
-
3
1. 漏洞描述 漏洞编号： CVE-2014-0160 发现人员： 安全公司Codenomicon和谷歌安全工程师 漏洞简述：...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK