# Documentation and Analysis of the Linux Random Number Generator

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

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

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

## Linux‑RNG
### Linux‑RNG 架構
* 發生硬體事件後，Linux‑RNG 會進行熵估計
* 將事件時間＆值混合到 4096 bits 的熵池 (input_pool)
* 熵池 (input_pool)
* 指的是保存隨機資料的儲存區域
* 資料透過確定性輸入和 LFSR-based 的狀態轉換函數進行處理，再以 Blake2s-based 雜湊函數輸出
* 由熵池維護的資料處理是完全確定性的


* input_pool 是收集並壓縮來自硬體事件的熵的熵池。此熵池的大小為 4,096 位元。
* ChaCha20 DRNG 的內部狀態為 512 位元。然而，只有 256 位元（ChaCha20 狀態的關鍵部分）充滿了隨機資料，其從 input_pool 取得其種子數據，並可透過以下方式存取：
* 透過`/dev/urandom`、`/dev/random` 或 `getrandom` 系統呼叫從使用者空間獲取
* 透過 `get_random_bytes`函數從核心空間取得。

### input_pool
##### structure

// 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 Pool State Transition Function
LFSR 用於將新值插入熵池，並選擇適當的多項式 "stir" 熵池內隨機數後 "twist"，可以看到在 twist 中一次扭轉三位以降低計算成本。

enum poolinfo {
    POOL_WORDS = 128,
    POOL_WORDMASK = POOL_WORDS - 1,
    POOL_BYTES = POOL_WORDS * sizeof(u32),
    POOL_BITS = POOL_BYTES * 8,
    POOL_BITSHIFT = ilog2(POOL_BITS),
    ...
    /* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
    POOL_TAP1 = 104,
    POOL_TAP2 = 76,
    POOL_TAP3 = 51,
    POOL_TAP4 = 25,
    POOL_TAP5 = 1,
    ...
}

static u32 const twist_table[8] = {
0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };

1. 選擇指向將要更新的熵池字的索引。
2. 將步驟 1 中的 4 個位元組與以下內容進行 XOR 運算：
1. 步驟 1 所取得的索引值所指向的目前熵池字
2. 由此索引加上 LFSR 多項式的第一個 tap 所指向的目前熵池字
3. 透過將輸入與步驟 2 中多項式的抽頭指向的 5 個不同熵池字進行 XOR 運算計算得到的 u32 值，再透過與 twist_table 的一個值進行 XOR 運算進一步攪拌。這項操作使用雙射操作來排列字的前三位。這個想法是透過「扭曲」將這三位混合。
4. 步驟 3 計算所得的值替換步驟 1 中索引指向的熵池字的先前值，成為新的值。
5. 重複步驟 1，直到所有輸入位元組都混合到熵池值中。

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;
}


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

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

##### Entropy Pool Output Function

#define ENTROPY_SHIFT 3
static size_t account(size_t nbytes, int min)
{
    ...
    entropy_count = orig = READ_ONCE(r->entropy_count);
    /* never pull more than available */
    ibytes = min_t(size_t, nbytes, entropy_count >>
    (POOL_ENTROPY_SHIFT + 3));
    if (ibytes < min)
    ibytes = 0;
    nfrac = ibytes << (ENTROPY_SHIFT + 3);
    if ((size_t) entropy_count > nfrac)
    entropy_count -= nfrac;
    else
    entropy_count = 0;
    if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
    ...
    return ibytes;
}

### ChaCha20 DRNG
##### structure

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


## Interfaces to Linux-RNG
##### structure

static const struct memdev {
    const char *name;
    mode_t mode;
    const struct file_operations *fops;
    struct backing_dev_info *dev_info;
} devlist[] = {
...
    [8] = { "random", 0666, &random_fops, NULL },
    [9] = { "urandom", 0666, &urandom_fops, NULL },
...
};

##### The callback functions for `/dev/random`

const struct file_operations random_fops = {
    .read = random_read,
    .write = random_write,
    .poll = random_poll,
    .unlocked_ioctl = random_ioctl,
...
    .fasync = random_fasync,
    .llseek = noop_llseek,
};

#### random_poll
* read: 當 ChaCha20 DRNG 已經 fully seeded 表明有足夠的熵可用時，內核會喚醒輪詢進程，以允許它們通過單獨的調用獲取數據。
* 允許用戶空間 asynchronously poll /dev/random 以避免在讀取 /dev/random 時出現阻塞行為
* random_poll 會保持成功返回直到下次重新啟動
* write: 當entropy estimator低於給定閾值表明可用熵不足時，核心會喚醒等待寫輪詢的進程。

#### Read and Write Operation
dev/random：使用該裝置檔案存取隨機數產生器時，會呼叫`random_read`的讀取函數。該函數會阻止呼叫者，直到 ChaCha20 DRNG fully seeded。一旦發生這種情況，就會產生與下面概述的 `/dev/urandom` 相同的隨機數。

static int
write_pool(const char __user *buffer, size_t count)
{
...
    __u32 buf[16];
...
    while (count > 0) {
    bytes = min(count, sizeof(buf));
...
    count -= bytes;
...
    mix_pool_bytes(buf, bytes);
...
    }    
}

## Entropy Collection
### add_input_randomness
將目前事件的事件值與前一事件的事件值進行比較。如果兩個事件值相同（例如，滑鼠向一個方向移動兩步或按同一鍵兩次），則該事件將被丟棄。否則，事件將會被加入到 input_pool 中。

void add_input_randomness(unsigned int type, unsigned int code,
unsigned int value)
{
    static unsigned char last_value;
    /* ignore autorepeat and the like */
    if (value == last_value)
    return;
...
    last_value = value;
    add_timer_randomness(&input_timer_state,
    (type << 4) ^ code ^ (code >> 4) ^ value);
...
}

### add_interrupt_randomness

void add_interrupt_randomness(int irq)
{
...
    struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
    struct pt_regs *regs = get_irq_regs();
    unsigned long now = jiffies;
    cycles_t cycles = random_get_entropy();
...
    c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
    j_high = (sizeof(now) > 4) ? now >> 32 : 0;
    fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
    fast_pool->pool[1] ^= now ^ c_high;
    ip = regs ? instruction_pointer(regs) : _RET_IP_;
    fast_pool->pool[2] ^= ip;
    fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
    get_reg(fast_pool, regs);
    fast_mix(fast_pool);
...

    if ((fast_pool->count < 64) &&
    !time_after(now, fast_pool->last + HZ))
    return;
...
    fast_pool->last = now;
    __mix_pool_bytes(&fast_pool->pool, sizeof(fast_pool->pool));
...
    fast_pool->count = 0;
    /* award one bit for the contents of the fast pool */
    credit_entropy_bits(1);
}

1. 必須滿足中斷次數和過期時間這兩個條件。
2. ast_pool 的最後一次讀取的時間戳設定為目前時間。
3. ast_pool 的內容會混合到 input_pool 中。
4. 將接收的中斷數重設為零，以進行步驟 1 中的初始條件檢查。
5. 將 input_pool 的熵估計器增加 1 – i CPU 硬體隨機數產生器存在時，熵估計量增加 2。

### add_disk_randomness

#define QUEUE_FLAG_DEFAULT ((1 << QUEUE_FLAG_IO_STAT) | \
                            (1 << QUEUE_FLAG_STACKABLE) | \
                            (1 << QUEUE_FLAG_SAME_COMP) | \
                            (1 << QUEUE_FLAG_ADD_RANDOM))
void add_disk_randomness(struct gendisk *disk)
{
    if (!disk || !disk->random)
    return;
...
    add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
}

### add_device_randomness
`add_device_randomness` 的目標是在裝置驅動程式初始化期間向 input_pool 提供資料，在啟動期間，ChaCha20 DRNG 被視為first seeded 之前， `add_device_randomness`接收到的所有資料都將注入 ChaCha20 DRNG 而不是 input_pool。這將保證在 boot 期間源自 `/dev/urandom` 的資料流能夠從輸入資料中獲益。

### add_hwgenerator_randomness
用於核心硬體 RNG 裝置驅動程式，其介面框架將獲得的熵透過`mix_pool_bytes`直接混合到 input_pool 中。
硬體 RNG 驅動程式框架實作了一個核心線程，該線程不斷從註冊的硬體 RNG 設備讀取數據，並使用從硬體設備獲取的數據呼叫`add_hwgenerator_randomness`介面函數，如果 input_pool 的熵估計器中的值全部低於變數`random_write_wakeup_bits`設定的閾值，則允許呼叫者將資料送入 Linux‑
RNG。