lin_ux_linux的ChinaUnix博客

“有效的程序员不应该浪费很多时间用于程序调试,他们应该一开始就不要把故障引入。”

  • 博客访问: 95905
  • 博文数量: 74
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 276
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-28 23:52
文章分类

全部博文(74)

文章存档

2017年(20)

2014年(54)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题

分类: 网络与安全

0x01 前言

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

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

hf

0x02 分析

^领导说了必须得有图^

看了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)中,由于 ord(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。

0x03 写在最后

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

gl


0x04 参考

1. http://intothesymmetry.blogspot.com/2016/01/openssl-key-recovery-attack-on-dh-small.html

2 .https://openssl.org/news/secadv/20160128.txt

阅读(173) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册