Volume 0x0b, Issue 0x3b, Phile #0x0f of 0x12


|=--------=[ CRYPTOGRAPHIC RANDOM NUMBER GENERATORS ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Author: DrMungkee <pub@drmungkee.com> ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Translator: winewind <winewind@163.com>]=-------=|



密碼學(xué)里的隨機(jī)數(shù)發(fā)生器

----| 介紹

對(duì)于密碼系統(tǒng)的安全性來說，每個(gè)組件都是很重要的。一個(gè)組件設(shè)計(jì)的失敗可能使其他所有的組件崩潰。密碼隨機(jī)數(shù)常常被用作密鑰，補(bǔ)充信息，輔助信息和初始化向量。對(duì)每一個(gè)組件來說，使用一個(gè)好的隨機(jī)數(shù)發(fā)生器（RNG）是必要的。利用計(jì)算機(jī)行為的可預(yù)測(cè)性,可以人為的制造很多復(fù)雜因素。本文的范圍涵括了隨時(shí)數(shù)產(chǎn)生器的設(shè)計(jì)，執(zhí)行和分析。將要涉及的隨機(jī)數(shù)發(fā)生器(RNG)包括：NoiseSpunge, Intel 隨機(jī)數(shù)發(fā)生器（Intel RNG），Linux下的“/dev/random”和Yarrow。


----| 關(guān)鍵詞：

RNG - 隨機(jī)數(shù)發(fā)生器（Random Number Generator）
PRNG - 偽隨機(jī)數(shù)發(fā)生器（Pseudo Random Number Generator）
信息熵（entropy） - 不可預(yù)知信息（Unpredictable information）
冗余信息（redundancy）- 可預(yù)知信息（Predictable or probabilistic information）

（譯者注：entropy一詞源于物理，是“熵”的意思。在信息技術(shù)中引入，從而有了“信息熵”的說法。“熵”的特性：在封閉系統(tǒng)中，系統(tǒng)的熵只會(huì)增加或保持不變，系統(tǒng)的平衡點(diǎn)是熵最大的時(shí)候。無線電中常翻譯成“平均信息量”。我也不知道這里用信息熵的說法是否便于理解。如果覺得別扭，就理解成一種信息好了）

（譯者注：這里我加入一段引來的文章，可能會(huì)讓大家對(duì)這個(gè)名詞了解得更好：現(xiàn)代信息學(xué)的基礎(chǔ)是信息熵理論，即對(duì)被傳送信息進(jìn)行度量的一種平均值，單位是比特。四十年代，現(xiàn)代信息論創(chuàng)始人、美國(guó)貝爾實(shí)驗(yàn)室科學(xué)家閃農(nóng)（C．Shannon）發(fā)明了信息熵理論，由此提出了數(shù)據(jù)優(yōu)化編碼、輸入輸出效率、通訊傳遞渠道效率、多余度和數(shù)據(jù)壓縮等一系列信息科學(xué)基礎(chǔ)理論和技術(shù)。信息熵是信息產(chǎn)業(yè)的地基。比如，不管計(jì)算機(jī)硬件軟件如何更新?lián)Q代，英文的字符平均信息熵（靜態(tài)信息熵）是4．03比特，因而，處理和儲(chǔ)存英文數(shù)據(jù)的每個(gè)字符的編碼不能少于5比特；中文的漢字平均信息熵是9．65比特，因而，處理和儲(chǔ)存中文數(shù)據(jù)的每個(gè)字符的編碼不能少于10比特。）


1.0) 概述

設(shè)計(jì)一個(gè)隨機(jī)數(shù)發(fā)生器(RNG)需要考慮各種因素。在白噪音環(huán)境中（譯者注：在一定帶寬內(nèi)，在各個(gè)頻率上，各種噪音的強(qiáng)度都是一樣的），輸出必須是不可識(shí)別的。輸出的任何一部分都是不可預(yù)知的。而且基于已知的結(jié)果，無法推算出上一步（不可逆）和下一步的結(jié)果。如果一個(gè)隨機(jī)數(shù)產(chǎn)生器不能遵照這個(gè)標(biāo)準(zhǔn)，那么產(chǎn)生的密碼是不安全的。

1.1) 信息熵（entropy）的收集：

為了滿足第一條和第二條要求，為這些信息熵找尋好的來源（信息源）就成了一個(gè)首選任務(wù)。這些信息源對(duì)于攻擊者必須是不可監(jiān)測(cè)的。而且任何對(duì)信息源的操作對(duì)攻擊者來說都是不可知和無法重復(fù)的。

鼠標(biāo)的移動(dòng)常常被用作信息熵的一種。但是如果RNG不能正確的處理信息熵，將會(huì)產(chǎn)生大量的冗余信息。舉個(gè)例子，鼠標(biāo)移動(dòng)的時(shí)間間隔是100毫秒。當(dāng)鼠標(biāo)在各方向快速移動(dòng)時(shí)，其位置記錄如下：


    X-軸          Y-軸
  0000001011110101  0000000100101100   注意：在各個(gè)坐標(biāo)中只
  0000001000000001  0000000100001110   有最后九位是隨機(jī)的。
  0000001101011111  0000001001101001   
  0000001000100111  0000000111100100
  0000001010101100  0000000011111110
  0000000010000000  0000000111010011
  0000001000111000  0000000100100111
  0000000010001110  0000000100001111
  0000000111010100  0000000011111000
  0000000111100011  0000000100101010

下面的例子演示了一個(gè)更加實(shí)際的信息熵的收集過程。保留X-坐標(biāo)和Y-坐標(biāo)的最后四位(因?yàn)樗鼈冏钪匾?,和采樣得到的時(shí)間作異或運(yùn)算，并把它們隨意排列如下：

   X    Y     時(shí)間    異或后
  1010  1001  00100110  01111111
  0100  1100  00101010  00000110
  0101  0010  01011111  01110101
  1001  1100  10110000  11111100
  0101  0100  11001110  11100010
  0101  1100  01010000  01111100
  1011  0000  01000100  00011100
  0111  0111  00010111  00101000
  0011  0101  01101011  01110110
  0001  0001  11011000  11010001

這是一個(gè)好辦法，因?yàn)閺母髯鴺?biāo)得到的四位數(shù)代表了在16像素平面上的任意方向（譯者注：上面的數(shù)據(jù)表明，這個(gè)范圍對(duì)紀(jì)錄鼠標(biāo)的運(yùn)動(dòng)已經(jīng)足夠大了），而不是 256*256平面上65536種移動(dòng)方向。選用時(shí)間是因?yàn)殡m然它們是連續(xù)的，但是它們的最后八位在CPU時(shí)鐘周期內(nèi)非常頻繁的變化,這些比特位是無法人為預(yù)料的。異或運(yùn)算用于合并兩方面的信息熵。在合并數(shù)字并且保留各比特位的獨(dú)立上，異或是個(gè)好辦法：）

最常見的信息源包括用戶的人為反應(yīng)或某種經(jīng)過排列變形后的高頻時(shí)鐘的序列。把上面兩種合二為一得到的結(jié)果往往就是我們所需要的。用高精度采集用戶觸發(fā)事件的反應(yīng)時(shí)間（擊鍵，磁盤輸入/輸出，中斷，鼠標(biāo)點(diǎn)擊）的方法有其優(yōu)越性，因?yàn)橛脩魝�(gè)體行為和精確的時(shí)間是不可預(yù)知的。

有些信息看起來是足夠隨機(jī)的，但實(shí)際上未必。有時(shí)可以把網(wǎng)絡(luò)的輸運(yùn)情況作為一種信息源，但我們并不推薦這樣做，因?yàn)檫@種信息畢竟還是可以由某些外來因素控制的。另一個(gè)缺點(diǎn)是使用毫秒精度的時(shí)鐘：對(duì)于比較高的要求，這種刷新頻率顯得的太慢了。

在討論信息熵收集方法缺點(diǎn)方面，這里有一個(gè)不錯(cuò)的案例：Netscape公司使用的SSL加密協(xié)議是可破解，它并沒有使用真正的RNG。（譯者注：可以在下面的網(wǎng)址找到介紹 http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html）Netscape公司標(biāo)志進(jìn)程和父進(jìn)程時(shí)使用時(shí)間和日期，并把它們當(dāng)作唯一的信息源。在win9x中進(jìn)程標(biāo)志通常都是由一個(gè)小于100的值（每增加一個(gè)新進(jìn)程就加一）和win9x第一次啟動(dòng)時(shí)的時(shí)間日期作異或運(yùn)算得到。雖然由哈希函數(shù)得到的結(jié)果看起來是隨機(jī)的，實(shí)際上猜測(cè)出那個(gè)值，計(jì)算并且得到正確的結(jié)果并不是件難事。如果可利用的信息熵非常有限，那么輸出結(jié)果是不是真的隨機(jī)也就不是很重要了（好像有點(diǎn)無奈的意思）。


1.2 信息熵的估算

我們不能忽視對(duì)收集到的信息熵總數(shù)的估算。這一步很重要。否則隨機(jī)數(shù)產(chǎn)生器輸出結(jié)果中信息熵的數(shù)量有可能超過輸入的信息熵的數(shù)量。根據(jù)相應(yīng)的系統(tǒng)參數(shù)，我們可以給各個(gè)信息源賦相應(yīng)的值。比如，對(duì)于鍵盤活動(dòng)，不管我們能夠收集的信息熵總數(shù)是多少，我們都可以假設(shè)所有鍵盤活動(dòng)產(chǎn)生的信息熵的大小都是4比特的。如果RNG在文件服務(wù)器上，并且把磁盤輸入/輸出作為信息源，我們可以根據(jù)某時(shí)刻正在訪問磁盤的用戶數(shù)相應(yīng)的估計(jì)信息熵，而不是根據(jù)訪問序列。如果基于后者，則可能產(chǎn)生多余的信息。對(duì)信息熵大小的估算不一定要和輸入或輸出的大小一樣。這條準(zhǔn)則在今后的計(jì)算中能起到安全預(yù)防的作用。

對(duì)信息熵的估算還有其他的方法。如果信息源超過一定時(shí)間間隔后還沒有給我們提供數(shù)據(jù)，使用統(tǒng)計(jì)的方法計(jì)算偏差會(huì)獲得更好的效果。我們可以從buffer收集大量的數(shù)據(jù)信息，經(jīng)過壓縮，得到壓縮比的值。相對(duì)于之前輸入的大量數(shù)據(jù)，統(tǒng)計(jì)測(cè)試表明，最后一次輸入的數(shù)據(jù)對(duì)于檢驗(yàn)當(dāng)前輸入數(shù)據(jù)整體屬性起不到什么作用。但是對(duì)于RNG來說，則意味著可以把這些只能增加統(tǒng)計(jì)概率的輸入數(shù)據(jù)舍棄。

最好的辦法莫過于多試幾次。在估算信息熵值時(shí)用一種方法往往是不夠的。信息源的情況是復(fù)雜的，得到的信息熵也是多種多樣的。可是在實(shí)際中，對(duì)所有的信息熵的大小往往賦同一個(gè)值。因此在做這種假設(shè)之前，必須仔細(xì)的分析一下。多嘗試幾個(gè)值是明智的選擇。而最小的值往往是最準(zhǔn)確的。


1.3) 信息熵的集合

沒有任何信息源可以說是完美無缺的。確切點(diǎn)說，在計(jì)算機(jī)上是這樣。這就是為什么我們?cè)赽uffer（信息熵的集合）收集了信息之后還要進(jìn)行一些處理。收集完畢后，信息熵就被輸入到一個(gè)集合里。這個(gè)集合必須和輸入有以下的關(guān)系：要知道包含元素的個(gè)數(shù)，把最后一次輸入合并到之前收集的數(shù)據(jù)中并保持其一致性。另外，拋開那些收集到的信息熵的屬性不論，集合還要為這些數(shù)據(jù)提供一個(gè)至少看起來隨機(jī)的狀態(tài)（相似的輸出在這個(gè)集合里也應(yīng)該是看起來隨機(jī)的）。

對(duì)于某個(gè)集合狀態(tài)，處理集合內(nèi)容時(shí)（這里指把所有元素合并起來），既不能減少元素，也不能添加元素。如果經(jīng)過某個(gè)合并函數(shù)的處理，集合變大了，那么必須保證這對(duì)信息熵的估算是沒有影響的。只有那些負(fù)責(zé)收集信息熵的函數(shù)才能改變信息熵的大小。而且這些收集函數(shù)是分開作用的，彼此獨(dú)立。

最好的合并函數(shù)是哈希算法（譯者注：又稱散列法）。哈希算法能夠接受任意大小的輸入，它的大范圍輸出可以反映信息熵合并的速度，并且這個(gè)算法的輸出是不確定的。為了保護(hù)那些合并后的信息熵（譯者注：保證沒有信息丟失），哈希函數(shù)輸入的大小不大于輸出的。也就是說，如果哈希函數(shù)的輸出是160位的，那么之前的輸入最多160位。如果哈希函數(shù)用于密碼處理上是安全的（事實(shí)上的確如此），那么輸出的信息熵的個(gè)數(shù)應(yīng)該和輸入的一樣。但是如果輸出的多于輸入，并不能認(rèn)為信息熵集合里的態(tài)一定增加了。

處理大集合有以下幾種途徑：一種方法是把這個(gè)集合線性hash（雜化）。使用這種方法，你可能需要一個(gè)buffer保存最近的一次輸入。hash從buffer的尾部開始，一次只hash一塊（塊的大小和輸出的大小相同）。每次把當(dāng)前輸出和前一個(gè)塊的hash結(jié)果作異或運(yùn)算，以次保證整個(gè)集合只被最近的一次輸入作用，而不會(huì)改寫以前的結(jié)果。這只是一個(gè)例子。不管你選擇什么樣的處理方式，必須保證這種方式遵守前面所說的各條準(zhǔn)則。

另一個(gè)處理大集合的方法是“multiple hash(多樣雜化)”，使集合的內(nèi)容互相影響。一個(gè)常見的用途就是用于處理包含“不可操作的信息熵”的集合。一旦這個(gè)集合滿了，它就會(huì)被hash并用于更新另一個(gè)集合。更新的方式可以是更新hash的關(guān)系，也可以是直接作異或運(yùn)算。這樣盡可能多的集合就串聯(lián)了起來。為了避免丟失已有的信息熵，一些集合只有在它們的父集合（更新這些集合的集合）被更新若干次（譯者注：更新次數(shù)事先定義好的）后才能被操作。比如，只有當(dāng)?shù)谝粋�(gè)hash集合被更新了8次后，下一個(gè)集合才能被更新。只有下一個(gè)集合被更新滿了3次，它才能用于hash第三個(gè)集合。在這種方法里，第三個(gè)集合包含了經(jīng)過24次hash的信息熵。這樣保留下來的原始信息熵變少了（受雜化關(guān)系的限制）但是這些信息熵的性質(zhì)卻更好了。因?yàn)榈谌齻�(gè)集合里的信息源完全基于24次輸入的信息熵。

向一個(gè)集合中輸入信息熵往往稱為更新或播種。這種信息熵的集合和基于它自身構(gòu)建的輸出函數(shù)實(shí)際上是一個(gè)PRNG。在收集信息熵的過程中獲得的真正的隨機(jī)種子才是得到RNG的原因。只要輸入了一個(gè)好的信息熵，RNG就產(chǎn)生一個(gè)無界區(qū)域（沒有輸出模式）。這和PRNG正好相反。相對(duì)于RNG的無界區(qū)域，后者是從一個(gè)半確定的點(diǎn)開始，重復(fù)以前的所有輸出，并且重復(fù)的順序和RNG是一樣的。

信息熵的集合對(duì)于防范攻擊者推算RNG以前的輸出和以后的輸出結(jié)果至關(guān)重要。對(duì)RNG的攻擊就是基于三部分：對(duì)信息熵集合性質(zhì)的了解，信息熵的輸入和以前的輸出結(jié)果。要防止別人了解集合當(dāng)前的狀態(tài)，就要對(duì)以后的輸出結(jié)果做一些處理。因此，集合必須不時(shí)地做一些大的變動(dòng)，刪除一部分或是全部的信息熵。這個(gè)過程叫做再播種。再播種，總是（譯者注：用逗號(hào)隔開是為了強(qiáng)調(diào)），在輸出之前用一些新的信息熵替換那些已經(jīng)被刪除的。如果沒有上面的替換，這個(gè)集合的安全性就很成問題了。RNG不需要再播種，但是如果沒有這步，就必須不停的添加信息熵的輸入，添加的速度還要高于輸出的。

并不是任何時(shí)候都要再播種的。只有當(dāng)未用過的信息熵積累了足夠多并且占了集合空間的一大部分時(shí)才使用再播種。要注意的是，對(duì)集合中信息熵的估算要隨著輸入數(shù)據(jù)的大小作相應(yīng)的調(diào)整。再播種不能頻繁的使用。是否使用它的唯一根據(jù)就是隨機(jī)數(shù)生成器輸出的比特位數(shù)和整個(gè)集合的大小。當(dāng)集合里95%的信息熵都已經(jīng)輸出時(shí)采用再播種，這是一個(gè)比較適當(dāng)?shù)念l率。這里我們假設(shè)信息熵的輸入是在RNG輸出的空隙間完成的。如果不是這樣，那么使用再播種的次數(shù)有可能應(yīng)該更多一些。在輸出空隙間輸入的信息熵越少，攻擊者就越容易找到輸出方式的蛛絲馬跡，從而推算出上一次輸出的結(jié)果（這樣循環(huán)往復(fù)，一個(gè)鏈?zhǔn)降哪嫦蛲扑憔陀锌赡艹晒Φ氐玫焦�擊者想要的東西）。（譯者注：這里我們并不規(guī)定兩次輸出之間只能有一次輸入。相反，輸入的數(shù)據(jù)應(yīng)該多于輸出。這樣，可以想象，在集合里用不到的數(shù)據(jù)會(huì)越來越多。等他們多到一定程度時(shí)，如上文的95%，一次性的替換掉。這就是一次的再播種。）

1.4）輸出函數(shù)

RNG的輸出函數(shù)必須是單向的。單向的意思是輸入的數(shù)據(jù)經(jīng)過函數(shù)處理可以得到輸出，但是根據(jù)輸出的數(shù)據(jù)無法計(jì)算出輸入的原始數(shù)據(jù)（譯者注：就是不可逆啦，饒舌）。單向的hash函數(shù)是一個(gè)非常好的選擇。更復(fù)雜的方法是把集合中的一部分元素作為key data（譯者注：不好意思，我一時(shí)還想不出什么好的詞），使用對(duì)稱加密算法，對(duì)另一部分加密，并且輸出密文。壓縮-解壓縮也是一個(gè)效率很高的單向函數(shù)。為了達(dá)到目的，我們可以把集合中一部分元素當(dāng)作PRNG的種子，生成多種輸出（根據(jù)PRNG的種子大小而定）。然后把這些輸出統(tǒng)統(tǒng)放進(jìn)一個(gè)雜化函數(shù)得到結(jié)果。這樣做保證了效率，因?yàn)樘幚頃r(shí)很多中間態(tài)（解壓縮）hash的結(jié)果都是一樣的，真正起作用的只是解壓縮前的那個(gè)初始態(tài)。

RNG每次輸出時(shí)，對(duì)它信息熵的估算都要隨輸出的大小而減少。這樣做的前提是假設(shè)輸出的數(shù)據(jù)都是由信息熵組成。由于輸出的信息熵仍然保留在集合里，這些東西現(xiàn)在就成了冗余信息，也不該再把它們當(dāng)作信息熵了（在集合里）。如果集合的大小是512位，且每次輸出信息熵的大小是160位，那么三次輸出之后，基本上所有的信息熵都被hash了，這個(gè)集合也就需要再播種了。

在處理信息熵集合時(shí)，有一個(gè)幾乎不可能解決的問題：我們沒辦法確定信息熵的哪些位是要輸出的，哪些不是。緩解這個(gè)問題最好的辦法是：即便你看到了RNG的輸出結(jié)果，我們也根本不讓你知道哪些信息熵被用了幾次。（譯者注：看起來有點(diǎn)掩耳盜鈴，但的確管用。我偷偷地用，用幾次誰(shuí)也不知道。感覺差不多了，我就再播種了。神不知鬼不覺）當(dāng)一次輸出完成后，集合的態(tài)發(fā)生變化，重新排序。這樣，在既不添加信息熵也不再播種的情況下，RNG的輸出結(jié)果也不會(huì)重復(fù)。集合的態(tài)的重新排序必須通過單向函數(shù)完成，而且輸出函數(shù)必須滿足前面提到的各條原則。只要處理的過程不違反前面的規(guī)定，我們認(rèn)為集合里信息熵的大小在排序前后總是一致的。

1.5）執(zhí)行

如果執(zhí)行時(shí)不順利的話，我們前面所作的所有努力都是白費(fèi)。這里關(guān)于執(zhí)行我們要談三個(gè)方面的東西：媒質(zhì)，硬件/軟件和輸出的使用。

在未加密狀態(tài)，儲(chǔ)存媒質(zhì)和通信媒質(zhì)各占了一個(gè)風(fēng)險(xiǎn)。下表列出了各種媒質(zhì)的風(fēng)險(xiǎn)程度。對(duì)于風(fēng)險(xiǎn)程度的比例說明是這樣的：

0 - no risk    無風(fēng)險(xiǎn)
1 - low risk    低風(fēng)險(xiǎn)
2 - medium risk  中等風(fēng)險(xiǎn)
3 - high risk   高風(fēng)險(xiǎn)

MEDIA （媒質(zhì)）                 RISK（風(fēng)險(xiǎn)）
---------------------------------------------------
RAM          <storage>（儲(chǔ)存）      0 *&
Hard Drive     <storage>（儲(chǔ)存）      1 *&
Shared memory   <transfer>（傳輸）      1 *&
Removable disks  <transfer>（傳輸）      2
LAN          <communication>（通訊）  2 &
WAN          <communication>（通訊）  3

任何正確加密的媒質(zhì)的風(fēng)險(xiǎn)都是0。
*如果儲(chǔ)存媒質(zhì)是在一臺(tái)與網(wǎng)絡(luò)相連的計(jì)算機(jī)上時(shí)，風(fēng)險(xiǎn)度還要加1。
&如果可以通過物理途徑到達(dá)的話（computer/Lan），風(fēng)險(xiǎn)度也要加1。

所有媒質(zhì)的最高風(fēng)險(xiǎn)都應(yīng)該被解釋成執(zhí)行風(fēng)險(xiǎn)（向脆弱的機(jī)制說再見吧:）。高風(fēng)險(xiǎn)在實(shí)際中是不可接受的。媒質(zhì)的風(fēng)險(xiǎn)程度是否可被接受取決于RNG的輸出值（想想這在攻擊者眼中的價(jià)值吧）。除非在你的壁櫥里有許多的萬(wàn)能鑰匙，否則一本私人日記就足以應(yīng)付介質(zhì)風(fēng)險(xiǎn)了（譯者注：這里可能不太好了解。但就我的經(jīng)歷，國(guó)外用的日記本大多是帶鎖的。國(guó)內(nèi)也有這種日記本，不過好像比較貴）。有關(guān)工業(yè)機(jī)密的一定要采用零風(fēng)險(xiǎn)的RNG。雖然什么樣的風(fēng)險(xiǎn)是可以接受的往往取決于程序員，但是用戶應(yīng)該清楚地知道自己的選擇。

硬件的RNG需要有監(jiān)測(cè)能力。如果硬件發(fā)生了任何的物理修改，RNG就停止輸出。這可以防止外界探測(cè)信息熵集合狀態(tài)和輸出。同時(shí)，外界無法通過頻率，輻射，電壓或者其他由RNG運(yùn)行時(shí)產(chǎn)生的信息監(jiān)控硬件的運(yùn)轉(zhuǎn)。一旦上述的任何一項(xiàng)可被探測(cè)，對(duì)于集合或輸出來說都是一個(gè)危險(xiǎn)。所以，所有的RNG硬件都要適當(dāng)?shù)钠帘纹饋怼?br/>
軟件的執(zhí)行就微妙的多了。防范逆向工程始終是個(gè)大問題，除非可執(zhí)行文件發(fā)出的數(shù)字信號(hào)是在和操作系統(tǒng)一樣的層次上執(zhí)行的。否則，任何對(duì)逆向工程的防御措施只能是“緩兵之計(jì)”。所以，程序員一定要盡量減少軟件的風(fēng)險(xiǎn)因素（上面的風(fēng)險(xiǎn)系數(shù)表對(duì)逆向工程依然適用）。