跳至內容

EFF DES破解機

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
電子前哨基金會這台價值250,000美元的DES破解機包含1,856個特別定製的專用集成電路，能在短短幾天之內暴力破解DES的密鑰。圖中展示了機器的雙面電路板，安裝了64個「深譯」芯片

EFF DES破解機（英語：EFF DES cracker）是電子前哨基金會（EFF）在1998年建造的機器，用於暴力破解美國政府的數據加密標準，即DES加密算法，暱稱「深譯」（英語：Deep Crack）。這台機器能夠對DES密鑰空間中所有的密鑰逐一進行嘗試，從而將密文破解，其目的在於證明DES的密鑰長度不足，不能保證安全。

本機器的相關技術資料，包括原理圖、電路圖、芯片VHDL源代碼、模擬器源代碼，均被電子前哨基金會公開發表在《破解DES》一書中，並使用了公有領域許可協議，允許任何人複製、使用與修改。為了避開美國政府的出口管制，源代碼是以書本形式而不是電子形式發布的。書中的源代碼含有機器可讀的元數據，方便讀者使用OCR將源代碼錄入計算機。[1]

背景

密鑰長度爭議

DES是最早的計算機加密算法之一，它在政府、金融、網絡等許多領域都得到了廣泛應用。並且，該加密算法是美國聯邦政府的一項標準，美國政府鼓勵使用DES加密除了國家機密之外的任何敏感信息。[2]

DES加密算法的密鑰長度為56位[3]，這意味着加密時存在256個密鑰可供選擇，即7.2萬萬億（72,057,594,037,927,936）種可能性。但是，DES依然長期面臨「密鑰長度過短、安全性不足」的批評。

早在1975年算法公開之初，著名的斯坦福大學密碼學家馬丁·赫爾曼與惠特菲爾德·迪菲就批評DES算法易被暴力破解，因此不安全，惟有將密鑰長度提升到至少128位才能保證安全。[4]二人還構想了一台可在一天內測試所有密鑰的機器，需要的成本為2000萬美元，並指出這對於美國國家安全局（NSA）等情報機構而言並非是一筆很大的開銷，並認為成本在10年後還會進一步下降到20萬美元。[5]

在隨後的20年間，芯片的價格確實不斷下降、性能不斷提升，使電子前哨基金會這樣的小型非營利組織也具有了破解DES的能力。[6]

對密碼學的管制

參見：密碼戰爭

在20世紀，以NSA為首的美國政府以及盟友為了維護自身的利益，對密碼學進行嚴格管制，限制密碼學的傳播並降低現有系統的安全性，甚至加入後門。[7]例如，一位在1980年代曾參與過GSM研發的專家表示，為保護手機通話不被竊聽，原計劃採用128位加密進行保護。但隨後遭到英國政府方面的施壓，使最終的A5/1加密算法被迫削弱為54位，團隊中的許多專家對此十分憤怒。[8]時至90年代末，隨着互聯網與電子商務的興起，使用密碼學保護公民隱私與商業信息的訴求，與美國政府管制政策之間的矛盾逐漸升溫。[9]媒體與公眾將這段歷史時期統稱為密碼戰爭。[7]

直到1998年DES已被兩次破解後，美國聯邦調查局局長路易斯·弗里（英語：Louis Freeh）依然堅持對密碼學的嚴格管制，始終不承認DES並不安全：

DES挑戰賽

由於上述原因，RSA安全公司（英語：RSA Security）希望以實際行動向公眾展示DES的密鑰長度過短，時下已不能保證安全性，因此在1997年舉辦了首屆DES挑戰賽，成功者可獲得一萬美元的獎金[11]。第一屆大賽被來自科羅拉多州洛夫蘭的洛克·沃瑟所帶領的團隊破解成功，耗時96天[12][13][14]。接着，RSA安全公司隨後舉辦了第二屆挑戰賽[15]，其中的初賽由互聯網最早的分布式計算平台distributed.net（英語：distributed.net）的22,000名志願者們挑戰成功。他們使用自己的個人電腦參與計算，共歷時39天，於1998年2月成功破解密文，[16][17]解密後得到「機密信息為：人多好辦事」（The secret message is: Many hands make light work）的文本。

電子前哨基金會「深譯」使用的定製微芯片

即使在DES已被兩次破解以後，聯邦調查局局長路易斯·弗里依然以「破譯時間過長，沒有意義」為理由，拒絕承認DES已不安全。因此，RSA再次發起了第二次挑戰賽的複賽。[10]1998年，電子前哨基金會建造了「深譯」（名字來自IBM的「深藍」國際象棋電腦），總共花費不超過250,000美元。[18]為了響應第二屆DES挑戰賽的號召，「深譯」加入了1998年7月15日舉行的複賽，僅用56小時成功破解了DES加密的消息，獲得了10,000美元獎金。破譯後得到「機密信息為：是時候讓128位，192位與256位密鑰登場了」（The secret message is: It's time for those 128-, 192-, and 256-bit keys）的文本。[19][20][21]此次暴力破解攻擊展現了破解DES是非常可行的計劃，多數政府和大型企業完全有能力建造一台類似「深譯」的機器。[22]

六個月之後，電子前哨基金會響應了RSA安全公司舉辦的第三屆挑戰賽[23][24][25][26]，並與distributed.net團隊合作破譯了另一則DES加密的消息，再次獲得了10,000美元。這次的整個破譯過程不到一天，僅用22小時15分，於1999年1月19日完成破解。[27][28][29][30][31]

同年10月，美國政府宣布DES標準不會被廢除，但推薦使用其增強版三重DES替代。[32]然而，這需要將DES反覆運行三次，使計算速度更加緩慢。而且與直覺相反，由於中途相遇攻擊的存在，三重DES的安全性僅僅是原密鑰長度的兩倍（2112），並非三倍（2168）。[33]可見三重DES的安全性只有112位，離密碼學界所推薦的128位仍有一定差距，而且還需要高昂的計算成本，將其應用於互聯網時不能令人滿意。[34]

2002年5月26日，高級加密標準（即AES）正式取代了DES數據加密標準成為了新的聯邦政府標準。[35]不同於DES，AES不僅將密鑰長度提升至128位與256位，還大幅提升了計算速度，[36]並廣泛應用於今日的互聯網。[37][38]

技術

「深譯」由密碼學研究公司（英語：Cryptography Research）、先進無線科技公司（Advanced Wireless Technologies）與電子前哨基金會聯合設計，總設計師是密碼學研究公司的主席保羅·科奇（英語：Paul Kocher）。先進無線科技公司製造了1856片定製芯片（代號「深譯」，型號AWT-4500），分別組裝在29塊電路板上，每塊電路板64片。這些電路板再被分別放入6個模塊，然後安裝在一台改裝過的Sun-4/470工作站（英語：Sun-4）的機箱中。[1]為了協助密鑰的搜尋工作，另外還使用了一台運行Linux操作系統的個人電腦負責控制機器。[6][1]整台機器每秒鐘能嘗試900億個密鑰，共需要9天時間對所有可能的密鑰進行完整的搜索，但實際使用時，破解出正確的密鑰往往只需要花費一半的時間。[20]

本機器的相關技術資料，包括原理圖、電路圖、芯片VHDL源代碼、模擬器源代碼，均被電子前哨基金會公開發表在《破解DES》一書中，並使用了公有領域許可協議，允許任何人複製、使用與修改。為了避開美國政府的出口管制，源代碼是以書本而不是電子形式發布的。書中的源代碼含有機器可讀的元數據，方便讀者使用OCR將源代碼錄入計算機。[1]

2006年，又一台定製硬件攻擊（英語：custom hardware attack）DES加密的機器問世，名為COPACOBANA（為英語：COst-optimized PArallel COdeBreaker的縮寫，意為「低成本並行密碼破譯機」）。該機器得益於集成電路技術的進步，採用FPGA的設計，進一步降低了破解DES的成本。[39][40]2012年7月，安全研究人員大衛·赫爾頓（David Hulton）與莫克西·馬林斯佩克（Moxie Marlinspike）公布了一個通過暴力破解DES加密從而破解MS-CHAPv2協議的雲計算工具，這讓普通大眾能夠在24小時之內利用一對已知的明文和密文破解DES密鑰。[41]

參考文獻

  1. ^ 1.0 1.1 1.2 1.3 Electronic Frontier Foundation. Cracking DES - Secrets of Encryption Research, Wiretap Politics & Chip Design. Oreilly & Associates Inc. 1998 [2016-10-30]. ISBN 1-56592-520-3. （原始內容存檔於2013-10-17）. 
  2. ^ National Institute of Standards and Technology. Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard. Federal Information Processing Standards Publication 74 (技術報告). 1981 [2016-10-31]. （原始內容存檔於2004-02-15）. 
  3. ^ 約翰遜, T. 美国冷战期间的密码学，1945-1989.第三部：解雇和重组，1972-1980，232页. NSA, DOCID 3417193 (file released on 2009-12-18, hosted at cryptome.org). 2009-12-18 [2010-01-03]. （原始內容存檔於2010-08-05）. 
  4. ^ 迪菲, W與海爾曼, M, 「NBS的DES密碼分析完全調查 （頁面存檔備份，存於網際網路檔案館）」 IEEE Computer 10 (6), June 1977, pp74–84
  5. ^ DES (Data Encryption Standard) Review at Stanford University - Recording and Transcript. 1976 [2017-03-31]. （原始內容存檔於2012-05-03）. 
  6. ^ 6.0 6.1 EFF. Frequently Asked Questions (FAQ) About the "EFF DES Cracker" Machine. [2016-10-31]. （原始內容存檔於2016-10-31）. The PC that controls the machine originally ran Windows 95, but the EFF team replaced it with Linux so it could be operated remotely over the Internet. 
  7. ^ 7.0 7.1 Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age, Steven Levy, Penguin, 2001
  8. ^ Sources: We were pressured to weaken the mobile security in the 80's. Aftenposten. 2014 [2018-04-10]. （原始內容存檔於2016-04-25）. 
  9. ^ Ranger, Steve. The undercover war on your internet secrets: How online surveillance cracked our trust in the web. TechRepublic. 24 March 2015 [2016-06-12]. （原始內容存檔於2016-06-12）. 
  10. ^ 10.0 10.1 RSA ANNOUNCES ANOTHER DES CRACKING CONTEST FOR JANUARY. The Free Library. December 23, 1998 [2018-04-10]. （原始內容存檔於2022-04-06）. 
  11. ^ RSA Data Security. RSA Laboratories Secret-Key Challenge. 1997 [2016-10-31]. （原始內容存檔於1999-02-02）. 
  12. ^ Curtin, Matt; Dolske, Justin. A Brute Force Search of DES Keyspace. ;login: (USENIX). May 1998 [2016-10-31]. （原始內容存檔於2016-10-19）. 
  13. ^ Team of Universities, Companies and Individual Computer Users Linked Over the Internet Crack RSA's 56-Bit DES Challenge (新聞稿). REDWOOD CITY, Calif., USA: RSA Security. RSA Security. June 19, 1997 [2016-10-31]. （原始內容存檔於2006-11-07）. 
  14. ^ Associated Press. Standard cryptography code broken. USA Today (SAN FRANCISCO). Feb 28, 1999 [2016-10-31]. （原始內容存檔於1999-04-28）. 
  15. ^ RSA to Launch "DES Challenge II" at Data Security Conference (新聞稿). REDWOOD CITY, Calif., USA: RSA Security. RSA Security. December 17, 1997 [2016-10-31]. （原始內容存檔於2006-11-07）. 
  16. ^ David C. McNett. The secret message is.... distributed.net. 24 February 1998 [27 February 2014]. （原始內容存檔於2016-03-04）. 
  17. ^ RSA’s Secret-Key Challenge Solved by Distributed Team in Record Time (新聞稿). REDWOOD CITY, Calif., USA: RSA Security. RSA Security. February 26, 1998 [2016-10-31]. （原始內容存檔於2006-11-07）. 
  18. ^ DES Cracker Project. EFF. [July 8, 2007]. （原始內容存檔於2017年5月7日）. On Wednesday, July 17, 1998 the EFF DES Cracker, which was built for less than $250,000, easily won RSA Laboratory's "DES Challenge II" contest and a $10,000 cash prize. 
  19. ^ DES-II-2 Challenge. [2016-10-31]. （原始內容存檔於2002-02-01）. 
  20. ^ 20.0 20.1 Fed Encryption Standard Exposed. Wired. 17 Jul 1998 [2016-10-31]. （原始內容存檔於1998-12-05）. 
  21. ^ EFF quickly cracks Data Encryption Standard. ZDNet. 17 Jul 1998 [2016-10-31]. （原始內容存檔於1999-01-16）. 
  22. ^ Kelly, S.. Security Implications of Using the Data Encryption Standard (DES). IETF. December 2006. RFC 4772. This project clearly demonstrated that a practical system for brute force DES attacks was well within reach of many more than previously assumed. Practically any government in the world could easily produce such a machine, and in fact, so could many businesses. 
  23. ^ RSA to Launch DES Challenge III Contest at 1999 Data Security Conference (新聞稿). SAN MATEO, Calif., USA: RSA Security. RSA Security. December 22, 1998 [2016-10-31]. （原始內容存檔於2006-12-11）. 
  24. ^ Sykes, Rebecca. RSA wants you to crack this code. CNN. December 23, 1998 [2016-10-31]. （原始內容存檔於2001-05-17）. 
  25. ^ Oakes, Chris. RSA: Crack DES in a Day. Wired. Dec 22, 1998 [2016-10-31]. （原始內容存檔於2006-02-22）. 
  26. ^ Glave, James. The Great Code Race. Wired (SAN JOSE, California). Jan 18, 1999 [2016-10-31]. （原始內容存檔於2000-08-17）. 
  27. ^ David C. McNett. US Government's Encryption Standard Broken in Less Than a Day (PDF). distributed.net. 19 January 1999 [27 February 2014]. （原始內容存檔 (PDF)於2016-03-04）. 
  28. ^ RSA Code-Breaking Contest Again Won by Distributed.Net and Electronic Frontier Foundation (EFF) (新聞稿). San Jose, CA., USA: RSA Security. RSA Security. January 19, 1999 [2016-10-31]. （原始內容存檔於2006-12-11）. 
  29. ^ Record set in cracking 56-bit crypto. CNET (SAN JOSE, California). January 2, 2002 [2016-10-31]. （原始內容存檔於2016-10-31）. 
  30. ^ Glave, James. Code-Breaking Record Shattered. Wired. Jan 19, 1999 [2005-04-15]. （原始內容存檔於2005-04-15）. 
  31. ^ Nelson, Matthew. Cracking DES code all in a day's work for security experts. CNN (SAN JOSE, Calif.). January 21, 1999 [2016-10-31]. （原始內容存檔於2016-10-31）. 
  32. ^ United States Department of Commerce. FIPS PUB 46-3: Data Encryption Standard (DES) (PDF). 1999-10-25 [2016-11-01]. （原始內容存檔 (PDF)於2012-04-07）. 
  33. ^ Blondeau, Céline. Lecture 3: Block Ciphers (PDF). CS-E4320 Cryptography and Data Security. [2018-04-10]. （原始內容存檔 (PDF)於2018-02-23）. 
  34. ^ Schmeh, Klaus. Cryptography and Public Key Infrastructure on the Internet. Wiley. 2003: 68, 71. ISBN 978-0470847459. 
  35. ^ Westlund, Harold B. NIST reports measurable success of Advanced Encryption Standard. Journal of Research of the National Institute of Standards and Technology. 2002 [2016-11-01]. （原始內容存檔於2016-11-01）. 
  36. ^ Schneier, Bruce; Kelsey, John; Whiting, Doug; Wagner, David; Hall, Chris; Ferguson, Niels. Performance Comparisons of the AES submissions (PDF). 1999-02-01 [2010-12-28]. （原始內容 (PDF)存檔於2011-06-22）. 
  37. ^ Hubert Kario. July 2016 scan results. Securitypitfalls. [2016-11-02]. （原始內容存檔於2016-11-04）. 
  38. ^ Julien Vehent. TLS stats from 1.6 billion connections to mozilla.org. Quelques digressions sous GPL... 2016-08-04 [2016-11-02]. （原始內容存檔於2016-09-05）. 
  39. ^ 存档副本. [2016-10-30]. （原始內容存檔於2016-07-24）. 
  40. ^ Kumar, Sandeep; Paar, Christof; Pelzl, Jan; Pfeiffer, Gerd; Schimmler, Manfred. Breaking Ciphers with COPACOBANA –A Cost-Optimized Parallel Code Breaker. Cryptographic Hardware and Embedded Systems - CHES 2006. Workshop on Cryptographic Hardware and Embedded Systems: 101–118. 2006 [2016-10-31]. doi:10.1007/11894063_9. [永久失效連結]
  41. ^ Marlinspike, Moxie; Hulton, David. Divide and Conquer: Cracking MS-CHAPv2 with a 100% success rate. Cloud Cracler. 29 July 2012 [2016-10-30]. （原始內容存檔於2016-03-16）. 
取自「https://zh.wikipedia.org/w/index.php?title=EFF_DES破解机&oldid=84362809」