原文鏈接，介紹如何在Linux系統(tǒng)中確保隨機(jī)數(shù)生成器具有良好的隨機(jī)性。Linux系統(tǒng)本身是確定性的，如何生成不確定的隨機(jī)數(shù)呢？請(qǐng)看下文。如發(fā)現(xiàn)錯(cuò)誤，請(qǐng)留言或者發(fā)送郵件到zwzm85@gmail.com。未經(jīng)授權(quán)，請(qǐng)勿轉(zhuǎn)載。
在構(gòu)建安全系統(tǒng)時(shí)，一個(gè)隨機(jī)數(shù)的來(lái)源是必備品。缺少它們，大多數(shù)加密系統(tǒng)都會(huì)奔潰，雙方通訊得私密性和真實(shí)性也會(huì)被顛覆。比如，你在瀏覽https://blog.cloudflare.com這個(gè)鏈接，那么你使用的SSL連接就需要隨機(jī)數(shù)來(lái)確保安全（它們被用于建立安全連接）。
我們已經(jīng)在上篇博客中寫(xiě)過(guò)為什么安全系統(tǒng)需要隨機(jī)數(shù)，但是從計(jì)算機(jī)中獲取隨機(jī)數(shù)真的很難。這篇博客探尋Linux內(nèi)部的隨機(jī)數(shù)生成器，看看它是如何克服在一個(gè)完全不隨機(jī)的機(jī)器上生成隨機(jī)數(shù)的難題。
CloudFlare的服務(wù)器需要優(yōu)質(zhì)的隨機(jī)數(shù)來(lái)源以完成身份驗(yàn)證和確保SSL中的完美向前完全性。但是，從內(nèi)在層面來(lái)看，我們所使用的計(jì)算機(jī)都是確定性的機(jī)器，它們服從指令而且被要求按照可預(yù)測(cè)的方式來(lái)執(zhí)行那些指令。完全沒(méi)有內(nèi)置不確定性和不可預(yù)測(cè)性：沒(méi)有簡(jiǎn)單的方法讓計(jì)算機(jī)去擲硬幣或者骰子。想在計(jì)算機(jī)中獲取隨機(jī)性，你必須尋求外部世界的幫助。
消費(fèi)者計(jì)算機(jī)和移動(dòng)設(shè)備都有很多傳感器，它們可以提供不可預(yù)測(cè)的輸入。如果足夠仔細(xì)的測(cè)量，用戶鍵盤(pán)敲擊時(shí)間和鼠標(biāo)移動(dòng)軌跡都具有一定程度的隨機(jī)性。麥克風(fēng)和攝像頭的噪聲也可以提供很多的隨機(jī)性。移動(dòng)設(shè)備甚至有更多的隨機(jī)源，包括無(wú)線信號(hào)的波動(dòng)、運(yùn)動(dòng)傳感器和GPS信息。
最需要隨機(jī)數(shù)的服務(wù)器上并沒(méi)有這些傳感器。特別是有些服務(wù)器還是運(yùn)行在虛擬環(huán)境中，連精確的系統(tǒng)時(shí)鐘可能都不能訪問(wèn)。對(duì)于CloudFlare的服務(wù)器，我們目前依賴(lài)Linux操作系統(tǒng)內(nèi)置的隨機(jī)數(shù)生成器。
Linux是世界上最受歡迎的操作系統(tǒng)之一。從世界上許多最大型的網(wǎng)站（Google，F(xiàn)acebook，Amazon和Apple等等）的web服務(wù)器和數(shù)據(jù)中心，到臺(tái)式機(jī)（Ubuntu，Chrome OS等等），再到嵌入式設(shè)備（智能電視，安卓等等），Linux都可以成為它們的操作系統(tǒng)。CloudFlare的軟件也構(gòu)建在Linux操作系統(tǒng)內(nèi)核的堅(jiān)實(shí)基礎(chǔ)之上。
Linux本身提供一個(gè)隨機(jī)數(shù)服務(wù)，這樣任何程序都可以在任意時(shí)間獲取隨機(jī)數(shù)。很幸運(yùn)，Linux是開(kāi)源軟件，我們可以通過(guò)閱讀代碼了解其工作原理。并且驗(yàn)證它可以為我們的加密提供合適的隨機(jī)數(shù)來(lái)源。
熵和隨機(jī)性
并不是所有的隨機(jī)性都是相同的。隨機(jī)性有兩種：均勻性和不可預(yù)測(cè)性。如果運(yùn)行足夠長(zhǎng)的時(shí)間后，所有的數(shù)字出現(xiàn)得很均勻，那么這個(gè)隨機(jī)數(shù)生成器提供了‘均勻的’輸出。那對(duì)于隨機(jī)過(guò)程建模很有用，但是對(duì)于安全來(lái)說(shuō)不夠好。
對(duì)于計(jì)算機(jī)安全，隨機(jī)數(shù)需要很難被猜出：它們需要是不可預(yù)測(cè)的。數(shù)字可預(yù)測(cè)性被量化為熵。
一個(gè)公正的擲硬幣提供一位熵值：硬幣正面或反面著地的概率一樣（可以被想成0和1）。因?yàn)楦怕氏嗟?，所以硬幣的‘輸出’不存在可預(yù)測(cè)性。我們稱(chēng)它提供一位熵值。
一個(gè)不公正的擲硬幣提供不足一位熵值，因?yàn)槿绻阒榔蛐詴?huì)更加容易猜到結(jié)果。擲一個(gè)兩面都是正面的硬幣不提供任何熵，因?yàn)榻Y(jié)果可以被百分百猜出來(lái)。
熵和統(tǒng)計(jì)隨機(jī)性不同。數(shù)字流的統(tǒng)計(jì)特性不能保證該流中包含任何熵。比如，常量pi的數(shù)字在任何統(tǒng)計(jì)測(cè)量中看起來(lái)都是隨機(jī)的，但是其不包含任何熵，因?yàn)橛锌偹苤墓娇梢杂?jì)算出它們從而完美地預(yù)測(cè)下一個(gè)值是什么（另外，pi是一個(gè)正規(guī)數(shù)：所有數(shù)字出現(xiàn)得概率一樣）。
此外，大數(shù)字也不總是含有大量的熵。你可以獲取一個(gè)小的隨機(jī)數(shù)，然后把它變成大的隨機(jī)數(shù)同時(shí)保持熵不變。比如，獲取一個(gè)介于1到16的隨機(jī)數(shù)，然后用類(lèi)似SHA-1的算法計(jì)算其加密散列值。獲得的160位數(shù)字看起來(lái)非常隨機(jī)，但是這些數(shù)字只會(huì)有僅僅16中可能性。獲取隨機(jī)數(shù)的池子容量的大小確定隨機(jī)性的強(qiáng)弱。
對(duì)于加密密鑰，用于創(chuàng)建它們的熵的多少和其猜測(cè)難度有關(guān)。一個(gè)從熵值是20的源產(chǎn)生的128位密鑰并不比20位的密鑰更安全（譯者語(yǔ)：熵一樣大）。要?jiǎng)?chuàng)建安全的密鑰必須要有一個(gè)優(yōu)異的熵源。
暢游池中
在Linux中，所有隨機(jī)性的源頭都是一個(gè)被稱(chēng)為內(nèi)核熵池（譯者語(yǔ)：原文是kernel entropy pool）的東西。這是一個(gè)私密保存在內(nèi)核內(nèi)存中的大數(shù)字（4096位）。這個(gè)數(shù)字有可能性。所以它可以包含4096位熵。有一點(diǎn)需要注意：內(nèi)核需要能夠從一個(gè)擁有4096位熵的源填滿該內(nèi)存。那就是難點(diǎn)：尋找大量的隨機(jī)性。
熵池有兩種使用方式：從其中生成隨機(jī)數(shù)和內(nèi)核再向其填充熵。當(dāng)從池中生成隨機(jī)數(shù)時(shí)，池子的熵值會(huì)降低（因?yàn)楂@取到隨機(jī)數(shù)的人就有了一些池子的信息）。因此隨著隨機(jī)數(shù)被發(fā)放出去，池子的熵值也在降低，必須為其重新填充。
重新填充池子的過(guò)程被稱(chēng)為攪拌（stirring）：多個(gè)新的熵源被攪拌混合成池中的數(shù)位。
這就是隨機(jī)數(shù)生成如何在Linux上執(zhí)行的關(guān)鍵。如果需要隨機(jī)性，從熵池中獲取。當(dāng)可用的時(shí)候，其他隨機(jī)源會(huì)被用于攪拌填充熵池，減少其可預(yù)測(cè)性。具體細(xì)節(jié)設(shè)計(jì)一些數(shù)學(xué)知識(shí)，但是了解Linux隨機(jī)數(shù)生成器的工作原理很有趣，因?yàn)槠湓砗退眉夹g(shù)也適用于其他軟件和系統(tǒng)中的隨機(jī)數(shù)生成。
內(nèi)核對(duì)池中熵的位數(shù)維護(hù)了一個(gè)粗略估算值。你可以使用下面的命令檢查這個(gè)估算值：
cat /proc/sys/kernel/random/entropy_avail
擁有大量可用熵的健康Linux系統(tǒng)會(huì)返回接近完整的4096位熵。如果返回值小于200，那么系統(tǒng)運(yùn)行在低熵狀態(tài)。
內(nèi)核在監(jiān)視你
我說(shuō)過(guò)系統(tǒng)會(huì)獲取其他源的隨機(jī)性，并將它們攪拌填充到熵池中。這是通過(guò)被稱(chēng)為時(shí)間戳的東西來(lái)完成。
大多數(shù)系統(tǒng)都有精確的內(nèi)部時(shí)鐘。每次用戶和系統(tǒng)進(jìn)行交互，那個(gè)時(shí)間的時(shí)鐘值都會(huì)被記錄成時(shí)間戳。即使年、月、日很容易猜，但是毫秒和微妙不好猜，因此時(shí)間戳包含一些熵值。從用戶鼠標(biāo)和鍵盤(pán)獲取的時(shí)間戳以及來(lái)自網(wǎng)絡(luò)和磁盤(pán)的時(shí)長(zhǎng)信息各自具有不同的熵值。
在時(shí)間戳中找到的熵怎么傳遞到熵池中呢？簡(jiǎn)單，用數(shù)學(xué)把它們混合在一起。好吧，如果你喜歡數(shù)學(xué)的話是挺簡(jiǎn)單的。
把它混合起來(lái)
熵的一個(gè)基本屬性是有良好的混合性。如果你有兩個(gè)不相關(guān)的隨機(jī)流，然后把它們合并在一起，新的流不會(huì)擁有更少的熵。合并一些低熵的源會(huì)得到一個(gè)高熵的源。
你所需要的是一個(gè)正確的合并函數(shù)：可以用來(lái)把兩個(gè)熵源合并的函數(shù)。這樣的函數(shù)中最簡(jiǎn)單的就是邏輯異或（XOR）。下面的真值表展示了XOR函數(shù)如何合并兩個(gè)不同隨機(jī)流的位x和y。
即使其中一個(gè)源的數(shù)位沒(méi)有足夠的熵，在其和另一個(gè)源進(jìn)行異或時(shí)也不會(huì)有任何危害。熵值一直保持增加。在Linux內(nèi)核中，使用異或合并時(shí)間戳到主熵池中。
生成隨機(jī)數(shù)
加密應(yīng)用需要非常高的熵。如果128位密鑰是由僅僅64位熵生成，那么只需要次就可以猜出，而不是
次。這之間的區(qū)別是用一千臺(tái)計(jì)算機(jī)運(yùn)行幾年就可以暴力破解和用全世界的計(jì)算機(jī)運(yùn)行比宇宙歷史還長(zhǎng)的時(shí)間才能完成。
加密系統(tǒng)需要盡可能每位都有一個(gè)熵值（譯者語(yǔ)：密鑰的每位都有一個(gè)熵，1024位的密鑰的熵值要是1024）。如果系統(tǒng)熵池中沒(méi)有4096位熵，那怎么才能讓系統(tǒng)返回一個(gè)完全的隨機(jī)數(shù)呢？一種方法就是使用加密散列函數(shù)。
加密散列函數(shù)輸入任意長(zhǎng)度的數(shù)據(jù)，輸出一個(gè)固定長(zhǎng)度的數(shù)字。修改輸入的一位數(shù)據(jù)會(huì)導(dǎo)致輸出完全改變。散列函數(shù)擅長(zhǎng)把多個(gè)事物混合在一起。這個(gè)混合屬性使得來(lái)自輸入的熵均勻的分布在輸出中。如果輸入熵的位數(shù)比輸出的位數(shù)還多，那么輸出將會(huì)十分隨機(jī)。這就是從熵池中獲取高熵值隨機(jī)數(shù)的原理。
Linux內(nèi)核使用的散列函數(shù)是標(biāo)準(zhǔn)的SHA-1加密散列。通過(guò)散列整個(gè)熵池和應(yīng)用一些其他算數(shù)，會(huì)生成160位的隨機(jī)數(shù)給系統(tǒng)使用。在此以后，系統(tǒng)會(huì)相應(yīng)地降低熵池的估算熵值。
正如上面說(shuō)過(guò)的，如果熵池中沒(méi)有足夠的熵，那對(duì)其使用類(lèi)似SHA-1這樣的散列函數(shù)會(huì)是危險(xiǎn)的。這也是為什么我們要一直緊盯著可用的系統(tǒng)熵值：如果它降得太低，那么隨機(jī)數(shù)生成的輸出的熵值就會(huì)比其本身應(yīng)該有要低。
耗盡熵
耗盡熵對(duì)系統(tǒng)來(lái)說(shuō)很危險(xiǎn)。當(dāng)系統(tǒng)的熵值估算低于160位，即SHA-1散列的長(zhǎng)度，事情會(huì)變得復(fù)雜。對(duì)于程序和性能的影響取決于你使用兩種Linux隨機(jī)數(shù)生成器的哪一個(gè)。
Linux為隨機(jī)數(shù)據(jù)暴露兩個(gè)接口，它們?cè)陟刂邓降偷臅r(shí)候表現(xiàn)大相徑庭。它們分別是/dev/random和/dev/urandom。當(dāng)熵池的熵值低到可以被預(yù)測(cè)，兩個(gè)請(qǐng)求隨機(jī)數(shù)的接口都會(huì)有問(wèn)題。
當(dāng)熵值過(guò)低，/dev/random會(huì)阻塞調(diào)用者直到系統(tǒng)的熵值恢復(fù)到足夠高的水平。這保證產(chǎn)生的隨機(jī)數(shù)的熵很高。如果在一個(gè)時(shí)間要求嚴(yán)格的服務(wù)中使用/dev/random，然后系統(tǒng)的熵值低于安全的最低值，那么延遲（譯者語(yǔ)：因?yàn)?code>/dev/random在系統(tǒng)熵值過(guò)低時(shí)，會(huì)阻塞調(diào)用者）會(huì)損害服務(wù)質(zhì)量。
另一方面，/dev/urandom不會(huì)阻塞。它仍然返回熵池的散列值，即使其中已經(jīng)幾乎沒(méi)有熵。這個(gè)數(shù)據(jù)不一定是低熵。只要熵池中還有足夠的熵，使用它并沒(méi)什么害處。然而，如果熵池沒(méi)有被補(bǔ)充，那這個(gè)數(shù)據(jù)不適合加密用途。
解決這個(gè)問(wèn)題的辦法就是為系統(tǒng)加入更多的熵。
硬件隨機(jī)數(shù)生成的拯救？
Intel的Ivy Bridge系列處理器有個(gè)被稱(chēng)為“安全密鑰”的有趣特性。這些處理內(nèi)部包含一塊特殊的硬件來(lái)生成隨機(jī)數(shù)。一個(gè)RDRAND匯編指令返回?fù)?jù)稱(chēng)源于芯片的熵值很高的隨機(jī)數(shù)據(jù)。
有人宣稱(chēng)Intel的硬件數(shù)字生成器可能不是完全隨機(jī)的。因?yàn)樗粺圃诠栊酒校阅莻€(gè)斷言很難驗(yàn)證。事實(shí)證明，即使生成得數(shù)字有一些偏向性，只要它不是系統(tǒng)隨機(jī)性的唯一來(lái)源，它仍然可以提供幫助。即使隨機(jī)數(shù)生成器有后門(mén)，隨機(jī)性的混合特性也證明它不會(huì)降低池中的熵。
在Linux中，如果存在硬件隨機(jī)數(shù)生成器，Linux內(nèi)核會(huì)使用XOR函數(shù)把RDRAND的輸出混入熵池的散列值中。這位于Linux源代碼的這里（C語(yǔ)言的XOR操作符是^）。
第三方熵生成器
硬件數(shù)字生成器并不是哪里都有，Linux內(nèi)核自身獲取隨機(jī)性的來(lái)源也有限。針對(duì)這種情況，出現(xiàn)了一些第三方隨機(jī)數(shù)生成工具。其中就有依賴(lài)處理器緩存時(shí)間的havedeg，還有從外部音頻或視頻輸入設(shè)備采集噪音的audio-entropyd和video-entropyd。通過(guò)把這些從額外來(lái)源收集得熵混入到Linux熵池中，系統(tǒng)的熵值肯定會(huì)增加。
來(lái)源的多樣性
主要需要理解得是更好的隨機(jī)性來(lái)源于多樣性。從不同的來(lái)源獲取隨機(jī)數(shù)，然后把它們一起混合會(huì)得到更好的隨機(jī)數(shù)。對(duì)于服務(wù)器，這應(yīng)該包含機(jī)器本地?cái)?shù)據(jù)（硬件隨機(jī)數(shù)生成器，網(wǎng)絡(luò)耗時(shí)）和位于安全地點(diǎn)的外部獲取來(lái)源。
展望未來(lái)
除了上述說(shuō)到的來(lái)源，還有很多隨機(jī)數(shù)來(lái)源可以獲取。這些包括火山燈，太空噪音和光的量子屬性。通過(guò)增加新的源到Linux中的方法，CloudFlare正在開(kāi)發(fā)一個(gè)系統(tǒng)用以確保所有服務(wù)器都能有高質(zhì)量的隨機(jī)數(shù)。這些系統(tǒng)會(huì)在未來(lái)幾個(gè)月上線，到時(shí)候我們會(huì)和社區(qū)分享其中的細(xì)節(jié)。v
