2龍好早以前說，能不能把這篇文章翻了，我拿到文章一看，有點意思，但是很多東西我不清楚，然后在維基百科上看了一些關于Entropy（熵）和PRNG（偽隨機生成器）和RNG（隨機數生成器）的文章，很拖沓，坑卻越挖越大，今天打算跟隨原文的過程的說一下這篇文章所說到的事情，但是不是完整的翻譯。
直到我看完之后才想起來，這個事情Superhei曾經在Discuz的代碼里也提出過：http://www.80vul.com/dzvul/sodb/14/sodb-2008-14.txt，也是：http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/。
文章里出現一個Entropy（熵），我這里引用一下wikipeida中文的一段話來解釋下這個東西。
英語文本數據流的熵比較低，因為英語很容易讀懂，也就是說很容易被預測。即便我們不知道下一段英語文字是什么內容，但是我們能很容易地預測，比如，字母e總是比 字母z多，或者qu字母組合的可能性總是超過q與任何其它字母的組合。如果未經壓縮，一段英文文本的每個字母需要8個比特來編碼，但是實際上英文文本的熵 大概只有4.7比特。
接下來是文章，總體來說：能力有限，如存在錯誤，請多多指出。 注：文章內token,salt,nonce，PRNG,RNG這些縮寫我只注了一次，而seed有些地方寫成了隨機數種子，有些地方寫了seed。
隨機值在PHP中很常見，在框架內或者類庫中你都可能看到用它生成的token（令牌），salt（鹽值），這些都被當做一種輸入放到對應的函數內，隨機數很常見很常用。
生成一個范圍內的隨機數，一個隨機的用以加密的密匙，一個不可以被猜測到的可用于驗證用戶權鑒的字符，生成一個sessionid什么的，我們都會用到隨機。
但是這些使用中都存在一個隱患，如果攻擊者可以預測你用RNG（隨機數生成器）或者PRNG（偽隨機數生成器）生成的隨機結果會是什么，那他也差不多能知道你最后生成token是什么，或者nonce（一次性驗證的憑證）是什么，所以，好的隨機數必須是不可以被預測到得隨機數。
但是作者認為，在PHP內存在兩個關于隨機數的弱點：
1，信息泄露。
2，熵池不足。
信息泄露的意思是，在隨機數生成過程中能泄露過程中的一些東西，例如偽隨機數種子的值，有了這個隨機數的結果也可以更簡單的獲取到。
熵池不足的意思是，隨機數初始的內部狀態或者隨機數種子的組成的成分就很有限，大概就在一個范圍內，PRNG生成的結果也就在一個可能猜到的范圍內。
兩個對PHP編寫的代碼來說，都不算好消息。
很多人都搞不清楚什么是隨機值，可能有些人覺得用unique產生的值和其他隨機數比的話，前者更安全一點，后者可能很容易就獲取到了，我實際上不認同這個。
關于隨機數的討論應該基于目的，如果你期望使用的隨機數是不可被預測的，重要的，那你的隨機數就應該不可被預測。
影響隨機數的強度的是生成用的熵，熵簡單來說是到字節的不確定性，舉個例子，我拿出個2進制的字符，它就包含0和1，如果攻擊者什么都不知道，好，我們的熵是2，如果攻擊者知道結果一定是1，我們的熵就是0比特了，因為能否預測這個需求是和不確定性相反的。
這個在PHP里比較明顯，mt_rand生成的隨機值永遠只是數字，它不輸出字符串，特殊字符什么的，所以攻擊者只需要嘗試數字，如果我們使用/dev/random來生成隨機數會比前者的熵池更大。
而且，mt_rand不是真的隨機數生成器，它是PRNG（偽隨機生成器），采取的是一種被稱為梅森旋轉的算法，用以生成高質量的偽隨機數，它會采用隨機數種子來生成隨機數的值。
你可以本地測試一下下面的代碼
#!php
mt_srand(1361152757.2);
for ($i=1; $i < 25; $i++) {
echo mt_rand(), PHP_EOL;
}
產生的隨機數看上去是不是很正常，也沒什么問題，你再運行一次你會發現結果還是一樣的，這不保證在PHP的版本變化后還是如此，但是在過去流行的版本里，是這樣的。 如果攻擊者可以獲取隨機數種子，他就可以預測用梅森旋轉算法生成的mt_rand的值。 這個特性讓隨機數種子變成了能否預測的關鍵。
PHP使用的三種PRNG算法，所以如果攻擊者可以獲取隨機數種子，那么就知道對應算法的結果。
1，線行同余方法 例如：lcg_value
2，梅森旋轉算法 例如 mt_rand
3，原生C語言支持的函數 例如rand
以上實際上在內部函數也復用了，例如array_rand，uniqid，也就是說攻擊者如果可以跑一遍所有可能的隨機數種子，那么以上所有的值它都可以獲取。
為了生成可靠的隨機數，PHP也使用外置的熵池，比如openssl_pseudo_random_bytes() 使用Linux系統上的/dev/urandom，或者mcrypt_create_iv()使用了Windows上使用了CSPRNG（Windows密碼安全偽隨機數生成器），但是這取決于OpenSSL和Mcrypt擴展在PHP里沒有開。 /dev/urandom其實也是個PRNG，但是它使用/dev/random 產生高熵池難以預測的種子。
這些告訴我們：
如果需要不被預測的隨機數，你的選擇是使用openssl_pseudo_random_bytes()，你可以退而設置MCRYPT_DEV_URANDOM使用mcrypt_create_iv()，你也可以直接讀/dev/urandom，如果失敗了，你也沒有別的選擇了，你只能反復使用現有的隨機數或者密匙進行混合。
理論就是這樣，我們來看看我們如何利用知識去實踐。
在實踐中，PHP的PRNG都用于各種非常重要的地方。
openssl_pseudo_random_bytes()函數只在PHP5.3提供，并且在5.3.4以上的windows上才有，PHP也是在那個版本在Windows上支持mcrypt_create_iv()函數，基于此Windows只支持MCRYPT_RAND影響著rand函數的值，所以5.3之前的有很多應用可能沒有較強的隨機數生成器。
想想我們在線的服務，使用了下面的代碼：
$token = hash('sha512', mt_rand());
好，一步一步來黑了它。 該脆弱應用的特性： 這不是詳細的特性，脆弱特性可以和這份列表有不少出入。
這是很重要的，每個php進程的種子只會生成一次，如果我們可以對一個PHP進程發送兩次請求，PHP會使用同一個種子。
為了猜測隨機數種子，我們需要一個PHP生成的隨機數，無論是mt_rand的結果還是再進行了一下哈希運算，最主要的是要和第二步我們猜測下一個隨機數在同一個進程。
如果你在攻擊一個開源應用你是可以知道這些的，或者收買一個雇員以獲取私有的代碼，或者前雇員，或者，你自己完全的猜測它的算法，有些token生成算法是簡單又粗暴，有可能是mt_rand()或者md5一下mt_rand()，我在這里是假設使用SHA512，接下來我們會看到它也解決不了問題。
我們的攻擊非常簡單，我們要發送兩個請求到PHP，服務器會keepalive并且接受第二個請求，接下來我們叫它們為請求A和請求B，獲取A請求中的token，比如CSRF token，比如密碼重置token，這個token將被嚴刑拷打，直到它供出它媽是誰，哦，不，它的seed是什么。
B請求更有趣了，讓我們提交一個請求去重置管理員的密碼，邏輯呢？邏輯是它們是同一個媽生的，哦不，同一個seed生成的(A請求的同一個進程，我們keepalive了）。我們解開A請求里的token的seed的時候，我們就可以用這個seed生成管理員重置密碼的鏈接，并且點擊它。
以下條件要在這次攻擊里滿足：
1，使用請求A去獲取一個token，這個token我們可以推出seed的值。
2，使用請求B去擁有一個同樣算法生成后放在應用數據庫內用以修改密碼的的token。
3，破解SHA512獲取這個隨機數被服務器加密之前的數是什么。
4，使用這個隨機數我們去暴力破解出來這個隨機數的seed是什么。
5，使用這個seed生成一個用以密碼重設的token值。
6，使用我們的密碼重設token去重設管理員的密碼
7，獲取管理員的賬戶玩一下。
好，我們開始吧
一步一步的來
我目標的token和密碼重設的token都依賴于mt_rand的輸出，在我們的例子里，這是一個虛構的應用，它生成的token都是使用統一方案生成的，我們只需要找到CRSF的token并且存在哪里一會兒用。
這個請求就是很簡單的提交一個密碼重設的表單。這個token會存在數據庫里發給用戶一個email，這個token要能算出來，如果服務器的特性符合要求，這個請求會和請求A是同一個PHP進程處理的，因此能確認兩個請求都使用了mt_rand去調用了同一個隨機數種子。
SHA512開發者們都比較敬畏，因為它是SHA-2家族的算法里目前最大的數字。但是無論如何來說，我們的目標使用它存在一個缺陷 - “隨機值都只是數字” （也就是說它的不確定性或者說熵池，太弱了）。如果你去看mt_getrandmax()的返回值，你會發現mt_rand()返回的最大的數字也只是20億1千4百7十萬種組合。這種級別的數字你還是可以暴力破解的。
別這么快就聽信我的話。如果你有最近代的低階GPU。當我打算找出一個hash的值的時候，我選擇專業的hashcat-lite。這個版本的hashcat是目前最快的暴力破解的工具之一，你可以在這里下載：http://hashcat.net/oclhashcat-lite/
Generate a token using the method I earlier prescribed using the following script: 用下面的腳本生成一個我剛才說到的token：
#!php
$rand = mt_rand();
echo "Random Number: ", $rand, PHP_EOL;
$token = hash('sha512', $rand);
echo "Token: ", $token, PHP_EOL;
這模仿我們從請求A能獲取的那個SHA512后的hash，并且接下來我們把它放在hashcat里跑一下。
./oclHashcat-lite64 -m1700 --pw-min=1 --pw-max=10 -1?d -o ./seed.txt <SHA512 Hash> ?d?d?d?d?d?d?d?d?d?d
這是所有的參數的意思
-m1700: 定義hash的算法，1700的意思就是SHA512
-pw-min=1 定義hash加密之前的數字的最小的長度
-pw-max=10 定義hash加密之前數字的最大的長度
-1?d 定義我們自定義的字典是僅包含數字
-o ./seed.txt 輸出的文件會被重寫，別忘了不會有輸出在屏幕上。
?d?d?d?d?d?d?d?d?d?d: 表示格式，最長10位，全是數字。
如果一切順利，你的GPU也沒有爆炸，hashcat幾分鐘內會找出隨機數hash之前的原文是什么，是的，是幾分鐘，我先前花了一些時間去解釋熵池是怎么工作的，然后你現在就可以在練習中明白，mt_rand()產生結果的可能性是如此的少，以至于SHA512加密后我的所有結果我們很短一段時間就計算結束了，使用hash去處理mt_rand的結果幾乎沒有什么用。
關于hashcat的一些其他用法可以參考之前drops的文章：GPU破解神器Hashcat使用簡介
我們上面說到了，SHA512后的數字解出來只需要幾分鐘。這會告訴你接下來干什么，通過這個隨機數，我們接下來要在跑一個腳本來暴力破解，這個工具叫做php_mt_seed。這是一個小工具，它的作用是取出mt_rand的結果并且暴力破解定位哪些隨機數種子會生成那個我們剛才獲取的隨機數，你可以在http://download.openwall.net/pub/projects/php_mt_seed/下載對應的版本，如果出現問題的話，你可以選擇一個老一點的版本（最新的版本在我在虛擬環境里測試的時候有些問題）。
./php_mt_seed <對應的隨機數>
這要花比算SHA512要長的時間。它燒的是CPU，不過它會在CPU上嘗試任何可能的隨機數種子，這將會出現一個或多個隨機數種子（也就是這些隨機數種子都能產生這個數字）。
在上一步，我們暴力破解獲取這個隨機數的種子，因為mt_rand調用的種子數不多，這里有另外一個使用python編寫的暴力破解mt_rand的工具：https://github.com/GeorgeArgyros/Snowflake
Assuming that the total calls to mt_rand() across both Request A and Request B were just two, you can now start predicting the token with the candidate seeds using:
假設在請求A和請求B中調用mt_rand的最大次數是兩次，接下來你可以使用我們獲取的seed們（有候選的）來預測下一個token是什么。
#!php
function predict($seed) {
/**
* Seed the PRNG
*/
mt_srand($seed);
/**
* Skip the Request A call to the function
*/
mt_rand();
/**
* Predict and return the Request B generated token
*/
$token = hash('sha512', mt_rand());
return $token;
}
這個函數會返回對應的seed返回的下一個token。
Entropy 熵 http://en.wikipedia.org/wiki/Entropy http://zh.wikipedia.org/wiki/%E7%86%B5_%28%E4%BF%A1%E6%81%AF%E8%AE%BA%29
梅森旋轉算法： http://en.wikipedia.org/wiki/Mersenne_twister http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95
PRNG 偽隨機數生成器 http://en.wikipedia.org/wiki/PRNG
RNG 隨機數生成器 http://en.wikipedia.org/wiki/Random_number_generator http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8