Try   HackMD

Documentation and Analysis of the Linux Random Number Generator

Documentation and Analysis of the Linux Random Number Generator

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 核心元件獲取隨機數。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

NDRNG Noise Source:

  1. 在實體設備上:智慧卡、特殊電路、硬體安全模組 (HSM) 等。
  2. 常規硬體的事件行為:人機互動(e.g.滑鼠移動或鍵盤打字)、硬碟或中斷。
  3. 利用 CPU 功能:time-based 噪音源、使用 RDRAND 等硬體噪音源的 CPU 指令
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

Linux‑RNG

Linux‑RNG 架構

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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • input_pool 是收集並壓縮來自硬體事件的熵的熵池。此熵池的大小為 4,096 位元。
  • ChaCha20 DRNG 的內部狀態為 512 位元。然而,只有 256 位元(ChaCha20 狀態的關鍵部分)充滿了隨機資料,其從 input_pool 取得其種子數據,並可透過以下方式存取:
    • 透過/dev/urandom/dev/randomgetrandom 系統呼叫從使用者空間獲取
    • 透過 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;
}

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Entropy Estimator

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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • 當對具有分數位的整數值進行操作時,整數值將保持不變。
  • 取得目前位元總數中的熵量: 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;
...
};

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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 中。

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