原文网址：http://www.javacodegeeks.com/2013/03/ weaknesses-in-java-pseudo-random-number-generators-prngs.html 译文网址：http://blog.dontcareabout.us/2013/03/java-prng.html BBS 版以 markdown 格式撰写 ______________________________________________________________________ 这是 Kai Michaelis、Jorg Schwenk 还有我在 [RA Conference 2013] 的 Cryptographers' Track 发表论文的总结。 你可以取得我演讲时的[投影片]、还有[论文全文]。 我们对常见 Java library 所产生的乱数序列进行分析， 这些 Java library 用了 PRNG （Pseudo Random Number Generator，通常是 SecureRandom）， 我们发现在特定条件下有明显的弱点。 为了让这篇文章尽可能简短，各种 PRNG 所用的演算法、详细的 bug 描述、 统计检验的结果都略过不提，但是论文里头都有。 我们的调查涵盖 PRNG 本身、以及它们用来作 seed 的 entropy collector （例如没有可用的实数产生器时）。 **底线：需要品质良好的乱数时，不要使用 PRNG！** [RA Conference 2013]: https://ae.rsaconference.com/US13/connect/ sessionDetail.ww?SESSION_ID=3386&tclass=popup [投影片]: https://ae.rsaconference.com/US13/connect/fileDownload/ session/85EEC4CC0848A5E7793DDEC27550D7A6/CRYP-W25.pdf [论文全文]: http://link.springer.com/chapter/10.1007%2F978-3-642-36095-4_9 有很多测量品质的方式。首先，我们分析程式码， 然後试图（且成功地）发现导致缺陷的明显程式错误。 再者，我们对产生出来的乱数序列进行统计检验。 最後，我们在特定情况下（高系统负载、某些 component 无法使用...... 等等） 对演算法作压力测试。 [Apache Harmony] ================ 虽然已经退休了（译注：原文是 although retried，应该是 typo）， 但是 Apache Harmony 仍然活在 Android source code 中 （参见[这里][Harmony Wikipedia]）、 是几百万台机器的一部分。 [Apache Harmony]: http://harmony.apache.org/ [Harmony Wikipedia]: http://en.wikipedia.org/wiki/ Apache_Harmony#Use_in_Android_SDK 弱点 ---- 其中一个发现的 bug 直接影响 Android 平台。 其余的 bug 只在 Apache Harmony 当中， 「并没有」出现在 Android source code 里头。 1. 当建立一个自己提供 seed 的 SecureRandom instance （呼叫没有参数的 constructor 以及後续呼叫 `setSeed()`）， 在插入起始值之後，程式码无法调整 byte offset （在 state buffer 中的 pointer）。 这导致 counter 跟一开始的 padding（一个 32 bit word） 覆盖掉 seed 的一部分、而不是加在後头。 2. 当在 Unix-like 的 OS 下执行时， 新的 SecureRandom instance 给的 seed 是 20 byte、 来自 urandom 或是 random device。 如果两个 device 都无法存取，这个实作会提供一个备援的 seed 工具。 一旦这个 seed 工具已经收集到需要的 byte 数， 因为不明原因 most significant bit 会设定为 0。 结果就是 SecureRandom instance 的有效 seed 中， 每个 byte 只有 7/8，少了 8bit 而只剩下 56bit 的安全性 （因为第一个 bug 的关系，所以全部只有 64 bit）。 更糟的是，由於其他有问题的 modulo reduction， 单一呼叫 seed 工具的 entropy 被限制为 31 bit。 当观察产生出来的 byte 时，entropy collector 的问题是显而易见的。 下面这张图将两个 consecutive byte 标为一个点：  两个方向都缺乏大於 127 的数字。 GNU Classpath ============= 在有名的 [IcedTea] project 中有用到一部分的 GNU Classpath， 最为人知的是 Linux 上的 64-bit Java browser plugin。 [GNU Claspath]: http://www.gnu.org/software/classpath/ [IcedTea]: http://icedtea.classpath.org/wiki/Main_Page 弱点 ---- 这个 library 包含了一个关於 internal state 的明显弱点。 这个 bug 是关於在 hash 函数中使用相同的 Initialization Vector（IV）。 这减少了 internal state 未知的 byte 数量， 从 32 减少到只有 20。 entropy collector 演算法很难预测，这样很好， 但是它倚赖 thread 之间竞争 CPU 时间的行为， 要影响这个行为很容易（透过让系统处於高负载的情况下）。 thread 在执行期检查不够严格、无法确保良好的随机性。 下面的图表显示要输出平均分布是有困难的，留下了大片的斑点。 这张图是在系统高负载的情况下 entropy collector 执行的结果：  相反地，在正常条件下会是这样：  [OpenJDK] ======= 官方免费 open source 的 JavaSE 实作， 大抵上等同於 Oracle 提供的版本。 大多数的 Java 使用者可能都是用这份程式码。 [OpenJDK]: http://openjdk.java.net/ 弱点 ---- code review 没有找出什麽明显的弱点。 entropy collector 倚赖 thread 递增计数器， 但是有别於 GNU Classpath，它会确保执行时间的最小值。 得到的结果图形被很均匀地填满。  [The Legion of Bouncy Castle] ============================= 以某些角度来看，这个 library 跟其他的不太一样， 因为它只是一个非常综合性的加密演算法 library。 它有多个 SecureRandom 的替代品。 BouncyCastle 的 entropy collector 可以在两种模式下运作： 快速模式与慢速模式，`random` 输出会使用不同的 byte 数。 [The Legion of Bouncy Castle]: http://www.bouncycastle.org/java.html 弱点 ---- 跟 OpenJDK 相同，Bouncy Castle 的 SecureRandom 替代品 （DigestRandomGenerator）也没有什麽明显的 bug。 相反地 VMPCRandomGenerator 已知是有弱点的。 entropy collector 在两种模式下都可以把图形填满的很均匀。 快速模式的图：  慢速模式的图：  总结 ==== 上头这些实作的限制、不可设定的 internal state 是十分有趣的。 几乎所有实作都靠 SHA-1 作为 hash 函数。 因此，在 key 产生器大於 160 bit 时似乎没啥用处。 只有 Apache Harmony 是用 512bit 的 internal state， 但是它的程式有问题。 blog 的文章省略了很多细节与统计数据，只是为了提供一个快速而简单的评论。 如果你有兴趣知道更详细的内容，麻烦请去读完整的论文。 ______________________________________________________________________ 译注：说真的，翻完自己都看不懂，还是去看原始论文吧 Orz -- 钱锺书： 说出来的话 http://www.psmonkey.org 比不上不说出来的话 Java 版 cookcomic 版 只影射着说不出来的话 and more...... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.25.4.190 ※ 编辑: PsMonkey 来自: 114.25.15.134 (03/31 11:29)