天天看點
傳回

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

基礎介紹

文中若有不當之處還請各位大佬多多點評

我的部落格：https://whoamianony.top/

公衆号：WHOAMIAnony

随機數并不随機

首先需要聲明的是，計算機不會産生絕對随機的随機數，計算機隻能産生“僞随機數”。其實絕對随機的随機數隻是一種理想的随機數，即使計算機怎樣發展，它也不會産生一串絕對随機的随機數。計算機隻能生成相對的随機數，即僞随機數。

僞随機數并不是假随機數，這裡的“僞”是有規律的意思，就是計算機産生的僞随機數既是随機的又是有規律的。 怎樣了解呢？産生的僞随機數有時遵守一定的規律，有時不遵守任何規律；僞随機數有一部分遵守一定的規律；另一部分不遵守任何規律。比如“世上沒有兩片形狀完全相同的樹葉”，這正是點到了事物的特性，即随機性，但是每種樹的葉子都有近似的形狀，這正是事物的共性，即規律性。從這個角度講，你大概就會接受這樣的事實了：計算機隻能産生僞随機數而不能産生絕對随機的随機數。

真随機數和僞随機數的概念

  • 真随機數發生器：英文為：true random number generators ，簡稱為：TRNGs，是利用不可預知的實體方式來産生的随機數。
  • 僞随機數發生器：英文為：pseudo-random number generators ，簡稱為：PRNGs，是計算機利用一定的算法來産生的。

PHP的僞随機數有關的兩個函數

mt_rand()

mt_rand() 函數使用 Mersenne Twister 算法傳回随機整數（随機數生成器）。

文法

說明

如果沒有提供可選參數 min 和 max，mt_rand() 傳回 0 到 RAND_MAX 之間的僞随機數。

很多老的 libc 的随機數發生器具有一些不确定和未知的特性而且很慢。PHP 的 rand() 函數預設使用 libc 随機數發生器。mt_rand() 函數是非正式用來替換它的。該函數用了 Mersenne Twister 中已知的特性作為随機數發生器，它可以産生随機數值的平均速度比 libc 提供的 rand() 快四倍。

例子

在本例中，我們會傳回一些随機數：

<?php
echo(mt_rand());
echo(mt_rand());
echo(mt_rand(10,100));
?>

輸出類似：

3150906288
513289678
35

mt_srand()

mt_srand() 播種 Mersenne Twister 随機數生成器。

文法

參數 seed：規定播種值、用 seed 來給随機數發生器播種。

例子

在本例中，我們将播種随機數生成器：

<?php
mt_srand(mktime());
echo(mt_rand());
?>

輸出類似：

這段代碼的意思是，是通過mt_srand分發seed種子，然後種子有了後，才能靠mt_rand()來生成随機數。

為什麼随機數要用種子播種，對種子的了解

首先我們要知道，計算機不能産生絕對的随機數，隻能産生僞随機數。僞就是有規律的意思。僞随機數就是說計算機産生的随機數是有規律的。那麼計算機是怎麼産生随機數的？當然是通過算法，這個算法是有映射關系的，如我放進1，他會出來一個特定的數

這是某個系統的随機數算法。

我們可以把這個算法看成是一個黑盒子，你放進一個數，就會出來一個特定的數，并把這個數當做下一次的種子在放進去。在這裡，你第一次放進去的數就是随機數種子，也就是說随機種子（Random Seed）就是這些随機數的初始值。

系統實作随機數是把目前的系統時間放進去，每次時間都不一樣，是以可以實作每次出來的數都不一樣。如果你每次都放進一樣的種子，生成的随機數列就是一樣的了。

注釋：自 PHP 4.2.0 起，不再需要用 srand() 或 mt_srand() 函數給随機數發生器播種了，随機數生成器可以自動播種，是以沒有必要使用該函數。

PHP僞随機數安全

可預測性

mt_rand()并不是一個真随機數生成函數，實際上絕大多數程式設計語言中的随機數函數生成的都是僞随機數。

僞随機是由可确定的函數，通過一個種子（常用時鐘）播種，産生的僞随機數。這意味着：如果知道了種子，或者已經産生的随機數，或者已知産生的随機數的一部分，都可能獲得接下來随機數序列的資訊，知道了你的随機數序列，就可以确定你的種子值。 （可預測性）。

簡單假設一下 mt_rand()内部生成随機數的函數為: rand = seed+(i10) 其中 seed 是随機數種子， i 表示第幾次調用這個随機數函數。當我們同時知道 i 和 rand 兩個值的時候，就能很容易的算出seed的值來。比如 rand=21 , i=2 代入函數 21=seed+(210) 就能得到 seed=1 。是不是很簡單，當我們拿到seed之後，就能計算出當 i 為任意值時候的 rand 的值了。

PHP的自動播種

我們已經知道每一次mt_rand()被調用都會根據seed和目前調用的次數i來計算出一個僞随機數。而且seed是自動播種的：

Note: 自 PHP 4.2.0 起，不再需要用 srand() 或 mt_srand() 給随機數發生器播種，因為現在是由系統自動完成的。

那麼問題就來了，到底系統自動完成播種是在什麼時候，如果每次調用mt_rand()都會自動播種那麼破解seed也就沒意義了。

不幸的是，php每次調用mt_rand()函數時，都會先檢查是否已經播種。如果已經播種就直接産生随機數，否則調用php_mt_srand來播種。也就是說每個php cgi程序期間，隻有第一次調用mt_rand()會自動播種。接下來都會根據這個第一次播種的種子來生成随機數。

php_mt_seed

我們已經知道随機數的生成是依賴特定的函數，上面曾經假設為 rand = seed+(i*10) 。對于這樣一個簡單的函數，我們當然可以直接計算出一組解來，但 mt_rand() 實際使用的函數可是相當複雜且無法逆運算的。有效的破解方法其實是窮舉所有的種子并根據枚舉出的種子生成随機數序列再跟已知的随機數序列做比對來驗證種子是否正确。php_mt_seed就是這麼一個工具，它的速度非常快，跑完2^32位seed也就幾分鐘。 它可以根據單次mt_rand()的輸出結果直接爆破出可能的種子，當然也可以爆破類似mt_rand(1,100)這樣限定了MIN MAX輸出的種子。

很多國内開發者在程式中使用了mt_rand()來生成安全令牌、核心加解密key等等導緻嚴重的安全問題。

用到的是爆破，已經有寫好的C腳本了。

這裡簡單的介紹下這個腳本咋用

種子爆破工具——php_mt_seed

下載下傳位址：http://www.openwall.com/php_mt_seed

它可以根據單次mt_rand()的輸出結果直接爆破出可能的種子，當然也可以爆破類似mt_rand(1,100)這樣限定了MIN MAX輸出的種子。

下載下傳後，執行如下指令編譯生成：

kali下，進入目錄，make

具體使用

php_mt_seed的用法可能很簡單，也可能很複雜，具體取決于用例的詳細資訊。這是一個最簡單的用法示例：

首先使用PHP生成一個“随機”數字，例如：

$ php5 -r 'mt_srand(1234567890); echo mt_rand(),"\n";'
1328851649

然後運作cracker（在此示例中，在與上面用于建構的系統相同的系統上）：

$ time ./php_mt_seed 1328851649
    Pattern: EXACT
    Version: 3.0.7 to 5.2.0
    Found 0, trying 0xfc000000 - 0xffffffff, speed 16261.0 Mseeds/s
    Version: 5.2.1+
    Found 0, trying 0x1e000000 - 0x1fffffff, speed 91.8 Mseeds/s
    seed = 0x1fd65f9a = 534142874 (PHP 7.1.0+)
    Found 1, trying 0x26000000 - 0x27ffffff, speed 91.9 Mseeds/s
    seed = 0x273a3517 = 658126103 (PHP 5.2.1 to 7.0.x; HHVM)
    Found 2, trying 0x48000000 - 0x49ffffff, speed 91.9 Mseeds/s
    seed = 0x499602d2 = 1234567890 (PHP 5.2.1 to 7.0.x; HHVM)
    seed = 0x499602d2 = 1234567890 (PHP 7.1.0+)
    Found 4, trying 0xfe000000 - 0xffffffff, speed 91.9 Mseeds/s
    Found 4
   
    real    0m47.028s
    user    6m15.211s
    sys     0m0.015s

php_mt_seed首先搜尋舊版PHP 3.0.7至5.2.0的種子，通常隻需一秒鐘即可完成。然後，它會同時搜尋PHP 5.2.1至7.0.x和PHP 7.1.0+的種子，這需要一段時間。

下面示範一個複雜的用法示例：

php_mt_seed 在其指令行上可以有1、2、4或更多的數字。數字指定了對 mt_rand()函數輸出的限制，如mt_rand(0,50)。

當僅使用一個數字調用時，這是mt_rand函數的第一個用來爆破種子的輸出。

當用2個數字調用時，它們是第一個mt_rand()的輸出應落入的範圍（最小和最大，按該順序）。

當用4個數字調用時，前2個給出第一個mt_rand()輸出的界限，後兩個2給出傳遞到mt_rand()的範圍。

執行個體——[GWCTF 2019]枯燥的抽獎

進入題目

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

是個猜字元的遊戲，并且告訴你了一部分值：

utP4yKDDVV

，估計是已知産生的随機數的一部分。

F12 檢視源碼，發現check.php：

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

進入check.php，給出了你源碼：

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

可知源碼的邏輯是，先産生一個0到999999999之間的随機整數作為随機數種子被mt_srand()函數播種。然後在

$str_long1

這一長串字元串中用mt_rand()來随機取出20個字元構成字元串

$str

并輸出

$str

的前十位給你。最後，将你猜的輸入的值拼上給你的值與

$str

進行強類型比較，對比成功則傳回flag。可見，如果最後能POST正确的20位，獲得flag。那麼關鍵就是，要根據給你的10位密碼，反推出mt_srand的種子是什麼，進而依葫蘆畫瓢構造私鑰。

接下來我們用php_mt_seed工具對随機數種子進行爆破。

先用腳本将僞随機數轉換成php_mt_seed可以識别的資料格式：

str1='abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
str2='utP4yKDDVV'
str3 = str1[::-1]     # 倒序
length = len(str2)    # 10
res=''
for i in range(len(str2)):
    for j in range(len(str1)):
        if str2[i] == str1[j]:
            res+=str(j)+' '+str(j)+' '+'0'+' '+str(len(str1)-1)+' '
            break
print res

// 前兩個str(j)代表第一個mt_rand()輸出的界限，後兩個參數0和str(len(str1)-1)表示傳遞到 mt_rand()的範圍為0到61
PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

得到：

将這一串拿到工具裡去使用

爆破出僞随機數和php版本

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

爆破的到種子為：206396968，如下改寫源碼，便可以得到完整的字元串

<?php
mt_srand(206396968);

$str_long1 = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
$str='';
$len1=20;
for ( $i = 0; $i < $len1; $i++ ){
    $str.=substr($str_long1, mt_rand(0, strlen($str_long1) - 1), 1);       
}
echo $str;

?>
PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎

拿着得到得字元轉送出即可得到flag：

PHP的僞随機數爆破基礎介紹執行個體——[GWCTF 2019]枯燥的抽獎
CTF-Web 字元串 算法 安全
上一篇: Python:urllib2子產品Handler處理器 和 自定義OpenerHandler處理器 和 自定義Opener
下一篇: 利用堆棧進行表達式求值

繼續閱讀