雙橢圓曲線確定性隨機數發生器（Dual_EC_DRBG），也被稱作雙橢圓曲線隨機數發生器，是一種使用橢圓曲線密碼學實現的密碼學安全偽隨機數發生器(CSPRNG)。直到2017年被撤銷之前，儘管受到了大量密碼學家們的批評，被認為存在潛在的後門，該算法自2016年6月左右被公開起，在七年的時間內都是NIST SP 800-90A定義的4個（現為3個）標準的CSPRNG之一。
基本介紹
- 中文名：雙橢圓曲線確定性隨機數發生器
- 外文名：Dual_EC_DRBG
- 又稱：雙橢圓曲線隨機數發生器
- 公開時間：2016年6月
簡介,弱點：一個潛在的後門,安全性,包含可能後門的軟體和硬體,
簡介
這是一個由美國國家標準協會（NIST）制定並被美國國家安全局（NSA）大力提倡的隨機數發生器。Dual_EC_DRBG利用橢圓曲線算法的機制生成隨機數。這個算法涉及到在曲線上取點並反覆在橢圓曲線上進行“打點”操作。該算法公布之後，據報導可能存在一個後門程式，可以根據一個密碼完全預測其返回的數字順序。最近，RSA公司由於其安全產品生產線上的隨機數發生器被設定為默認的偽隨機數發生器而召回了它的部分產品。無論這種隨機數發生器是否被寫了後門程式都不會改變橢圓曲線技術本身的力量，但這確實引起了關於對橢圓曲線標準化過程的一些問題。這也是我們應該將注意力用在確保系統充分使用隨機數的部分原因。
弱點：一個潛在的後門
在算法成為ANSI，ISO以及之前由美國國家標準與技術研究院（NIST）認可的正式標準的一部分之前，算法的加密安全性的弱點是眾所周知的並且公開批評。公開發現的弱點之一是該算法有可能為那些知道盜版後門 - 美國政府的國家安全局（NSA） - 而不是其他人 - 提供有利的盜版後門。 2013年，“紐約時報”報導，他們擁有但從未向公眾發布的檔案“似乎證實”後門是真實的，並且作為其Bullrun解密計畫的一部分被NSA故意插入。在2013年12月，路透社一篇文章稱，在2004年，NIST標準化Dual_EC_DRBG之前，NSA支付RSA安全千萬$的秘密協定使用Dual_EC_DRBG作為RSA BSAFE加密庫默認，導致RSA信息安全成為最重要的不安全算法的分銷商。RSA回答說，他們“斷然否認”他們曾經故意與國家安全局勾結，採用一種眾所周知的有缺陷的算法，並說“我們從來沒有[與NSA]的關係保持秘密”。
某時在2004年的第一個已知的出版之前，可能kleptographic後門是與Dual_EC_DRBG的設計發現，與具有不同尋常的特性，這是任何人理論上是不可能Dual_EC_DRBG的設計，但Dual_EC_DRBG的設計師（NSA）確認後門的存在。 Bruce Schneier在標準化後不久就得出結論，“相當明顯的”後門（以及其他缺陷）意味著沒有人會使用Dual_EC_DRBG。後門將允許NSA解密，例如使用Dual_EC_DRBG作為CSPRNG的SSL/TLS加密。
最初提交Dual_EC_DRBG的ANSI標準組的成員了解潛在後門的確切機制以及如何禁用它，但沒有採取足夠的步驟無條件地禁用後門或廣泛宣傳它。在Dan Shumow和Niels Ferguson的出版物，或Certicom的Daniel R. L. Brown和Scott Vanstone的2005專利申請描述後門機制之前，一般的加密社區最初並未意識到潛在的後門。
在2013年9月，紐約時報報導，由愛德華·斯諾登泄露的內部NSA備忘錄指出，美國國家安全局在標準化進程已經努力最終成為Dual_EC_DRBG標準的獨立的一個編輯，並得出結論認為，Dual_EC_DRBG標準確實包含國家安全局的後門。作為回應，NIST表示“NIST不會刻意削弱加密標準。”根據紐約時報的報導，NSA每年花費2.5億美元在軟體和硬體中插入後門作為Bullrun計畫的一部分。總統顧問委員會隨後成立，負責審查美國國家安全局的行為，其中包括美國政府“全力支持而不是破壞制定加密標準的努力”。
2014年4月21日，NIST從其關於隨機數發生器的指南草案中撤回了Dual_EC_DRBG，該指南建議“儘快將當前用戶的Dual_EC_DRBG轉換為其餘三種已批准的算法之一。”
安全性
在NIST SP 800-90A中包含Dual_EC_DRBG的既定目的是其安全性基於數論的計算硬度假設。數學安全性降低證明可以證明，只要理論問題的數量很難，隨機數發生器本身就是安全的。但是，Dual_EC_DRBG的製造商沒有公布Dual_EC_DRBG的安全性降低，並且在NIST草案發布後不久就發現了Dual_EC_DRBG確實不安全，因為它每輪輸出太多比特。太多位的輸出（以及精心選擇的橢圓曲線點P和Q）是使NSA後門成為可能的原因，因為它使攻擊者能夠通過強力猜測來恢復截斷。在最終發布的標準中沒有更正過多位的輸出，使得Dual_EC_DRBG既不安全又無後顧之憂。
在許多其他標準中，意味著任意的常數是通過我的套數原則選擇的，其中常數是從例如pi中得出的，其方式幾乎沒有調整的餘地。但是，Dual_EC_DRBG沒有指定如何選擇默認的P和Q常量，可能是因為它們是由NSA構造為後門的。由於標準委員會意識到了後門的可能性，因此包括了實施者選擇自己的安全P和Q的方法。但是標準中的確切表述是這樣的，即FIPS 140-2驗證需要使用所謂的後向P和Q，因此OpenSSL項目選擇實施後門P和Q，即使他們意識到潛在的後門並且更願意生成他們自己的安全P和Q. 紐約時報後來寫道，國家安全局在標準化過程中起作用，最終成為該標準的獨立的一個編輯。
後來由Daniel RL Brown和KristianGjøsteen為Dual_EC_DRBG發布了安全證明，表明生成的橢圓曲線點與均勻隨機橢圓曲線點無法區分，並且如果在最終輸出截斷中輸出的位數較少，如果兩個橢圓曲線點P和Q是獨立的，如果顯示三個問題很難（通常只接受其中一個是硬的），那么Dual_EC_DRBG是安全的。證據依賴於三個問題很難的假設：決策性的Diffie-Hellman假設（通常被認為很難），以及兩個通常不被認為難以解決的新問題：截斷點問題和x-對數問題。與許多替代CSPRNG（沒有安全性降低）相比，Dual_EC_DRBG相當慢，但Daniel R.L.Brown認為安全性降低使得慢速Dual_EC_DRBG成為一種有效的替代方案（假設實現者禁用明顯的後門）。請注意，Daniel R.L. Brown為橢圓曲線加密專利的主要所有者Certicom工作，因此在推廣EC CSPRNG時可能存在利益衝突。
所謂的NSA後門將允許攻擊者通過查看單輪（32位元組）的輸出來確定隨機數生成器的內部狀態;然後可以容易地計算隨機數發生器的所有未來輸出，直到用外部隨機源重新接種CSPRNG。這使得例如SSL / TLS易受攻擊，因為TLS連線的設定包括以明文形式傳送隨機生成的加密隨機數。NSA所謂的後門將取決於NSA知道e * Q = P的單個e - 這是一個難題，給定Q和P，但如果你可以選擇P和Q則容易生成。因此，e是一個秘密密鑰，據推測只有NSA才知道，所謂的後門是一個盜版非對稱隱藏後門。Matthew Green的部落格文章“Dual_EC_DRBG的多重缺陷”通過使用Crypto 1997中引入的離散日誌kleptogram，對所謂的NSA後門如何工作進行了簡化解釋。
在許多其他標準中，意味著任意的常數是通過我的套數原則選擇的，其中常數是從例如pi中得出的，其方式幾乎沒有調整的餘地。但是，Dual_EC_DRBG沒有指定如何選擇默認的P和Q常量，可能是因為它們是由NSA構造為後門的。由於標準委員會意識到了後門的可能性，因此包括了實施者選擇自己的安全P和Q的方法。但是標準中的確切表述是這樣的，即FIPS 140-2驗證需要使用所謂的後向P和Q，因此OpenSSL項目選擇實施後門P和Q，即使他們意識到潛在的後門並且更願意生成他們自己的安全P和Q. 紐約時報後來寫道，國家安全局在標準化過程中起作用，最終成為該標準的獨立的一個編輯。
後來由Daniel RL Brown和KristianGjøsteen為Dual_EC_DRBG發布了安全證明，表明生成的橢圓曲線點與均勻隨機橢圓曲線點無法區分，並且如果在最終輸出截斷中輸出的位數較少，如果兩個橢圓曲線點P和Q是獨立的，如果顯示三個問題很難（通常只接受其中一個是硬的），那么Dual_EC_DRBG是安全的。證據依賴於三個問題很難的假設：決策性的Diffie-Hellman假設（通常被認為很難），以及兩個通常不被認為難以解決的新問題：截斷點問題和x-對數問題。與許多替代CSPRNG（沒有安全性降低）相比，Dual_EC_DRBG相當慢，但Daniel R.L.Brown認為安全性降低使得慢速Dual_EC_DRBG成為一種有效的替代方案（假設實現者禁用明顯的後門）。請注意，Daniel R.L. Brown為橢圓曲線加密專利的主要所有者Certicom工作，因此在推廣EC CSPRNG時可能存在利益衝突。
所謂的NSA後門將允許攻擊者通過查看單輪（32位元組）的輸出來確定隨機數生成器的內部狀態;然後可以容易地計算隨機數發生器的所有未來輸出，直到用外部隨機源重新接種CSPRNG。這使得例如SSL / TLS易受攻擊，因為TLS連線的設定包括以明文形式傳送隨機生成的加密隨機數。NSA所謂的後門將取決於NSA知道e * Q = P的單個e - 這是一個難題，給定Q和P，但如果你可以選擇P和Q則容易生成。因此，e是一個秘密密鑰，據推測只有NSA才知道，所謂的後門是一個盜版非對稱隱藏後門。Matthew Green的部落格文章“Dual_EC_DRBG的多重缺陷”通過使用Crypto 1997中引入的離散日誌kleptogram，對所謂的NSA後門如何工作進行了簡化解釋。
包含可能後門的軟體和硬體
使用Dual_EC_DRBG的實現通常是通過庫獲得的。 至少RSA Security（BSAFE庫），OpenSSL，Microsoft和Cisco都有包含Dual_EC_DRBG的庫，但只有BSAFE默認使用它。 據路透社的文章透露，RSA Security和NSA之間達成了1000萬美元的秘密協定，RSA Security的BSAFE是該算法中最重要的分銷商。OpenSSL的Dual_EC_DRBG實現存在一個缺陷，使其無法在測試模式之外工作，OpenSSL的Steve Marquess從中得出結論，沒有人使用OpenSSL的Dual_EC_DRBG實現。
NIST提供了經過CSPRNG實施FIPS 140-2驗證的產品清單。已驗證的CSPRNG列在Description/Notes欄位中。 請注意，即使Dual_EC_DRBG列為已驗證，默認情況下也可能未啟用。 許多實現來自庫實現的重命名副本。
BlackBerry軟體是非默認使用的示例。它包括對Dual_EC_DRBG的支持，但不支持默認值。但黑莓有限公司並沒有向可能使用它的任何客戶發出諮詢，因為他們認為可能的後門不是漏洞。傑弗里卡爾引用黑莓的一封信：
Dual EC DRBG算法僅適用於第三方開發人員通過[Blackberry]平台上的Cryptographic API。對於Cryptographic API，如果第三方開發人員希望使用該功能並明確設計和開發了一個請求使用API的系統，則可以使用它。
Bruce Schneier指出，即使未默認啟用，將後備CSPRNG作為選項實施也可以使NSA更容易監視具有軟體控制命令行開關以選擇加密算法的目標，或者“註冊表“系統，像大多數Microsoft產品，如Windows Vista：
特洛伊木馬非常非常大。不能說這是一個錯誤，這是收集按鍵的大量代碼。但是，將[bit-one]更改為[在註冊表中更改機器上的默認隨機數生成器]的第二位可能不會被檢測到。獲得後門是一種低陰謀，高度否定的方式。因此，將它放入庫和產品中是有好處的。- Bruce Schneier
2013年12月發布了一個概念驗證後門，它使用泄漏的內部狀態來預測隨後的隨機數，這種攻擊在下次重新開始之前是可行的。
2015年12月，瞻博網路宣布他們的ScreenOS固件的一些修訂使用了Dual_EC_DRBG和可疑的P和Q點，在他們的防火牆中創建了一個後門。最初它應該使用Juniper選擇的Q點，它可能或者可能沒有以可證明的安全方式生成。然後使用Dual_EC_DRBG為ANSI X9.17 PRNG播種。這會使Dual_EC_DRBG輸出混淆，從而殺死後門。但是，代碼中的“錯誤”暴露了Dual_EC_DRBG的原始輸出，從而危及系統的安全性。然後這個後門被一個改變了Q點和一些測試向量的未知方所取代。有關NSA通過Juniper防火牆進行持久後門訪問的指控已於2013年由Der Spiegel發布。
盜版後門是NSA的NOBUS政策的一個例子，它具有隻有他們可以利用的安全漏洞。
Dual EC DRBG算法僅適用於第三方開發人員通過[Blackberry]平台上的Cryptographic API。對於Cryptographic API，如果第三方開發人員希望使用該功能並明確設計和開發了一個請求使用API的系統，則可以使用它。
Bruce Schneier指出，即使未默認啟用，將後備CSPRNG作為選項實施也可以使NSA更容易監視具有軟體控制命令行開關以選擇加密算法的目標，或者“註冊表“系統，像大多數Microsoft產品，如Windows Vista：
特洛伊木馬非常非常大。不能說這是一個錯誤，這是收集按鍵的大量代碼。但是，將[bit-one]更改為[在註冊表中更改機器上的默認隨機數生成器]的第二位可能不會被檢測到。獲得後門是一種低陰謀，高度否定的方式。因此，將它放入庫和產品中是有好處的。- Bruce Schneier
2013年12月發布了一個概念驗證後門，它使用泄漏的內部狀態來預測隨後的隨機數，這種攻擊在下次重新開始之前是可行的。
2015年12月，瞻博網路宣布他們的ScreenOS固件的一些修訂使用了Dual_EC_DRBG和可疑的P和Q點，在他們的防火牆中創建了一個後門。最初它應該使用Juniper選擇的Q點，它可能或者可能沒有以可證明的安全方式生成。然後使用Dual_EC_DRBG為ANSI X9.17 PRNG播種。這會使Dual_EC_DRBG輸出混淆，從而殺死後門。但是，代碼中的“錯誤”暴露了Dual_EC_DRBG的原始輸出，從而危及系統的安全性。然後這個後門被一個改變了Q點和一些測試向量的未知方所取代。有關NSA通過Juniper防火牆進行持久後門訪問的指控已於2013年由Der Spiegel發布。
盜版後門是NSA的NOBUS政策的一個例子，它具有隻有他們可以利用的安全漏洞。
