Linux 核心專題: 亂數產生器研究

執行人: teresasa0731
解說錄影

補上解說錄影

Reviewed by `popo8712`

你在使用 add_device_randomness 函數將隨機數據注入熵池時，提到了它在系統啟動期間直接將數據注入到 ChaCha20 DRNG，而非 input_pool。請問在這種設計中，如果系統啟動期間發生了並發請求，如何確保這些隨機數據的安全性和正確性？

在 ChaCha20 DRNG 尚未初始化之前，若是有調用亂數的情況，系統會回傳帶有 GRND_INSECURE flag 的 "best effort" 隨機數，提醒使用者這個是尚未被驗證"足夠安全"的。

Reviewed by `weihsinyeh`

問題一 : 在測試亂數品質中，是怎麼知道亂數品質好，是因為 FIPS 140-2 successes: 1000，但這個 successes 跟 failures 是怎麼被歸類的?

此處 FIPS 140-2 測試主要是針對整個 RNG 架構的安全性評估，關於亂數的品質可以用統計方式分析，像是透過卡方檢定來測試生成的亂數是否為均勻分佈(實作測試補在內文)。

Reviewed by `w96086123`

在文中並沒有提到亂數品質的判定標準，只有出現成功與否？

同上，已補上判定的實驗～

Reviewed by `randyuncle`

現在的 /dev/char/random.c 中的 _mix_pool_byte() 實作已被改成使用 brake2s。想請問一下，這樣的改變會使得 /dev/random 和 /dev/urandom 的亂數取用更快或更慢？和 LFSR 相比，此實作的改變是否使得產出的亂數品質更好？

BLAKE2s 在 Linux 5.17 取代原本熵池中 SHA-1 的 hash function，根據 pull request ，更新過後的熵池提取速度加快了 131%，除此之外 SHA-1 存在的碰撞問題也相應緩解。

Reviewed by `jujuegg`

你提到 PRNG 必須具備高度的安全性，以防止對其內部狀態的預測或重構。那在程式碼以及內部架構完全公開的情況下，這個亂數產生器有哪部分是像加密演算法中的密鑰一樣隱藏起來的?

這個部份在廣泛定義上是指初始的 seed 需要被保護，而以 Linux 核心討論的 RNG 來說，在一開始引入隨機數加入熵池、透過 /dev/random 和 /dev/urandom 提取亂數都有加密的操作，確保不會從生成的亂數回推內部狀態。

任務說明

Linux 核心的若干子系統依賴亂數產生器，而隨著版本的更迭，核心逐步改進其亂數產生器的品質，本專案探究 Linux 核心的相關考量。

TODO: PRNG 的考量因素

TODO: check https://hackmd.io/@jhan1998/HJaVavfXu#PRNG and https://hackmd.io/@PHD/ryiV8GolP#Linear-Feedback-Shift-Register-LFSR

PRNG(pseudo random number generator)

實際上的真亂數產生器是很難在軟體上實現的，所以希望設計一個偽亂數產生器生成 Pseudo random number(PRN)，其 Entropy 呈 uniform distribution 的分佈，雖然是透過確定性
方式產生（所謂的不確定性我認為可以引用說法： known unknown 來解釋），但在使用的數量範圍內足夠隨機。
PRNG 是起於一個隨機種子啟動初始狀態，他的特點是同一個初始狀態生成的序列都是相同的（可再現性），其循環週期定義為 "無重複前綴長度在所有起始狀態中的最大值"，像是以下舉例的線性反饋移位暫存器（LFSR）的周期通常是 2n−1（內部狀態為 n 位）。

考量因素

週期長度 (Period Length):
理想的 PRNG 應該具有足夠長的週期，以確保在使不會遇到重複的數據，像是 Mersenne Twister (MT19937) 的週期長度達到
$2^{19937} - 1$ ，足以應付大多數日常應用（當然片段的品質還需要再做評估）。
均勻分布 (Uniform Distribution) & 獨立性 (Independence):
確保 PRNG 生成的數字符合基本的分佈且互相無相依性，可以通過一些統計測試來驗證，像是卡方檢定、 K-S test 或是自相關檢驗 (Autocorrelation Test) 都是常見的測試方法。
生成速度:
在需要大量隨機數的場景下，生成速度會是 PRNG 的性能瓶頸之一，所以在複雜的計算與運算速度上需要考量應用場景而做權衡。
再現性 (Reproducibility):
考量到偽隨機數是需要被實驗與測試驗證的，那初始狀態用的 seed 與後續生成的序列必須相應，以確保這些測試是有效的。
安全性 (Security):
此點主要針對在密碼學上的應用，PRNG 必須具備高度的安全性，以防止對其內部狀態的預測或重構。
所謂安全的 PRNG 通常會稱為 CSPRNG (Cryptographically Secure PRNG)，具備不可預測、前後向安全性（就是攻擊者獲得內部狀態下，無法推出過去產生/未來生成的資訊），當然也有基本的抗攻擊能力，所以 CSPRNG 通常會加上 hash function 以及一些加密算法來保護內部狀態，如下討論的 Linux 核心的 /dev/random 及 /dev/urandom 就是 CSPRNG 的實現。

在現代密碼學上的討論都是基於算法等流程都是公開的，所有加密的安全性都是源自密鑰，同理在隨機數生成也可以用這個方式解釋，就算內部架構被公開，都應該保持其安全性。
標準測試:
有公正標準的測試才能夠量化的證明是一個"好的 PRNG"，像是 NIST SP 800-22 或 Diehard 測試套件都是常見的標準測試。

TODO: 評估 xoroshiro128+ PRNG

解釋 xoroshiro128+ 的原理
對照〈Scrambled Linear Pseudorandom Number Generators〉論文，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？

$\to$ 搭配閱讀: 不亂的「亂數」

/dev/random 計算隨機數時用到 entropy pool，此池的 entropy 總數的多少直接影響所有隨機數的計算快慢。所以會在開機時，儘量收集足夠的 entropy。(此問題的 systemd-random-seed 執行階段間過長應該就是因為 entropy pool 準備的比較慢導致的)

正常情況下預設使用的 /dev/random 是比較慢的，它是從驅動程式、環境噪音等地方收集 entropy ，然後彙總到 entropy pool。它通常在啟動時阻塞，直到收集到足夠的 entropy ，然後永久解除阻塞。

`xoroshiro128+` 原理

從名字可以看出與 xor, rotate, shift, rotate 有關，此 PRNG 是 LFSR 的子集，透過簡單的移位/旋轉的線性變換，來提高生成偽隨機數的運算速度。

source code

注意書寫規範：

使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
注意看程式碼規範的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。

已修正。

static inline uint64_t rotl(const uint64_t x, int k)
{
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2];

uint64_t next(void)
{
    const uint64_t s0 = s[0];
    uint64_t s1 = s[1];
    const uint64_t result = s0 + s1;

    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);  // a, b
    s[1] = rotl(s1, 37);                    // c

    return result;
}

每次存取隨機數是將當前狀態的 s[0] + s[1] 輸出，並將當前狀態進行更新為:

s[0] = (s[0] 左旋轉 24 位) xor (s[0] xor s[1]) xor (s[1] 左移 16 位)
s[0] = (s[1] xor s[0]) 左旋轉 37 位

補上更多原理和其亂度的討論。

取出 xoroshiro.c 相關的程式碼後撰寫腳本測試，設計先取出 /dev/random 的真亂數作為初始化 seed ，之後跑大量測試並紀錄生成的亂數，在進行卡方檢定來確定其是否為均勻分佈，測試結果如下：

test case = 1000000000, alpha = 0.05
Chi-square statistic: 1.0188214046719955e-06
P-value: 1.0

可以看到 p 值大於顯著性水平 α（這裡設置為 0.05），也就是生成亂數非常接近於預期的均勻分佈，且一般來說接近 1.0 時，我們無法拒絕虛無假設（即觀察數據與期望值相符）。

與 `/dev/random` 及 `/dev/urandom` 比較

ksort 的 xoro 核心模組 xoro_mod.c

設計比較 linux 的 RNG 與 PRNG 的 xoroshiro+ 在生成速度上的差異，可以看到後者在生成量達到 1000000 Bytes 時速度明顯下降，因前者是直接在熵池存取亂數，而後者需要實際進入循環計算來取得，當存取量增加時會影響到效能;另外考量到 linux 的 RNG 設計有硬體加速與經過系統呼叫存取，效率上可能會較純軟體模擬的 xoroshiro+ 高。

Length (Bytes)  /dev/random (ms)        /dev/urandom (ms)       xoroshiro++ (ms)
100             0.006199                0.001669                0.016928
1000            0.005960                0.006676                0.044823
10000           0.053644                0.043154                0.413179
100000          0.557899                0.476837                4.511356
1000000         4.826546                4.900694                51.253557

TODO: 闡述 Linux RNG 架構

參見 Documentation and Analysis of the Linux Random Number Generator，應涵蓋到 section 3.9

Linux‑RNG 在 drivers/char/random.c 中實作，透過裝置檔案 /dev/random 和 /dev/urandom 以及 getrandom sys.call 為使用者空間應用程式提供對其隨機數產生器的存取。此外提供 API get_random_bytes ，允許其他 Linux 核心元件獲取隨機數。

The Linux operating system kernel offers via the device files/dev/randomand /dev/urandom as well as the getrandom system call access to its random number generator for user space applications. In addition, the Linux-RNG offers in-kernel interfaces to allow other Linux kernel components to obtain random numbers.

其中 /dev/random 和 /dev/urandom 最大的不同是隨機數的取得方式， /dev/random 是從熵池中不重複挑選組成隨機數並回傳，但若熵池中的隨機性資料不足時，會阻塞等待 (I/O block) 直到有足夠的熵可供使用，通常用在高度隨機性，如驗身份認證或密鑰生成等場合。而相對來說 /dev/urandom 則以一種安全的加密算法（如 chacha20 等）來補充熵池中不足的隨機性資料，適用於一般的亂數生成需求。
但隨著版本更迭，目前兩個方式在實際使用上已經相差無幾，詳細演變參考自 Uniting the Linux random-number devices

解釋 entropy pool 的運作原理和其安全考量。

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 Pool)

發生硬體事件後，Linux‑RNG 會進行熵估計，並將事件時間＆值收集並壓縮混合到 4096 bits 的熵池，而所謂硬體事件的熵可以指的是系統、驅動程式等來源的環境噪音。
這些"熵"透過 (1) 混合函數加入熵池，以 LFSR-based 的狀態轉換函數進行資料處理，再以 (2) Blake2s-based 雜湊函數，透過 /dev/random 、 /dev/urandom 或是系統呼叫 get_random_bytes 來輸出亂數，後者系統呼叫是預設回傳 /dev/urandom 中的隨機數，可以透過 flag 更改。

int getrandom(void *buf, size_t buflen, unsigned int flags);

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 位元，其儲存結構如下：

// the pointer to the static data block that holds the actual
static u32 input_pool_data[POOL_WORDS] __latent_entropy;    
random pool.
static struct {
...
u16 add_ptr;         // the index to the current pool word that was accessed
u16 input_rotate;    // the input data rotation value
int entropy_count;   // the entropy estimator value 
}

Entropy Estimator

熵估計器的值永遠不會大於對應的熵池的大小，因為熵池最多可以容納與其大小一樣多的熵，也不能全部小於零。另外必須使用與其比較或處理的值相同的維度進行處理。

當對具有分數位的整數值進行操作時，整數值將保持不變。
取得目前位元總數中的熵量: right-shift 3 bits
以位元組為單位處理熵池的熵內容: right-shift 6 bits (8bits=1byte)

環境噪音來源 Noise Source

NDRNG

以硬體生成的真隨機亂數角度來看，是透過物理過程而非程式碼計算實現的，像是設備運作的熱力學噪音、量子現象、製程差異等都在理論上算是不可預測的 (non-deterministic) 。

在實體設備上：智慧卡、特殊電路、硬體安全模組 (HSM) 等。
常規硬體的事件行為：人機互動（e.g.滑鼠移動或鍵盤打字）、硬碟或中斷。
利用 CPU 功能：time-based 噪音源、使用 RDRAND 等硬體噪音源的 CPU 指令

in Linux RNG

在 Linux 核心中則根據 drivers/char/random.c 中可以看到主要來自輸入裝置發出的中斷，將其混合後加入熵池。

void add_device_randomness(const void *buf, size_t len);
void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy, bool sleep_after);
void add_bootloader_randomness(const void *buf, size_t len);
void add_vmfork_randomness(const void *unique_vm_id, size_t len);
void add_interrupt_randomness(int irq);
void add_input_randomness(unsigned int type, unsigned int code, unsigned int value);
void add_disk_randomness(struct gendisk *disk);

其中 add_device_randomness 函數目的是在設備驅動程序初始化期間向 input_pool 提供隨機數據。在系統啟動期間， ChaCha20 偽隨機數生成器（DRNG）在初次設置種子之前，add_device_randomness 接收到的所有數據都會直接注入到 ChaCha20 DRNG 而非 input_pool。這樣能確保在系統啟動期間，從 /dev/urandom 獲取的隨機數流能夠充分利用這些注入的隨機數，以提升品質和安全性。

另外在 Linux 3.16 之前的版本透過工具 rng-tools 將硬體產生的亂數加入到熵池，後來在版本更動 v3.17 commit be4000b 中提到 kernel 引入 add_hwgenerator_randomness 後會直接將硬體亂數加入 dev/random

`add_early_randomness()`

此函式用於在啟動階段時為系統提供熵源 (entropy source) ，一開始是選擇呼叫 add_device_randomness() 來添加隨機數到系統熵池中，但為了考慮到透過此方式加入須經過認證 (credit) ，故在 commit db516da 中提到改成用 add_hwgenerator_randomness 來在初始化時期可以直接取用隨機數而非等待其他執行緒啟動驗證。

注意用語，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary

已修改！

後來版本更新加入專門蒐集系統熵源的核心執行緒 (rngd) 後，考量到函式冗餘性與可能造成死鎖的情況，在最近提出的 commit 67ec8cd 中移除該函式。

LFSR

LFSR(Linear-feedback shift register) 作為移位暫存器，其輸出會取決於先前的輸入狀態，可以用不同的 XOR 運算與暫存器組合，簡單來說會給予一個初始狀態，經過線性運算後得到的結果輪轉成為下一輪的 MSB。

在 linux 中的 tools/perf/bench/numa.c 可以看到基礎的 LFSR 實作，在多處理器系統中引入隨機性，避免在多核心系統執行多個工作時，頻繁切換同步機制而影響效能。

注意用語。什麼是「高同步性」？

已修改！

/drivers/char/random.c

而在熵池應用中， LFSR 用於將新值插入熵池，並選擇適當的多項式 "stir" 熵池內隨機數後 "twist"，可以看到每次扭轉三位以降低計算成本。

static void _mix_pool_bytes(struct entropy_store *r, const void *in,
int nbytes)
{
    ...
    input_rotate = input_pool.input_rotate;
    i = input_pool.add_ptr;
    /* mix one byte at a time to simplify size handling and churn
    faster */
    while (nbytes--) {
        w = rol32(*bytes++, input_rotate);
        i = (i - 1) & POOL_WORDMASK;
        /* XOR in the various taps */
        w ^= input_pool_data[i];
        w ^= input_pool_data[(i + POOL_TAP1) & POOL_WORDMASK];
        w ^= input_pool_data[(i + POOL_TAP2) & POOL_WORDMASK];
        w ^= input_pool_data[(i + POOL_TAP3) & POOL_WORDMASK];
        w ^= input_pool_data[(i + POOL_TAP4) & POOL_WORDMASK];
        w ^= input_pool_data[(i + POOL_TAP5) & POOL_WORDMASK];
        /* Mix the result back in with a twist */
        input_pool_data[i] = (w >> 3) ^ twist_table[w & 7];
        /*
        * Normally, we add 7 bits of rotation to the pool.
        * At the beginning of the pool, add an extra 7 bits
        * rotation, so that successive passes spread the
        * input bits across the pool evenly.
        */
        input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
    }
    input_pool.input_rotate = input_rotate;
    input_pool.add_ptr = i;
}

在 while-loop 中循環處理輸入的 n bytes 隨機數，

依熵池結構讀取的 rotate 將當前字串 left-shift ，並確保指針位置在熵池範圍內
分別在 6 個位置 (tap = 104,76,51,25,1) 進行 XOR 運算，改變熵池的狀態
位移 3 位後再與 twist_table 進行 XOR 運算，引入更多隨機性
根據當前指針位置更新旋轉的位數後，進入下一輪混合

mix_bytes 中選擇的 tap 位置除了考量到均勻分佈，以及將最後 tap 位置設定在 1 來加速 twist 外，還有隨機性上的考量，在程式碼中提及參考了 CRC-32 多項式與類似 twisted GFSR 的架構，另外論文 "The Linux Pseudorandom Number Generator Revisited" 也有相關的數學分析，此處尚待閱讀理解。

ChaCha20 DRNG

ChaCha20 是一種對稱串流加密算法，使用 128 位的密鑰和 64 位的初始向量（IV）作為輸入，生成 256 位的密鑰流，然後與明文進行 XOR 運算加密。解密只需再次將密鑰流與密文 XOR 運算即可。

linux/lib/crypto/chacha.c

struct crng_state {
u32 state[16];
unsigned long init_time;
...
};

左邊列顯示 ChaCha20 DRNG 的內部狀態為 512 位元，但其中只有 256 位元充滿隨機資料。
第二列則是初始化階段的狀態，常數使用 16 位元組字串擴展成 32 位元組 "Expand 32-byte k" ，而密鑰、計數器等則是從熵池中提取。
每次輸出區塊產生後會更新計數器與 seed time ，下一次 chacha20 區塊操作會與先前略為不同，進而形成加密的比特流(bit-stream)。

Linux RNG 的安全性考量

為了確保熵池內的隨機數品質，透過 "credit" 的機制來管理與紀錄有多少 entropy 添加到熵池中，以及這些 entropy 對熵池狀態的影響，例如來自用戶空間或是外部源輸入的 entropy 是需要被驗證的（前面有提到來自 hwgenerator 的隨機數是可以直接視為高品質的）。
另外討論到熵池的熵計數，當熵池加入新熵時，需要考慮到新熵可能會覆蓋原有的熵，根據理論的熵值更新公式：

entropy \leftarrow entropy + (pool_size - entropy) \cdot (1 - \exp (- \frac{add\_entropy}{pool\_size}))

可以看出新熵對現有熵值的貢獻是漸進並趨於理想值。
根據以上，credit_entropy_bits()設計是為了安全並精準控制熵計數，並且確保每次循環增加最多為 pool_size/2防止過度增減或是無窮循環影響到生成的隨機數品質。

TODO: 評估 Raspberry Pi 4 RNG

Hardware-based Random Number Generators
Raspberry Pi的硬體亂數產生器
註: rpi4 來不及到貨，先以 rpi3b+ 做實驗

實驗環境： Raspberry 3B+

$ cat /proc/version
Linux version 6.6.35-v8+ (dom@buildbot) (aarch64-linux-gnu-gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0, GNU ld (GNU Binutils for Ubuntu) 2.38)

$ cat /proc/cpuinfo
Revision        : a020d3
Serial          : 00000000829480eb
Model           : Raspberry Pi 3 Model B Plus Rev 1.3

硬體隨機數產生器 `/dev/hwrng`

安裝套件與測試工具

$ sudo modprobe bcm2835-rng
$ sudo apt-get install rng-tools

根據 Raspberry Pi 官方文件可以知道 Broadcom BCM2835 芯片系列最早用於 Raspberry Pi Model B 和 Model A，而後續版本雖然使用同系列不同 SoC 版本，但基於相容性考量，仍以最早的 bcm2835-rng 來命名模組;另在 Linux 中，驅動硬體隨機數產生器（hwrng）通過註冊 bcm2835-rng 到 drivers/char/hw_random/core.c 中來供應應用層和熵池使用。

測試亂數產生器品質

$ sudo cat /dev/hwrng | rngtest -c 1000
rngtest 2.2
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 1000
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=15.733; avg=831.626; max=6510416.667)Kibits/s
rngtest: FIPS tests speed: (min=20.487; avg=28.684; max=43.448)Mibits/s
rngtest: Program run time: 25456939 microseconds

讀取 /dev/hwrng 來使用工具 rngtest 執行 1000 次測試，可以看到在 FIPS 140-2 測試中表現良好。

測試亂數生成時間

撰寫腳本來分別量測軟體隨機數產生器與硬體隨機數產生器的耗時。

因測試時發現 bcm2835-rng 是內建模組無法禁用，故目前未找到方法測試引入 hwrng 對熵池效率的影響。

重新編譯器 Linux 核心，對比該組態開啟與否的表現。

腳本

#!/bin/bash

start=$(date +%s%N)
dd if=/dev/urandom of=/dev/null bs=1 count=10000000 status=none
end=$(date +%s%N)
elapsed=$((end-start))

echo "/dev/urandom - Elapsed time: $((elapsed / 1000000)) ms"

計算讀取約 10 MiB 的隨機數所需時間，並透過一次性取用大量隨機數來檢查 /dev/random 是否相較於使用 /dev/urandom 耗用更多時間。

測試結果

$ ./test_rng.sh
/dev/urandom - Elapsed time: 34121 ms
/dev/random - Elapsed time: 35534 ms
/dev/hwrng - Elapsed time: 85343 ms

透過大量讀取隨機數後測試結果如上，可以看到 /dev/urandom 用時確實較少。根據以上，為了證明 /dev/random 在熵池不足時的阻塞情況，另外量測讀取不同數量的隨機數耗時比較，並將時間繪製如下：
rng_test

在取用數量達到約 620KiB 時 /dev/random 耗時遽增，推測此處出現熵池不足而等待的情況。

從程式碼實作的角度去解讀上述實驗。

FIPS 140-2 測試

官方文件：
FIPS PUB 140-2 SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC
MODULES

目前FIPS 140-2的規範是國際上業界所公認的密碼學模組標準，透過多項要求來驗證整個亂數生成器模組的安全性。
其訂定密碼學模組的四種安全等級，從最低要求的第一級到最高階的第四級，皆須滿足安全要件，包括加密模組的資訊流與控制界面、授權的角色/服務之身分驗證與金鑰管理、模組的有限狀態模型、物理性安全與電磁干擾、運行環境、自我測試規範與設計文件等 11 項。