Documentation and Analysis of the Linux Random Number Generator
Documentation and Analysis of the Linux Random Number Generator
Big picture of Linux Random Number Generator
Linux‑RNG 在 drivers/char/random.c
中實作,透過裝置檔案系統 /dev/random
和 /dev/urandom
以及 getrandom
sys.call 為使用者空間應用程式提供對其隨機數產生器的存取。此外提供API get_random_bytes
,允許其他 Linux 核心元件獲取隨機數。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
NDRNG Noise Source:
- 在實體設備上:智慧卡、特殊電路、硬體安全模組 (HSM) 等。
- 常規硬體的事件行為:人機互動(e.g.滑鼠移動或鍵盤打字)、硬碟或中斷。
- 利用 CPU 功能:time-based 噪音源、使用 RDRAND 等硬體噪音源的 CPU 指令
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Linux‑RNG
Linux‑RNG 架構
- 發生硬體事件後,Linux‑RNG 會進行熵估計
- 將事件時間&值混合到 4096 bits 的熵池 (input_pool)
- 熵池 (input_pool)
- 指的是保存隨機資料的儲存區域
- 資料透過確定性輸入和 LFSR-based 的狀態轉換函數進行處理,再以 Blake2s-based 雜湊函數輸出
- 由熵池維護的資料處理是完全確定性的
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- input_pool 是收集並壓縮來自硬體事件的熵的熵池。此熵池的大小為 4,096 位元。
- ChaCha20 DRNG 的內部狀態為 512 位元。然而,只有 256 位元(ChaCha20 狀態的關鍵部分)充滿了隨機資料,其從 input_pool 取得其種子數據,並可透過以下方式存取:
- 透過
/dev/urandom
、/dev/random
或 getrandom
系統呼叫從使用者空間獲取
- 透過
get_random_bytes
函數從核心空間取得。
structure
Entropy Pool State Transition Function
LFSR 用於將新值插入熵池,並選擇適當的多項式 "stir" 熵池內隨機數後 "twist",可以看到在 twist 中一次扭轉三位以降低計算成本。
- 選擇指向將要更新的熵池字的索引。
- 將步驟 1 中的 4 個位元組與以下內容進行 XOR 運算:
- 步驟 1 所取得的索引值所指向的目前熵池字
- 由此索引加上 LFSR 多項式的第一個 tap 所指向的目前熵池字
- 透過將輸入與步驟 2 中多項式的抽頭指向的 5 個不同熵池字進行 XOR 運算計算得到的 u32 值,再透過與 twist_table 的一個值進行 XOR 運算進一步攪拌。這項操作使用雙射操作來排列字的前三位。這個想法是透過「扭曲」將這三位混合。
- 步驟 3 計算所得的值替換步驟 1 中索引指向的熵池字的先前值,成為新的值。
- 重複步驟 1,直到所有輸入位元組都混合到熵池值中。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Entropy Estimator
熵估計器的值永遠不會大於對應的熵池的大小,因為熵池最多可以容納與其大小一樣多的熵,也不能全部小於零。另外必須使用與其比較或處理的值相同的維度進行處理。
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- 當對具有分數位的整數值進行操作時,整數值將保持不變。
- 取得目前位元總數中的熵量: right-shift 3 bits
- 以位元組為單位處理熵池的熵內容: right-shift 6 bits (8bits=1byte)
Entropy Pool Output Function
ChaCha20 DRNG
structure
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Interfaces to Linux-RNG
structure
The callback functions for /dev/random
random_poll
- read: 當 ChaCha20 DRNG 已經 fully seeded 表明有足夠的熵可用時,內核會喚醒輪詢進程,以允許它們通過單獨的調用獲取數據。
- 允許用戶空間 asynchronously poll /dev/random 以避免在讀取 /dev/random 時出現阻塞行為
- random_poll 會保持成功返回直到下次重新啟動
- write: 當entropy estimator低於給定閾值表明可用熵不足時,核心會喚醒等待寫輪詢的進程。
Read and Write Operation
dev/random:使用該裝置檔案存取隨機數產生器時,會呼叫random_read
的讀取函數。該函數會阻止呼叫者,直到 ChaCha20 DRNG fully seeded。一旦發生這種情況,就會產生與下面概述的 /dev/urandom
相同的隨機數。
Entropy Collection
將目前事件的事件值與前一事件的事件值進行比較。如果兩個事件值相同(例如,滑鼠向一個方向移動兩步或按同一鍵兩次),則該事件將被丟棄。否則,事件將會被加入到 input_pool 中。
add_interrupt_randomness
- 必須滿足中斷次數和過期時間這兩個條件。
- ast_pool 的最後一次讀取的時間戳設定為目前時間。
- ast_pool 的內容會混合到 input_pool 中。
- 將接收的中斷數重設為零,以進行步驟 1 中的初始條件檢查。
- 將 input_pool 的熵估計器增加 1 – i CPU 硬體隨機數產生器存在時,熵估計量增加 2。
add_disk_randomness
add_device_randomness
add_device_randomness
的目標是在裝置驅動程式初始化期間向 input_pool 提供資料,在啟動期間,ChaCha20 DRNG 被視為first seeded 之前, add_device_randomness
接收到的所有資料都將注入 ChaCha20 DRNG 而不是 input_pool。這將保證在 boot 期間源自 /dev/urandom
的資料流能夠從輸入資料中獲益。
add_hwgenerator_randomness
用於核心硬體 RNG 裝置驅動程式,其介面框架將獲得的熵透過mix_pool_bytes
直接混合到 input_pool 中。

硬體 RNG 驅動程式框架實作了一個核心線程,該線程不斷從註冊的硬體 RNG 設備讀取數據,並使用從硬體設備獲取的數據呼叫add_hwgenerator_randomness
介面函數,如果 input_pool 的熵估計器中的值全部低於變數random_write_wakeup_bits
設定的閾值,則允許呼叫者將資料送入 Linux‑
RNG。