Fight For Freedom

01月 15

攻破随机数产生器(一)

       随机数生成器(Random number generator)是通过一些算法、物理讯号、环境噪音等来产生看起来似乎没有关联性的数列的方法或装置。丢硬币、丢骰子洗牌就是生活上常见的随机数产生方式。大部分计算机上的伪随机数,并不是真正的随机数,只是重复的周期比较大的数列,是按一定的算法和种子值生成的。  ----维基百科

       由此我们可以看出随机数生成器分为两类,一类是非确定性随机数产生器,这是基于完全不可预测的物理过程,比如在random.org上提供了“真”随机值,据说是根据“atmospheric noise”来产生的;另一类是确定性随机数产生器,利用算法来生成,如果种子保密且算法优质的话,我们可以认为它的输出是随机的序列。这些输出的随机序列将会用于密码学的应用中。

       但是,如果选取的种子范围不够大,那么就很容易被爆破,而这些随机数常用于关键的枢纽上,后果不言而喻,这往往是程序员自身的问题。可当随机算法产生漏洞时,带来的效果更是毁灭性的,任何依此搭建的体系将会轰然倒塌,安全将不复存在。这次我将详解Dual_EC_DRBG所带来的问题。

 


背景

       Dual_EC_DRBG,全称为Dual Elliptic Curve Deterministic Random Bit Generation,是基于椭圆曲线的确定性随机数生成器。2007,两名微软的研究人员Dan Shumow和Niels Ferguson就发现,Dual_EC_DRBG算法可以被植入后门。他们提到,如果算法中使用的常数经过特殊选择,并且用来选择这些常数所使用的数据被算法设计者保存下来,那么该算法设计者在知道该算法生成随机序列的前32个字节的情况下,可以预知未来所有生成的“随机”序列。

       目前最新的进展是,斯诺登披露的文件证明了,美国国家安全局(NSA)通过贿赂RSA公司,使其在BSafe安全软件中采用Dual_EC_DRBG算法。而Dual_EC_DRBG则是NSA精心设计的留有后门的算法(当然NSA可能没有告诉RSA公司这一点)。

 


基础知识

      椭圆曲线密码学(Elliptic curve cryptography,ECC)是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是:
   
      G对应为椭圆曲线E的基点,d为私钥由自己选择,然后生成对应公钥Q=dG,私钥自己保存,(p, a, b, G, Q)是已知的。由于它的安全性基于有限域椭圆曲线离散对数问题的难解性:由d和G计算Q容易,而由Q和G计算d则是指数级的难度,几乎不可能。补充:椭圆曲线里自定义了一套加法的规则。
   
     椭圆是一系列点的群结合,参数都是事先定义好的。还是给英文解释比较容易理解:
     - Prime modulus p: a prime number used to define the finite field Z/pZ in which the equation elements are defined.
     - The order r: this is the order of the EC and the total number of points into the group.
     - a and b: fixed integers used in curve’s equation. a is set to -3 in NIST GF(p) curves.
     - A Generator point defined by Gx and Gy: This point is considered as the base element of the group.

原理详解

     

       上图是随机数产生器的原理图,是公开的。additional input我们暂时把它设为null;φ的作用只是大整数和二进制数之间的映射,可忽略;x(A)表示A点的x坐标,P是椭圆的基点,Q是官方直接给出的(但并没说给出的原因)。我们整体来看下。

        它首先随机产生了一个数t,经过了φ(x(t*P)),然后分为了两部分,分别进入内部和外部状态。内部状态就是这样不断地经过φ(x(t*P))来改变,而外部状态经过内部状态弹出的一个数s,经φ(x(s*Q))变化再提取出相应字节成为了伪随机数。过程就是这么简单。下面举前两轮的例子:

       令in表示内部种子的值,on表示输出值。

       第一轮:

   

       第二轮:

     

       原理已经介绍完了,下面的问题是我们能否通过第一轮输出的o0推测第二轮输出的o1呢?那我们简单推一下(仔细盯着上面式子),要想知道第二轮输出o1,就必须知道第二轮的内部状态i2,但要知道i2,就必须要知道第一轮的内部状态i1。但我们不可能知道该随机数产生器的内部状态。可我们知道第一轮的输出o1啊,万一我们让第一轮输出状态o0跟第二轮内部状态i2产生联系呢,再细一点,万一让P和Q之间产生某种联系呢,那么是否就可以通过第一轮输出o0直接解出第二轮的输出o1呢?

       我们假设下P=Qd。(d就被称为NSA留下的后门)

       假设第一轮输出o0的点为 A = i1Q (注:o0是A的x坐标),

 

       然后两边同时乘以d,得到  dA = i1dQ

       因为P=dQ,所以 i1P = dA,

       那么第二轮的内部种子值 i2=φ( x( dA ) )即我们就可以根据o1= φ( x( i2Q ) )很轻松地将o1计算出。  

       总述,现在我只要算出第一轮输出值o0的点坐标A,乘以d,取x坐标,再乘以Q,最后再取x坐标,就可以得到o1了。

       追根溯源,造成问题的关键是常数Q,在标准中根本就没涉及到选择此常数的原因。如果Q经过特殊选择,并且用来选择这些常数所使用的数据被算法设计者保存下来,那么该算法设计者在知道该算法生成随机序列的前32个字节的情况下,可以预知未来所有生成的“随机”序列。这就跟DES的S盒来路不明是一样,被人们所怀疑诟病。补充:在实际情况中,输出一般是30个字节,我们可通过爆破的方法去求解,2的16次方,完全在可以接受的范围内。


实验

1. 选定一条NIST P-256椭圆曲线,其中a, b, p, r等都是已知的;  y2= x3+ ax + b ( mod p )

2. 随机选取一数e;

3. 计算Q = P*e,P作为椭圆的基点;

4. 根据以上伪随机数产生规则,输出o0

5. 求出下一产生数o1,并验证是否正确。

      细心的同学可能注意到了,这里为什么是Q=P*e,而不是上面讲的P=Q*d。因为P是基点,是固定了的,所以我们需要先选取后门d模r的逆e。     

      第一轮的输出o0,后门d和Q都是已知的。     

     下面是该椭圆曲线和Dual_EC_DRBG后门的代码,并打印出已知条件Q、e和第一轮输出o0

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os
import random
import seccure
import struct
import gmpy

def gen_d(order):
    d = os.urandom(32)
    d = int(d.encode('hex'),16)
    return d % order

def generate_backdoor(curve,d):
    #Create a known relationship between P and Q
    Q = curve.base
    Q = Q * d

    return Q

class dual_ec_dbrg(object):
    def __init__(self,seed,curve,qx,qy):
        self.i0 = seed
        self.curve = curve
        self.P = curve.base
        self.Q = seccure.AffinePoint(qx,qy,self.curve)
        if (not self.Q.on_curve):
            print "Chosen Q Not on Curve!"
            return
#Q = d*P
    def getrand(self):
        first = self.P * gmpy.mpz(self.i0)
        x = first.x
        out = self.Q * x
        self.i0 = int(first.x)
        return int(out.x)

p256curve = seccure.Curve.by_name_substring('nistp256')
e = gen_d(p256curve.order)
Q = generate_backdoor(p256curve,e)

gen = dual_ec_dbrg(random.randint(0,2 ** 32),p256curve,int(Q.x),int(Q.y))

o0 = gen.getrand()
print "Q.x: "+str(int(Q.x))
print "Q.y: "+str(int(Q.y))
print "e: "+ str(int(e))
print "o0: "+str(int(o0))

       我们的思路就是根据刚才的结论倒推回去。x(A)表示点A的x坐标。      

       o1=x(i2*Q) <-- i2 = x(dA) <-- o0=x(A)。

      难点在于通过x坐标o0求出其点A,这里要用到二次剩余系解法 (Tonelli–Shanks Algorithm)。该算法用到了欧拉判别条件,通过一系列的步骤判断,得到结果,没看懂。这毕竟是数学家的事,我就拿来用用。此处应有传送门

      d的值等于e关于模r的逆,r是椭圆曲线事先给出的定值,e已知的。      

      然后基本上就没什么要点了。   

def modular_sqrt(a, p):

    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) / 4, p)

    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1


    x = pow(a, (s + 1) / 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in xrange(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):#欧拉判别

    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

a = p256curve.a
b = p256curve.b
m = p256curve.m  #mod p

y = gmpy.mpz(0)
y = (pow(o0,3,m)+ a*o0 + b)%m
y = modular_sqrt(y,m)

A = seccure.AffinePoint(o0,y,p256curve)

assert(A.on_curve)

r = p256curve.order
d = gmpy.mpz(0)
d = gmpy.invert(gmpy.mpz(e),r)

i2 = (A*d).x
o1 = (Q*i2).x
print "predict o1: "+ str(o1)

real_o1 = gen.getrand()
print "real o1: "+ str(real_o1)



 待续

       实验是经过简化的,在实际情况中会比这个复杂,但关键点都讲到了。由于Q的参数来历不明,可能被设计者精心设计过拿到d了,如果真要修复的话,那就每次运行伪随机数产生器PRNG时都随机产生Q,所以d的值就不可能得到了。

       在下一篇文章中,我将会讲解另一个随机数产生器是怎么被攻破的,与因Dual_EC_DRBG的后门被攻破的原理不同,它已普遍地应用在php、ruby、python中,如果开发者不慎重,那将会产生严重的后果。


参考资料

http://redswallow.github.io/2013/12/ecc-and-dual-ec-drbg

https://www.zhihu.com/question/22343037

On the Possibility of a Back Door  in the NIST SP800-90 Dual Ec Prng pdf
......

标签:none

还不快抢沙发

添加新评论

captcha
请输入验证码

最新文章

最近回复

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

    分类

    其它