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

執行人: ShamrockLee
期末專題講解影片
 簡報

勘誤:

範圍: 簡報、期末專題解說影片的「 PRNG 介紹」

-虛擬亂數產生器是一種能產生性質類似亂數的數列的遞迴函數
+虛擬亂數產生器是一種能產生性質類似亂數的數列的演算法

解釋:

如果直接以遞迴函數作為 PRNG 來產生數列，那只要知道比該遞迴函數的輸入還要多的項，就能預測往後的數值，密碼學上不安全。
PRNG 內部的狀態 (state) 變化能夠由遞迴函數描述，而輸出值是由內部狀態透過令一個函數決定。

${\begin{cases} s t a t e_{i + 1} = f (s t a t e_{i}) \\ o u t p u t_{i} = g (s t a t e_{i}) \end{cases}$
$s t a t e_{0}$ 由亂數種子 (seed) 決定。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

提問清單

Tausworthe generator 一度使用於 Linux 核心 (lib/random32.c) 作為 PRNG，後續 Linux 改版時，基於什麼考量變更 PRNG 呢？

根據 Willy Tarreau 所貢獻的 commit c51f8f88d705 當中的 commit message ，利用 Tausworthe generator (LFSR) 實作的 PRNG 能讓攻擊者從一段已知的數列推測其他部份的值，導致運用於 SSL 等需要 CSPRNG 的場合時不安全。
該 commit 解決的方式，是將 prandom （ Linux PRNG ）改以基於 SipHash 的演算法實作。ShamrockLee

任務簡述

第 3 週測驗題第三題介紹到 Linear feedback shift register (LFSR)，這也是 Linux 核心亂數產生器 (RNG) 的基礎之一。本任務探討 Linux RNG 的原理、實作機制，以及應用場景。

相關素材:

重做第 3 週測驗題第三題，並彙整其他學員的成果

線性回饋移位暫存器原理與 Linux 核心當中的實作與應用

線性回饋移位暫存器，正如其名，是指遞迴關係能以線性函數（具疊加性、一次齊次性的函數）表達、主要以一串位移暫存器組成的電子電路，或上述電路所代表的演算法。

Fibonacci LFSR （又稱 Maximum-length LFSR ）由一列相接的移位暫存器組成，邏輯電平隨時脈朝右方傳遞，並透過對事先選定的幾個暫存器值做抑或運算決定最左方的數值。其值構成的序列稱為 maximum-length sequence （ MLS 、 M-sequence ）。

以軟體實作相應的 PRNG 時，能定義 lfsr 函式，其輸入值為指向無號整數的指標，該整數的各個位元即對應到電字電路各個移位暫存器的邏輯電平。以最高位對應上述最左端的暫存器，並以位元右移模擬移位暫存器的行為。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

（圖片取自 Wikipedia，以 CC0 授權。原圖為 SVG 檔。之後有時間的話，打算以 Graphviz 重製。）

上圖展示一個 Fibonacci 線性回饋移位暫存器，以第 11, 13, 14, 16 位元的值做 XOR 運算後指派到第 1 位元，而第 k 位元的值指派到第 k + 1 位元（

k \geq 1

）。

（目前未能理解

x^{16} + x^{14} + x^{13} + x^{11} + 1

與上述運算的關聯。）

多項式的乘方跟 64-bit 整數第幾位數正好相反。第 0 位是
$x^{64}$ ，第 1 位是
$x^{63}$ 故式子中 (*up) >> 3 是代表
$x^{64 - 3}$ 為
$x^{61}$ 以此類推。
lib/random32.c 內有說明。 PRNG 用 LFSR 去產生。

以下測驗 3 中的程式碼，便是利用 ((*up) >> (64 - k)) & 1 取得

2^{64 - k}

位的值以做 XOR 運算，接著利用 ((*up) >> 1) | (new_bit << 63) 得到將運算結果指派到

2^{63}

位，其他位右移一位的值，並指派回 *up 。

/* Implementation of LFSR (linear feedback shift register)
 * on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
 * (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
 */
static void lfsr(uint64_t *up)
{
    uint64_t new_bit =
        ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
    /* don't have to map '+1' in polynomial */
    *up = ((*up) >> 1) | (new_bit << 63);
    /* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}

以線性回饋移位暫存器的原理實作的 PRNG 又稱為 Tausworthe 產生器（ Tausworthe generator ），或許和 Robert C. Tausworthe 於 1965 年在期刊 Mathematics of Computation 上發表的論文 Random Numbers Generated by Linear Recurrence Modulo Two 有關。這個別稱在 Linux 核心專案中也有出現。

利用

git log --grep='\(LFSR\|[Ll]inear [Ff]eedback [Ss]hift [Rr]egister\|[Tt]ausworthe\)'

能列出 Linux 核心原始碼中，所有 commit message 提到 LFSR 的 commits 。截至 v6.4-rc6 （ commit 858fd168a95c ），在 master 分支上共有 23 個 commits 含有此關鍵字。再以關鍵字搜尋程式碼，能幫助我們了解 LFSR 實作於 Liunx 核心的過程。

Linux 核心專案於 2.6.2-rc2 開始採用 Git 版本控制系統，對應的 commit 1474855d0878 也是專案中最早的 commit 。而在這之前， Fibonacci LFSR 實作就已出現在 drivers/net/ewrk3.c 的函數 get_hw_addr 中，作為 EtherWORKS 乙太網路卡 driver 的一部分。

另外在 net/core/utils.c 當中， net-random 函數時做了 taus88 演算法，是一種 maximally equidistributed combined Tausworthe generator ，是由 Pierre L'Ecuyer 所設計的演算法，週期大約為

2^{88}

。

當時雖然已有 include/linux/random.h ，但直到 commit aaa248f6c9c8 （發布於 2.6.19-rc3 ）， net_random 才獨立成 lib/random32.c 當中的 random32 ，並宣告於 include/linux/random.h 中。

random32 經過一系列改進，包含 reseeding 與升級演算法到 taus113 （ commit a98814cef879 ）。

Fibonacci LFSR 或 Galoise LFSR 仍被當做一種簡單的 PRNG ，在 driver 、 profiler 等處實作。

整數
$\log_{2}$ 在 Linux 核心當中的實作

整數

\log_{2}

函數在 Linux 核心當中以 ilog2 命名。

Linux 核心專案中， include/linux/ilog2.h 提供 __ilog2_u32 、 __ilog2_u64 函數，及 log2 、 const_log2 巨集。前二者事實上就只是回傳 fls(n) - 1 （或 fls64(n) - 1）。

巨集 log2(n) 針對輸入型別選擇要呼叫的函數。巨集 const_log2(n) 主要在提供類似 C++ constexpr 在編譯時求值的支援。實作方式是藉由 GCC extension __builtin_constant_p(n) 偵測輸入值是否在編譯階段已知；若是則傳入一連串條件運算子，從左至右一一確認每個位元是否為零；若否則調用 log2(n) 巨集。

Linux 核心針對不同的處理器指令提供不同的 fls 實作，針對有支援 GCC extension __builtin_clz(n) 的環境，直接使用 32 - __builtin_clz(n) 或 64 - __buitlin_clz(n) 。針對其他指令集，則使用 inline assembly 實作。另外有 include/asm-generic/bitops/fls.h ，使用以下 C 語言實作，透過二分搜尋來找到變數左方位元皆為零的區域大小。

/**
 * fls - find last (most-significant) bit set
 * @x: the word to search
 *
 * This is defined the same way as ffs.
 * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
 */

static __always_inline int fls(unsigned int x)
{
	int r = 32;

	if (!x)
		return 0;
	if (!(x & 0xffff0000u)) {
		x <<= 16;
		r -= 16;
	}
	if (!(x & 0xff000000u)) {
		x <<= 8;
		r -= 8;
	}
	if (!(x & 0xf0000000u)) {
		x <<= 4;
		r -= 4;
	}
	if (!(x & 0xc0000000u)) {
		x <<= 2;
		r -= 2;
	}
	if (!(x & 0x80000000u)) {
		x <<= 1;
		r -= 1;
	}
	return r;
}

無分支、不使用 extension 的 `fls` 實作嘗試

Linux 核心專案未提供，不使用編譯器 extension 且平台無關的 fls 實作。我嘗試改寫上述平台無關的實作，以

x = x << (!(x & 0xffff0000u)) << 4

或

static int x1 = x << (!(x & 0xffff0000u)) << 4

取代

if (!(x & 0xffff0000u)) {
	x <<= 16;
}

試圖避開（顯式）分支，但以 gcc -O2 -std=c99 -S 編譯後，卻發現編譯產生的組合語言，分支和原本的實作一樣多。

我另外在 quiz2 中實作了，但指令數量從 Linux 核心實作的 24 個，上升到 40 個。尚未測試過效能，但以指令數量的成長來看，可能會造成效能損失。即使如此，在有 constant time 要求或其他需要避免分支的場合，還是有潛在用途。

對照〈回顧 bitops 並改進〉

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

上述無分支的 fls 實作，其原理為

將最高非零位元以外的位元設為零
以 bit masks 做二分搜尋，算出非零位元的索引

另外，將第一部的「最高非零位元」改為「最低非零位元」，就能實作 fls 。

〈回顧 bitops 並改進〉制定 gen_ffs 與 gen_fls 巨集界面，並透過 _Pragma("GCC unroll 6") 運算子在巨集內展開迴圈（ unroll loop ），不增加 branch 就能相容不同整數型態寬度的輸入值。（選用 6 是因為

2^{6} = 64

。〈回顧 bitops 並改進〉文中也提到，若未來要適用於 128-bit 的輸入值，能上調為 7 。）

上述技巧僅適用於 GCC 編譯器。考慮到 Clang 也支援 loop unrolling ，能定義巨集

#ifdef __clang__
#define unroll_ffls_branchless _Pragma("clang loop unroll_count(6)")
#elif __GNUC__ >= 8
#define unroll_ffls_branchless _Pragma("GCC unroll 6")
#else
#define unroll_ffls_branchless
#endif

並將 unroll_ffls_branchless 加在巨集定義的迴圈之前，這樣無論以 GCC 與 Clang 編譯，迴圈都能正確展開。類似的作法出現在 Linux 核心 i40e_xsk driver 、 ice_xsk driver 當中。

利用前述迴圈展開技巧，能將 fls 、 ffs 實作所需的步驟拆解為三個巨集

__preserve_msb_branchless 「保留非零最高位元」的無分支實作
__preserve_lsb_branchless 「保留非零最低位元」的無分支實作
__locate_bit_branchless 「定位非零位元索引」的無分支實作

對照 gen_fls 與 gen_ffs 界面，能分別實作 gen_fls_branchless 與 gen_ffs_branchless 巨集。其界面相容於，能如同 gen_f{f,l}s 一般套用到相關 clz 、 ctz 等函數實作。

〈回顧 bitops 並改進〉對 Linux 核心當中現有實作分析後，發現「索引從 1 開始」與「索引從 0 零開始」兩種風格，並以「回傳 0 」處理「索引從 0 開始」風格的例外（輸入值為 0 的情形）。這樣一來，「從 0 開始」在輸入值為 0 、為 1 時會對應到同樣的值，而有資訊損失。因此我針對「從 1 開始」實作運算步驟，並在 gen_fls_branchless 與 gen_ffs_branchless 內處理「從 0 開始」的例外。

「從 1 開始」特別考慮輸入值為零的情形，拆解的三個巨集都要具備處理此種例外的步驟。上述例外處理主要透過 !! 將數值對應到 0 或 1 （編譯成組合語言後會是 TEST 指令），或使用 bit mask 。

以下是實作的程式碼：
__preserve_msb_branchless:

/* Preserve the most significant bit set of X and unset others.
 * Return zero when non set.
 */
#define __preserve_msb_branchless(X, type)                                   \
    do {                                                                     \
        type __is_nonzero = !!(X);                                           \
        (X) = (X) >> 1;                                                      \
        unroll_ffls_branchless for (size_t _i_exp = 1;                       \
                                    _i_exp < (sizeof(X) << 3); _i_exp <<= 1) \
        {                                                                    \
            (X) |= (X) >> _i_exp;                                            \
        }                                                                    \
        (X) += __is_nonzero;                                                 \
    } while (0)

不考慮整數類型寬度與 0 輸入值處理的話，這段程式的行為就是

將非零最高位以下的位元都設為 1 ，本身設為 0

x = x >> 1;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
// ...

加一後就留下目標位元
```
x += 1;
```

例外處理的部份，則是考慮當輸入值為零時，步驟 1 做完之後 x 會是 0 ，和輸入值是 1 的情形無法分別，故須在進行步驟 1 之前先儲存 !!x ，以決定步驟 2 是否要加一。

__preserve_lsb_branchless:

/* Preserve the least significant bit set of X and unset others.
 * Return zero when non set.
 */
#define __preserve_lsb_branchless(X, type)                                   \
    do {                                                                     \
        unroll_ffls_branchless for (size_t _i_exp = 1;                       \
                                    _i_exp < (sizeof(X) << 3); _i_exp <<= 1) \
        {                                                                    \
            (X) |= (X) << _i_exp;                                            \
        }                                                                    \
        type _x_upperfilled = (X);                                           \
        (X) = ~(X) + (!!_x_upperfilled);                                     \
        (X) &= _x_upperfilled;                                               \
    } while (0)

仿照 __preserve_msb_branchless 的思路，這次把最低非零位元右方的位元都設為 1 ，這樣為 0 的位元剛好就都在目標位元左方。

這時套用 bitwise NOT 翻轉所有位元，就呈現類似 __preserve_msb_branchless 第一部進行完之後的情形，接著只要加 1 就好。

__locate_bit_branchless:

/* Take in an unsigned integer with at most one bit set, and then
 * output the 1-based digit of that bit. Return 0 if no bits are set.
 *
 * Bits higher than (2**64 - 1) will be truncated.
 *
 * Determine the result bit value through binary search with the following
 * masks:
 *
 * 0b01010101'01010101'01010101'01010101'01010101'01010101'01010101'01010101u
 * 0b01100110'01100110'01100110'01100110'01100110'01100110'01100110'01100110u
 * 0b01111000'01111000'01111000'01111000'01111000'01111000'01111000'01111000u
 * 0b01111111'10000000'01111111'10000000'01111111'10000000'01111111'10000000u
 * 0b01111111'11111111'10000000'00000000'01111111'11111111'10000000'00000000u
 * 0b01111111'11111111'11111111'11111111'10000000'00000000'00000000'00000000u
 * 0b10000000'00000000'00000000'00000000'00000000'00000000'00000000'00000000u
 */
#define __locate_bit_branchless(x_pow2, in_type, out_type)              \
    ((out_type) (((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x5555555555555555u))))    \
                  << 0) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x6666666666666666u))))    \
                  << 1) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x7878787878787878u))))    \
                  << 2) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x7f807f807f807f80u))))    \
                  << 3) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x7fff80007fff8000u))))    \
                  << 4) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x7fffffff80000000u))))    \
                  << 5) +                                               \
                 ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \
                                             0x8000000000000000u))))    \
                  << 6)))

gen_fls_branchless:

/* Branchless version of gen_fls */
#define gen_fls_branchless(in_type, out_type, start_from, fn_name) \
    static __always_inline out_type fn_name(in_type x)             \
    {                                                              \
        __preserve_msb_branchless(x, in_type);                     \
        out_type _ret = __locate_bit_branchless(x, in_type, out_type);                \
        return _ret - (out_type) ((!(start_from)) & (!(_ret)));    \
    }
    }

gen_ffs_branchless:

/* Branchless version of gen_ffs */
#define gen_ffs_branchless(in_type, out_type, start_from, fn_name) \
    static __always_inline out_type fn_name(in_type x)             \
    {                                                              \
        __preserve_lsb_branchless(x, in_type);                     \
        out_type _ret = __locate_bit_branchless(x, in_type, out_type);                \
        return _ret - (out_type) ((!(start_from)) & (!(_ret)));    \
    }

2023-07-11 更新：

根據 Linux 核心官方文件 Minimal requirements to compile the Kernel ， Linux 核心專案支援以 5.1 版或之後的 GCC 編譯。這代表 Linux 核心內的程式，以受到支援的編譯器版本編譯，產生的目的碼都必須有正確的行為。

gen_f{f,l}s_bratchless 的價值在於產生沒有分支的 ffs 、 fls 實作，但前述實作用到的 _Pragma("GCC unroll 6") 功能，在 GCC 8才加入。原本設想以 conditional directives 定義巨集 unroll_ffls_branchless 以避免在未支援此 directive 的編譯器上編譯時產生的警告訊息或錯誤，但這也意謂在上述較低版本的編譯器上，迴圈可能根本沒展開，而導致出現分支。這對於 gen_f{f,l}s 可能只是效能下降，但對於 gen_f{f,l}s_branchless 來說是行為不正確，必須改善。

以下是改善後的實作：

/* Preserve the most significant bit set of X and unset others.
 * Return zero when non set.
 */
#define __preserve_msb_branchless(X, type)       \
    do {                                         \
        type _is_nonzero = !!(X);                \
        (X) >>= 1;                               \
        (X) |= (X) >> 1;                         \
        (X) |= (X) >> 2;                         \
        (X) |= (X) >> 4;                         \
        (X) |= (X) >> ((sizeof(type) > 1) << 3); \
        (X) |= (X) >> ((sizeof(type) > 2) << 4); \
        (X) |= (X) >> ((sizeof(type) > 4) << 5); \
        (X) += _is_nonzero;                      \
    } while (0)

/* Preserve the least significant bit set of X and unset others.
 * Return zero when non set.
 */
#define __preserve_lsb_branchless(X, type)       \
    do {                                         \
        (X) |= (X) << 1;                         \
        (X) |= (X) << 2;                         \
        (X) |= (X) << 4;                         \
        (X) |= (X) << ((sizeof(type) > 1) << 3); \
        (X) |= (X) << ((sizeof(type) > 2) << 4); \
        (X) |= (X) << ((sizeof(type) > 4) << 5); \
        type _x_upperfilled = (X);               \
        (X) = ~(X) + (!!_x_upperfilled);         \
        (X) &= _x_upperfilled;                   \
    } while (0)

為了不依賴迴圈展開就能相容不同整數類型寬度，我們能手動展開至符合 64 位元整數類型的執行次數，再將每次執行欲移動的位元數與類型寬度比較，再用這項布林值決定是否歸零移動的位元數。由於比較的部份在編譯時期已知，能期待編譯器將之最佳化而不產生分支。

`lab0-c` 中 `log2_lshift16.h` 的原理與效能改善

原理

lab0-c 當中的 log2_lshift16.h 儲存有預先計算好的

\log_{2}

值對應關係。其結構是由條件控制所建立的 search tree 。其輸入值比數學上的值向左偏移 16 位元，輸出值比數學上的值向左偏移 3 位元，以整數表示定點數（ fixed-point number ）。

由輸出值皆為負數看來，輸入值對應到定點數

(0, 1]

的範圍。

效能改善

藉由

\log

的數學特性，能將輸入值限縮在更小的範圍，強制其小數點後第一位（整數的

2^{15}

位）為 1 ，否則先左移再查詢。這樣就能降低樹高，減少查詢時間。搭配指令集對 __builtin_clz64 的支援，預期能達到更高的效能，並減少檔案大小。

Linux RNG 架構與文獻探討

隨機事件收集

Linux 核心從多重來源蒐集隨機事件並估計其「熵」
- 硬體隨機數產生器（ HWRNG ）
- 鍵盤、滑鼠輸入（計算週期數）
- 中斷事件（計算週期數）
- Linus Jitter Dance

隨機事件混合

LFSR

TODO: 研讀 Linux RNG 相關文獻並記錄自己的認知和疑惑

至少要涵蓋以下:

儘量紀錄理解狀況、彙整文件，並紀錄問題。藉由上述認知回覆下方問題:

Linux RNG 如何達到 CSPRNG 要求？以真實應用場景來舉例說明
LFSR 在 Linux RNG 的實作有何影響？以 Linux 核心原始程式碼搭配解說
Linux 的 /dev/random 和 /dev/urandom 對應到內部哪些實作？如何運用硬體 RNG 或者相關機制 (例如 Raspberry Linux 的 /dev/hwrng) 呢？如何確保其「夠亂」呢？

TODO: 撰寫 Linux 核心模擬測試 RNG 框架並提供可能的 `hwrng` 實作

對 Linux RNG 有足夠認知後，撰寫 Linux 核心模組來測試，並搭配 Linux 核心原始程式碼和〈Documentation and Analysis of the Linux Random Number Generator〉，探討如何運用硬體特性作為有效的 entropy source，從而實作 hwrng。

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

任務簡述

重做第 3 週測驗題第三題，並彙整其他學員的成果

線性回饋移位暫存器原理與 Linux 核心當中的實作與應用

整數 log2 在 Linux 核心當中的實作

無分支、不使用 extension 的 fls 實作嘗試

lab0-c 中 log2_lshift16.h 的原理與效能改善

原理

效能改善

Linux RNG 架構與文獻探討

隨機事件收集

隨機事件混合

TODO: 研讀 Linux RNG 相關文獻並記錄自己的認知和疑惑

TODO: 撰寫 Linux 核心模擬測試 RNG 框架並提供可能的 hwrng 實作

整數
$\log_{2}$ 在 Linux 核心當中的實作

無分支、不使用 extension 的 `fls` 實作嘗試

`lab0-c` 中 `log2_lshift16.h` 的原理與效能改善

TODO: 撰寫 Linux 核心模擬測試 RNG 框架並提供可能的 `hwrng` 實作