Linux kernel

初探 Linux kernel 亂數產生器 – random generator

在產生 key 或者進行一些安全應用時, 常會有需要 “亂數” 的使用需求.

user space 有下列四種介面可以跟 Linux kernel 取得亂數.

 


1. /dev/random (blocking random source) 位於 drivers/char/random.c

Linux kernel 收集來自系統, 驅動程式或其它來源的環境噪音, 並轉換成 entropy 放入 entropy pool 中. 再由 entropy 生成所謂的 “亂數”

  • entropy 為描述系統混亂無序程度的物理量 [3].

哪些環境噪音才能被轉化成 entropy 呢 ? 根據 drivers/char/random.c 來看, 主要為輸入裝置發出中斷的時間, IRQ 的 cycle counters, 硬碟讀寫的時間 (注意 – 不包括 flash based 的儲存裝置, ex: SSD)

2016-10-05_201843.png

 

此介面主要適用於對安全需求比較高的應用. (例: 產生金鑰). 若 entropy 不夠時, I/O operation 會被 block 住, 直到收集了足夠的 entropy.

以產生 GPG key 為例, 若 entropy 不夠會顯示下列訊息. 這時就要趕緊生出足夠的 entropy, 否則 process 會一直處於等待 I/O 的狀態.

**We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
Not enough random bytes available. Please do some other work to give
the OS a chance to collect more entropy! (Need 210 more bytes)**

2. /dev/urandom (non-blocking random source) 位於 drivers/char/random.c

這介面會重覆使用 entropy 以產生亂數, 所以不會發生 entropy 不夠而導致 I/O block 的情況. 但相對產生的亂數也不夠 “隨機”.

所以 kernel 有額外設計 add_device_randomness 這個函式, 透過加入一些資料到 pool 中進行初始化 (非增加 entropy), 避免在重覆應用 entropy 的前提下產生相同或者類似的亂數. 但即便如此, 出來的亂數在使用上來說還是不夠安全.

2016-10-05_204953.png

 

此介面主要適用於對安全需求比較低的應用. (例: 不須具備安全性需求的遊戲).

 

3. system call  (kernel 3.17 之後開始支援) [7] – 位於 drivers/char/random.c

使用 system call  getrandom() 可以取得亂數值.

getrandom() 定義在 drivers/char/random.c 由下圖可得知, 預設是回傳 /dev/urandom 中的 entropy.

2016-10-06_104949.png

getrandom() 函式宣告如下

[code language=”c”]
#include <linux/random.h>

int getrandom(void *buf, size_t buflen, unsigned int flags);
[/code]

由於預設是取得 /dev/urandom pool 中的 entropy, 若想要取得 /dev/random entropy 則需要修改 flags.

需要注意的是, 一次讀取最大能拿到的位元數分別如下:

  • /dev/random : 512 bytes
  • /dev/urandom : 33554431 bytes

詳細用法可以參考 man page [6].

使用 getrandom() system call 可以取得亂數值, 反過來如果要寫入資料以增加 entropy 則要透過 ioctl system call.

除了增加 entropy 外, 透過 ioctl command也能查詢目前 entropy 數量等等. ioctl command 列表如下圖, 命名相當清楚, 直接看 code 就可以知道在做什麼了.

2016-10-05_231209.png

 

4. /dev/hwrng – 位於 drivers/char/hw_random 並需要硬體元件支援

上述三點都是使用 Linux kernel 亂數產生器產生亂數, 但除此之外, 我們還可以使用硬體亂數產生器來產生亂數 – 如果系統不具備硬體亂數產生器, 請忽略此章節

現今除了 ARM SoC 大多有內建硬體亂數產生器外, 也可以透過 TPM [2] 硬體產生亂數.

  • 硬體亂數產生器對我們而言, 就是一個黑盒子, 會有些許安全性上的考量.所以請謹慎評估後再使用.

hwrng driver 透過 hwrng_register() 註冊到 drivers/char/hw_random/core.c 中. 請先開啟對應的 driver 選項, 然後再搭配 cryptodev-linux [1] 來建立 userspace interface, 即可透過 /dev/hwrng 來讀取硬體產生的亂數, 如下圖:

2016-10-06_145232.png

 

* 3.16 之後的 kernel 使用 add_hwgenerator_randomness [8][9], 直接將硬體產生的亂數加入到 /dev/random. 如果使用之前版本的 kernel, 可參照下一章節 – 產生 entropy 的工具 :  rng-tools


產生 entropy 的工具

平常我們可以透過下列指令來確認 entropy 是否足夠

[code language=”bash”]
cat /proc/sys/kernel/random/entropy_avail
[/code]

除了輸入裝置發出中斷的時間, IRQ 的 cycle counters, 硬碟讀寫的時間能產生 entropy 外, 也可以使用下列工具來協助產生 entropy

  • rng-tools [4]

主要功能是將硬體產生的亂數加入到 /dev/random 的 entropy pool, 以實現單一接口.

* 不適用於 kernel 版本 > 3.16 ,  3.16 之後的 kernel 使用 add_hwgenerator_randomness [8][9], 直接將硬體產生的亂數加入到 /dev/random

  • haveged  [5]

使用 HAVEGE algorithm 來產生亂數. 但產生的亂數品質不若硬體產生的好. 不建議使用在高安全性的應用中.


 

 

ref:

[1]: http://cryptodev-linux.org/

[2]: https://en.wikipedia.org/wiki/Trusted_Platform_Module

[3]: https://www.ibm.com/developerworks/cn/linux/1404_caobb_kvmrandom/

[4]: https://wiki.archlinux.org/index.php/Rng-tools

[5]: https://wiki.archlinux.org/index.php/Haveged

[6]: http://man7.org/linux/man-pages/man2/getrandom.2.html

[7]: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c6e9d6f38894798696f23c8084ca7edbf16ee895

[8]: http://linux-kernel.2935.n7.nabble.com/PATCH-1-2-add-direct-interface-for-true-hardware-RNGs-td713040.html

[9]: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=be4000bc4644d027c519b6361f5ae3bbfc52c347

發表迴響