关于 /dev/urandom 的流言终结

2019-05-05
16分钟阅读时长

有很多关于 /dev/urandom/dev/random 的流言在坊间不断流传。然而流言终究是流言。

本篇文章里针对的都是近来的 Linux 操作系统,其它类 Unix 操作系统不在讨论范围内。

/dev/urandom 不安全。加密用途必须使用 /dev/random

事实/dev/urandom 才是类 Unix 操作系统下推荐的加密种子。

/dev/urandom 伪随机数生成器 pseudo random number generator (PRND),而 /dev/random 是“真”随机数生成器。

事实:它们两者本质上用的是同一种 CSPRNG (一种密码学伪随机数生成器)。它们之间细微的差别和“真”“不真”随机完全无关。(参见:“Linux 随机数生成器的构架”一节)

/dev/random 在任何情况下都是密码学应用更好地选择。即便 /dev/urandom 也同样安全,我们还是不应该用它。

事实/dev/random 有个很恶心人的问题:它是阻塞的。(参见:“阻塞有什么问题?”一节)(LCTT 译注:意味着请求都得逐个执行,等待前一个请求完成)

但阻塞不是好事吗!/dev/random 只会给出电脑收集的信息熵足以支持的随机量。/dev/urandom 在用完了所有熵的情况下还会不断吐出不安全的随机数给你。

事实:这是误解。就算我们不去考虑应用层面后续对随机种子的用法,“用完信息熵池”这个概念本身就不存在。仅仅 256 位的熵就足以生成计算上安全的随机数很长、很长的一段时间了。(参见:“那熵池快空了的情况呢?”一节)

问题的关键还在后头:/dev/random 怎么知道有系统会多少可用的信息熵?接着看!

但密码学家老是讨论重新选种子(re-seeding)。这难道不和上一条冲突吗?

事实:你说的也没错!某种程度上吧。确实,随机数生成器一直在使用系统信息熵的状态重新选种。但这么做(一部分)是因为别的原因。(参见:“重新选种”一节)

这样说吧,我没有说引入新的信息熵是坏的。更多的熵肯定更好。我只是说在熵池低的时候阻塞是没必要的。

好,就算你说的都对,但是 /dev/(u)random 的 man 页面和你说的也不一样啊!到底有没有专家同意你说的这堆啊?

事实:其实 man 页面和我说的不冲突。它看似好像在说 /dev/urandom 对密码学用途来说不安全,但如果你真的理解这堆密码学术语你就知道它说的并不是这个意思。(参见:“random 和 urandom 的 man 页面”一节)

man 页面确实说在一些情况下推荐使用 /dev/random (我觉得也没问题,但绝对不是说必要的),但它也推荐在大多数“一般”的密码学应用下使用 /dev/urandom

虽然诉诸权威一般来说不是好事,但在密码学这么严肃的事情上,和专家统一意见是很有必要的。

所以说呢,还确实有一些专家和我的一件事一致的:/dev/urandom 就应该是类 UNIX 操作系统下密码学应用的首选。显然的,是他们的观点说服了我而不是反过来的。(参见:“正道”一节)


难以相信吗?觉得我肯定错了?读下去看我能不能说服你。

我尝试不讲太高深的东西,但是有两点内容必须先提一下才能让我们接着论证观点。

首当其冲的,什么是随机性,或者更准确地:我们在探讨什么样的随机性?(参见:“真随机”一节)

另外一点很重要的是,我没有尝试以说教的态度对你们写这段话。我写这篇文章是为了日后可以在讨论起的时候指给别人看。比 140 字长(LCTT 译注:推特长度)。这样我就不用一遍遍重复我的观点了。能把论点磨炼成一篇文章本身就很有助于将来的讨论。(参见:“你是在说我笨?!”一节)

并且我非常乐意听到不一样的观点。但我只是认为单单地说 /dev/urandom 坏是不够的。你得能指出到底有什么问题,并且剖析它们。

你是在说我笨?!

绝对没有!

事实上我自己也相信了 “/dev/urandom 是不安全的” 好些年。这几乎不是我们的错,因为那么德高望重的人在 Usenet、论坛、推特上跟我们重复这个观点。甚至连 man 手册都似是而非地说着。我们当年怎么可能鄙视诸如“信息熵太低了”这种看上去就很让人信服的观点呢?(参见:“random 和 urandom 的 man 页面”一节)

整个流言之所以如此广为流传不是因为人们太蠢,而是因为但凡有点关于信息熵和密码学概念的人都会觉得这个说法很有道理。直觉似乎都在告诉我们这流言讲的很有道理。很不幸直觉在密码学里通常不管用,这次也一样。

真随机

随机数是“真正随机”是什么意思?

我不想搞的太复杂以至于变成哲学范畴的东西。这种讨论很容易走偏因为对于随机模型大家见仁见智,讨论很快变得毫无意义。

在我看来“真随机”的“试金石”是量子效应。一个光子穿过或不穿过一个半透镜。或者观察一个放射性粒子衰变。这类东西是现实世界最接近真随机的东西。当然,有些人也不相信这类过程是真随机的,或者这个世界根本不存在任何随机性。这个就百家争鸣了,我也不好多说什么了。

密码学家一般都会通过不去讨论什么是“真随机”来避免这种哲学辩论。他们更关心的是 不可预测性 unpredictability 。只要没有任何方法能猜出下一个随机数就可以了。所以当你以密码学应用为前提讨论一个随机数好不好的时候,在我看来这才是最重要的。

无论如何,我不怎么关心“哲学上安全”的随机数,这也包括别人嘴里的“真”随机数。

两种安全,一种有用

但就让我们退一步说,你有了一个“真”随机变量。你下一步做什么呢?

你把它们打印出来然后挂在墙上来展示量子宇宙的美与和谐?牛逼!我支持你。

但是等等,你说你要它们?做密码学用途?额,那这就废了,因为这事情就有点复杂了。

事情是这样的,你的真随机、量子力学加护的随机数即将被用进不理想的现实世界算法里去。

因为我们使用的几乎所有的算法都并不是 信息论安全性 information-theoretic security 的。它们“只能”提供计算意义上的安全。我能想到为数不多的例外就只有 Shamir 密钥分享和 一次性密码本 One-time pad (OTP)算法。并且就算前者是名副其实的(如果你实际打算用的话),后者则毫无可行性可言。

但所有那些大名鼎鼎的密码学算法,AES、RSA、Diffie-Hellman、椭圆曲线,还有所有那些加密软件包,OpenSSL、GnuTLS、Keyczar、你的操作系统的加密 API,都仅仅是计算意义上安全的。

那区别是什么呢?信息论安全的算法肯定是安全的,绝对是,其它那些的算法都可能在理论上被拥有无限计算力的穷举破解。我们依然愉快地使用它们是因为全世界的计算机加起来都不可能在宇宙年龄的时间里破解,至少现在是这样。而这就是我们文章里说的“不安全”。

除非哪个聪明的家伙破解了算法本身 —— 在只需要更少量计算力、在今天可实现的计算力的情况下。这也是每个密码学家梦寐以求的圣杯:破解 AES 本身、破解 RSA 本身等等。

所以现在我们来到了更底层的东西:随机数生成器,你坚持要“真随机”而不是“伪随机”。但是没过一会儿你的真随机数就被喂进了你极为鄙视的伪随机算法里了!

真相是,如果我们最先进的哈希算法被破解了,或者最先进的分组加密算法被破解了,你得到的这些“哲学上不安全”的随机数甚至无所谓了,因为反正你也没有安全的应用方法了。

所以把计算性上安全的随机数喂给你的仅仅是计算性上安全的算法就可以了,换而言之,用 /dev/urandom

Linux 随机数生成器的构架

一种错误的看法

你对内核的随机数生成器的理解很可能是像这样的:

image: mythical structure of the kernel’s random number generator

“真正的随机性”,尽管可能有点瑕疵,进入操作系统然后它的熵立刻被加入内部熵计数器。然后经过“矫偏”和“漂白”之后它进入内核的熵池,然后 /dev/random/dev/urandom 从里面生成随机数。

“真”随机数生成器,/dev/random,直接从池里选出随机数,如果熵计数器表示能满足需要的数字大小,那就吐出数字并且减少熵计数。如果不够的话,它会阻塞程序直至有足够的熵进入系统。

这里很重要一环是 /dev/random 几乎只是仅经过必要的“漂白”后就直接把那些进入系统的随机性吐了出来,不经扭曲。

而对 /dev/urandom 来说,事情是一样的。除了当没有足够的熵的时候,它不会阻塞,而会从一直在运行的伪随机数生成器(当然,是密码学安全的,CSPRNG)里吐出“低质量”的随机数。这个 CSPRNG 只会用“真随机数”生成种子一次(或者好几次,这不重要),但你不能特别相信它。

在这种对随机数生成的理解下,很多人会觉得在 Linux 下尽量避免 /dev/urandom 看上去有那么点道理。

因为要么你有足够多的熵,你会相当于用了 /dev/random。要么没有,那你就会从几乎没有高熵输入的 CSPRNG 那里得到一个低质量的随机数。

看上去很邪恶是吧?很不幸的是这种看法是完全错误的。实际上,随机数生成器的构架更像是下面这样的。

更好地简化

Linux 4.8 之前

image: actual structure of the kernel’s random number generator before Linux 4.8

你看到最大的区别了吗?CSPRNG 并不是和随机数生成器一起跑的,它在 /dev/urandom 需要输出但熵不够的时候进行填充。CSPRNG 是整个随机数生成过程的内部组件之一。从来就没有什么 /dev/random 直接从池里输出纯纯的随机性。每个随机源的输入都在 CSPRNG 里充分混合和散列过了,这一切都发生在实际变成一个随机数,被 /dev/urandom 或者 /dev/random 吐出去之前。

另外一个重要的区别是这里没有熵计数器的任何事情,只有预估。一个源给你的熵的量并不是什么很明确能直接得到的数字。你得预估它。注意,如果你太乐观地预估了它,那 /dev/random 最重要的特性——只给出熵允许的随机量——就荡然无存了。很不幸的,预估熵的量是很困难的。

这是个很粗糙的简化。实际上不仅有一个,而是三个熵池。一个主池,另一个给 /dev/random,还有一个给 /dev/urandom,后两者依靠从主池里获取熵。这三个池都有各自的熵计数器,但二级池(后两个)的计数器基本都在 0 附近,而“新鲜”的熵总在需要的时候从主池流过来。同时还有好多混合和回流进系统在同时进行。整个过程对于这篇文档来说都过于复杂了,我们跳过。

Linux 内核只使用事件的到达时间来预估熵的量。根据模型,它通过多项式插值来预估实际的到达时间有多“出乎意料”。这种多项式插值的方法到底是不是好的预估熵量的方法本身就是个问题。同时硬件情况会不会以某种特定的方式影响到达时间也是个问题。而所有硬件的取样率也是个问题,因为这基本上就直接决定了随机数到达时间的颗粒度。

说到最后,至少现在看来,内核的熵预估还是不错的。这也意味着它比较保守。有些人会具体地讨论它有多好,这都超出我的脑容量了。就算这样,如果你坚持不想在没有足够多的熵的情况下吐出随机数,那你看到这里可能还会有一丝紧张。我睡的就很香了,因为我不关心熵预估什么的。

最后要明确一下:/dev/random/dev/urandom 都是被同一个 CSPRNG 饲喂的。只有它们在用完各自熵池(根据某种预估标准)的时候,它们的行为会不同:/dev/random 阻塞,/dev/urandom 不阻塞。

Linux 4.8 以后

image: actual structure of the kernel’s random number generator from Linux 4.8 onward

在 Linux 4.8 里,/dev/random/dev/urandom 的等价性被放弃了。现在 /dev/urandom 的输出不来自于熵池,而是直接从 CSPRNG 来。

我们很快会理解为什么这不是一个安全问题。(参见:“CSPRNG 没问题”一节)

阻塞有什么问题?

你有没有需要等着 /dev/random 来吐随机数?比如在虚拟机里生成一个 PGP 密钥?或者访问一个在生成会话密钥的网站?

这些都是问题。阻塞本质上会降低可用性。换而言之你的系统不干你让它干的事情。不用我说,这是不好的。要是它不干活你干嘛搭建它呢?

我在工厂自动化里做过和安全相关的系统。猜猜看安全系统失效的主要原因是什么?操作问题。就这么简单。很多安全措施的流程让工人恼火了。比如时间太长,或者太不方便。你要知道人很会找捷径来“解决”问题。

但其实有个更深刻的问题:人们不喜欢被打断。它们会找一些绕过的方法,把一些诡异的东西接在一起仅仅因为这样能用。一般人根本不知道什么密码学什么乱七八糟的,至少正常的人是这样吧。

为什么不禁止调用 random()?为什么不随便在论坛上找个人告诉你用写奇异的 ioctl 来增加熵计数器呢?为什么不干脆就把 SSL 加密给关了算了呢?

到头来如果东西太难用的话,你的用户就会被迫开始做一些降低系统安全性的事情——你甚至不知道它们会做些什么。

我们很容易会忽视可用性之类的重要性。毕竟安全第一对吧?所以比起牺牲安全,不可用、难用、不方便都是次要的?

这种二元对立的想法是错的。阻塞不一定就安全了。正如我们看到的,/dev/urandom 直接从 CSPRNG 里给你一样好的随机数。用它不好吗!

CSPRNG 没问题

现在情况听上去很惨淡。如果连高质量的 /dev/random 都是从一个 CSPRNG 里来的,我们怎么敢在高安全性的需求上使用它呢?

实际上,“看上去随机”是现存大多数密码学基础组件的基本要求。如果你观察一个密码学哈希的输出,它一定得和随机的字符串不可区分,密码学家才会认可这个算法。如果你生成一个分组加密,它的输出(在你不知道密钥的情况下)也必须和随机数据不可区分才行。

如果任何人能比暴力穷举要更有效地破解一个加密,比如它利用了某些 CSPRNG 伪随机的弱点,那这就又是老一套了:一切都废了,也别谈后面的了。分组加密、哈希,一切都是基于某个数学算法,比如 CSPRNG。所以别害怕,到头来都一样。

那熵池快空了的情况呢?

毫无影响。

加密算法的根基建立在攻击者不能预测输出上,只要最一开始有足够的随机性(熵)就行了。“足够”的下限可以是 256 位,不需要更多了。

介于我们一直在很随意的使用“熵”这个概念,我用“位”来量化随机性希望读者不要太在意细节。像我们之前讨论的那样,内核的随机数生成器甚至没法精确地知道进入系统的熵的量。只有一个预估。而且这个预估的准确性到底怎么样也没人知道。

重新选种

但如果熵这么不重要,为什么还要有新的熵一直被收进随机数生成器里呢?

djb 提到 太多的熵甚至可能会起到反效果。

首先,一般不会这样。如果你有很多随机性可以拿来用,用就对了!

但随机数生成器时不时要重新选种还有别的原因:

想象一下如果有个攻击者获取了你随机数生成器的所有内部状态。这是最坏的情况了,本质上你的一切都暴露给攻击者了。

你已经凉了,因为攻击者可以计算出所有未来会被输出的随机数了。

但是,如果不断有新的熵被混进系统,那内部状态会再一次变得随机起来。所以随机数生成器被设计成这样有些“自愈”能力。

但这是在给内部状态引入新的熵,这和阻塞输出没有任何关系。

random 和 urandom 的 man 页面

这两个 man 页面在吓唬程序员方面很有建树:

/dev/urandom 读取数据不会因为需要更多熵而阻塞。这样的结果是,如果熵池里没有足够多的熵,取决于驱动使用的算法,返回的数值在理论上有被密码学攻击的可能性。发动这样攻击的步骤并没有出现在任何公开文献当中,但这样的攻击从理论上讲是可能存在的。如果你的应用担心这类情况,你应该使用 /dev/random

实际上已经有 /dev/random/dev/urandom 的 Linux 内核 man 页面的更新版本。不幸的是,随便一个网络搜索出现我在结果顶部的仍然是旧的、有缺陷的版本。此外,许多 Linux 发行版仍在发布旧的 man 页面。所以不幸的是,这一节需要在这篇文章中保留更长的时间。我很期待删除这一节!

没有“公开的文献”描述,但是 NSA 的小卖部里肯定卖这种攻击手段是吧?如果你真的真的很担心(你应该很担心),那就用 /dev/random 然后所有问题都没了?

然而事实是,可能某个什么情报局有这种攻击,或者某个什么邪恶黑客组织找到了方法。但如果我们就直接假设这种攻击一定存在也是不合理的。

而且就算你想给自己一个安心,我要给你泼个冷水:AES、SHA-3 或者其它什么常见的加密算法也没有“公开文献记述”的攻击手段。难道你也不用这几个加密算法了?这显然是可笑的。

我们在回到 man 页面说:“使用 /dev/random”。我们已经知道了,虽然 /dev/urandom 不阻塞,但是它的随机数和 /dev/random 都是从同一个 CSPRNG 里来的。

如果你真的需要信息论安全性的随机数(你不需要的,相信我),那才有可能成为唯一一个你需要等足够熵进入 CSPRNG 的理由。而且你也不能用 /dev/random

man 页面有毒,就这样。但至少它还稍稍挽回了一下自己:

如果你不确定该用 /dev/random 还是 /dev/urandom ,那你可能应该用后者。通常来说,除了需要长期使用的 GPG/SSL/SSH 密钥以外,你总该使用/dev/urandom

该手册页的当前更新版本毫不含糊地说:

/dev/random 接口被认为是遗留接口,并且 /dev/urandom 在所有用例中都是首选和足够的,除了在启动早期需要随机性的应用程序;对于这些应用程序,必须替代使用 getrandom(2),因为它将阻塞,直到熵池初始化完成。

行。我觉得没必要,但如果你真的要用 /dev/random 来生成 “长期使用的密钥”,用就是了也没人拦着!你可能需要等几秒钟或者敲几下键盘来增加熵,但这没什么问题。

但求求你们,不要就因为“你想更安全点”就让连个邮件服务器要挂起半天。

正道

本篇文章里的观点显然在互联网上是“小众”的。但如果问一个真正的密码学家,你很难找到一个认同阻塞 /dev/random 的人。

比如我们看看 Daniel Bernstein(即著名的 djb)的看法:

我们密码学家对这种胡乱迷信行为表示不负责。你想想,写 /dev/random man 页面的人好像同时相信:

  • (1) 我们不知道如何用一个 256 位长的 /dev/random 的输出来生成一个无限长的随机密钥串流(这是我们需要 /dev/urandom 吐出来的),但与此同时
  • (2) 我们却知道怎么用单个密钥来加密一条消息(这是 SSL,PGP 之类干的事情)

对密码学家来说这甚至都不好笑了

或者 Thomas Pornin 的看法,他也是我在 stackexchange 上见过最乐于助人的一位:

简单来说,是的。展开说,答案还是一样。/dev/urandom 生成的数据可以说和真随机完全无法区分,至少在现有科技水平下。使用比 /dev/urandom “更好的“随机性毫无意义,除非你在使用极为罕见的“信息论安全”的加密算法。这肯定不是你的情况,不然你早就说了。

urandom 的 man 页面多多少少有些误导人,或者干脆可以说是错的——特别是当它说 /dev/urandom 会“用完熵”以及 “/dev/random 是更好的”那几句话;

或者 Thomas Ptacek 的看法,他不设计密码算法或者密码学系统,但他是一家名声在外的安全咨询公司的创始人,这家公司负责很多渗透和破解烂密码学算法的测试:

用 urandom。用 urandom。用 urandom。用 urandom。用 urandom。

没有完美

/dev/urandom 不是完美的,问题分两层:

在 Linux 上,不像 FreeBSD,/dev/urandom 永远不阻塞。记得安全性取决于某个最一开始决定的随机性?种子?

Linux 的 /dev/urandom 会很乐意给你吐点不怎么随机的随机数,甚至在内核有机会收集一丁点熵之前。什么时候有这种情况?当你系统刚刚启动的时候。

FreeBSD 的行为更正确点:/dev/random/dev/urandom 是一样的,在系统启动的时候 /dev/random 会阻塞到有足够的熵为止,然后它们都再也不阻塞了。

与此同时 Linux 实行了一个新的 系统调用 syscall ,最早由 OpenBSD 引入叫 getentrypy(2),在 Linux 下这个叫 getrandom(2)。这个系统调用有着上述正确的行为:阻塞到有足够的熵为止,然后再也不阻塞了。当然,这是个系统调用,而不是一个字节设备(LCTT 译注:不在 /dev/ 下),所以它在 shell 或者别的脚本语言里没那么容易获取。这个系统调用 自 Linux 3.17 起存在。

在 Linux 上其实这个问题不太大,因为 Linux 发行版会在启动的过程中保存一点随机数(这发生在已经有一些熵之后,因为启动程序不会在按下电源的一瞬间就开始运行)到一个种子文件中,以便系统下次启动的时候读取。所以每次启动的时候系统都会从上一次会话里带一点随机性过来。

显然这比不上在关机脚本里写入一些随机种子,因为这样的显然就有更多熵可以操作了。但这样做显而易见的好处就是它不用关心系统是不是正确关机了,比如可能你系统崩溃了。

而且这种做法在你真正第一次启动系统的时候也没法帮你随机,不过好在 Linux 系统安装程序一般会保存一个种子文件,所以基本上问题不大。

虚拟机是另外一层问题。因为用户喜欢克隆它们,或者恢复到某个之前的状态。这种情况下那个种子文件就帮不到你了。

但解决方案依然和用 /dev/random 没关系,而是你应该正确的给每个克隆或者恢复的镜像重新生成种子文件。

太长不看

别问,问就是用 /dev/urandom !


via: https://www.2uo.de/myths-about-urandom/

作者:Thomas Hühn 译者:Moelf 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出