EFF DES破解机

EFF DES破解机（英语：EFF DES cracker）是电子前哨基金会（EFF）在1998年建造的机器，用于暴力破解美国政府的数据加密标准，即DES加密算法，昵称“深译”（英语：Deep Crack）。这台机器能够对DES密钥空间中所有的密钥逐一进行尝试，从而将密文破解，其目的在于证明DES的密钥长度不足，不能保证安全。

电子前哨基金会这台价值250,000美元的DES破解机包含1,856个特别定制的专用集成电路，能在短短几天之内暴力破解DES的密钥。图中展示了机器的双面电路板，安装了64个“深译”芯片

本机器的相关技术资料，包括原理图、电路图、芯片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 (Technical report). 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]. 
  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）.