随机数生成器(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公司这一点)。
基础知识

上图是随机数产生器的原理图,是公开的。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
还不快抢沙发