Java 各種亂數產生器（PRNG）的弱點

原文網址：http://www.javacodegeeks.com/2013/03/weaknesses-in-java-pseudo-random-number-generators-prngs.html

這是 Kai Michaelis、Jörg Schwenk 還有我在 RA Conference 2013 的 Cryptographers' Track 發表論文的總結。 你可以取得我演講時的投影片、還有論文全文。 我們對常見 Java library 所產生的亂數序列進行分析， 這些 Java library 用了 PRNG（Pseudo Random Number Generator，通常是 SecureRandom）， 我們發現在特定條件下有明顯的弱點。 為了讓這篇文章盡可能簡短，各種 PRNG 所用的演算法、詳細的 bug 描述、 統計檢驗的結果都略過不提，但是論文裡頭都有。 我們的調查涵蓋 PRNG 本身、以及它們用來作 seed 的 entropy collector （例如沒有可用的實數產生器時）。 底線：需要品質良好的亂數時，不要使用 PRNG！

有很多測量品質的方式。首先，我們分析程式碼， 然後試圖（且成功地）發現導致缺陷的明顯程式錯誤。 再者，我們對產生出來的亂數序列進行統計檢驗。 最後，我們在特定情況下（高系統負載、某些 component 無法使用...... 等等） 對演算法作壓力測試。

Apache Harmony

雖然已經退休了（譯註：原文是 although retried，應該是 typo）， 但是 Apache Harmony 仍然活在 Android source code 中 （參見這裡）、 是幾百萬台機器的一部分。

弱點

其中一個發現的 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。

弱點

這個 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 使用者可能都是用這份程式碼。

弱點

code review 沒有找出什麼明顯的弱點。 entropy collector 倚賴 thread 遞增計數器， 但是有別於 GNU Classpath，它會確保執行時間的最小值。 得到的結果圖形被很均勻地填滿。

The Legion of Bouncy Castle

以某些角度來看，這個 library 跟其他的不太一樣， 因為它只是一個非常綜合性的加密演算法 library。 它有多個 SecureRandom 的替代品。 BouncyCastle 的 entropy collector 可以在兩種模式下運作： 快速模式與慢速模式，random 輸出會使用不同的 byte 數。

弱點

跟 OpenJDK 相同，Bouncy Castle 的 SecureRandom 替代品 （DigestRandomGenerator）也沒有什麼明顯的 bug。 相反地 VMPCRandomGenerator 已知是有弱點的。 entropy collector 在兩種模式下都可以把圖形填滿的很均勻。

快速模式的圖：

慢速模式的圖：

總結

上頭這些實作的限制、不可設定的 internal state 是十分有趣的。 幾乎所有實作都靠 SHA-1 作為 hash 函數。 因此，在 key 產生器大於 160 bit 時似乎沒啥用處。 只有 Apache Harmony 是用 512bit 的 internal state， 但是它的程式有問題。 blog 的文章省略了很多細節與統計數據，只是為了提供一個快速而簡單的評論。 如果你有興趣知道更詳細的內容，麻煩請去讀完整的論文。