# Linux 核心專題: 亂數產生器研究
> 執行人: h0w726
>
[解說錄影](https://www.youtube.com/watch?v=-sBup5Asuj0)

### Reviewed by `fcu-D0812998`
> 簡介 Liunx 如何產生亂數

應該是 Linux。
### Reviewed by `Hande1004`

解釋文中提到的 LFSR 及 blake2s 為何?
## 任務簡述
研讀 [2024 年報告](https://hackmd.io/@sysprog/BkhlALt8A) (包含解說錄影和問答)，紀錄你的認知和疑慮，並重新整理在本頁面，隨後繼續完成去年的 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.6

## TODO: 闡述 Linux RNG 架構
### 簡介 Linux 如何產生亂數
Linux 核心會從硬體事件收集熵，這些硬體事件包括中斷、裝置驅動、硬碟的讀寫操作等等
這些熵會被收集到熵池，也就是圖中的 `input_pool` , chacha20 為 DRNG，會從熵池中取得種子並產生亂數，可以透過使用者層級的 `/dev/random` 以及 `/dev/urandom` 或是核心層級的 `get_random_bytes` 取得亂數。
`/dev/random` 以及 `/dev/urandom` 的差異為，`/dev/random` 只有在熵池或 chacha20 取得足夠多的熵，才能取得隨機數，否則會阻塞直到熵足夠。

其中中斷是與其他一般硬體事件有區別的部分，正常情況下，每秒會觸發數百到數千個中斷，若每次中斷都直接將數據寫入 `input_pool` 會造成系統效能的降低，為了快速返回中斷，Linux 核心使用 `fast_pool` 專門處理從中斷事件收集的熵，`fast_pool` 滿足兩個條件才會將數據混入 `input_pool`

* 接收到 64 個以上中斷
* 距離上一次混入經過一秒以上

其中 `fast_pool` 的結構如下

struct fast_pool {
	unsigned long pool[4];
	unsigned long last;
	unsigned int count;
	struct timer_list mix;
};

`count` 紀錄已接收的中斷數量，`last` 紀錄上一次混入的時間
每個 CPU 都有一個 `fast_pool` ，處理其所接收到的中斷。當發生中斷時，會根據高解析度時間戳、jiffies 以及中斷編號更新 `fast_pool`，直到滿足條件才混入熵池。
## 熵池
熵池是一塊儲存隨機數據的記憶體區塊，大小為 128 個 words ，在 [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) 提及的 Linux 5.17 版本中，數據混入熵池前，會使用 LFSR 使數據更亂才混入。但是在最新的 Linux 版本中，因為效能及安全問題，LFSR 已經被棄用，取而代之的是使用 blake2s 雜湊函數，根據 [pull request](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/drivers/char/random.c?id=6e8ec2552c7d13991148e551e3325a624d73fac6)，這樣的改動更安全且在 i7-11850H CPU上，可以達到 225% 的效能提升。
### LFSR
LFSR 全名為 Linear feedback shift register，從名字可以得知其與移位和回饋有關


[source](https://hackmd.io/@PHD/ryiV8GolP#Linear-Feedback-Shift-Register-LFSR)
* 清除最右邊的 bit，並輸出到 keystream
* 將剩下的 bits 全部向右移動一位
* 根據選擇的 tap ，取出其對應位置的值進行 XOR 或其他操作，並放入最左邊。

混入熵池使用到 LFSR 的過程如下圖

假如目前要更新熵池裡第 40 個 word ，首先會將目前輸入的 byte 擴展為 32 bits，接著將其與目前熵池中第 40 + tap 的 word 做 XOR，這 5 個 tap 的值為 (104,76,51,25,1)，得到的值為 `w` ，接著會把 `w` 右移 3 跟 `twist_table [ w & 7 ]`做 XOR 增加隨機性，`twisc_table` 裡為 CRC32 常數。

### blake2s
blake2s 雜湊函數，在目前的 Linux 亂數產生器中，作為熵混入熵池前，以及熵池要輸出種子給 chacha20 DRNG 使用時，用來增加隨機性的方法。