## Linux 核心專題: 亂數產生器研究
> 執行人: teresasa0731
> [解說錄影](https://youtu.be/05N54zvABpE)
:::danger
補上解說錄影
:::
### 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()`](https://github.com/torvalds/linux/blob/master/drivers/char/random.c#L628C1-L630C39) 實作已被改成使用 brake2s。想請問一下，這樣的改變會使得 `/dev/random` 和 `/dev/urandom` 的亂數取用更快或更慢？和 LFSR 相比，此實作的改變是否使得產出的亂數品質更好？
> BLAKE2s 在 Linux 5.17 取代原本熵池中 SHA-1 的 hash function，根據 [pull request](https://lore.kernel.org/lkml/20220106235920.995517-1-Jason@zx2c4.com/) ，更新過後的熵池提取速度加快了 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 位）。
### 考量因素
1. 週期長度 (Period Length):
理想的 PRNG 應該具有足夠長的週期，以確保在使不會遇到重複的數據，像是 Mersenne Twister (MT19937) 的週期長度達到 $2^{19937}−1$，足以應付大多數日常應用（當然片段的品質還需要再做評估）。
2. 均勻分布 (Uniform Distribution) & 獨立性 (Independence):
確保 PRNG 生成的數字符合基本的分佈且互相無相依性，可以通過一些統計測試來驗證，像是卡方檢定、 K-S test 或是自相關檢驗 (Autocorrelation Test) 都是常見的測試方法。
3. 生成速度:
在需要大量隨機數的場景下，生成速度會是 PRNG 的性能瓶頸之一，所以在複雜的計算與運算速度上需要考量應用場景而做權衡。
4. 再現性 (Reproducibility):
考量到偽隨機數是需要被實驗與測試驗證的，那初始狀態用的 seed 與後續生成的序列必須相應，以確保這些測試是有效的。
5. 安全性 (Security):
此點主要針對在密碼學上的應用，PRNG 必須具備高度的安全性，以防止對其**內部狀態的預測或重構**。
所謂安全的 PRNG 通常會稱為 CSPRNG (Cryptographically Secure PRNG)，具備不可預測、前後向安全性（就是攻擊者獲得內部狀態下，無法推出過去產生/未來生成的資訊），當然也有基本的抗攻擊能力，所以 CSPRNG 通常會加上 hash function 以及一些加密算法來保護內部狀態，如下討論的 Linux 核心的 `/dev/random` 及 `/dev/urandom` 就是 CSPRNG 的實現。
>在現代密碼學上的討論都是基於算法等流程都是公開的，所有加密的安全性都是**源自密鑰**，同理在隨機數生成也可以用這個方式解釋，就算內部架構被公開，都應該保持其安全性。
6. 標準測試:
有公正標準的測試才能夠量化的證明是一個"好的 PRNG"，像是 NIST SP 800-22 或 Diehard 測試套件都是常見的標準測試。
## TODO: 評估 xoroshiro128+ PRNG
> 解釋 `xoroshiro128+` 的原理
> 對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)
`/dev/random` 計算隨機數時用到 entropy pool，此池的 entropy 總數的多少直接影響所有隨機數的計算快慢。所以會在開機時，儘量收集足夠的 entropy。(此問題的 systemd-random-seed 執行階段間過長應該就是因為 entropy pool 準備的比較慢導致的)
正常情況下預設使用的 `/dev/random` 是比較慢的，它是從驅動程式、環境噪音等地方收集 entropy ，然後彙總到 entropy pool。 它通常在啟動時阻塞，直到收集到足夠的 entropy ，然後永久解除阻塞。
### `xoroshiro128+` 原理
從名字可以看出與 **xo**r, **ro**tate, **shi**ft, **ro**tate 有關，此 PRNG 是 LFSR 的子集，透過簡單的移位/旋轉的線性變換，來提高生成偽隨機數的運算速度。
> [source code](https://prng.di.unimi.it/xoroshiro128plus.c)
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
> 已修正。
:::
```c
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 位
:::danger
補上更多原理和其亂度的討論。
:::
取出 `xoroshiro.c` 相關的程式碼後撰寫腳本測試，設計先取出 `/dev/random` 的真亂數作為初始化 seed ，之後跑大量測試並紀錄生成的亂數，在進行卡方檢定來確定其是否為均勻分佈，測試結果如下：
```shell
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](https://github.com/sysprog21/ksort/blob/master/xoro_mod.c)
設計比較 linux 的 RNG 與 PRNG 的 `xoroshiro+` 在生成速度上的差異，可以看到後者在生成量達到 1000000 Bytes 時速度明顯下降，因前者是直接在熵池存取亂數，而後者需要實際進入循環計算來取得，當存取量增加時會影響到效能;另外考量到 linux 的 RNG 設計有硬體加速與經過系統呼叫存取，效率上可能會較純軟體模擬的 `xoroshiro+` 高。
```shell
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](https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN_V4_5.pdf?__blob=publicationFile&v=9)，應涵蓋到 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/random `and `/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](https://lwn.net/Articles/884875/)
:::danger
解釋 entropy pool 的運作原理和其安全考量。
:::
### 熵池 (Entropy Pool)
發生硬體事件後，Linux‑RNG 會進行熵估計，並將事件時間＆值收集並壓縮混合到 4096 bits 的熵池，而所謂硬體事件的熵可以指的是系統、驅動程式等來源的環境噪音。
這些"熵"透過 (1) 混合函數加入熵池，以 LFSR-based 的狀態轉換函數進行資料處理，再以 (2) Blake2s-based 雜湊函數，透過 `/dev/random` 、 `/dev/urandom` 或是系統呼叫 `get_random_bytes` 來輸出亂數，後者系統呼叫是預設回傳 `/dev/urandom` 中的隨機數，可以透過 `flag` 更改。
```c
int getrandom(void *buf, size_t buflen, unsigned int flags);
```
`input_pool` 指的是一個保存隨機資料的儲存區域，此熵池的大小為 4,096 位元，其儲存結構如下：
```c
// 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) 。
1. 在實體設備上：智慧卡、特殊電路、硬體安全模組 (HSM) 等。
2. 常規硬體的事件行為：人機互動（e.g.滑鼠移動或鍵盤打字）、硬碟或中斷。
3. 利用 CPU 功能：time-based 噪音源、使用 RDRAND 等硬體噪音源的 CPU 指令
##### in Linux RNG
在 Linux 核心中則根據 [drivers/char/random.c](https://github.com/torvalds/linux/blob/master/drivers/char/random.c) 中可以看到主要來自**輸入裝置發出的中斷**，將其混合後加入熵池。
```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](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=be4000bc4644d027c519b6361f5ae3bbfc52c347) 中提到 kernel 引入 `add_hwgenerator_randomness` 後會直接將硬體亂數加入 `dev/random`
##### `add_early_randomness()`
此函式用於在啟動階段時為系統提供熵源 (entropy source) ，一開始是選擇呼叫 `add_device_randomness()` 來添加隨機數到系統熵池中，但為了考慮到透過此方式加入須經過**認證 (credit)** ，故在 [commit db516da](https://github.com/torvalds/linux/commit/db516da95ce458f0cab5e7ae2db93fd821484d7d) 中提到改成用 `add_hwgenerator_randomness` 來在初始化時期**可以直接取用隨機數**而非等待其他執行緒啟動驗證。
:::danger
注意用語，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary
> 已修改！
:::
後來版本更新加入專門蒐集系統熵源的核心執行緒 (rngd) 後，考量到函式冗餘性與可能造成死鎖的情況，在最近提出的 [commit 67ec8cd](https://github.com/torvalds/linux/blob/master/drivers/char/hw_random/core.c) 中移除該函式。
### LFSR
LFSR(Linear-feedback shift register) 作為移位暫存器，其輸出會取決於先前的輸入狀態，可以用不同的 XOR 運算與暫存器組合，簡單來說會給予一個初始狀態，經過線性運算後得到的結果輪轉成為下一輪的 MSB。
在 linux 中的 [tools/perf/bench/numa.c](https://elixir.bootlin.com/linux/latest/source/tools/perf/bench/numa.c#L790) 可以看到基礎的 LFSR 實作，在多處理器系統中引入隨機性，避免在多核心系統執行多個工作時，頻繁切換同步機制而影響效能。
:::danger
注意用語。什麼是「高同步性」？
> 已修改！
:::
> [/drivers/char/random.c](https://elixir.bootlin.com/linux/latest/source/drivers/char/random.c#L638)
而在熵池應用中， LFSR 用於將新值插入熵池，並選擇適當的多項式 "stir" 熵池內隨機數後 "twist"，可以看到每次扭轉**三位**以降低計算成本。
```c
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 隨機數，
1. 依熵池結構讀取的 `rotate` 將當前字串 left-shift ，並確保指針位置在熵池範圍內
2. 分別在 6 個位置 (tap = 104,76,51,25,1) 進行 XOR 運算，改變熵池的狀態
3. 位移 3 位後再與 `twist_table` 進行 XOR 運算，引入更多隨機性
4. 根據當前指針位置更新旋轉的位數後，進入下一輪混合
mix_bytes 中選擇的 tap 位置除了考量到**均勻分佈**，以及將最後 tap 位置設定在 1 來**加速 twist** 外，還有隨機性上的考量，在程式碼中提及參考了 CRC-32 多項式與類似 twisted GFSR 的架構，另外論文 ["The Linux Pseudorandom Number Generator Revisited"](http://eprint.iacr.org/2012/251.pdf) 也有相關的數學分析，此處尚待閱讀理解。
### ChaCha20 DRNG
ChaCha20 是一種**對稱串流加密算法**，使用 128 位的密鑰和 64 位的初始向量（IV）作為輸入，生成 256 位的密鑰流，然後與明文進行 XOR 運算加密。解密只需再次將密鑰流與密文 XOR 運算即可。
> [linux/lib/crypto/chacha.c](https://github.com/torvalds/linux/blob/master/lib/crypto/chacha.c)
```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 的隨機數是可以直接視為高品質的）。
另外討論到熵池的熵計數，當熵池加入新熵時，需要考慮到新熵可能會覆蓋原有的熵，根據理論的熵值更新公式：
$\text{entropy} \leftarrow \text{entropy} + (\text{pool_size} - \text{entropy}) \cdot \left( 1 - \exp\left(-\frac{\text{add\_entropy}}{\text{pool\_size}}\right) \right)$
可以看出新熵對現有熵值的貢獻是漸進並趨於理想值。
根據以上，`credit_entropy_bits()`設計是為了安全並精準控制熵計數，並且確保每次循環增加最多為 `pool_size/2`防止過度增減或是無窮循環影響到生成的隨機數品質。
## TODO: 評估 Raspberry Pi 4 RNG
> Hardware-based Random Number Generators
> [Raspberry Pi的硬體亂數產生器](https://yehnan.blogspot.com/2013/08/raspberry-pi.html)
> 註: rpi4 來不及到貨，先以 rpi3b+ 做實驗
##### 實驗環境： Raspberry 3B+
```shell
$ 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`
##### 安裝套件與測試工具
```shell
$ sudo modprobe bcm2835-rng
$ sudo apt-get install rng-tools
```
根據 [Raspberry Pi 官方文件](https://www.raspberrypi.com/documentation/computers/raspberry-pi.html)可以知道 Broadcom BCM2835 芯片系列最早用於 Raspberry Pi Model B 和 Model A，而後續版本雖然使用同系列不同 SoC 版本，但基於相容性考量，仍以最早的 `bcm2835-rng` 來命名模組;另在 Linux 中，驅動硬體隨機數產生器（hwrng）通過註冊 `bcm2835-rng` 到 `drivers/char/hw_random/core.c ` 中來供應應用層和熵池使用。
```graphviz
digraph G {
rankdir=TB;
rngd_rngtest [label="rngd/rngtest"];
hwrng [label="/dev/hwrng",shape = "rectangle"];
hwrngcore [label="hwrngcore",shape = "rectangle"];
hwrng_driver [label="hwrng driver",shape = "rectangle"];
rngd_rngtest -> hwrng -> hwrngcore -> hwrng_driver;
}
```
### 測試亂數產生器品質
```shell
$ 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 對熵池效率的影響。
:::danger
重新編譯器 Linux 核心，對比該組態開啟與否的表現。
:::
##### 腳本
```bash
#!/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` 耗用更多時間。
##### 測試結果
```shell
$ ./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` 在熵池不足時的阻塞情況，另外量測讀取不同數量的隨機數耗時比較，並將時間繪製如下：
在取用數量達到約 620KiB 時 `/dev/random` 耗時遽增，推測此處出現熵池不足而等待的情況。
:::danger
從程式碼實作的角度去解讀上述實驗。
:::
### FIPS 140-2 測試
> 官方文件：
> [FIPS PUB 140-2 SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC
MODULES](https://csrc.nist.gov/files/pubs/fips/140-2/upd2/final/docs/fips1402.pdf)
目前FIPS 140-2的規範是國際上業界所公認的**密碼學模組標準**，透過多項要求來驗證**整個亂數生成器模組的安全性**。
其訂定密碼學模組的四種安全等級，從最低要求的第一級到最高階的第四級，皆須滿足安全要件，包括加密模組的資訊流與控制界面、授權的角色/服務之身分驗證與金鑰管理、模組的有限狀態模型、物理性安全與電磁干擾、運行環境、自我測試規範與設計文件等 11 項。
Sign in with Wallet
Connect another wallet