再谈随机数引起的阻塞问题

Java的随机数实现有很多坑,记录一下这次使用jdk1.8里新增的加强版随机数实现SecureRandom.getInstanceStrong() 遇到的问题。

之前在维护ali-tomcat的时候曾发现过jvm随机数算法选用不当导致tomcat的SessionID生成非常慢的情况,可以参考JVM上的随机数与熵池策略Docker中apache-tomcat启动慢的问题 这两篇文章。不过当时没有太追究,以为使用了-Djava.security.egd=file:/dev/./urandom就可以避免了,在这次项目里再次遇到随机数导致所有线程阻塞之后发现这块还挺多规则。

本次项目中使用的是jdk1.8,启动参数里设置了

-Djava.security.egd=file:/dev/./urandom

使用的随机数方式是Java8新增的:

SecureRandom.getInstanceStrong();

碰到故障时,线程阻塞在

"DubboServerHandler-xxx:20880-thread-1789" #28440 daemon prio=5 os_prio=0 tid=0x0000000008ffd000 nid=0x5712 runnable [0x000000004cbd7000]
java.lang.Thread.State: RUNNABLE
    at java.io.FileInputStream.readBytes(Native Method)
    at java.io.FileInputStream.read(FileInputStream.java:246)
    at sun.security.provider.NativePRNG$RandomIO.readFully(NativePRNG.java:410)
    at sun.security.provider.NativePRNG$RandomIO.implGenerateSeed(NativePRNG.java:427)
    - locked <0x00000000c03a3c90> (a java.lang.Object)
    at sun.security.provider.NativePRNG$RandomIO.access$500(NativePRNG.java:329)
    at sun.security.provider.NativePRNG$Blocking.engineGenerateSeed(NativePRNG.java:272)
    at java.security.SecureRandom.generateSeed(SecureRandom.java:522)

因为这个地方有加锁,locked <0x00000000c03a3c90>,所以其它线程调用到这里时会等待这个lock:

"DubboServerHandler-xxx:20880-thread-1790" #28441 daemon prio=5 os_prio=0 tid=0x0000000008fff000 nid=0x5713 waiting for monitor entry [0x000000004ccd8000]
java.lang.Thread.State: BLOCKED (on object monitor)
    at sun.security.provider.NativePRNG$RandomIO.implGenerateSeed(NativePRNG.java:424)
    - waiting to lock <0x00000000c03a3c90> (a java.lang.Object)
    at sun.security.provider.NativePRNG$RandomIO.access$500(NativePRNG.java:329)
    at sun.security.provider.NativePRNG$Blocking.engineGenerateSeed(NativePRNG.java:272)
    at java.security.SecureRandom.generateSeed(SecureRandom.java:522)

去查 NativePRNG$Blocking代码,看到它的文档描述:

A NativePRNG-like class that uses /dev/random for both seed and random material. Note that it does not respect the egd properties, since we have no way of knowing what those qualities are.

奇怪怎么-Djava.security.egd=file:/dev/./urandom参数没起作用,仍使用/dev/random作为随机数的熵池,时间久或调用频繁的话熵池很容易不够用而导致阻塞;于是看了一下 SecureRandom.getInstanceStrong()的文档:

Returns a SecureRandom object that was selected by using the algorithms/providers specified in the securerandom.strongAlgorithms Security property.

原来有自己的算法,在 jre/lib/security/java.security 文件里,默认定义为:

securerandom.strongAlgorithms=NativePRNGBlocking:SUN

如果修改算法值为NativePRNGNonBlocking:SUN的话,会采用NativePRNG$NonBlocking里的逻辑,用/dev/urandom作为熵池,不会遇到阻塞问题。但这个文件是jdk系统文件,修改它或重新指定一个路径都有些麻烦,最好能通过系统环境变量来设置,可这个变量不像securerandom.source属性可以通过系统环境变量-Djava.security.egd=xxx来配置,找半天就是没有对应的系统环境变量。只好修改代码,不采用SecureRandom.getInstanceStrong这个新方法,改成了SecureRandom.getInstance("NativePRNGNonBlocking")

对于SecureRandom的两种算法实现:SHA1PRNGNativePRNGsecurerandom.source 变量的关系,找到一篇解释的很清楚的文章:Using the SecureRandom Class

On Linux:

1) when this value is “file:/dev/urandom” then the NativePRNG algorithm is registered by the Sun crypto provider as the default implementation; the NativePRNG algorithm then reads from /dev/urandom for nextBytes but /dev/random for generateSeed

2) when this value is “file:/dev/random” then the NativePRNG algorithm is not registered by the Sun crypto provider, but the SHA1PRNG system uses a NativeSeedGenerator which reads from /dev/random.

3) when this value is anything else then the SHA1PRNG is used with a URLSeedGenerator that reads from that source.

4) when the value is undefined, then SHA1PRNG is used with ThreadedSeedGenerator

5) when the code explicitly asks for “SHA1PRNG” and the value is either “file:/dev/urandom” or “file:/dev/random” then (2) also occurs

6) when the code explicitly asks for “SHA1PRNG” and the value is some other “file:” url, then (3) occurs

7) when the code explicitly asks for “SHA1PRNG” and the value is undefined then (4) occurs

至于SHA1PRNG算法里,为何用urandom时,不能直接设置为file:/dev/urandom而要用变通的方式设置为file:///dev/urandom或者 file:/dev/./urandom,参考这里

In SHA1PRNG, there is a SeedGenerator which does various things depending on the configuration.

  1. If java.security.egd or securerandom.source point to “file:/dev/random” or “file:/dev/urandom”, we will use NativeSeedGenerator, which calls super() which calls SeedGenerator.URLSeedGenerator(/dev/random). (A nested class within SeedGenerator.) The only things that changed in this bug was that urandom will also trigger use of this code path.

  2. If those properties point to another URL that exists, we’ll initialize SeedGenerator.URLSeedGenerator(url). This is why “file:///dev/urandom”, “file:/./dev/random”, etc. will work.

再谈随机数引起的阻塞问题》上有5条评论

  1. hongjiang 文章作者

    https://www.ibm.com/developerworks/community/blogs/5144904d-5d75-45ed-9d2b-cf1754ee936a/entry/linux_%25e7%25b3%25bb%25e7%25bb%259f%25e4%25b8%25ad%25e9%259a%258f%25e6%259c%25ba%25e6%2595%25b0%25e5%259c%25a8_kvm_%25e4%25b8%25ad%25e7%259a%2584%25e5%25ba%2594%25e7%2594%25a8?lang=en

    虚拟机环境下和服务器情况类似,输入设备操作很少,相对于 Host 而言,Disk I/O 也相对较少,因此依赖 Guest 自身 PRNG 产生的随机数质量不高,因此虚拟机通常从 Host(宿主机)获取部分随机数据。对于 KVM 虚拟机来说,存在一个半虚拟化设备 virtio-rng 作为硬件随机数产生器。Linux Kernel 从 2.6.26 开始支持 virtio-rng, QEMU 在 1.3 版本加入了对 virtio-rng 的支持。 virtio-rng 设备会读取 Host 的随机数源并且填充到 Guest(客户机)的熵池中。

    回复
  2. hongjiang 文章作者

    Intel’s Ivy Bridge family 有一个功能叫”Secure Key”, 处理器包含了一个内部硬件 DRNG(Digital Random Number Generator)用于产生随机数,使用汇编指令 RDRAND 即可获得高强度的随机数,Linux Kernel 会使用异或操作把 RDRAND 产生的随机数混合进熵池, 代码实现在 drivers/char/random.c 的 extract_entropy()函数里。

    回复
  3. hongjiang 文章作者

    还有一些第三方的硬件随机数生成器,通常是 USB 或者 PCI 设备,主要是在服务器上使用。Linux Kernel 的 hwrng(hardware random number generator)抽象层(/dev/hwrng 设备)可以选择监控 RNG 设备,并且在熵池数据不足的时候要求设备提供随机数据到 kernel 的熵池,rngd 守护进程可以读取 hwrng 的数据然后补给到 kernel 的熵池中。

    回复
  4. hongjiang 文章作者

    http://kernel.taobao.org/index.php?title=%E5%86%85%E6%A0%B8%E6%9C%88%E6%8A%A52013-09

    Hardware random number generators
    在机器上运行的程序是一个确定型状态机,因此它不能自己产生真正的随机数。随机数的需求是个很通用的需求,内核提供了我们称之为伪随机数(PRNG)生成器的机制,理论上,攻击者是可以完全猜中PRNG的产生结果,但如果PRNG生成器能够考虑缘于外部事件的熵,安全性就也还可以在多数情况下满足要求。
    其实硬件可以通过采集量子噪音生成真正的随机数,也有一些处理器内置了随机数生成器,通过RDRAND指令就读出它们。硬件RNG的问题是几乎不可能检验它们的结果。如果恶意代理商伪造了硬件RNG,几乎不可能被检测出来。最近研究也证明,只需要在对硬件做很小的修改就可以干扰硬件RND,并且还可以通过随机性验证。因恐怕也不能完全信任硬件RND。
    于是,关于内核是否使用硬件RND就开始了讨论。有些开发者希望排除掉这种“熵源”只使用具有不确定性外部的熵源。也可以将硬件RND与这些熵源混合在一起构成所谓的“熵池”,再进一步生成供使用的随机数结果。理论上在这种方法下即使硬件RNG被劫持了,也不会对随机数结果造成什么影响。还有一些关于RDRAND指令性能和TPM(trusted platform module)上RNG的讨论,但都非主流了,不再赘述。
    Overestimated entropy
    如上所述,内核试图尽可能使用外部贡献的熵,其中一个熵源就是设备中断的发生时间,通常可以使用get_cycles()读取time stamp counter (TSC)得到,但Stephan Mueller指出:在许多架构上,这个函数只是返回0,这样熵池中的熵值就会偏低。他建议读取硬件时钟,但Ted Ts’o反对说这种方法太慢,他在MIPS上的经验表明,每个体系结构上总有些随着时间而自动增长的计数器,虽然宽度不一定很长,但作为熵源这些计数器也足够使用了。虽然还没有明确的解决方案,但Ted乐观地表示大可不必需要担心这点。
    Peter发起了另一个话题:在内核试图写入熵池时,并没有考虑到它其实是在覆写已经计算好的熵,因此存在熵值过高的现象。他发了一些补丁解决这个问题,但反响寥寥,原因可能是Ted在另一个话题中提到,估算熵池中的熵值是很困难的,这需要知道所有熵源的情况。
    总得来说,内核试图使用一些偏向保守的方案以改善因为硬件RNG攻击导致的安全缺陷,最后一句:“In this world, one cannot do a whole lot better than that”。

    回复
  5. hongjiang 文章作者

    http://tinylab.org/myths-about-urandom/

    /dev/urandom 也不是完美的,有两重问题:

    Linux 不像 FreeBSD,它的 /dev/urandom 总是非阻塞的。其整个安全性的保证,要求开始时刻必须是随机的,即要有一个种子。

    刚启动时,Linux 内核还没来得及收集熵,所以 /dev/urandom 给出的随机数不是那么随机的。

    这点上,FreeBSD 做的比较好:其上的 /dev/random 和 /dev/urandom 就是同一设备。在开始时刻,/dev/random 是阻塞的,直到收集到足够熵。之后就不阻塞了。

    对此 Linux 也有补救措施,那就是本次开机,保存的一些随机数到一个种子文件。下次启动时读入该种子文件(将种子文件内容写入 /dev/urandom)。从而在启动中,能汲取上次开机的随机性。

    至于在什么时候写种子文件,在关机脚本中写不是很好。例如死机崩溃了,就没机会写了。所以,别依赖每次都正常关机。
    还有,在安装完系统后的第一次启动,上面机制失效了。其对策为,系统安装时,安装器会写一个种子文件。
    对于虚拟机,是另一层面的问题了:人们总是喜欢克隆虚拟机,或者存虚拟机快照,此时种子文件不起作用。
    但其解决方案也不是到处用 /dev/random,而是类似在克隆后,或从快照中恢复后,进行补种。

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注