Fight For Freedom

02月 08

深入剖析CVE-2016-0701

        在乌云上看了360一同学对openssl的CVE-2016-0701私钥恢复攻击进行了分析,感谢其分享精神。不过我对其文章有些小质疑,并提出了自己的一些看法,欢迎大家讨论。


背景

       我们先来看看各大媒体是怎样叙述这个漏洞的。

     “首先,这个漏洞存在于OpenSSL v1.0.2。依赖它的应用,必须是使用数字签名算法生成基于DH密钥交换的临时key。默认情况下,该类服务器将复用相同的DH私钥,这会让它更易受到密钥覆盖攻击。基于DSA的DH(Diffie Hellman)配置(依赖于静态DH加密套件),也是会受影响的。”

     “当其他附加条件满足后,黑客可以发送大量的握手请求包到存在漏洞的服务器或者PC机。进行了足够的计算后,黑客会获得部分密钥值,最后结合中国剩余定理,能够推导出完整的解密密钥。

     “如果实际中应用了DH设置的基于“不安全”的质数或者“not Lim-Lee”,或者是openssl中默认设置(特别是SSL_OP_SINGLE_DH_USE 没有设置)的静态DH密码套件和DHE套件,那么都会是有问题的,易受到攻击。很多流行的比如apache mod_ssl就可能会用到静态DH密码套件。

       个人感觉比较模糊,不是很具体,脑补不出场景来。乌云上那哥们却提出了其它的看法,“在使用DH算法时对不同客户端使用了相同私钥和不安全的大素数,导致攻击者可以通过降阶的攻击方式(或者是秘钥恢复估计)来获取服务器端的私钥,从而解密tls。”,“私钥恢复攻击,就是对不安全素数的降阶攻击”。

      嗯嗯,稍微有点清晰了。区别是官方给的解答是需要通过多次握手,而360那哥们的理解是只需一次OK,并且攻击算法也不同。下面我将对其原理和场景进行简单剖析。

 


原理探究

       在我原来写的文章中https原理的来龙去脉之二提到过,DH密钥交换算法。如果我们能够通过攻击计算得到相互通信的key,那么就可以将双方通信的内容进行解密。

一. DH密钥交换算法

       迪菲-赫尔曼密钥交换(Diffie–Hellman key exchange,简称“D–H”) 是一种安全协议。

       它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。Diffie-Hellman算法的保障是基于离散对数难题。

        y = gx mod p,即当已知大素数p和其一个原根a,对给定的y,要想计算出x是很困难的。

        假如用户A和用户B希望交换一个密钥。

        取大素数p和其一个原根g,公开。

        A选择随机数Xa<p, 计算出Ya = g^Xa mod p 

        B选择随机数Xb<p, 计算出Yb = g^Xb mod p

        双方都将X保密,将Y公开。

        A密钥计算: k = (Yb)^Xa mod p

        B密钥计算: k = (Ya)^Xb mod p

        k可以很容易地证明是相等的,作为双方通信的密钥。

        那么问题来了,如果已知p,原根g和y,那么怎么求到x。

        按理来说是不可能的,但是如果没有按照标准给的要求来呢?比如p(smooth number)并不是一个“安全素数”,可以被分解成很多小质因子。因此我们可以使用Pohlig-Hellman算法将私钥x求解出来。

二. Pohlig-Hellman算法

      乌云上那文章通篇都在讲pohlig-hellman算法,很可惜,那篇文章没有讲清楚。pohlig-hellman算法是很早以前就针对上述问题而提出来的。下面我就来详细讲解这算法是如何将x解出来的。

       重新叙述一遍条件

       y = g^x mod p

       1. y,p,g已知;

       2. p不是“安全素数”。

       目的:求解x。

       过程

       1. φ(p) = p-1 = p1*p2*p3..pn,其中p1,p2....pn是x-1的质因子,并且值都被认为比较小;

       2. 以p1为例:

       令x = a1*p1 + b1,即是 b1 = x mod p1.....(1)

       y^(φ(p)/p1) = (g^x)(φ(p)/p1) mod p   ......(2)

       将(2)带入(1)中得:

              y^(φ(p)/p1) = g^(φ(p)*a1) * g^(b1*φ(p)/p1)  mod p   ......(3)

       根据欧拉定理有:g^φ(p) mod p =1 ......(4)

       将(4)带入(3)中,得到:

       y^(φ(p)/p1)  = g^(φ(p)/p1*b1) mod p   ......(5)

       好了,这样可能不是很好看,那再令:

       y1=y^(φ(p)/p1) 、g1 = g^(φ(p)/p1)    ......(6)

       注意,y1、g1都是可以求出来的,相当于已知。

       3. 将假设的(6)带进(5)中,有:y1 = g1^b1 mod p

       可能这时有人会问,这不又转换成离散对数难题了吗?

       不是的,我们再回过头看b1是怎么来的,(1)中已经很明显说明了b1<p1的,条件里已经说了p1,p2等都是小质因子,那么我们就可以爆破去解得b1。那么就有x = b1 mod p。

    同理可得b2, b3...
    x = b1 mod p1;
    x = b2 mod p2;
    ......
    x = bn mod pn
    最后由中国剩余定理求解出x就ok了。

      乌云上那篇文章讲得通俗易懂,但有个关键地方没讲到,坑了我一晚上。如图:

       不管正推逆推,都凑不出文中给的划线等式,而这个地方恰恰又是最关键的,后面推导的都是以这个为基础的,不然中国剩余定理是用不出来的。

       其实划线的第一个xb就是上面我讲解的b1,是要用到欧拉定理的,即如上(4)、(5)式子,但文中又恰恰省去了这么关键的地方。

       如果计算出x即私钥,那么就可以将共享密钥算出来,k = (Yb)^Xa mod p = (Ya)^Xb mod p。TLS把这个共享密钥作为PreMaster Secret,但还需将Master Secret计算出来,由于服务端和客户端都有一份相同的PreMaster secret和随机数,这个随机数将作为后面产生Master secret的种子。客户端和服务端将计算出同样的Master secret。然后在wireshark设置好Master Secret就可以解密了。(注:在https原理的来龙去脉之二提到过)


疑惑

一. CVE-2016-0701的攻击方式是这样的吗

1. 这种攻击方式是很早以前上个世纪就研究公布出来的,为什么openssl这私钥恢复漏洞现在才被人发现,不符合常理;

2. 看了漏洞发现者的博客,我也对其中间的步骤感到不解,即calculate yb = g*xa (mod p) * B”和“yb^xa * B^xa (mod p)”

3. 作者在计算x时也用了穷举(for TLS these means try to handshake many sessions),这表明了“多次握手”,但我这个证明计算中却没有,只需一次就能。

       针对离散对数问题的攻击方式有好几种,上述讲的pohlig-hellman算法只是其中一种,原文中给出了此类问题的攻击方式的研究文章,但由于其中专业词汇太多,连蒙带猜也看不下去了,已浅尝辄止。(A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup)

       所以我很怀疑上述讲解的pohlig-hellman攻击方式并不适用于CVE-2016-0701,可能是其它的算法。但不管怎么说,此类攻击方式早已比较成熟,但该漏洞却最近才被人发现,实在让人感到疑惑。

二. “不安全素数”p到底是怎么产生的

       从这个漏洞的根源上来讲是因为p的不合理选取,p不是一个“安全素数”(如果 p1 是素数,p2 = p1*2+1 也是素数,那么 p2就是安全素数,反之则是不安全的)。但在原根g的选取上我们经常是用如下算法:

(1). 利用素性验证算法,生成一个大素数q;

(2). 令p = q * 2 + 1;

(3). 利用素性验证算法,验证p是否为素数,如果p是合数,则跳转到第一步;

(4). 生成一个随机数g,1 < g < p-1;

(5). 验证g2 mod p 和 gq mod p 都不等于1,否则跳转到第四步;

(6). g是大素数p的原根。

        这种常用的原根产生算法从根本上就肯定了p一定是个安全素数,但在这个漏洞产生中却出现了p不是一个安全素数的情况,表明openssl中使用了其它的产生原根的方法,对p并没做限制。可依然感觉很不可思议。


其它

       查了好多资料,看到国内国外对CVE-2016-0701分析好少,花了快两天时间耗在这上面,赶紧把文章发了吧,不然不知自己又会拖到多久。唉,其实还有挺多疑惑的,忘了。还想做做实验的,但涉及到的东西又太多,无从下手。以后再补坑吧。

       最近慢慢变忙,没多少时间来玩这些了,自己也变得越来越懒,寒假都已经过去一半多了。-||-。

       祝大家新年快乐~

 

参考文献:
A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup pdf

标签:none

已有 2 人抢先你了

  1. ld ld

    1. 搜索CVE-2016-0701 进入 https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-0701。
    2. 在页面中有个git链接:https://git.openssl.org/?p=openssl.git;a=commit;h=878e2c5b13010329c203f309ed0c8f2113f85648。
    3. 页面里面说:
    Historically OpenSSL only ever generated DH parameters based on "safe"
    primes. More recently (in version 1.0.2) support was provided for
    generating X9.42 style parameter files such as those required for RFC
    5114 support. The primes used in such files may not be "safe". Where an
    application is using DH configured with parameters based on primes that
    are not "safe" then an attacker could use this fact to find a peer's
    private DH exponent. This attack requires that the attacker complete
    multiple handshakes in which the peer uses the same DH exponent.

    A simple mitigation is to ensure that y^q (mod p) == 1

    也就是在1.0.2 之前使用的安全素数,之后遵循RFC 5114标准,开始没有安全素数检查。
    RFC 5114 成功背锅。
    我想,这样,应该可以解决你的疑惑了。

    1. 十分感谢解惑,特别是解决问题的方法。

添加新评论

captcha
请输入验证码

最新文章

最近回复

  • lynahex:十分感谢解惑,特别是解决问题的方法。
  • ld:1. 搜索CVE-2016-0701 进入 https://cv...
  • lynahex:好的。
  • xdxd:友链已加~~~希望有机会多多交流~~
  • lynahex:恩,重测了下是可以的。可能当时一些危险函数被我禁掉了。 thx
  • 过客:虽然博主文章过了好久了,本地system测试还是可以执行的
  • 友情链接

    分类

    其它