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


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



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

----| 介紹

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


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

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

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

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


1.0) 概述

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

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

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

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


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

下面的例子演示了一個更加實際的信息熵的收集過程。保留X-坐標和Y-坐標的最后四位(因為它們最重要),和采樣得到的時間作異或運算，并把它們隨意排列如下：

   X    Y     時間    異或后
  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

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

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

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

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


1.2 信息熵的估算

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

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

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


1.3) 信息熵的集合

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

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

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

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

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

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

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

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

1.4）輸出函數(shù)

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

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

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

1.5）執(zhí)行

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

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

0 - no risk    無風險
1 - low risk    低風險
2 - medium risk  中等風險
3 - high risk   高風險

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

任何正確加密的媒質(zhì)的風險都是0。
*如果儲存媒質(zhì)是在一臺與網(wǎng)絡相連的計算機上時，風險度還要加1。
&如果可以通過物理途徑到達的話（computer/Lan），風險度也要加1。

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

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