使用 openssl 生成弱密鑰要注意什麼？（低熵）

（免責聲明：我是普通的軟體工程師，只有基本的加密知識，如果可以為外行解釋，那麼很有幫助。）

我擔心在使用 openssl 的共享 linux 機器上生成弱密鑰。一些問題：

1. 熵必須有多低才會危險？如果我跑步，cat /proc/sys/kernel/random/entropy_avail我會得到大約 130 到幾千的任何東西。而且似乎波動很快。

攻擊在 130 處是否可行，或者它必須走多低（50、10、1、0）？我沒有看到任何硬性數據。這種攻擊只是理論上的還是要在實踐中破壞它需要多少工作？ 2. 在有足夠的熵生成密鑰之前，openssl 會阻塞嗎？我的理解是，/dev/urandom它不會阻塞並且是預設設置，但是/dev/random會阻塞。我認為/dev/random這不是出於性能/一致性原因的預設設置？openssl 中是否有一個標誌或選項，您可以選擇使用/dev/random它以防萬一？ 3. 在共享盒子上，鄰居有什麼辦法可以耗盡系統上的所有隨機性，並強迫你生成一個弱密鑰？似乎阻塞直到有足夠的熵可以解決上面的這個（＃3）。 4. 給定您已經生成的公鑰/私鑰 - 有什麼方法可以證明它是低熵生成的？

很抱歉有多個問題，但它們似乎相關，因此想將其作為一個問題發布。非常感謝！

考慮到 Linux 作業系統，我將回答它是最流行的類 Unix 作業系統之一（在具有urandom. 如果您需要其他作業系統，請通知我。此外，我將使用Linux 3.3.3 核心中的 random.c驅動程序的原始碼來回答，因為它是最好的/dev/random機製文件之一。另一篇是論文：Analysis of the Linux Random Number Generator, Gutterman 2006, 086.pdf - 查看第 4-6 頁和圖 2.1（幻燈片）。然後您可以查看The Linux Pseudorandom Number Generator Revisited, Lacharme 2012, 251.pdf論文。甚至維基百科在這裡也可能會有所幫助。

Linux中有幾個隨機池：

• 512 字節（128 個 4 字節字）的主池；傳入的熵被添加到它；
• 為 128 字節生成隨機數的輔助池/dev/random
• Urandom 池（或另一個輔助池）128 字節用於/dev/urandom

為所有三個池維護單獨的熵計數器，但通常主池的計數器是平均值。“可用”計數器來自主池。

當您要求隨機數據時，會從相應的輔助池中提取部分熵（使用涉及 SHA1 的單向函式），然後將其部分添加（混合）到池中。提取的部分數據提供給隨機數據的消費者。使用者和核心都消耗熵，例如，當啟用 ASLR（在大多數發行版中啟用）時，核心使用隨機驅動程序的 API 來啟動程序。有一個有趣的例子，當做幾個時cat /proc/sys/kernel/random/entropy_avail會偷走大部分熵，可能這也是你的情況，在 StackOverflow 上證明。要監視entropy_avail您應該使用一些守護程序或簡單的 C 程序，這些程序將多次重新讀取池而無需重新啟動程序。

當輔助池具有低熵時，從主池中提取一部分熵（再次使用加密單向函式），然後將一部分重新混合回主池，一部分混合到消費池。

1）熵必須有多低才會危險？如果我執行 cat /proc/sys/kernel/random/entropy_avail 我會得到大約 130 到幾千的任何東西。而且似乎波動很快。

我想考慮“我可以從隨機源中提取entropy_avail多少高質量隨機位”的估計。/dev/random在沒有熵的情況下只給出高質量的比特和塊，而/dev/urandom給出任何質量的比特。當熵高時，urandom給出高質量的比特，但當熵為零時，它（可能）給出加密偽隨機數序列（在幾乎所有其他流行的作業系統中都有這種 CSPRNG 生成器的更好範例：FreeBsd/OpenBSD、MacOS、多發性硬化症）。但是 251.pdf（第 4.3 部分，第 16 頁）說“因此，如果內部狀態沒有受到損害並且三個池由未知值初始化，則假定沒有熵輸入的 Linux PRNG 是安全的。”

這里分析了 Linux 中熵估計背後的數學（對軟體工程師沒有用，只是加減數字）。

/dev/random和/dev/urandom驅動有源碼：http: //lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L261 （可以打開DEBUG_ENT查看隨機驅動的實際工作）

/*
 * Configuration information
 */
#define INPUT_POOL_WORDS 128
#define OUTPUT_POOL_WORDS 32
#define SEC_XFER_SIZE 512
#define EXTRACT_SIZE 10  --- 10 bytes to be extracted from secondary pools


/*
 * The minimum number of bits of entropy before we wake up a read on
 * /dev/random.  Should be enough to do a significant reseed.
 */
static int random_read_wakeup_thresh = 64;

如果available_entropy低於 64 位，則沒有人會讀取/dev/random. 所以，這是非常低的，較小的值會阻止所有正在閱讀的人/dev/random

/*
 * If the entropy count falls under this number of bits, then we
 * should wake up processes which are selecting or polling on write
 * access to /dev/random.
 */
static int random_write_wakeup_thresh = 128;

如果available_entropy低於 128 位，並且有一些好人可以從使用者空間給我們更多的熵，請嘗試讓他們這樣做。所以，即使是 128 位的熵，我們也不是處於最佳狀態，也不願意尋求幫助。

/*
 * When the input pool goes over trickle_thresh, start dropping most
 * samples to avoid wasting CPU time and reduce lock contention.
 */

static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;

如果超過 128*28 = 3584 位，我們拒絕添加來自外部源的所有可用熵（但一些“樣本”仍將混入主池）；當有很多可用熵時，一些傳入的熵將被添加到輔助池（但不會添加到 urandom 池）。

1a) 攻擊在 130 處是否可行，或者它必須走多低 (50, 10, 1, 0)？我沒有看到任何硬性數據。這種攻擊只是理論上的還是要在實踐中破壞它需要多少工作？

為了對隨機驅動程序進行有效的攻擊，我認為，攻擊者應該以某種方式預測主池的狀態。檢查http://eprint.iacr.org/2006/086.pdf中的第 2.2 部分- 初始化。主池最初在系統啟動時填充，攻擊者想要預測它是如何初始化的（使用了哪些隨機源以及輸入數據是什麼）。這可能是嵌入式設備或無人值守伺服器或虛擬化伺服器中的問題，它們具有少量不可預測的熵源。主要來源是：使用者生成的（鍵盤、滑鼠）、外圍設備（中斷，例如來自網路）、響應時間難以預測的設備（硬碟）。

大多數嵌入式設備將沒有硬碟，外圍設備數量很少（並且都是該模型的標準配置），沒有任何使用者坐在啟動 PC 前並在不可預知的時刻移動滑鼠和按鍵。他們也可能有質量差的計時資源（來自外部來源的熵數據是 32 位時間戳和 32 位屬性；如果您只能根據 32kHz 石英測量時間戳，那麼您的情況就不好了，最好使用時鐘滴答計數器或現代 Intel/AMD CPU，它是 3GHz，具有一些難以預測的可變性）。

嵌入式設備具有標準快閃記憶體映像的標準化設置（通常不會在設備的整個實時更新），並且某些設備或只讀可啟動媒體（Knoppix、OpenWRT）在啟動/關閉時錯誤地保存/恢復熵。正確的實現是在關機時從一些隨機儲存中保存 512 字節到持久儲存，並在啟動時將它們回饋到/dev/random早期（在 linux 資源中也有評論：確保系統啟動時的不可預測性；/etc/rc.d/init.d/randomSysV 時代啟動系統中的腳本）。

有一些嵌入式問題的新概述以及在哪裡搜尋良好的隨機性：http ://cseweb.ucsd.edu/users/swanson/papers/Oakland2013EarlyEntropy.pdf工作的結論：“隨機性是一項基本的系統服務。除非系統準備好為應用程序提供高熵隨機性，否則不能說系統已成功啟動。 ”

我認為最危險的事情是在高度嵌入式設備上的已知時刻啟動後儘早生成一些密鑰。要破解密鑰，黑客需要對所有熵源進行反向預測，並對生成密鑰時的主池狀態和輔助池狀態進行建模。這項任務很難，但有時比攻擊密鑰本身更容易。我現在無法展示 urandom 攻擊的範例，但我認為它們存在​​於一些易受攻擊的裝置中。

我還認為，debian 的 openSSL 版本比糟糕的隨機質量更致命：http ://www.schneier.com/blog/archives/2008/05/random_number_b.html http://xkcd.com/221/有可能每個固定的 RSA 密鑰大小只有大約數十萬個密鑰，因為 urandom 輸入被禁用，openssl 唯一和最好的可用熵輸入是程序 ID 或 PID，在 linux 上通常限制為 32-65 千。

2. openssl 是否會阻塞，直到有足夠的熵來生成密鑰？我的理解是 /dev/urandom 不會阻塞並且是預設設置，但 /dev/random 會阻塞。我假設 /dev/random 不是出於性能/一致性原因的預設設置？

openssl 不會阻塞（我認為，沒有檢查現代版本），因為沒有明確的方法來檢測 urandom 熵太低並切換到幾乎完全 PRNG 模式的時刻。/dev/urandom 上只有幾個 ioctl 可以讀取 avaliable_entropy。openssl 只嘗試使用自己的 PRNG，它由目前時間和 openssl 的 pid 以及來自 urandom 或 RANDFILE 的數據播種。

http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L109

109 * The two other interfaces are two character devices /dev/random and
110 * /dev/urandom.  /dev/random is suitable for use when very high
111 * quality randomness is desired (for example, for key generation or
112 * one-time pads), as it will only return a maximum of the number of
113 * bits of randomness (as estimated by the random number generator)
114 * contained in the entropy pool.
115 *
116 * The /dev/urandom device does not have this limit, and will return
117 * as many bytes as are requested.  As more and more random bytes are
118 * requested without giving time for the entropy pool to recharge,
119 * this will result in random numbers that are merely cryptographically
120 * strong.  For many applications, however, this is acceptable.

因此，正如 random 和 urandom 的來源所說，您不應該從中生成長期密鑰urandom，但仍然可以使用它來生成會話密鑰以做一些不有價值的事情（例如 SSL 到 facebook 的會話密鑰以查看更多帶有貓的圖像）。

當您詢問 openssl 密鑰生成時，您應該定義要生成的密鑰是什麼。如果它是 TLS 的會話密鑰，並且您在伺服器上，那麼使用 of/dev/random將限制客戶端可以連接的數量（沒有那麼多熵並且/dev/random會阻塞，我認為這是在 openSSL 中使用 urandom 的原因之一）。

但是，當您為 20 年 SSL 證書生成一些 4096 位 RSA 密鑰時，您希望使用具有良好外部熵來源的機器，在重新啟動時正確保存/恢復熵，並且人類使用了一段時間。

實際上，當真正的硬體隨機源可用（不是 Linux LRNG - PRNG）時，最好生成更有價值的密鑰，例如一些平衡熱雜訊測量方案（僅採用模數轉換器的最低精度位 - ADC） . 即使在現代英特爾 CPU（可能也在威盛的 CPU 中，不知道 AMD 或 ARM）中也有很好的硬體隨機源（輸出的 AES 逆變器循環的熱雜訊），請檢查伺服器上的設備。更新一些 HW RNG（論文 2013）中可能存在很難檢查的缺陷，因為有缺陷的隨機數據是由設備製造商的私鑰加密的。/dev/hwrng

使用高價值密鑰的唯一正確方法是在（內部）經過認證的 HSM（硬體安全模組）上生成它們，並僅在防篡改HSM（嘗試打開此類HSM 的情況，或者取出他們的電池，你的私鑰就會消失。有趣的情況是，當密鑰是某些銀行的最萬能鑰匙時 - 數百萬個 PIN 碼可能會在一瞬間失去……）。僅允許以拆分形式提取私鑰 - 當有 N 部分密鑰分佈在安全人員周圍時（每個部分都可以在官員的密鑰下加密）並且需要 K 部分來重建原始密鑰（例如通過Shamir 方案）。

主要規則是估計資訊的價值（例如，您的私人照片花費大約數十萬美元；但 google 或 facebook 的 SSL 證書花費數十億美元），資訊應該保持安全多長時間，以及需要多少投資以破壞您的資訊。例如，設置橡膠軟管密碼分析可能要花費大約 100-50 萬美元（竊取知道/可以訪問秘密/包含秘密並使用車庫扳手/勸告/烙鐵獲取秘密的某人或某物 - 烙鐵應該只用於從快閃記憶體卡上拆下快閃記憶體晶片，而不是其他東西），因此 HSM 和密鑰的拆分備份是銀行和 IT 巨頭有價值的密鑰的唯一變體。

2b) openssl 中是否有一個標誌或選項，您可以選擇使用 /dev/random 以防萬一？

有一個 hack 可以強制 openssl 使用來自 /dev/random 的數據：http ://bugs.debian.org/cgi-bin/bugreport.cgi?bug=88728

  dd if=/dev/random bs=1 count=1024 of=filename; 
  export RANDFILE=filename
  # use openssl here

（您可以使用 strace 驗證 openssl 實際上打開“文件名”以獲得隨機性並且沒有打開 /dev/urandom）

3）在共享盒子上，鄰居有沒有辦法耗盡系統上的所有隨機性，並強迫你生成一個弱密鑰？似乎阻塞直到有足夠的熵可以解決上面的這個（＃3）。

有一種方法可以消耗大部分隨機性，（即使是遠端的，通過 TCP-syn cookie 生成，參見086 論文的第 3.4 節；保留大約 64-128 位僅供 /dev/random 使用，第 18 頁 of 251.pdf ）。但即使在耗盡時，鄰居也無法通過 urandom 加密弱點僅通過收聽/dev/random和urandom。你們倆都將獲得池 SHA1 的不同部分的部分 SHA1-s（每個都用主池中的 SHA1 部分重新填充），並且你們中的任何人都不應該能夠重建主池的狀態。最壞的情況是使用 urandom 並且可用的熵為 0（這可能有點難以實現）。即使在這種情況下，您也會得到帶有未知種子的加密偽隨機生成器。攻擊者被迫同時破解遞歸 SHA1 並精確猜測種子（如果熵耗盡則為 128 字節的隨機資訊，或在未耗盡的情況下為 512 字節的主池）。即使系統中只有一個使用者排他地獲得了 urandom 的所有輸出（如果他在某個時間仍然沒有主池內容），這個任務也難以解決。

共享機器的根可以做任何事情：編寫核心模組來轉儲主/輔助池的狀態；模擬有 1600 萬位可用熵，而/dev/random將在循環中輸出類似的東西SHA1("THIS IS TRUE RANDOM,BELIEVE ME")；竊取您的 openssl 程序的記憶體轉儲以轉儲密鑰；讀取您儲存在 fs 私鑰上的資訊；攔截從您發送到“您的”openssl 的按鍵作為密碼，以解密您安全儲存的私鑰。而聰明的鄰居，如果他是披著羊皮的狼，就會嘗試獲取root權限來獲取你的鑰匙。

共享機器上的聰明攻擊者可能會嘗試對您的加密庫和加密算法安裝側通道攻擊，並且存在實際攻擊，例如使用精確的記憶體測量（Bernstein 2005：“AES 上的記憶體定時攻擊”），即使他還活著在其他虛擬機中。這是例如將英特爾 CPU 內的 AES 加密作為單獨的硬體塊移動的原因之一，不容易發生記憶體側通道洩漏。

因此，不要使用公共/共享機器或您無法控制的機器（您應該是 root 或可靠的人）來使用有價值的資訊進行加密。

4）給定您已經生成的公鑰/私鑰 - 有什麼方法可以證明它是低熵生成的？

我認為不，如果池被正確初始化，並且它們的內容是安全的（沒有根攻擊者）。

在一些非常糟糕的嵌入式安裝中，沒有計時（設備啟動到 1970 年），沒有池保存/恢復（或者在 urandom 讀取之後恢復太晚，就像在某些 ubuntus 中一樣），在生成密鑰之前沒有任何隨機輸入；當某些啟動腳本生成密鑰時；然後攻擊者可以對池的狀態進行建模並重新生成相同的密鑰。

還有一篇論文搜尋在低熵設備上生成的弱密​​鑰：https ://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf “探勘你的 Ps 和 Qs：檢測廣泛傳播網路設備中的弱鍵”。他們通過掃描數百萬台設備並比較它們的密鑰來檢測壞密鑰：

在 TLS 的情況下，至少 5.23% 的主機使用所有者從未更改過的製造商預設密鑰，另外 0.34% 似乎由於隨機數生成器故障而生成了與一台或多台其他主機相同的密鑰。

並通過檢查鍵的弱點；再次 - 通過比較大量掃描的密鑰，對於 RSA，他們發現了許多模組 N1 和 N2，其中 N1=p1q1 和 N2=p1q2。我理解這種情況，因為有弱鍵，但你無法區分弱鍵和好鍵。但是，如果密鑰是從固定的低熵設備狀態（首次啟動，早期生成）生成的，那麼有一定機率會找到另一個生成與第一台設備相同的 p 或 q 的設備（相同的硬體平台）（如果兩者都有，N 將是相同的）。

更令人擔憂的是，通過利用 RSA 和 DSA 在隨機性不足時使用的已知弱點，我們能夠僅從我們的掃描數據中計算出 64,000 (0.50%) 個 TLS 主機和 108,000 (1.06%) 個 SSH 主機的私鑰. 在 RSA 的情況下，共享一個素因子的不同模數將導致公鑰看起來不同，但其私鑰可以通過計算最大公約數 (GCD) 有效地計算。

DSA 要求生成具有大量熵的“臨時密鑰 k”。k 不應針對不同的消息重複，但有些 k 是相同的。

幾乎所有（易受攻擊的主機）都提供將它們辨識為無頭或嵌入式系統的資訊，包括路由器、伺服器管理卡、防火牆和其他網路設備。此類設備通常在首次啟動時自動生成密鑰，並且與傳統 PC 相比可能具有有限的熵源

.. Linux 的隨機數生成器 (RNG) 可能會出現引導時熵空洞，導致 urandom 在可能出現在無頭和嵌入式設備中的條件下產生確定性輸出。

引用自：https://crypto.stackexchange.com/questions/9412