DES的破解方法?

时间:2021-12-09 03:28:40

《秘密密钥挑战赛》节选

  1997年1月28日,美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”(Secret-KeyChallange)竞赛,分别悬赏$1000、$5000、$10000用于攻破不同密钥长度的RC5密码算法,同时还悬赏$10000破密钥长度为56bits的DES算法。

  加密明文的密钥是随机选取的,明文和密钥都被严格保密,只向挑战者们公布密文和所用的初始化向量。解出的密钥以E-Mail的方式迅速报告给RSA公司,第一个解出密钥的人即成为相应挑战赛的胜利者。加利福尼亚大学伯克利分校的研究生IanGoldberg用大约250台工作站组成的网络,只用了3.5小时就攻破了40位的RC5算法。在瑞士建立的一个欧洲小组使用了遍及欧洲的3,500台机器,13天时间攻破48位密码。Brewer预计在类似的环境中攻破一个56位的密码需要大约22年。

  DES分组加密算法是美国*于1977年公布的数据加密标准,已在银行业和金融业使用了近二十年,自从其公布起,DES就一直不断地被人们研究和攻击,它是世界上最知名的、使用最广泛的分组密码算法。目前攻击DES的最有效的办法是密钥穷举攻击,Verser设计了一个密钥穷举攻击程序,用以穷举所有可能的DES密钥,直至找到正确的那一个密钥,这个计算机程序可以从Internet上分发和下载。他把这项计划命名为DESCHALL,这项计划开始时只有几百人参与,最终吸引了数万名志愿者参加。每有一名新的志愿者加入,DESCHALL小组就为其分配一部分密钥空间让其测试,这样,正确的密钥最终会在某一名志愿者的计算机中出现。参与DESCHALL计划的Internet志愿者使用了企业、高校和*大量的计算资源,其中有计算能力强大的小型机、工作站,更不乏普通的PC机,参与的志愿者或计算机的具体数字尚未有精确的统计,但根据IP地址统计至少有78156个。基于IP地址的统计还显示,每天最多有1400台志愿计算机在工作。

  美国克罗拉多州的程序员RockeVerser从97年3月13日起,在Internet上数万名志愿者的协同工作下,在RSA挑战赛公布之后的第140天、DESCHALL计划实施的第96天,6月17日的晚10点39分,盐湖城iNetZ公司的职员Michael Sanders在他那台主频为奔腾90Hz、16M内存的PC机上成功地解出了DES的明文,找到了正确的密钥(8558891ab0c851b6)。RockeVerser的这次胜利,很有可能成为其最后一击,标志着DES时代的即将结束。这将作为密码学上的一个里程碑载入史册。

  DES的全部密钥穷举量为7.2e16,DESCHALL计划完成时,搜索的密钥量为1.773e16,占全部密钥穷举量的24.6%,平均每天最多搜索6.0e14个,每秒最多搜索7,0e9个,其中最后24小时搜索了5.59e14个,占全部穷举量的0.7%,假若一开始就以这个速度搜索,则DESCHALL计划只需32天即可完成。DES被破的消息公布之后,舆论界顿时哗然,因为依靠Internet的分布式计算能力,公众已经可以轻而易举地攻破DES。在如此短的时间内DES被攻破的消息让那些使用DES进行保密通信的机构、公司和个人从心里打了一个寒颤。英国剑桥的资金和技术决策主任DavidWeisman认为,DES的破解应使人们认识到随着计算能力的增长,必须相应增加算法的密钥长度。

  此次DESCHALL在96天中攻破DES,还是有一定的“幸运”因素在内。根据统计资料,整个搜索过程遍历密钥空间的仅为24.6%,这就大大节约了穷搜所需时间。截止到目前,56比特的RC5挑战至今尚未被攻破。这样的挑战还会继续进行,虽然未见分晓,但可以认为,不论是DES、RC5还是其它别的算法,也不论算法的强弱,56比特密钥的使用方式都是不保密的。

  在DESCHALL向DES发起穷举攻击的同时,从瑞典发起的一个攻击小组,SolNET也对DES发起了攻击。由于美国严禁密钥攻击算法出口到除加拿大的其他国家,因此DESCHALL计划仅限于美国和加拿大执行。而SolNET通过向世界发布他们的软件,也取得了可观的成绩。他们的搜索速度最高达到了每秒30亿密钥组合,并在不断加快,到竞赛结束时他们总共搜索了近一亿亿可能密钥,约为密钥总空间的七分之一。

  在DESCHALL完成了他们的工作后,SolNET在网页上发表了一条简短的消息,宣布SolNET的工作停止,并请仍然有兴趣的人参加Bovine RC5攻击计划对56位RC5密钥的攻击。事实上,现在已有数十个小组开始了这项工作,而Bovine看来是很有希望赢得这次竞赛的小组之一。

 

http://bbs.pediy.com/archive/index.php?t-25261.html