跳转到内容

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 attackDES加密的机器问世,名为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).