 |  |
|
級別： 初級 Gary McGrawReliable Software Technologies 2000 年 4 月 01 日 在本系列的 第一部分中，Gary McGraw 和 JohnViega 討論了精確隨機數(shù)生成。在這一部分，即本系列的第二部分中，Gary和 John研究了隨機數(shù)的硬件源。這些源有時可以提供比全軟件解決方案更高的安全性保證（雖然我們也將處理基于硬件的隨機數(shù)發(fā)生器中的缺點）。 從本專欄的上一部分中，我們知道了隨機數(shù)通常會產(chǎn)生很重要的安全性后果。問題是確定性的機器很難實現(xiàn)隨機。最佳答案就是使用好的物理度量來生成隨機數(shù)（或至少是偽隨機數(shù)發(fā)生器的種子）。許多自然現(xiàn)象就具備這種條件。其訣竅就是它們必須有一些可測量的特性，而且行為至少要盡可能隨機（如果不能真正做到隨機）。（這種隨機性是在量子力學(xué)級別上提出的。還不知道隨機性真正是量子力學(xué)的固有部分，還是我們的科學(xué)理論還不夠好，不能預(yù)測我們應(yīng)該能夠預(yù)測的結(jié)果。）收集隨機性的真正硬件設(shè)備是基于測量諸如原子的放射性衰變或熱輻射中的波動（某些 Pentium III 處理器就測量后者）之類的事情。 在這一部分中，我們將研究隨機數(shù)的硬件源。這些源有時可以提供比全軟件解決方案更高的保證（雖然也有許多糟糕的硬件隨機數(shù)發(fā)生器）。我們確實意識到基于硬件的解決方案并不總是可行，只要這句話就夠了。例如，您也許希望將應(yīng)用程序分發(fā)給全球數(shù)以萬計的用戶，而且還需要每部臺式機上有好的隨機數(shù)。直到世界上每臺計算機都在硬件中安裝了隨機數(shù)發(fā)生器為止，總是需要一種盡可能接近真正隨機性的軟件。 在我們深入研究之前，我們需要考慮是否可能滿足這種隨機性需要。我們在上一部分中討論了傳統(tǒng)的偽隨機數(shù)發(fā)生器，而且討論了將它們用于注重安全性的用途上有多可怕。PRNG 算法也無法滿足需要。硬件（在 下面討論）是一個好的選擇，但是卻很昂貴且不易使用。 幸好，有一個折中方法。使用軟件執(zhí)行合理的隨機性作業(yè)，而不必求助于基于硬件的解決方案，這點是可能的。當(dāng)然，您需要牢記這一點：硬件始終可以比軟件做得更好，即使不是永遠(yuǎn)。我們將在下一部分中討論替代軟件解決方案。 真正的隨機數(shù)發(fā)生器是非確定的。那表示，作為旁觀者，應(yīng)該永遠(yuǎn)無法以任何一致性猜測到設(shè)備的輸出，即使您知道設(shè)備使用的算法。例如，如果設(shè)備輸出一系列 0 和 1，0 和 1 在任何特定輸出中出現(xiàn)的機會應(yīng)該相等。即使掌握了設(shè)備內(nèi)部工作的全部知識，任何猜中的可能性也只有 50% 左右（對于某些范圍的行為）。 在計算機上執(zhí)行非確定性事情的唯一方法是從一些自然的隨機過程中收集數(shù)據(jù)。我們最喜歡的一種方法涉及使用電子 Geiger 計數(shù)器，每次當(dāng)它檢測到放射性衰變時，它就會生成一個脈沖。衰變之間的時間是一個實足的、純粹的隨機部分。尤其是，沒有人可以預(yù)測到下一次衰變的時間大于還是小于自上次衰變以來的時間。那就產(chǎn)生了一位隨機信息。我們可能得到更多。 比如說，假設(shè)我們正在觀察某些我們期望每秒都發(fā)生衰變的材料，但衰變也許會前后相差十分之一秒發(fā)生。與其比較兩次衰變之間的時間，不如記錄衰變的時間，并且使用獨立數(shù)字位作為獨立的十進(jìn)制隨機數(shù)。也許百分之一秒是一個數(shù)字位，而千分之一秒是另一個數(shù)字位。我們可以根據(jù)計時器的精確程度來按比例抽取數(shù)字。此技術(shù)也許夠好，也許不夠好；在沒有嘗試使用它并對數(shù)據(jù)進(jìn)行一些統(tǒng)計分析的情況下，很難下定論！如果表示百分之一秒的數(shù)字幾乎總是 0，而表示偶爾發(fā)生的數(shù)字是 1，將會怎么樣？那不是非常隨機。如果我們的時鐘沒有那么強的功能，而且表示千分之一秒的數(shù)字始終是均勻的，或者至少很可能是均勻的，將會怎么樣？ 實際上，這種問題是經(jīng)常遇到的。所有事都可能出錯，從而使數(shù)據(jù)產(chǎn)生偏差。另一方面，如果我們保守一點，嘗試以保守方式從衰變中抽取出數(shù)據(jù)的單一位，就很少有機會產(chǎn)生測量引起的偏差。不幸的是，如果有一些偏差，很難斷定偏差有多大。我們關(guān)心的是平均信息量（真正的隨機性）中有多少位是真正可用的。我們希望能夠以某些精度測量該數(shù)字。為使我們的工作更簡單，我們將只研究一位。 任何源都有潛在的偏差。我們檢查了一種流行的硬件發(fā)生器，發(fā)現(xiàn)它返回 1 的概率是 49.81%，這表示發(fā)生器的偏差非常小，趨向于零?；蛟S基本自然現(xiàn)象的偏差也是這樣，但通常我們的測量工具（尚有不足之處）有錯誤。
我們?nèi)绾蜗?？一種常用方法是同時 XOR 位。如果某一位是 0 的概率是 0.5 + c，那么當(dāng)我們同時從一個發(fā)生器中 XOR 兩位時，概率就變成 0.5 + 2c2。如果我們 XOR 更多位，概率就會越來越接近均勻。當(dāng)然，概率永遠(yuǎn)不會達(dá)到均勻，但每個 XOR 操作都會消除許多偏差；您只需確定愿意接受多少偏差。由于我們使用兩位來創(chuàng)建一個偏差，我們就帶來了新問題，因為我們現(xiàn)在生成隨機位的速度只有以前的一半。 上述消除偏差的技術(shù)的一個潛在問題是即使在執(zhí)行了 XOR 之后，兩個連續(xù)位（或甚至是兩個不相鄰的位）之間有相關(guān)性，而攻擊者也許會利用這一點。實際上，XOR 可以幫助消除任何偏差，但它放大了位之間的相關(guān)性。 請考慮我們給出的用于從計時事件中抽取單一位的技術(shù)。如果我們使用同樣的技術(shù)嘗試從敲擊鍵盤中獲取隨機性，那會怎么樣？基本思路是記錄兩次擊鍵期之間的持續(xù)時間。如果某段持續(xù)時間大于前一段持續(xù)時間，則生成 1；否則生成 0。此技術(shù)在需要生成密鑰的程序中很常見，并且會使那些讓他們敲擊鍵盤幾分鐘也不會抱怨的用戶坐在計算機前。例如，某些版本的 PGP 就使用此技術(shù)（其它版本則利用鼠標(biāo)事件執(zhí)行類似的功能）。 但并非一切都能在意料之中。這里就是可能出錯的地方。按鍵之間的計時并不完全是隨機現(xiàn)象。我們已經(jīng)看到了向用戶提供需要反復(fù)輸入的樣本文本的程序。問題是某些鍵比其它鍵更易于觸到。如果正在輸入單詞“kiss”，輸入“i”和“s”之間的時間幾乎總是大于輸入兩個“s”字符之間的時間。產(chǎn)生一個位的事件肯定與產(chǎn)生下一個位的事件相關(guān)，從而導(dǎo)致最終偏差的增加。 我們?nèi)绾蜗@種相關(guān)性呢？一個解決方案就是采用多個隨機數(shù)據(jù)源，并且將數(shù)據(jù)流 XOR 到一起。按慣例，人們使用偽隨機流作為數(shù)據(jù)的第二來源。當(dāng)然，如果某人可以破壞偽隨機流，那么仍可以辨別出相關(guān)性（而且可以使用相關(guān)性來對付您，就象我們將要演示的）。 怎么回事？誰會關(guān)心隨機數(shù)發(fā)生器中是否有一點偏差？在理論上，偏差會使攻擊者的工作變得更容易。然而，實際上，小的偏差并不太可能導(dǎo)致系統(tǒng)破壞。例如，Bruce Schneier 留意到即使發(fā)生器產(chǎn)生的數(shù)字中 55% 都是 0，每位仍然能產(chǎn)生 0.99277 位的平均信息量。那意味著，精確導(dǎo)向地強力搜索 168 位密鑰，平均起來，2,109 次嘗試中會成功一次，而不是如果不存在偏差時所預(yù)期的 2,111 次嘗試中成功一次。但是，萬一人們可能犯錯，大多數(shù)人寧愿犯安全性方面的錯誤。 一種通過消除偏差而解決上述所有問題的常用解決方案是對隨機字節(jié)流應(yīng)用某種算法，該算法可以自然地消除任何統(tǒng)計趨勢。通常都使用壓縮算法和散列函數(shù)。
偏差的另一個源（特別隱秘的一種）是在外部現(xiàn)象中，即攻擊者有一些控制，或者有機會進(jìn)行復(fù)制。如果攻擊者對所測量現(xiàn)象的影響程度足夠產(chǎn)生重大的偏差，那么必將發(fā)生一個攻擊高潮，尤其是在一段很長的時期內(nèi)。例如，如果將網(wǎng)絡(luò)流量用作測量的現(xiàn)象，那么這個攻擊就很可行。攻擊者可以偷偷地控制到您機器的網(wǎng)絡(luò)流量，并且以這種方法產(chǎn)生很大的偏差。應(yīng)該避免這些容易受到控制或影響的現(xiàn)象。另一種技巧就是從 WAV 文件或聲卡提取背景噪聲（通常沒有連接話筒）。許多時候，這些源都沒有很多平均信息量；如果它們受到攻擊，那么就會變得毫無價值。同樣，實際上偏差可能是不相關(guān)的，但應(yīng)該防患于未然。 也許常用的隨機數(shù)最佳來源是測量放射性衰變。它根本不易于產(chǎn)生偏差，而是會帶來相對較小的自然偏差。另一個好的來源是測量半導(dǎo)體二極管散發(fā)的熱噪聲，然而如果得不到正確防護，附近的硬件可能會使輸出產(chǎn)生偏差。 生成隨機數(shù)的幾種硬件設(shè)備都是商業(yè)用的。也許最廣泛使用的設(shè)備是 ComScire QNG（請參閱 參考資料 ），它是使用并行端口連接到 PC 的外部設(shè)備。人們都認(rèn)為此設(shè)備是經(jīng)過精心設(shè)計的，而且在其輸出的統(tǒng)計分析方面做得極其好。它可以在每秒鐘生成 20,000 位（2,500 字節(jié)），這對于大多數(shù)注重安全性的應(yīng)用程序來說已經(jīng)足夠了。即使發(fā)生器產(chǎn)生的數(shù)據(jù)還不夠時，發(fā)生器的數(shù)據(jù)可以預(yù)先存儲，或者可以使用多個發(fā)生器。這個包的另一個好處是：當(dāng)生成數(shù)字時，設(shè)備驅(qū)動程序會對它們進(jìn)行統(tǒng)計測試，而且如果開始生成在統(tǒng)計上非隨機的數(shù)據(jù)，它會返回錯誤。在撰寫本文時，該設(shè)備價值 295 美元，可以從 ComScire 購得。Robert Davies 撰寫的關(guān)于此發(fā)生器的無偏見評論（請參閱 參考資料）聲稱它“看來是唯一為統(tǒng)計目的而特別設(shè)計的發(fā)生器，而且制造商花了一定的精力來了解最終產(chǎn)生的數(shù)字上的偏差和相關(guān)性的作用?！? 一種類似設(shè)備來自 Tundra 的 RBG 1210（請參閱 參考資料）。它們的設(shè)備有時會產(chǎn)生小的偏差，然而在別的方面卻通過了許多統(tǒng)計測試。明確建議使用轉(zhuǎn)換來消除偏差。此產(chǎn)品過去常常有一些裝配問題而通常會導(dǎo)致徹底失效，但相信它們會得到修復(fù)。 RBG 1210 是 PC 的內(nèi)部卡，它有可變采樣率。如果采樣過多，連續(xù)的位就會有很高的相關(guān)性，因為內(nèi)部硬件不會很快更改輸出以符合采樣率。但是，此設(shè)備將會每秒產(chǎn)生最多 160,000 位（20,000 字節(jié)）。 另一種很好玩的資源是 lavarand（請參閱 參考資料 ）。這種熱鬧的方法依賴于一組正在工作的 Lava Lite 燈中固有的混亂。一架數(shù)字照相機安置在六盞 lava 燈前，用于每隔一段時間拍攝一張照片。所產(chǎn)生的“噪音”數(shù)字圖像然后被以密碼方式散列到 140 位的種子值中。然后，將這個種子值饋送給出色的偽隨機數(shù)發(fā)生器（我們將在下一部分中討論）。但是，不要在注重安全性的代碼中使用 lavarand！請記住，每個人，包括壞蛋們，可以在 Web 上看到 lavarand 序列。SGI 并不銷售 lavarand 安裝程序。如果您遵循 lavarand 網(wǎng)頁上細(xì)致、詳細(xì)的建議，親自構(gòu)建 lavarand 并不困難。 但是，lavarand 并不希望與我們討論過的其它設(shè)備競爭。大多數(shù)安裝都很昂貴（因為近來 lava 燈的高價），并且發(fā)生器每秒只輸出 550 位（略少于 70 字節(jié)）。這樣一個設(shè)備對空間要求很高，需要一盞燈和一架照相機。最后，它很容易失敗，如壞掉的硬件。要解決后一個問題，SGI 使用六盞燈作為自動計時器，其中三盞始終打開。系統(tǒng)中每樣?xùn)|西都工作得格外好，只是帶寬相當(dāng)?shù)?。問題的部分原因是需要拍攝和掃描照片。但是，問題的大部分是因為數(shù)據(jù)很可能有統(tǒng)計偏差，因此大量精力花在了使用七個密碼散列和一個相當(dāng)慢（但非常好）的偽隨機數(shù)發(fā)生器來消除此類問題上。 當(dāng)去年 Intel 宣布他們將開始在其芯片組中添加基于熱能的硬件隨機數(shù)發(fā)生器，而且基本上不會增加客戶的成本時，許多安全性社區(qū)都變得很興奮。當(dāng)著名的密碼人員宣稱該發(fā)生器是隨機數(shù)的優(yōu)秀來源時，人們變得更興奮了。迄今為止，已經(jīng)交付了一些帶有硬件 RNG 的 CPU。所有帶 8xx 芯片組（810 或更高）的 Pentium III 都應(yīng)該擁有此功能。由于我們熟悉帶這種發(fā)生器的硬件，當(dāng)此功能可用時，我們會給您一些代碼供您使用。（我們已經(jīng)聽說一個令人不愉快的謠言：RNG 正遭到長期禁止，因為人們對它失去了興趣。我們希望這最終只是一個謠言。） 還有其它鮮為人知的產(chǎn)品用于在硬件中生成隨機數(shù)。在 Web 上有幾個資源可以向熟悉構(gòu)建硬件的人們演示如何廉價構(gòu)建自己的隨機數(shù)發(fā)生器（請參閱 參考資料）。
一旦擁有了隨機數(shù)的硬件源，您應(yīng)該問：“我的隨機數(shù)夠隨機嗎？”答案也許并不總是“是的”，您當(dāng)然想要知道什么時候發(fā)生這種情況。在開始使用他人的發(fā)生器之前先進(jìn)行測試，一點不為過。但是當(dāng)構(gòu)建自己的隨機數(shù)發(fā)生器時，認(rèn)真測試就尤其重要（但是，這樣做很容易擾亂我們的建議，我們建議購買一個高質(zhì)量的發(fā)生器，而不是構(gòu)建一個）。 現(xiàn)在有許多統(tǒng)計測試。它們采用各種形式，但共同思路是它們?nèi)家越y(tǒng)計方式檢查來自發(fā)生器的數(shù)據(jù)流，嘗試發(fā)現(xiàn)如果數(shù)據(jù)真是隨機的，是否可以在還沒有顯示的數(shù)據(jù)中找到任何模式。ComScire 設(shè)備在您使用它時會執(zhí)行這些測試，如果測試不成功，它會在運行時失敗。那是種很好的安全措施，但實際上，人們通常（也許很少）只在第一次使用之前預(yù)先檢查流，以確保發(fā)生器正在開足馬力運行。 確保數(shù)據(jù)流隨機性的最廣為人知的測試套件就是 George Marsaglia 的 DIEHARD 軟件包（請參閱 參考資料 ）。它對數(shù)據(jù)流執(zhí)行無數(shù)的測試。另一個適合此類測試的合理軟件包是 pLab（請參閱 參考資料）。這些測試做什么或者不做什么其實并不重要；我們只是必須相信它們正在測試發(fā)生器的質(zhì)量，并且認(rèn)真聽從我們正在使用的發(fā)生器是否沒有通過測試。 在構(gòu)建用于隨機數(shù)的硬件設(shè)備時，有一些諸如 DIEHARD 這樣的測試套件也捕捉不到的缺陷。例如，某些類型的偏差不會在大多數(shù)統(tǒng)計測試中顯示出來。由于這個原因，我們強烈建議：如果有可能的話，使用信譽好的商業(yè)硬件源來生成隨機數(shù)，而不要構(gòu)建自己的硬件源，因為您也許最終會不正確地測試您的發(fā)生器。如果您仍認(rèn)定需要親自測試發(fā)生器，我們建議您閱讀文章“True Random Number Generators”（請參閱 參考資料）。
在前兩部分中，我們展示了隨機數(shù)生成的兩個極端。一個極端是傳統(tǒng)的偽隨機數(shù)發(fā)生器，它很容易被攻破，因此不適合注重安全性的應(yīng)用程序。另一個極端是基于硬件的隨機數(shù)發(fā)生器，它可以執(zhí)行非常好的性能，但通常由于其昂貴的價格或缺少普遍可用性而不實用。 下次，我們將研究折中方法，在此方法中，隨機數(shù)確實很好，即使它們是在不使用硬件設(shè)備的情況下生成的，即使它們的生成速度有一點慢。我們將討論一類功能更加強大的偽隨機數(shù)發(fā)生器，并討論如何在不借助于特殊硬件的情況下從好的來源中收集隨機性。
| ||||||||||||||||||||||||||||||||
