使用RSA加密仍旧是安全的吗?

0
953

RSA可能会因为部署不小心而被破解,但这是否意味着它可以进行破解?

让我们来谈一谈RSA加密。上个月,我们对一个名为Bleichenbacher的猫的漏洞进行了报道,该漏洞可能会影响RSA密钥的生成。今天我们将来讨论一下,配置不良的RSA可能如何导致公钥被破解。

这实际上并不是一项新的研究,它源于2012年的一篇研究论文,但上周威廉•库斯莫尔(William Kuszmaul)在一篇有关Algorithm Soup的博客文章中对此进行了探讨。这篇文章写得很好,你有空可以看一看。William是麻省理工学院一名博士生,专攻计算机科学和算法。

或者,如果这听起来有点吓人,你可以让我来为你一一讲述。

不管怎样,今天我们将来讨论一下RSA密码系统,它的弱点以及为什么随机数生成器可能根本就不是随机的。

让我们从RSA开始

RSA代表Rivests-Shamir–Adleman,它们是其创建者的三个姓氏。正如我们之前讨论过的,公钥密码学实际上被“发现”了两次,一次是在1973年由英国情报机构政府通信总部(GCHQ)“发现”的——当时这被认为是不切实际的,另一次是在1976年由Whitfield Diffie和Martin Hellman(在Ralph Merkle的协助下)“发现”的。

在那个时候,事情还是相当理论化的,没有人能够使加密成为一个单向的功能,因为它几乎是不可能进行反向工程的。

1977年,Ron Rivest、Adi Shamir和Leonard Adleman开始着手实现这一目标。Rivest和Shamir都是计算机方面的科学家,而Adleman则是一名数学家。最终,在经历了几种失败的方法(几乎失去了所有希望)之后,他们找到了将质因数分解作为单向加密的方法。

素数——对于那些在高中数学课堂上一直睡觉,从来没有认真听过课的人——是大于1且只能被1和它们自身(因数)整除的数。

记住,公钥加密、单向加密、非对称加密——不管你喜欢怎么称呼它——是促进SSL/TLS密钥交换的关键。我们之前写过很多有关这一方面的文章,今天我们再深入一点。

当我们提到质因数分解时,它所意味的是,RSA会使用两个大的随机素数(p和q)——我们说的是非常大的、有几百位那么长——然后将它们相乘来创建一个公钥。

因此,p * q = x

而x =公钥

任何人都可以使用公钥来加密数据。通常,在SSL/TLS的情形中,加密的是会话密钥。然而,如果不知道p和q这两个素数的值,其他人就无法解密该消息。

为了让你能够更好地了解RSA的计算难度,分解一个232位长的数字需要花费少数几名研究人员超过1500年的时间来进行计算(分布在数百台计算机上)。

通常,密钥长度代表的是计算困难度。目前的标准是2,048位RSA密钥,而几年前还允许使用1,024位的密钥。一些组织使用的是3072位和4096位密钥,但是随着RSA密钥长度不断增长,它们提供的安全性与使用它们所需的计算能力并不相称。

因此,RSA有什么问题?

除了它的扩展能力较差,RSA的致命弱点是,它依赖于随机数生成器来确定质数(p和q)。

随机数生成器(RNG)只是一个生成数字序列的设备或程序, 而这些数字序列是不能进行有效预测的,因为所预测的结果并不比随机预测的准确度来得高。由此便产生了这个名字。

从RSA的角度看,随机数生成器有两大问题:

1. 他们并不是真正随机的

2. 几乎所有人使用的都是相同的数

我要尽量把理解难度控制在这一水平,因为我不是一个数学家,我不想让你的目光呆滞,两眼无神。因此,就有了这样的解释:

总而言之,有两种生成随机数的方法。第一种要求你映射一些自然发生的、有望是随机的事件或现象。实际上,宾夕法尼亚州立大学正在测试一种相当新的生物密钥生成方法,即将活细胞的运动映射到网格上,然后使用该网格来生成加密密钥。Cloudflare对其大堂里的熔岩灯也做了类似的处理。

坦白地说,第一种方法很吸引人,但它也是一个我们现在需要避免的“兔子洞”。第二种方法称为伪随机数生成,它依赖于计算算法。出于RSA加密的考虑,我们将这些称为安全地进行了加密的伪随机数生成器(CSPRNG),这些伪随机数生成器会生成不同看似是随机结果的长序列,而这些结果实际上完全是由一个更短的数值(称为种子)决定的。

以下是一些最常用的、进行了标准化的伪随机数生成器(CSPRNG)名单:

  • FIPS 186-4
  • NIST SP 800-900A Rev. 1
  • ANSI X9.17-1985A 附录C
  • ANSI X9.31-1998附录a .2.4
  • ANSI X9.62-2005,附录D

让我们回到种子上来。当你听到政客和执法官员谈论加密后门时,实现这一点的一种方法是,共享密钥生成过程中所使用的种子,这可以帮助更快速、更有效地确定密钥的数值。

种子多样性的缺失可以追溯到RSA的第一个问题:生成的素数并不是真正是随机的。

RSA加密提供的安全性不足99.8%

2012年,一篇名为《Ron was wrong, Whit is right》(暗指提出RSA的Ron Rivest和提出Diffie-Hellman算法的Whitfield Diffie)的研究论文,试图检验“每次生成密钥时都会做出不同的随机选择这一假设的有效性”。

我们已经讨论了随机数的生成并不是那么随机的这一问题,以及RNG所使用的相同的方式正得到广泛的使用。结果是许多公钥共享一个素数。

但为什么这是个问题呢?

原因如下:

这就是任何非数论专家感到惊讶的地方。如果两个公钥共享一个素数,那么这个素数就是公约数,令人惊讶的是,找到两个数的最大公分母比分解一个数要容易。找到公约数所需时间与位数成比例。一旦有了公约数,你就可以读取任何公钥所发送的消息。

这意味着,例如,你可以获取在SSL/TLS握手期间进行交换的会话密钥的副本,并窃听整个连接。

“有了这个想法,研究人员便开始扫描网络,并收集了620万个实际存在的公钥。然后,他们计算出了不同密钥对之间的最大公约数,从而在一个密钥与其他密钥共享一个质因素时,便会破解该密钥。总而言之,他们能够破解12934把密钥。换句话说,如果不小心进行了使用,RSA加密提供的安全性不足99.8%。”

这听起来有点微不足道,因为这大约是千分之二的概率。

但这是否意味着RSA被破解了呢?不完全是,只是很脆弱。2012年那篇论文的研究人员淡化了其中一件事,也就是William所注意到的一个因素,那就是在研究过程中所使用的算法能够帮助因式分解并破解近1.3万个公钥。

“根据作者的说法,在一个核上花费数小时的时间便能运行完成整个计算。但是粗略的计算表明,计算36万亿对密钥的最大公约数(GCD)需要数年的时间,而不是数小时。

这是通过一个巧妙的、但故意不透明的算法以及所谓的三对数因子来实现的。根据一篇论文,这种算法每破解1000对密钥大约需要7.65秒,运行完成所有620万对密钥大约需要13个小时。另一个稍微优雅一点的版本的算法可以在4.5秒内运行完成1000对,这将花费大约7个半小时来完成所有620万对密钥的计算。

让我们回到最初的问题。RSA能够被破解的吗?不能,但是它是很脆弱的。绝大多数被破解的密钥都来自路由器等设备,或像防火墙那样的嵌入式应用程序。这将指出一个事实,即许多制造商可能使用了相同的RNG,甚至可能使用了相同的播种。

具有讽刺意味的是,与逐个破解密钥相比,批量破解密钥似乎更容易。这意味着你需要确保你的公钥并没有与相关密钥共享素数。同时,评估你正在使用的CSPRNG,并检查它是否提供了足够的熵。熵,由于没有更好的定义,是一种衡量随机性的指标。随机性越高则越好。

或者,正如我们在上一篇有关RSA的博客文章中所建议到的,你总是可以切换到Elliptic Curve Diffie-Helman。

LEAVE A REPLY

Please enter your comment!
Please enter your name here