iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 3
1
Security

CTF 的三十道陰影系列 第 3

Day3: [Crypto] Pseudo-Random Number Generator

前言

昨天最後稍微提到交大程式安全作業-猜數字遊戲和 PRNG,今天就順著繼續這個主題把他講清楚說明白,順便爭取一點時間想之後的文章.....QQ

Pseudo-Random Number Generator

為什麼不使用真正的亂數 ?

首先要知道一件事情:

目前靠純軟體無法取得真正的亂數

目前電腦發展至今,目前的行為都是由人類所定義好,因此要在電腦上取得亂數廣義來說只有兩種方式:

  1. 亂數表
  2. 透過 PRNG 取得亂數

但亂數表必須占用儲存空間,不可能擁有無限的儲存空間,因此理論上如果能取得夠多的亂數將亂數表給用完,下一個亂數就可以被預測;而 PRNG 是透過演算法來產生亂數,因此只要被知道是用哪一個演算法和必要條件 (seed),也一樣可以預測接下來的亂數

現在如果需要在電腦上取得真正的亂數,一定要透過硬體的輔助,至於硬體取得的亂數是不是真正的亂數 (True Random Number),問題就相當複雜,需要牽扯 entropy 的定義和各種物理知識,像是量子力學,甚至會探討到一些哲學問題,有興趣的可以參考 random.org 的說明

先假定透過透過硬體可以取得 True Random Number,但每次需要跟硬體溝通的 latency 就一定比不上從 PRNG 取得的速度,因此實際上還是會搭配 PRNG 使用,如昨天所提到的,比較簡單的做法就是透過 /dev/urandom 取得 seed 之後再餵給 srand 使用

Cryptographically Secure Pseudo-Random Number Generator

這邊引用 Allen Chou 大大在 HITCON 2014 <應用密碼學入門 >提及的亂數特性:

  • 隨機性:看起來夠亂,沒有規律,所有數字分佈平均
  • 不可預測性:無法從之前的亂數數列猜出下一個亂數的值
  • 不可重複性:以後不可能再有同樣的數列

一般來說 PRNG 取得的亂數要能滿足 隨機性 (正式的名稱是 統計學偽隨機性),簡單的說是產生夠多的亂數後,二進制的 1 和 0 數量會接近相等,滿足此條件人類體感上就會覺得是足夠隨機的亂數

CSPRNG 除了上述條件外,還必須滿足 不可預測性,以下是 wiki 的定義:

給定隨機樣本的一部分和隨機演算法,不能有效的演算出隨機樣本的剩餘部分

但無論是 PRNG 或 CSPRNG 都無法達到 不可重複性,只有 TRNG 才滿足三者的條件,BTW,要應用在密碼學上只有 CSPRNG 或 TRNG 得到的亂數才足夠安全

常使用的 PRNG

  1. Linear Congruential Generator (LCG)
    • glibc rand 的實作採用此演算法,速度快但強度很弱
    • NOT CSPRNG
  2. Mersenne Twister (MT)
    • 目前很多程式語言 Random 模組的實作方式,有不錯的速度且足夠大的 pool,適用於大部分情況
    • python: Random
    • php: mt_rand()
      • php 的 rand() 使用系統的預設函式,Linux 底下會等同於 glibc rand
    • NOT CSPRNG
  3. Fortuna
    • FreeBSD 用以實作 /dev/urandom
  4. arc4random
    • 從 stream cipher 的 key 取得亂數
      • iv 透過 kernel 從 hardware 上取得 noise
      • 早期基於 rc4,但現在改用 ChaCha20 實作
  5. /dev/urandom
    • /dev/urandom/dev/random 兩者都會從 hardware 取得亂數 entropy
    • 最大的差別是 /dev/random 會在 entropy 不夠時 block 住,等到足夠亂時才能得到亂數,/dev/urandom 則是會重複使用 entropy
    • 根據 man random(7) 的描述,只有在產生 secret key 時才建議讀取 /dev/random
    • Linux 4.8 之後改用 ChaCha20 實作/dev/urandom

小結

雖然說 PRNG 不夠安全,但 CSPRNG 和 TRNG 的使用成本太高,因此大家實務上還是會透過後者產生 seed 後,再結合 PRNG 使用,只要清楚了解自己使用了哪一套 PRNG 以及使用亂數的情境,就可以避免被預測到亂數而產生資安隱患

0x02: 30C3CTF 2013 Number 100 Guess

這道題是 2013 年參加 30C3CTF 初賽解的題目,也是人生中第一次解出作業或 Wargame 外的 CTF 的題目 XD
題目也是猜數字,但不只要猜中數字,還要連續猜對 10 次才行,是典型的預測 PRNG 的題目,詳細 write up 可以參考我的 blog: https://ddaa.tw/30c3ctf_2013_number_100_guess.html

題目是用 python 寫的 server,程式邏輯大致如下:

r = random.Random()
r.seed(os.urandom(16))

while 1:
  answer = str(r.getrandbits(64)
	guess = c.recv()
	if guess != answer:
	  guess_right = 0
	  c.sendall("Nope, that was wrong, correct would have been %s...\n" % answer)
	  continue
	guess_right += 1
	if guess_right < guess_limit:
	  c.sendall("Yes! That was correct, awesome...\n")
	  continue
c.sendall("You did it! The flag is: %s" % flag)

python 的 Random.getrandbits() 是使用 Mersenne Twister,透過 seed 初始化後會產生 624 個 state,每個 state 代表一個 32 bit 的數字,並可以產生出一個 32 bit 的亂數

因為題目是用 while loop 無止盡的執行,而且每次都會把 random 取得的結果印出來,因此我們可以收集足夠多的亂數來反推 MT 亂數產生過程的 state,具體作法如下:

  1. 隨便猜錯一個數字,將 answer 拆成前半 a1 和後半 a2,分別是兩次 state 產生出來的亂數
  2. 用 a1, a2 反推出 state 代表的結果 s1, s2
  3. 重複 312 次,共得到 624 個state
  4. 透過 state 計算之後會產生的亂數,至此我們已經可以預測接下來所有的答案

延伸閱讀


上一篇
Day2: [Crypto] CTF 題型分類
下一篇
Day4: [Pwn] Buffer Overflow (CWE-120)
系列文
CTF 的三十道陰影31

尚未有邦友留言

立即登入留言