Did NSA Put a Secret Backdoor in New Encryption Standard?
http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
Bruce Schneier 11.15.07
隨機亂數（random numbers）對於密碼學相當緊要：可用在加密密鑰（encryption keys）、隨機認證挑戰（random authentication challenges）、初始向量（initialization vectors）、一次性隨機數（nonces）、密鑰協定方案（key-agreement schemes）、產生質數等等。破解了隨機亂數產生器（random-number generator），在大部分的情況下，你就等同於破解了整套安全系統。這就是為何你要對一套新的隨機亂數標準擔憂，那包含一套緩慢、設計拙劣的演算法，而且還可能包含後門給美國國家安全局（NSA）使用。
產生亂數並不是件簡單容易的事，而且這幾年來，研究者已經發現很多問題與攻擊方法（http://www.cs.virginia.edu/~rjg7v/annotated.html）。最近一篇報告（http://eprint.iacr.org/2007/419），在 Windows 2000 隨機亂數產生器中發現瑕疵。另一篇報告（PDF 檔，http://eprint.iacr.org/2006/086.pdf）在 Linux 隨機亂數產生器中發現缺點。回到 1996 年，一套 SSL 早期版本遭到破解（http://www.ddj.com/windows/184409807）因為有個缺陷在其隨機亂數產生器中。John Kelsey 連同 Niels Ferguson 在 1999 年和筆者共同創作 Yarrow（http://www.schneier.com/yarrow.html），一套基於我們自己密碼分析研究（（http://www.schneier.com/paper-prngs.html）的隨機亂數生器。筆者在 4 年後於一本叫做 Practical Cryptography（http://www.schneier.com/pc.html）的書中，筆者與 Ferguson 合寫，改善了這項設計 -- 並將其命名為 Fortuna。
美國政府在今年釋出一套新的隨機亂數產生器官方標準，而且它很有可能接著會被世界各地的軟、硬體開發者採納使用。它叫做 NIST Special Publication 800-90（PDF 檔，http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf），這份 130 頁的文件包含 4 中不同的、被認可的技術，稱為 DRBGs（Deterministic Random Bit Generators，決定論的隨機位元產生器）。這 4 中全都基於現有的密碼學元件（primitives）。一種是基於雜湊函數，一種是 HMAC 演算法（雜湊訊息身分驗證編碼，http://en.wikipedia.org/wiki/HMAC）一種是區塊加密（block ciphers）還有一種是橢圓曲線（elliptic curves）。只使用少數受到充分信任的密碼學元件，是種聰明的密碼學設計，所以利用現有的零件打造一套隨機亂數產生器是件好事。
不過這些產生器其中之一 -- 基於橢圓曲線的那一個 -- 並不像它者。被稱為 Dual_EC_DRBG，那不只是讀來佶屈聱牙，而且比它的同夥要慢上三個大大的數量級（1000 倍）。它會列在標準中只是因為它受到 NSA 擁護，這個單位在一年之前於 ANSI 一個相關的標準化計畫中首度推薦它。
NSA 總是密切涉及美國密碼學標準 -- 畢竟它是製造與破解機密編碼的專家。所以該局參與（美國商業部） NIST 標準，就自身而論並非惡意。只有當你看見 NSA 貢獻的幕後，問題才會浮現。
Dual_EC_DRBG 的問題（http://eprint.iacr.org/2006/190）在 2006 年初首度被描述（http://eprint.iacr.org/2007/048）。其中的數學相當複雜，不過一般來說，它所產生的隨機亂數有小偏差（bias）。這個問題不足以使得這套演算法一無是處 -- 而且 NIST 標準的附錄 E 描述了一個非必要的 work-around 以避免掉這個問題 -- 不過那是憂慮的起因。密碼學家是保守的一群人：我們不喜歡使用即便是只有一丁點小問題的演算法。
但今日，還有一個甚至更臭名遠播的東西圍繞在 Dual_EC_DRBG 四週。在 今年八月的 CRYPTO 2007 研討會，一篇非正式的演示中（PDF 檔，http://rump2007.cr.yp.to/15-shumow.pdf）Dan Shumow 與 Niels Ferguson 證明這套演算法包含了一個弱點，那只能用「後門」來描述它。
下面指出它如何運作：這裡有串常數 -- 一組固定的數字 -- 在標準中，用來定義該演算法的橢圓曲線。這些常數列在 NIST 出版品的附錄 A 中，不過並沒有解釋它們打哪來。
Shumow 與 Ferguson 證實，這些數字與居次的、祕密的一組數字有某種關係，那能扮演某種萬能鑰匙般的角色。如果你知道這組祕密數字，只要取得隨機亂數產生器 32 位元的輸出，你就可以「預料」其後的輸出。
打個實際一點的比方：為了要破解 TLS（http://en.wikipedia.org/wiki/Secure_Sockets_Layer）協定的安全，你只需要監視網路加密連線。而如果你知道祕密數字，你就能完全破解任何 Dual_EC_DRBG 的實例。
研究者們不知道這些祕密數字為何。不過因為這套演算法的運作方式，製造常數的人可能知道；那人擁有數學上的良機，能一前一後地產生常數與祕密數字。
當然，我們沒有辦法知道 NSA 是否知道可破解 Dual_EC-DRBG 的祕密數字。我們沒有辦法知道，是否有位 NSA 僱員研究出他自己對於常數的看法 -- 而且他有祕密數字。我們不知道是否有來自於 NIST 的某位，或 ANSI 工作小組當中的某人擁有它。或許沒有人有。
我們不知道這些常數首先從哪裡出現。我們只知道，想出這些東西的人可能擁有這個後門的鑰匙。而我們知道 NIST -- 或任何人 -- 無法用其他方法證明。
這真的是會引起驚慌的東西。
即使沒人知道祕密數字，但事實上這個後門的出現讓 Dual_EC_DRBG 變得相當脆弱。如果某人只要能決該演算法的橢圓曲線問題的一則實例，他實際上就擁有該領域的密鑰。他就能用它來進行他想要的任何惡毒目的。或者，他可以發表他的結果，使得該亂數產生器的每一種實作變得徹底不安全。
有可能以其他方法來實作 Dual_EC_DRBG，讓它避免掉這種後門，那就是藉由使用其他安全的隨機亂數產生器來產生新常數，然後公佈這個種子（seed）。這種方法甚至出現在 NIST 文件中，在附錄 A 裡。不過這道程序是非必要的，而且依筆者的猜測，大部分 Dual_EC_DRBG 的實作將不會理它。
如果這篇報導讓你覺得很困惑惶恐，加入這個俱樂部吧。筆者不解為何 NSA 如此堅持要將 Dual_EC_DRBG 納入標準當中。它沒理由當個活板門（trap door，指當成後門）：它是公開的，而且頗為顯著。它沒有工程上的前途：因為它太慢，沒有人想要用它。它也沒有向後相容性的遠景：要清掉一套隨機亂數產生器以另一套取而代之相當容易。
筆者的勸告是，如果你真的需要一套隨機亂數產生器，不要在任何情況下使用 Dual_EC_DRBG。如果你得使用 SP 800-90 這分文件中的東西，那使用 CTR_DRBG 或 Hash_DRBG。
在此同時，NIST 與 NSA 都得出來給個交代。
______________
Bruce Schneier，是 BT Counterpane 的 CTO，以及 Beyond Fear: Thinking Sensibly About Security in an Uncertain World 這本書的作者。
※ 相關報導：
＊ 機率遊戲
＊ DIY 亂數產生器
＊ 奇妙的 iPod 隨機播放是心電感應嗎？
＊ 真正隨機的亂數產生器上線
＊ 成本超低的真正隨機與物理性指印
＊ 搜尋 MD5 碰撞原始碼公佈
＊ 大陸女教授王小雲 破解美國安局超難密碼
＊ 世界頂級密碼 中國教授十年破五套
＊ 取代 SHA-1 的公開選拔賽
＊ 非破壞壓縮與 AI 獎金？
＊ 駭客在 DefCon 秀開鎖
＊ 從刷卡安全有漏洞 到肺結核個資外洩
沒有留言:
張貼留言