随机数生成器攻击

**隨機數生成器攻擊**（英語：Random number generator attack），是針對加密系統中，隨機數生成（RNG）的環節進行破壞或弱點利用的攻擊。

一個密碼系統的安全性取決於機密訊息只能由已授權人員可知，其他人不可知且不可預測。為了達到不可預測性，通常會採用一些隨機化的過程。為了系統的安全性，必須要有一個高品質的隨機數生成方式，低品質的生成方式會產生安全漏洞，導致系統發生洩密。由於亂數生成的部分通常只牽涉到單個孤立的硬體或軟體，非常容易尋找，所以對攻擊者而言特別有吸引力。如果攻擊者可以用一種他可以預測的偽亂數替換 RNG 過程，安全性就會受到完全損害，但是上游的測試對此通常是無法偵測到的。此外，對於已被破解的系統，攻擊者只需進行一次存取，不需要再進行回傳。與之相較，電腦病毒在偷取密鑰後，還需要透過電子郵件等方式將密鑰回傳給攻擊者。

## 人工生成的亂數

對於產生亂數這件事，人類通常表現不佳。魔術師、職業賭徒和詐騙犯都仰賴於人類行為的可預測性。在第二次世界大戰中，德國的譯電員們在使用恩尼格瑪密碼機時會依照指示隨機選擇三個字母作為轉子的初始設定。然而有些人會選用一些可預測的字母，比如他們自己或女友的名字縮寫，這大大的幫助了盟軍破解這些加密系統。另一個例子是電腦的使用者常常會選用一些容易預測方式選擇密碼。

儘管如此，Ran Halprin 與 Moni Naor 研究了在混合策略遊戲中的一些特定情況下，使用的人玩遊戲時的熵來產生隨機性。

## 攻擊

### 軟體亂數生成器

僅作為加密系統的其它組件而言，軟體亂數發生器在設計上應該能抵抗一定的攻擊。攻擊類型可能包括：

**直接密碼分析攻擊**
: 若攻擊者可以獲得亂數生成序列的一部分，並且可以據此將發生器的輸出從真正的隨機流中區分出來時，此類攻擊可行。

**以輸入為基礎的攻擊**
: 修改發生器的輸入來進行攻擊，例如通過將現存的熵「清洗」出現有的系統，並把系統設定為已知的狀態。

**狀態妥協擴充攻擊**
: 在內部保密狀態的發生器在某個時間是已知的，據此可以預測未來發生器的輸出或恢復之前的輸出。 這可能發生在發生器剛剛啟動並且發生器僅擁有少量或沒有擁有任何熵的時候（特別是電腦剛剛啟動並且正在執行一個非常標準的操作序列的時候），因此在這個狀態下，攻擊者可能能夠獲得初步的猜測值。

### 硬體亂數生成器

許多針對硬體亂數生成器的攻擊都是有可能的，包括嘗試擷取電腦的射頻發射（例如從電機噪音中推斷硬碟中斷時間），或者嘗試將受控的訊號回饋到假定的隨機源當中（比如關閉熔岩燈中的燈光或是將已知的強訊號回饋到音效卡）。

### 亂數生成器顛覆

顛覆亂數可以在密碼學安全偽亂數生成器中使用亂數種子值來生成，種子值雖然隱藏在軟體中，但是對攻擊者已知。相對較短，比如 24 到 40 位元，種子可以是真正隨機的，可以防止重複，但是並不足以防止攻擊者恢復「隨機」生成的金鑰。

亂數在使用前會通過數層特定的軟體和硬體。資料可能在外圍裝置中生成，通過電纜傳輸，由作業系統組件收集並由系統呼叫進行檢索。這一過程中的任何一點都可以替換顛覆的資料，並且幾乎無法檢測。

僅僅需要數平方毫米就可以使用積體電路建造一個用於生成顛覆亂數的硬體電路。通過將這種晶片放置在上游任何隨機性來源數位化的地方，就可以破壞最先進的硬體亂數生成器，例如在輸出驅動晶片中甚至在把電腦與生成器連接起來的電纜中。破壞晶片可以帶有一個時鐘來來把操作啟動時間限制到單位初次啟動之後，並且還能通過接受測試，也可以帶有用於開關控制的無線電接收器。破壞晶片的安裝可以是國家情報服務機構對製造商的要求，或者是之後任何有物理存取權的人。用於替換內建硬體亂數生成器的 CPU 晶片的可以是任意的相容晶片，其韌體中可以包含已顛覆的亂數生成器。

## 防禦

* 將硬體生成的亂數與高品質流加密輸出（比如邏輯互斥或）混合，並儘可能地接近使用點。流加密金鑰與亂數種子應當可以用可審計的方式進行修改並從可信來源中衍生，例如擲骰子。Fortuna 亂數生成器就是一個使用這些機制的範例演算法。
* 使用真正隨機的來源生成密碼。有些系統會代為使用者選擇隨機密碼而不讓使用者自行提交。
* 使用加密系統來記錄亂數生成過程，並提供審計生成過程的方法。
* 用現有的硬體構建安全系統，最好以未告知預期用途的方式購買硬體，例如大型零售機構。
* 在購買後保持對硬體的完全物理控制。

設計一個安全亂數生成器至少要求與設計密碼系統的其它部分一樣高的水平。

## 突出例子

### 可預測的網景亂數種子

在早期版本的網景傳輸層安全性協定（SSL）中的加密協定中使用了偽亂數，來源是偽亂數生成器根據三個變數衍生的：一天中的時間、行程 ID 與父行程 ID。這些偽亂數相對而言通常是可預測的，因此熵值很低並且也少於亂數，亦因此發現這一版本的 SSL 並不安全。Phillip Hallam-Baker 於 1994 年向網景公司報告了問題所在，隨後也向 CERN 網路團隊的一位研究員報告。但是問題在發布前並未修復。1995 年，Ian Goldberg 與 David Wagner 發現了這一問題，二人當時因為網景公司拒絕透露其亂數字生成器（靜默安全性）的細節，而不得不對目的碼進行逆向工程。亂數生成器在後來的版本（第二版及更高）中通過更強的亂數種子（即從攻擊者的角度來看，更隨機和更高的熵）得到修復。

### Microsoft Windows 2000/XP 中的亂數生成器

微軟使用未發布的演算法來為其 Windows 作業系統生成亂數值，並通過 CryptGenRandom 實用工具提供給使用者。2007 年 11 月，來自耶路撒冷希伯來大學與海法大學的 Leo Dorrendorf et al. 發布了一篇名為《Windows 作業系統中的亂數生成器的密碼學分析》（_Cryptanalysis of the Random Number Generator of the Windows Operating System_）的論文。 文中指出了當時微軟的生成方法中的嚴重缺陷，結論基於對 Windows 2000 中代碼的反組譯，但是根據微軟的說法，這些代碼也存在於 Windows XP。 微軟已經表示，文中描述的問題已經在 Windows 的後續版本中得到解決，後者使用了不同的亂數生成實現。

### 橢圓曲線 DRBG 中可能的後門

美國國家標準技術研究所（NIST）發布了「確定性隨機位發生器」，並且推薦於 NIST 的特刊 800 至 890 期中。其中叫 Dual\_EC\_DRBG 的生成器受到了國家安全局（NSA）的青睞。 Dual\_EC\_DRBG 使用橢圓曲線加密並包含一組推薦使用的常數。2007 年八月，來自微軟的 Dan Shumow 與 Niels Ferguson 顯示這些常數可以通過在演算法中建立一個竊密學後門的方式來構建。 2013 年九月，《紐約時報》（_The New York Times_）發文稱「NSA 向 NIST 於 2006 年接納的一向標準中植入了後門... 名為 Dual EC DRBG 標準」，從而揭示了 NSA 對美國人民進行了惡意軟體攻擊。2013 年 12 月，據路透社報導，愛德華・史諾登（Edward Snowden）發布的檔案顯示，NSA 已經向 RSA 安全公司支付了 1000 萬美元，將 Dual\_EC\_DRBG 作為後者的預設加密軟體，也因此出現更多關於該演算法包含 NSA 後門的擔憂。出於這些擔憂，2014 年，NIST 從其關於亂數發生器的指導草案中復原了，推薦「現有的 Dual EC DRBG 使用者儘快切換到其餘三個演算法。」

### MIFARE Crypto-1

Crypto-1 是由 NXP 開發的用於 MIFARE 晶片的加密系統。作為專有系統，其演算法最初並未公布。根據對晶片的逆向工程，來自維吉尼亞大學與 Chaos Computer Club 的研究人員發現了針對 Crypto-1 中亂數發生器的初始化不良漏洞。

### Debian OpenSSL

2008 年五月，安全研究員 Luciano Bello 透漏了一項發現，關於 2006 年在隨 Debian GNU/Linux 和其他基於 Debian 的發行版，例如 Ubuntu，中分發的 OpenSSL 軟體套件中亂數生成器的變化。這些變化大大降低了生成值的熵值，使得各種安全金鑰易受攻擊。這個安全漏洞是由於 Debian 開發者為解決冗餘代碼的編譯器警告，隨即對 OpenSSL 代碼做出了這些修改，從而導致了金鑰在世界範圍內的大量重構，儘管所有人都注意到了這個問題，但可以推測出許多舊金鑰仍在使用中。受影響的金鑰類型包含 SSH 金鑰、OpenVPN 金鑰、DNSSEC 金鑰、SSL/TLS 連接中使用的 X.509 憑證金鑰材料與對談金鑰。使用 GnuPG 或 GnuTLS 生成的金鑰由於使用了不同的方法來生成亂數而未受到影響。由非 Debian 系的 Linux 發行版生成的金鑰也未受到影響。接到報告之後，漏洞及時得到修補，但是任何仍然使用由舊代碼生成的金鑰的服務仍然是脆弱。許多軟體套件現在都包含針對弱金鑰黑名單的檢查，以試圖預防使用剩餘的弱金鑰，但是研究人員仍舊陸續發現了薄弱的金鑰實現。

### PlayStation 3

2010 年 12 月，一個自稱 _fail0verflow_ 的團體宣布了恢復橢圓曲線數位簽章演算法（ECDSA）私鑰的方法。索尼公司使用這種私鑰來為 PlayStation 3 來簽章遊戲包。攻擊的可能性來源於由於索尼未能為每個簽章產生一個新的亂數。

### RSA 公鑰分解

2012 年，Lenstra、Hughes、Augier、Bos、Kleinjung 與 Wachter 發布了一篇關於從網際網路收集數百萬個 RSA 公鑰的分析。他們僅使用了歐幾里得演算法就分解了 0.2% 的金鑰，利用的是基於整數分解的密碼系統特有的弱點。若 _n_ = _pq_ 是一個公鑰，_n_′ = _p_′_q_′ 是另一個，那麼如果偶然間 _p_ = _p_′，那麼簡單計算 gcd (_n_,_n_′) = _p_ 因數都是 _n_ 和 _n_′，完全破壞了兩個金鑰。一個進行過類似實驗的組織的一員 Nadia Heninger 說，劣質金鑰幾乎完全出現於嵌入式系統中，由兩組結果發現的共享素數問題是由於偽亂數發生器最初做種不良，然後在第一個和第二個素數的產生之間發生了重新做種。

### Java 即時碰撞

2013 年八月，據透露 Java 類 SecureRandom （頁面存檔備份，存於網際網路檔案館）中的錯誤可以在用於 Android 裝置上比特幣軟體中的 _k_ nonce 數值上生成衝突。當錯誤觸發時，私鑰可以恢復，因而導致包含錢包中的比特幣失竊。

## 另見

* 偽亂數生成器
* 密碼學安全偽亂數生成器
* 金鑰生成
* 一次性密碼本
* 鹽
* Nonce

## 參考資料

## 延伸閱讀

* Gutterman, Zvi; Benny Pinkas; Tzachy Reinman. Analysis of the Linux Random Number Generator (PDF). IEEE S&P. Oakland Conference. May 2006: 371–385 [2017-12-17]. （原始內容 (PDF) 存檔於 2017-12-07）.
* Eastlake, D. Randomness Requirements for Security. RFC. IETF. June 2005 [2017-12-17]. （原始內容存檔於 2018-05-09）.