Linux随機數發生器
日期：2017-11-29 01:42:10 星期三
- Linux随機數發生器
- 一、源代碼的基本情況
- Linux核心版本
- 涉及檔案
- 功能概述
- 二、外部通路接口
- 核心層輸出接口
- 使用者層輸出接口
- 環境噪音輸入接口
- 三、核心源碼分析
- 随機數發生器理論
- 熵池結構
- 熵的加入
- 随機數的生成
- 啟動腳本
- 四、回答主要問題
- 核心代碼抽取
- 初始化漏洞攻擊
- 五、參考文獻
- 一、源代碼的基本情況
一、源代碼的基本情況
Linux核心版本
3.5.4
涉及檔案
- /include/linux/random.h
- /drivers/char/random.c
功能概述
Linux核心随機數生成器是Linux作業系統核心的重要組成部分，該生成器從裝置驅動等地方擷取環境的随機噪聲，從理論上傳回難于預測的真随機數。該生成器的應用場景涵蓋于具有較高安全性的協定棧，防止被黑客等進行爆破，如TCP序列号生成、DNS封包ID生成、TLS/SSL加密之類需要難以被預測的随機數場景。
二、外部通路接口
核心層輸出接口
void get_random_bytes(void *buf, int nbytes);
void get_random_bytes_arch(void *buf, int nbytes);
get_random_bytes
，是一個核心接口，僅在核心程式設計中使用，會将随機數按照nbytes大小填充到buf分區，可用于TCP序列号的生成等。該函數為非阻塞，不會因為熵池的熵值不夠而阻塞，是以會有一定的安全問題。
get_random_bytes_arch
，也是一個核心接口，使用的是硬體架構級别的随機數生成器，是以效率比上面軟體生成的随機數高出好多。但是難以保證該硬體級别的随機數生成器是否足夠安全。如果需要比較快速，而且相信該硬體随機數生成器的安全性話，是個不錯的選擇。如果硬體不支援，會調用
get_random_bytes
函數。
使用者層輸出接口
除了上面兩個核心接口，在使用者層面也有相應的接口，就是linux中常見的
/dev/urandom
和
/dev/random
這兩個檔案。在shell中，可以用dd和cat等指令直接擷取随機數，也可以直接寫個程式讀取這兩個檔案即可。
# 從/dev/urandom處擷取32個位元組的随機數，并放置于本地的urand.txt檔案
dd if=/dev/urandom of=./urand.txt count= bs=
# 從/dev/random處擷取32個位元組的随機數，并放置于本地的rand.txt檔案
dd if=/dev/random of=./rand.txt count= bs=
/dev/random
适用于對随機數安全性要求比較高的情形，但為了保證安全，該檔案的讀取偶爾會阻塞等待熵池的熵值達到某個門檻值。
/dev/urandom
沒有上面的限制，不會因為熵值不夠而導緻阻塞，可以源源不斷擷取所需的随機數。但随着越來越多的随機數被擷取，而且熵池的随機源沒有被進一步補充，新産生的随機數的安全性就會有一定的下降，有可能被人攻破，但大多數的應用場景已經夠用了。
環境噪音輸入接口
void add_device_randomness(const void *, unsigned int);
void add_input_randomness(unsigned int type, unsigned int code, \
unsigned int value);
void add_interrupt_randomness(int irq, int irq_flags);
void add_disk_randomness(struct gendisk *disk);
add_device_randomness
，是一個核心接口，可将裝置資訊或者系統啟動等資訊添加到input和nonblocking的熵池中去，不同的機器會有不同的裝置資訊，如MAC位址、機器序列号等，主要是用于初始化這些熵池。為了避免擁有相同裝置的機器帶來的安全問題，該接口不增加熵池的熵值。
add_input_randomness
，也是一個核心接口，用于添加輸入裝置的随機性，該随機性包括輸入事件本身的資訊和輸入的中斷計時。
add_interrupt_randomness
，也是一個核心接口，使用中斷計時作為随機源添加到熵池中。
add_disk_randomness
，也是一個核心接口，使用硬碟的尋道時間作為熵池的随機源，但對于高性能的固态硬碟來講，尋道時間非常短，而且相對穩定，是以此時的尋道時間不适合用來作為随機源。
三、核心源碼分析
随機數發生器理論
計算機作為一種可預測性較強的裝置，很難生成真正的随機數，然而可以使用僞随機數算法來緩解這個問題。但僞随機數有很緻命的一點，就是攻擊者可以通過各種攻擊手段猜到僞随機數發生器的序列，在一些應用場景下，使用這樣的僞随機數是十分危險的。
為了解決上面的問題，我們可以從計算機的環境中收集“環境噪音”等外部攻擊者難以擷取的資訊，然後把它們用于随機數的生成，就可以確定産生的随機數難以被預測。來自環境的随機性來源包括鍵盤、滑鼠和某些中斷的中斷計時，以及其他非确定性特别強和難以被預測的事件。把這些來源的随機性使用類似CRC機制的方法加入到“熵池”中，這種CRC機制在密碼學角度可能不是特别安全，但速度足夠快，也可以在一定程度上避免被惡意加入熵。在加入熵的過程中，還會根據實際情況計算随機數産生器的内部狀态中的熵值，即該熵值代表該系統的随機程度，側面反映該系統此刻的安全性。
在擷取随機數時，随機數是通過對熵池進行SHA哈希計算得到的。使用SHA哈希，是為了避免熵池的内部狀态直接被外部擷取，進而直接對後面的随機數進行預測。雖然目前沒有人可以對SHA進行逆向，但是難以避免未來的技術可以攻陷。此時，要保證從随機發生器傳回的資料量小于熵池内部狀态的熵值，這樣輸出資料是完全不可預知的。同時，當輸出資料時，熵池的熵值也要進行相應地降低。
熵池結構
熵池的結構，如上圖所示，圖檔來源于[1]，并對其進行一定的修改，使其更加符合本次閱讀的源碼結構。
linux核心随機數生成器有三個熵池組成，分别是
input_pool
,
blocking_pool
和
nonblocking_pool
。每個熵池都有自己的熵值計數器，用于儲存熵池的随機程度。如果有環境噪音流入，會先直接進入
input_pool
中，同時會測量該環境噪音的熵值，并更新其計數器。
blocking_pool
和
nonblocking_pool
會根據具體需求，向
input_pool
拉取熵，此時它們的熵值計數器也要有相應的增減。
熵池的資料結構如下：
struct entropy_store;
struct entropy_store {
/* read-only data: */
struct poolinfo *poolinfo;
__u32 *pool;
const char *name;
struct entropy_store *pull;
int limit;
/* read-write data: */
spinlock_t lock;
unsigned add_ptr;
unsigned input_rotate;
int entropy_count;
int entropy_total;
unsigned int initialized:;
__u8 last_data[EXTRACT_SIZE];
};
poolinfo
指向熵池資訊的結構體，裡面有熵池大小以及基于GF(2)進行熵池混合的參數；
pool
指向具體存放熵池内部狀态的數組；
pull
指向可以進行拉取熵的熵池，由
blocking_pool
和
nonblocking_pool
使用；
limit
代表熵池的熵值是否需要限制在一定的範圍内；
lock
為核心自旋鎖，用于解決多線程搶占該熵池的問題；
entropy_count
是該熵池的計數器，用于儲存熵值；剩下的都是為了用于友善操作熵池内部狀态。
input_pool
的定義如下：
static __u32 input_pool_data[INPUT_POOL_WORDS];
static struct entropy_store input_pool = {
.poolinfo = &poolinfo_table[],
.name = "input",
.limit = ,
.lock = __SPIN_LOCK_UNLOCKED(&input_pool.lock),
.pool = input_pool_data
};
使用
static
關鍵詞對熵池内部狀态和熵池結構進行定義，保證其全局唯一。其他兩個熵池也是用類似的方法進行定義。
熵的加入
在熵池中加入熵的核心算法在
_mix_pool_bytes
函數中實作，使用了大量的異或、位移等運算将噪音資料打亂分散，最後存儲至熵池的數組中。
mix_pool_bytes
是對其進行自旋鎖的封裝，用于保證線程安全的。
而
credit_entropy_bits
用于更新熵池的熵值，裡面使用了一些原子操作，也可以保證線程安全。
static int rand_initialize(void)
{
init_std_data(&input_pool);
init_std_data(&blocking_pool);
init_std_data(&nonblocking_pool);
return ;
}
在初始化的時候，熵的加入依靠
rand_initialize
和
init_std_data
完成。他們使用時間和硬體随機數，調用
mix_pool_bytes
對三個熵池進行狀态初始化。
在系統運作過程中，使用上一章所講的四個導入接口進行熵池的更新：
void add_device_randomness(const void *, unsigned int);
void add_input_randomness(unsigned int type, unsigned int code, \
unsigned int value);
void add_interrupt_randomness(int irq, int irq_flags);
void add_disk_randomness(struct gendisk *disk);
add_device_randomese
根據裝置資訊直接更新熵池資料，但不對熵池的熵值進行更新。
add_input_randomness
和
add_disk_randomness
會最終調用
add_timer_randomness
完成熵池所有的更新，
add_timer_randomness
使用三階時間差的方法進行熵值的估算。
add_interrupt_randomness
使用自行實作的
fast_mix
完成熵池的更新。
随機數的生成
産生随機數的兩個核心函數是
extract_entropy
和
extract_entropy_user
。
extract_entropy
是在核心态中進行随機數的生成，并拷貝至核心态的記憶體中，是以不需要考慮與使用者态互動的細節。而
extract_entropy_user
需要把生成的随機數拷貝到使用者态的記憶體中，不僅需要使用
copy_to_user
進行記憶體拷貝，還需要在while循環中考慮程序排程和信号處理等問題，防止while循環耗時過長。
extract_entropy_user
和
extract_entropy
大體類似，不再展開對其讨論。
而
extract_entropy
的源碼大體如下，省去了一些無用部分：
static ssize_t extract_entropy(struct entropy_store *r, void *buf,
size_t nbytes, int min, int reserved)
{
...
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, min, reserved);
while (nbytes) {
extract_buf(r, tmp);
...
}
...
}
extract_entropy
先調用
xfer_secondary_pool
函數根據實際條件進行熵從
input_pool
往
blocking_pool
或者
nonblocking_pool
遷移。然後調用
account
函數根據目前熵池的特性計算目前熵池能導出的随機數的數量，比如
blocking_pool
需要保證熵值在一定範圍内，超出其範圍會縮減nbytes的大小。最後調用最重要也是最核心的
extract_buf
函數來對熵池裡的資料進行導出。
對
extract_buf
函數進行簡化後，代碼如下：
static void extract_buf(struct entropy_store *r, __u8 *out)
{
...
sha_init(hash.w);
spin_lock_irqsave(&r->lock, flags);
for (i = ; i < r->poolinfo->poolwords; i += )
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
__mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
spin_unlock_irqrestore(&r->lock, flags);
...
}
extract_buf
函數使用SHA對熵池中部分資料進行hash，然後調用
__mix_pool_bytes
将hash值重新混入熵池中，重新打亂熵池，使得熵池更加不可預測，防止黑客多次取值後直接逆向出随機數生成器的内部狀态。
在核心态，可以直接調用
get_random_bytes
通過
extract_entropy
擷取
nonblocking_pool
産生的不太安全但速度足夠快的随機數。
在使用者态，可通過讀取
/dev/urandom
檔案，最終調用核心中的
urandom_read
函數使用
extract_entropy_user
完成
nonblocking_pool
産生的随機數的讀取；也可以通過讀取
/dev/random
檔案，最終調用核心中的
random_read
函數使用
extract_entropy_user
完成
blocking_pool
産生的較為安全随機數的讀取。
啟動腳本
在系統啟動初期，由于沒有足夠的熵源保證随機數生成的熵值，此時對其進行攻擊較為容易。一個可行的解決方法是，自行在Linux系統内添加啟動腳本和關機前執行腳本，在關機前先把系統原有熵池的資料存到某個檔案中，然後開機的時候再将這些資料恢複到熵池中，保證熵池持續具有較大的熵值。同時為了避免突然斷電或者系統崩潰導緻關機腳本未執行的情況，啟動時在恢複熵池後，又把熵池的狀态存下來，或者使用定時任務來儲存熵池狀态。
在ubuntu 14.04系統中，啟動腳本在
/etc/init.d/urandom
。
四、回答主要問題
核心代碼抽取
為了進一步簡化整體的代碼，在抽取代碼來實作獨立随機數模拟器的時候，做了以下修改：
1. 去除多熵池的設計，隻保留nonblocking pool。
2. 去除 熵值估計 和 熵值門檻值管理 的函數
3. 去除産生和管理random和urandom檔案的部分操作
4. 補充了一些缺失的函數，如 sha_init, sha_transform, rol32, min_t 等
5. 添加main函數，用時間作為種子mix_pool_bytes到nonblocking pool中做初始化，并列印出随機數來測試。
改造後的代碼：
#include <string.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#define OUTPUT_POOL_WORDS 32
#define EXTRACT_SIZE 10
#define SHA_WORKSPACE_WORDS 80
#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
#define min_t(type,x,y) \
({type __x=(x); type __y=(y); __x<__y?__x:__y;})
#define BigLong(x) (x)
#define __u32 unsigned int
#define __u8 unsigned char
#define ssize_t int
static struct poolinfo {
int poolwords;
int tap1, tap2, tap3, tap4, tap5;
} poolinfo_table[] = {
/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
{ , , , , , },
/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
{ , , , , , },
};
#define POOLBITS poolwords*32
#define POOLBYTES poolwords*4
struct entropy_store;
struct entropy_store {
/* read-only data: */
struct poolinfo *poolinfo;
__u32 *pool;
const char *name;
/* read-write data: */
unsigned add_ptr;
unsigned input_rotate;
};
static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
static struct entropy_store nonblocking_pool = {
.poolinfo = &poolinfo_table[],
.name = "nonblocking",
.pool = nonblocking_pool_data
};
static __u32 const twist_table[] = {
, , , ,
, , , };
static inline uint32_t rol32(uint32_t word, unsigned int shift){
return (word << shift) | (word >> ( - shift));
}
static inline uint32_t ror32(uint32_t word, unsigned int shift){
return (word >> shift) | (word << ( - shift));
}
/* SHA Begin */
void sha_transform(uint32_t *digest, const char *in, uint32_t *W);
void sha_init(uint32_t *buf);
/* SHA End */
static void mix_pool_bytes(struct entropy_store *r, const void *in,
int nbytes, __u8 out[]){
unsigned long i, j, tap1, tap2, tap3, tap4, tap5;
int input_rotate;
int wordmask = r->poolinfo->poolwords - ;
const char *bytes = in;
__u32 w;
tap1 = r->poolinfo->tap1; tap2 = r->poolinfo->tap2;
tap3 = r->poolinfo->tap3; tap4 = r->poolinfo->tap4;
tap5 = r->poolinfo->tap5;
input_rotate = r->input_rotate; i = r->add_ptr;
/* mix one byte at a time to simplify size handling and churn faster */
while (nbytes--) {
w = rol32(*bytes++, input_rotate & );
i = (i - ) & wordmask;
/* XOR in the various taps */
w ^= r->pool[i]; w ^= r->pool[(i + tap1) & wordmask];
w ^= r->pool[(i + tap2) & wordmask]; w ^= r->pool[(i + tap3) & wordmask];
w ^= r->pool[(i + tap4) & wordmask]; w ^= r->pool[(i + tap5) & wordmask];
/* Mix the result back in with a twist */
r->pool[i] = (w >> ) ^ twist_table[w & ];
input_rotate += i ? : ;
}
r->input_rotate = input_rotate;
r->add_ptr = i;
if (out)
for (j = ; j < ; j++)
((__u32 *)out)[j] = r->pool[(i - j) & wordmask];
}
static void extract_buf(struct entropy_store *r, __u8 *out)
{
int i;
union {
__u32 w[];
unsigned long l[LONGS(EXTRACT_SIZE)];
} hash;
__u32 workspace[SHA_WORKSPACE_WORDS];
__u8 extract[];
/* Generate a hash across the pool, 16 words (512 bits) at a time */
sha_init(hash.w);
for (i = ; i < r->poolinfo->poolwords; i += )
sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
sha_transform(hash.w, extract, workspace);
memset(extract, , sizeof(extract));
memset(workspace, , sizeof(workspace));
hash.w[] ^= hash.w[]; hash.w[] ^= hash.w[];
hash.w[] ^= rol32(hash.w[], );
memcpy(out, &hash, EXTRACT_SIZE);
memset(&hash, , sizeof(hash));
}
static ssize_t extract_entropy(struct entropy_store *r, void *buf,
size_t nbytes){
ssize_t ret = , i;
__u8 tmp[EXTRACT_SIZE];
while (nbytes) {
extract_buf(r, tmp);
i = min_t(int, nbytes, EXTRACT_SIZE);
memcpy(buf, tmp, i);
nbytes -= i; buf += i; ret += i;
}
/* Wipe data just returned from memory */
memset(tmp, , sizeof(tmp));
return ret;
}
void get_random_bytes(void *buf, int nbytes){
extract_entropy(&nonblocking_pool, buf, nbytes);
}
int main(int argc,char* argv[]){
char buf[];
time_t seconds = time(NULL);
mix_pool_bytes(&nonblocking_pool, &seconds, sizeof(time_t), NULL);
if(argc == ) seconds = (time_t) atol(argv[]);
int i;
get_random_bytes(buf, );
for(i=; i<; ++i){
printf("%d ", buf[i]);
}
printf("\n");
return ;
}
由于篇幅有限，上面的 SHA 部分被省去，具體源碼可看附件。
編譯過程：
由于解決了所有對外的依賴，用最簡單的方式進行編譯即可。
初始化漏洞攻擊
原理：
上面提取的程式，使用了常用的time(NULL)産生的時間作為随機源，然後不再添加新的随機熵源了。
由于time(NULL)傳回是以“秒”為機關，同時該程式産出的随機數我們也得到了，是以我們隻需要知道上次啟動該程式的大緻時間，對初始化的時間設定一定的範圍進行爆破。當生成的随機數數列符合我們之前得到的随機數數列，此時進行初始化的時間種子便是之前運作該程式的初始條件，利用該初始條件我們可以預測該程式接下來産生的随機數。
實驗方案：
1. 在特定時間點，運作上述提取程式，産生32個随機數，将前20個作為攻擊程式的輸入，将12個作為攻擊程式的預測輸出。
2. 提取的程式可以自定義參數作為随機數種子，友善攻擊程式調用進行破解，預設不填使用系統時間。
3. 取一個時間範圍，運作攻擊程式進行爆破，攻擊程式會以不同時間作為種子調用提取程式進行爆破猜解，如果發現前20個符合輸出，随即進行後續預測，輸出後續的12個生成的随機數。
4. 判斷攻擊程式預測的12個随機數，和之前随機數程式生成的是否一緻，即可判斷該攻擊是否真實有效。
實驗Python代碼：
# encoding: utf-8
import os
import time
import random
def getRet(seed=None):
if seed is None:
argList = ['./rand']
else:
argList = ['./rand', str(seed)]
wf, rf = os.popen2(argList)
strList = rf.read().strip().split(' ')
intList = map(lambda x: int(x), strList)
wf.close()
rf.close()
return intList
if __name__ == '__main__':
target = getRet()
print "target List: ", target
waitTime = random.random() *
print "wait for %s s" % waitTime
time.sleep(waitTime)
print "let's attack!"
endTime = int(time.time())
beginTime = endTime -
for seed in range(beginTime, endTime):
ret = getRet(seed)
OK = True
for i in range():
if ret[i] != target[i]:
OK = False
break
if OK:
print "found the random seed %d" % seed
print "the predict list is ", ret[:]
print "the target list is ", target[:]
實驗結果：
進行三次實驗，得到實驗截圖如下所示：
可見，進行三次猜解，均成功預測原程式接下來的12個随機數數列。是以，一個随機數生成系統，如果沒有持續添加新的熵，而且初始狀态的搜尋空間比較小的情況下，很容易對整個随機數生成系統進行攻破。
五、參考文獻
- 曹潤聰, 曹立明. Linux 随機數生成器的原理及缺陷[J]. 計算機技術與發展, 2007, 17(10): 109-112.
- Gutterman Z, Pinkas B, Reinman T. Analysis of the linux random number generator[C]//Security and Privacy, 2006 IEEE Symposium on. IEEE, 2006: 15 pp.-385.
- Patrick Lacharme, Andrea Röck, Vincent Stubel, Marion Videau. Analysis of the Linux Random Number Generator. http://users.ics.aalto.fi/arock/slides/slides_devrand.pdf