- 曙海教育集團論壇 (http://www.adgdgn.cn/bbs/index.asp)
-- 硬件測試 (http://www.adgdgn.cn/bbs/list.asp?boardid=71)
---- 密碼學里的隨機數發生器 (http://www.adgdgn.cn/bbs/dispbbs.asp?boardid=71&id=2711)
-- 發布時間：2010-12-17 11:02:19
-- 密碼學里的隨機數發生器
Volume 0x0b, Issue 0x3b, Phile #0x0f of 0x12
|=--------=[ CRYPTOGRAPHIC RANDOM NUMBER GENERATORS ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Author: DrMungkee <pub@drmungkee.com> ]=--------=|
|=------------------------------------------------------------=|
|=----------=[Translator: winewind <winewind@163.com>]=-------=|
密碼學里的隨機數發生器
----| 介紹
對于密碼系統的安全性來說，每個組件都是很重要的。一個組件設計的失敗可能使其他所有的組件崩潰。密碼隨機數常常被用作密鑰，補充信息，輔助信息和初始化向量。對每一個組件來說，使用一個好的隨機數發生器（RNG）是必要的。利用計算機行為的可預測性,可以人為的制造很多復雜因素。本文的范圍涵括了隨時數產生器的設計，執行和分析。將要涉及的隨機數發生器(RNG)包括：NoiseSpunge, Intel 隨機數發生器（Intel RNG），Linux下的“/dev/random”和Yarrow。
----| 關鍵詞：
RNG - 隨機數發生器（Random Number Generator）
PRNG - 偽隨機數發生器（Pseudo Random Number Generator）
信息熵（entropy） - 不可預知信息（Unpredictable information）
冗余信息（redundancy）- 可預知信息（Predictable or probabilistic information）
（譯者注：entropy一詞源于物理，是“熵”的意思。在信息技術中引入，從而有了“信息熵”的說法。“熵”的特性：在封閉系統中，系統的熵只會增加或保持不變，系統的平衡點是熵最大的時候。無線電中常翻譯成“平均信息量”。我也不知道這里用信息熵的說法是否便于理解。如果覺得別扭，就理解成一種信息好了）
（譯者注：這里我加入一段引來的文章，可能會讓大家對這個名詞了解得更好：現代信息學的基礎是信息熵理論，即對被傳送信息進行度量的一種平均值，單位是比特。四十年代，現代信息論創始人、美國貝爾實驗室科學家閃農（C．Shannon）發明了信息熵理論，由此提出了數據優化編碼、輸入輸出效率、通訊傳遞渠道效率、多余度和數據壓縮等一系列信息科學基礎理論和技術。信息熵是信息產業的地基。比如，不管計算機硬件軟件如何更新換代，英文的字符平均信息熵（靜態信息熵）是4．03比特，因而，處理和儲存英文數據的每個字符的編碼不能少于5比特；中文的漢字平均信息熵是9．65比特，因而，處理和儲存中文數據的每個字符的編碼不能少于10比特。）
1.0) 概述
設計一個隨機數發生器(RNG)需要考慮各種因素。在白噪音環境中（譯者注：在一定帶寬內，在各個頻率上，各種噪音的強度都是一樣的），輸出必須是不可識別的。輸出的任何一部分都是不可預知的。而且基于已知的結果，無法推算出上一步（不可逆）和下一步的結果。如果一個隨機數產生器不能遵照這個標準，那么產生的密碼是不安全的。
1.1) 信息熵（entropy）的收集：
為了滿足第一條和第二條要求，為這些信息熵找尋好的來源（信息源）就成了一個首選任務。這些信息源對于攻擊者必須是不可監測的。而且任何對信息源的操作對攻擊者來說都是不可知和無法重復的。
鼠標的移動常常被用作信息熵的一種。但是如果RNG不能正確的處理信息熵，將會產生大量的冗余信息。舉個例子，鼠標移動的時間間隔是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
這是一個好辦法，因為從各坐標得到的四位數代表了在16像素平面上的任意方向（譯者注：上面的數據表明，這個范圍對紀錄鼠標的運動已經足夠大了），而不是 256*256平面上65536種移動方向。選用時間是因為雖然它們是連續的，但是它們的最后八位在CPU時鐘周期內非常頻繁的變化,這些比特位是無法人為預料的。異或運算用于合并兩方面的信息熵。在合并數字并且保留各比特位的獨立上，異或是個好辦法：）
最常見的信息源包括用戶的人為反應或某種經過排列變形后的高頻時鐘的序列。把上面兩種合二為一得到的結果往往就是我們所需要的。用高精度采集用戶觸發事件的反應時間（擊鍵，磁盤輸入/輸出，中斷，鼠標點擊）的方法有其優越性，因為用戶個體行為和精確的時間是不可預知的。
有些信息看起來是足夠隨機的，但實際上未必。有時可以把網絡的輸運情況作為一種信息源，但我們并不推薦這樣做，因為這種信息畢竟還是可以由某些外來因素控制的。另一個缺點是使用毫秒精度的時鐘：對于比較高的要求，這種刷新頻率顯得的太慢了。
在討論信息熵收集方法缺點方面，這里有一個不錯的案例：Netscape公司使用的SSL加密協議是可破解，它并沒有使用真正的RNG。（譯者注：可以在下面的網址找到介紹 http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html）Netscape公司標志進程和父進程時使用時間和日期，并把它們當作唯一的信息源。在win9x中進程標志通常都是由一個小于100的值（每增加一個新進程就加一）和win9x第一次啟動時的時間日期作異或運算得到。雖然由哈希函數得到的結果看起來是隨機的，實際上猜測出那個值，計算并且得到正確的結果并不是件難事。如果可利用的信息熵非常有限，那么輸出結果是不是真的隨機也就不是很重要了（好像有點無奈的意思
）。1.2 信息熵的估算
我們不能忽視對收集到的信息熵總數的估算。這一步很重要。否則隨機數產生器輸出結果中信息熵的數量有可能超過輸入的信息熵的數量。根據相應的系統參數，我們可以給各個信息源賦相應的值。比如，對于鍵盤活動，不管我們能夠收集的信息熵總數是多少，我們都可以假設所有鍵盤活動產生的信息熵的大小都是4比特的。如果RNG在文件服務器上，并且把磁盤輸入/輸出作為信息源，我們可以根據某時刻正在訪問磁盤的用戶數相應的估計信息熵，而不是根據訪問序列。如果基于后者，則可能產生多余的信息。對信息熵大小的估算不一定要和輸入或輸出的大小一樣。這條準則在今后的計算中能起到安全預防的作用。
對信息熵的估算還有其他的方法。如果信息源超過一定時間間隔后還沒有給我們提供數據，使用統計的方法計算偏差會獲得更好的效果。我們可以從buffer收集大量的數據信息，經過壓縮，得到壓縮比的值。相對于之前輸入的大量數據，統計測試表明，最后一次輸入的數據對于檢驗當前輸入數據整體屬性起不到什么作用。但是對于RNG來說，則意味著可以把這些只能增加統計概率的輸入數據舍棄。
最好的辦法莫過于多試幾次。在估算信息熵值時用一種方法往往是不夠的。信息源的情況是復雜的，得到的信息熵也是多種多樣的。可是在實際中，對所有的信息熵的大小往往賦同一個值。因此在做這種假設之前，必須仔細的分析一下。多嘗試幾個值是明智的選擇。而最小的值往往是最準確的。
1.3) 信息熵的集合
沒有任何信息源可以說是完美無缺的。確切點說，在計算機上是這樣。這就是為什么我們在buffer（信息熵的集合）收集了信息之后還要進行一些處理。收集完畢后，信息熵就被輸入到一個集合里。這個集合必須和輸入有以下的關系：要知道包含元素的個數，把最后一次輸入合并到之前收集的數據中并保持其一致性。另外，拋開那些收集到的信息熵的屬性不論，集合還要為這些數據提供一個至少看起來隨機的狀態（相似的輸出在這個集合里也應該是看起來隨機的）。
對于某個集合狀態，處理集合內容時（這里指把所有元素合并起來），既不能減少元素，也不能添加元素。如果經過某個合并函數的處理，集合變大了，那么必須保證這對信息熵的估算是沒有影響的。只有那些負責收集信息熵的函數才能改變信息熵的大小。而且這些收集函數是分開作用的，彼此獨立。
最好的合并函數是哈希算法（譯者注：又稱散列法）。哈希算法能夠接受任意大小的輸入，它的大范圍輸出可以反映信息熵合并的速度，并且這個算法的輸出是不確定的。為了保護那些合并后的信息熵（譯者注：保證沒有信息丟失），哈希函數輸入的大小不大于輸出的。也就是說，如果哈希函數的輸出是160位的，那么之前的輸入最多160位。如果哈希函數用于密碼處理上是安全的（事實上的確如此），那么輸出的信息熵的個數應該和輸入的一樣。但是如果輸出的多于輸入，并不能認為信息熵集合里的態一定增加了。
處理大集合有以下幾種途徑：一種方法是把這個集合線性hash（雜化）。使用這種方法，你可能需要一個buffer保存最近的一次輸入。hash從buffer的尾部開始，一次只hash一塊（塊的大小和輸出的大小相同）。每次把當前輸出和前一個塊的hash結果作異或運算，以次保證整個集合只被最近的一次輸入作用，而不會改寫以前的結果。這只是一個例子。不管你選擇什么樣的處理方式，必須保證這種方式遵守前面所說的各條準則。
另一個處理大集合的方法是“multiple hash(多樣雜化)”，使集合的內容互相影響。一個常見的用途就是用于處理包含“不可操作的信息熵”的集合。一旦這個集合滿了，它就會被hash并用于更新另一個集合。更新的方式可以是更新hash的關系，也可以是直接作異或運算。這樣盡可能多的集合就串聯了起來。為了避免丟失已有的信息熵，一些集合只有在它們的父集合（更新這些集合的集合）被更新若干次（譯者注：更新次數事先定義好的）后才能被操作。比如，只有當第一個hash集合被更新了8次后，下一個集合才能被更新。只有下一個集合被更新滿了3次，它才能用于hash第三個集合。在這種方法里，第三個集合包含了經過24次hash的信息熵。這樣保留下來的原始信息熵變少了（受雜化關系的限制）但是這些信息熵的性質卻更好了。因為第三個集合里的信息源完全基于24次輸入的信息熵。
向一個集合中輸入信息熵往往稱為更新或播種。這種信息熵的集合和基于它自身構建的輸出函數實際上是一個PRNG。在收集信息熵的過程中獲得的真正的隨機種子才是得到RNG的原因。只要輸入了一個好的信息熵，RNG就產生一個無界區域（沒有輸出模式）。這和PRNG正好相反。相對于RNG的無界區域，后者是從一個半確定的點開始，重復以前的所有輸出，并且重復的順序和RNG是一樣的。
信息熵的集合對于防范攻擊者推算RNG以前的輸出和以后的輸出結果至關重要。對RNG的攻擊就是基于三部分：對信息熵集合性質的了解，信息熵的輸入和以前的輸出結果。要防止別人了解集合當前的狀態，就要對以后的輸出結果做一些處理。因此，集合必須不時地做一些大的變動，刪除一部分或是全部的信息熵。這個過程叫做再播種。再播種，總是（譯者注：用逗號隔開是為了強調），在輸出之前用一些新的信息熵替換那些已經被刪除的。如果沒有上面的替換，這個集合的安全性就很成問題了。RNG不需要再播種，但是如果沒有這步，就必須不停的添加信息熵的輸入，添加的速度還要高于輸出的。
并不是任何時候都要再播種的。只有當未用過的信息熵積累了足夠多并且占了集合空間的一大部分時才使用再播種。要注意的是，對集合中信息熵的估算要隨著輸入數據的大小作相應的調整。再播種不能頻繁的使用。是否使用它的唯一根據就是隨機數生成器輸出的比特位數和整個集合的大小。當集合里95%的信息熵都已經輸出時采用再播種，這是一個比較適當的頻率。這里我們假設信息熵的輸入是在RNG輸出的空隙間完成的。如果不是這樣，那么使用再播種的次數有可能應該更多一些。在輸出空隙間輸入的信息熵越少，攻擊者就越容易找到輸出方式的蛛絲馬跡，從而推算出上一次輸出的結果（這樣循環往復，一個鏈式的逆向推算就有可能成功地得到攻擊者想要的東西）。（譯者注：這里我們并不規定兩次輸出之間只能有一次輸入。相反，輸入的數據應該多于輸出。這樣，可以想象，在集合里用不到的數據會越來越多。等他們多到一定程度時，如上文的95%，一次性的替換掉。這就是一次的再播種。）
1.4）輸出函數
RNG的輸出函數必須是單向的。單向的意思是輸入的數據經過函數處理可以得到輸出，但是根據輸出的數據無法計算出輸入的原始數據（譯者注：就是不可逆啦，饒舌）。單向的hash函數是一個非常好的選擇。更復雜的方法是把集合中的一部分元素作為key data（譯者注：不好意思，我一時還想不出什么好的詞），使用對稱加密算法，對另一部分加密，并且輸出密文。壓縮-解壓縮也是一個效率很高的單向函數。為了達到目的，我們可以把集合中一部分元素當作PRNG的種子，生成多種輸出（根據PRNG的種子大小而定）。然后把這些輸出統統放進一個雜化函數得到結果。這樣做保證了效率，因為處理時很多中間態（解壓縮）hash的結果都是一樣的，真正起作用的只是解壓縮前的那個初始態。
RNG每次輸出時，對它信息熵的估算都要隨輸出的大小而減少。這樣做的前提是假設輸出的數據都是由信息熵組成。由于輸出的信息熵仍然保留在集合里，這些東西現在就成了冗余信息，也不該再把它們當作信息熵了（在集合里）。如果集合的大小是512位，且每次輸出信息熵的大小是160位，那么三次輸出之后，基本上所有的信息熵都被hash了，這個集合也就需要再播種了。
在處理信息熵集合時，有一個幾乎不可能解決的問題：我們沒辦法確定信息熵的哪些位是要輸出的，哪些不是。緩解這個問題最好的辦法是：即便你看到了RNG的輸出結果，我們也根本不讓你知道哪些信息熵被用了幾次。（譯者注：看起來有點掩耳盜鈴，但的確管用。我偷偷地用，用幾次誰也不知道。感覺差不多了，我就再播種了。神不知鬼不覺
）當一次輸出完成后，集合的態發生變化，重新排序。這樣，在既不添加信息熵也不再播種的情況下，RNG的輸出結果也不會重復。集合的態的重新排序必須通過單向函數完成，而且輸出函數必須滿足前面提到的各條原則。只要處理的過程不違反前面的規定，我們認為集合里信息熵的大小在排序前后總是一致的。1.5）執行
如果執行時不順利的話，我們前面所作的所有努力都是白費。這里關于執行我們要談三個方面的東西：媒質，硬件/軟件和輸出的使用。
在未加密狀態，儲存媒質和通信媒質各占了一個風險。下表列出了各種媒質的風險程度。對于風險程度的比例說明是這樣的：
0 - no risk 無風險
1 - low risk 低風險
2 - medium risk 中等風險
3 - high risk 高風險
MEDIA （媒質） RISK（風險）
---------------------------------------------------
RAM <storage>（儲存） 0 *&
Hard Drive <storage>（儲存） 1 *&
Shared memory <transfer>（傳輸） 1 *&
Removable disks <transfer>（傳輸） 2
LAN <communication>（通訊） 2 &
WAN <communication>（通訊） 3
任何正確加密的媒質的風險都是0。
*如果儲存媒質是在一臺與網絡相連的計算機上時，風險度還要加1。
&如果可以通過物理途徑到達的話（computer/Lan），風險度也要加1。
所有媒質的最高風險都應該被解釋成執行風險（向脆弱的機制說再見吧:）。高風險在實際中是不可接受的。媒質的風險程度是否可被接受取決于RNG的輸出值（想想這在攻擊者眼中的價值吧）。除非在你的壁櫥里有許多的萬能鑰匙，否則一本私人日記就足以應付介質風險了（譯者注：這里可能不太好了解。但就我的經歷，國外用的日記本大多是帶鎖的。國內也有這種日記本，不過好像比較貴
）。有關工業機密的一定要采用零風險的RNG。雖然什么樣的風險是可以接受的往往取決于程序員，但是用戶應該清楚地知道自己的選擇。硬件的RNG需要有監測能力。如果硬件發生了任何的物理修改，RNG就停止輸出。這可以防止外界探測信息熵集合狀態和輸出。同時，外界無法通過頻率，輻射，電壓或者其他由RNG運行時產生的信息監控硬件的運轉。一旦上述的任何一項可被探測，對于集合或輸出來說都是一個危險。所以，所有的RNG硬件都要適當的屏蔽起來。
軟件的執行就微妙的多了。防范逆向工程始終是個大問題，除非可執行文件發出的數字信號是在和操作系統一樣的層次上執行的。否則，任何對逆向工程的防御措施只能是“緩兵之計”。所以，程序員一定要盡量減少軟件的風險因素（上面的風險系數表對逆向工程依然適用）。