維基百科

隨機數生成器攻擊

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

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

人工生成的隨機數

編輯

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

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

攻擊

編輯

軟件隨機數生成器

編輯

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

直接密碼分析攻擊
若攻擊者可以獲得隨機數生成序列的一部分，並且可以據此將發生器的輸出從真正的隨機流中區分出來時，此類攻擊可行。
以輸入為基礎的攻擊
修改發生器的輸入來進行攻擊，例如通過將現存的熵「清洗」出現有的系統，並把系統設置為已知的狀態。
狀態妥協擴展攻擊
在內部保密狀態的發生器在某個時間是已知的，據此可以預測未來發生器的輸出或恢復之前的輸出。 這可能發生在發生器剛剛啟動並且發生器僅擁有少量或沒有擁有任何熵的時候（特別是計算機剛剛啟動並且正在執行一個非常標準的操作序列的時候），因此在這個狀態下，攻擊者可能能夠獲得初步的猜測值。

硬件隨機數生成器

編輯

許多針對硬件隨機數生成器的攻擊都是有可能的，包括嘗試捕獲計算機的射頻發射（例如從電機噪音中推斷硬盤中斷時間），或者嘗試將受控的信號反饋到假定的隨機源當中（比如關閉熔岩燈中的燈光或是將已知的強信號反饋到聲卡）。

隨機數生成器顛覆

編輯

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

隨機數在使用前會通過數層特定的軟件和硬件。數據可能在外圍設備中生成，通過電纜傳輸，由操作系統組件收集並由系統調用進行檢索。這一過程中的任何一點都可以替換顛覆的數據，並且幾乎無法檢測。

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

防禦

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

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

突出例子

編輯

可預測的網景隨機數種子

編輯

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

Microsoft Windows 2000/XP 中的隨機數生成器

編輯

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

橢圓曲線DRBG中可能的後門

編輯

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

MIFARE Crypto-1

編輯

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

Debian OpenSSL

編輯

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

PlayStation 3

編輯

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

RSA公鑰分解

編輯

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

Java實時碰撞

編輯

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

另見

編輯

參考資料

編輯
  1. ^ Michael Jenkins; Lydia Zieglar. Commercial National Security Algorithm (CNSA) Suite Profile of Certificate Management over CMS. IETF draft draft-jenkins-cnsa-cmc-profile-00. U.S. National Security Agency. September 28, 2018 [2021-01-19]. （原始內容存檔於2019-03-23）. The use of inadequate pseudo-random number generators (PRNGs) can result in little or no security. The generation of quality random numbers is difficult. 
  2. ^ Halprin, Ran. Games for Extracting Randomness (PDF). [2017-12-17]. （原始內容 (PDF)存檔於2018-02-05）. 
  3. ^ Kelsey, J. Cryptanalytic Attacks on Pseudorandom Number Generators. Fast Software Encryption, Fifth International Workshop Proceedings. Springer-Verlag: 168–188. 1998 [15 August 2013]. （原始內容存檔於2015-07-15）. 
  4. ^ Goldberg, Ian. Randomness and Netscape Browser. Dr. Dobb's Journal. January 1996 [2017-12-17]. （原始內容存檔於2016-05-22）. 
  5. ^ Dorrendorf, Leo; Gutterman, Zvi; Pinkas, Benny. Cryptanalysis of the random number generator of the Windows operating system (PDF). ACM Transactions on Information and System Security. 1 October 2009, 13 (1): 1–32 [2017-12-17]. doi:10.1145/1609956.1609966. （原始內容 (PDF)存檔於2012-09-06）. 
  6. ^ Keizer, Gregg. Microsoft confirms that XP contains random number generator bug. Computerworld. November 21, 2007 [2017-12-17]. （原始內容存檔於2014-08-14）. 
  7. ^ Barker, Elaine. Recommendation for Random Number Generation Using Deterministic Random Bit Generators (PDF). NIST. January 2012 [2017-12-17]. （原始內容存檔 (PDF)於2013-10-09）. 
  8. ^ Schneier, Bruce. Did NSA Put a Secret Backdoor in New Encryption Standard?. Wired. November 15, 2007 [2017-12-17]. （原始內容存檔於2008-05-11）. 
  9. ^ Shumow, Dan. On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng (PDF). http://cr.yp.to/. 21 August 2007 [2017-12-17]. （原始內容存檔 (PDF)於2014-02-26）. 
  10. ^ Perlroth, Nicole. Government Announces Steps to Restore Confidence on Encryption Standards. The New York Times. 10 September 2013 [2017-12-17]. （原始內容存檔於2014-07-12）. 
  11. ^ Menn, Joseph. Exclusive: Secret contract tied NSA and security industry pioneer. San Francisco. Reuters. December 20, 2013 [December 20, 2013]. （原始內容存檔於2015-09-24）. 
  12. ^ NIST Removes Cryptography Algorithm from Random Number Generator Recommendations. National Institute of Standards and Technology. 21 April 2014 [2017-12-17]. （原始內容存檔於2016-08-29）. 
  13. ^ Nohl, Karsten. Reverse-engineering a cryptographic RFID tag. SS'08 Proceedings of the 17th conference on Security symposium. USENIX: 185–193. 2008-07-31 [2017-12-17]. （原始內容存檔於2019-03-23）. 
  14. ^ DSA-1571-1 openssl -- predictable random number generator. Debian Security Advisory. 13 May 2008 [2017-12-17]. （原始內容存檔於2014-02-20）. 
  15. ^ CVE-2008-0166. CVE. January 9, 2008 [2017-12-17]. （原始內容存檔於2021-05-06）. OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems uses a random number generator that generates predictable numbers, which makes it easier for remote attackers to conduct brute force guessing attacks against cryptographic keys. 
  16. ^ Schneider, Bruce. Random Number Bug in Debian Linux. May 19, 2008 [2017-12-17]. （原始內容存檔於2021-05-10）. 
  17. ^ 存档副本. [2017-12-17]. （原始內容存檔於2019-12-08）. 
  18. ^ Bendel, Mike. Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access. Exophase.com. 2010-12-29 [2011-01-05]. （原始內容存檔於2019-04-07）. 
  19. ^ Markoff, John. Flaw Found in an Online Encryption Method. The New York Times. February 14, 2012 [2017-12-17]. （原始內容存檔於2021-04-17）. 
  20. ^ Lenstra, Arjen; Hughes, James P.; Augier, Maxime; Bos, Joppe Willem; Kleinjung, Thorsten; Wachter, Christophe. Ron was wrong, Whit is right (PDF). Santa Barbara: IACR: 17. 2012 [2017-12-17]. （原始內容 (PDF)存檔於2021-04-28）. 
  21. ^ Chirgwin, Richard. Android bug batters Bitcoin wallets. The Register. 12 August 2013 [2017-12-17]. （原始內容存檔於2013-08-17）. 

延伸閱讀

編輯
取自「https://zh.wikipedia.org/w/index.php?title=随机数生成器攻击&oldid=79425359」