秘密的密钥挑战 国际互联网上一次成功的解密行动 于哲 1997-01-01 　　美国政府只允许出口密钥长度小于５６比特的加密产品，而且必须将钥匙托管给联邦授权机构。今年１月，美国一家著名的数据安全公司，为了迫使政府放松对加密产品的出口限制，通过国际互联网组织了一次名为“秘密的密钥挑战”的大规模协同解码竞赛，数万名志愿者在程序员Ｒｏｃｋｅ　Ｖｅｒｓｅｒ的指挥下，用了９６天的时间成功地破译了长达５６ｂｉｔ的密钥，美利坚为之沸腾。 #1　　悬赏破密 　　１９９７年１月２８日，美国的ＲＳＡ数据安全公司（以下简称ＲＳＡ公司）在公司的安全年会上，公布了一个名为“秘密的密钥挑战”的竞赛项目，分别悬赏一万、五千、一千美元用于攻破不同密钥长度的ＲＣ５密码算法，同时还悬赏一万美元破解密钥长度为５６比特的ＤＥＳ密码算法。ＲＳＡ公司发起这场挑战赛的目的是为了调查在互联网上的分布式计算能力，更主要的是为了测试不同密钥长度的ＲＣ５算法和密钥长度５６比特的ＤＥＳ算法的相对强度，也就是不被攻破的防守能力。 　　ＲＳＡ公司开展的一系列挑战赛选取了一些字符串作为待加密的明文，所有的字符都是以“Ｔｈｅ　ｕｎｋｎｏｗｎ　ｍｅｓｓａｇｅ　ｉｓ：”开头，其后加上不同的ＡＳＣＩＩ字符串，加密明文的密钥是随机选取的，对于ＤＥＳ算法，使用分组链接的加密模式生成密文，其初始化向量，也是随机选取的，明文和密钥都被严格保密，只向挑战者们公布密文和所用的初始化向量。挑战者解出密钥后用Ｅ－ｍａｉｌ（互联网上的电子邮件）的方式迅速报告给ＲＳＡ公司，第一个解出密钥的人即成为相应挑战赛的胜利者。 #1　　背景 　　ＲＳＡ数据安全公司是世界著名的密码公司。在１９８２年由公开密钥密码系统的发明人Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ和Ａｄｅｌ－ｍａｈ共同出资建立，总部设在美国加利福尼亚州的红杉市（Ｒｅｄｗｏｏｄ）。在世界范围内有超过八千万份ＲＳＡ数据加密和认证技术的拷贝在安装和使用。ＲＳＡ技术是Ｉｎｔｅｒｎｅｔ、ＷＷＷ、ＩＴＵ－Ｔ、ＩＳＯ、ＡＮＳＩ、ＩＥＥＥ，还有商业、金融和全球电子贸易网络的标准和协议中的标准的一部分。 　　ＤＥＳ是数据加密标准（Ｄａｔａ　ＥｎｃｒｙＰｔｉｏｎ　Ｓｔａｎｄａｒｄ）的缩写，是一个在１９７７年由美国政府作为一个官方标准定义和支持的分组加密算法。它的细节可以在最近的美国官方联邦信息处理标准版本中找到，ＤＥＳ算法自从公布之日起，人们对它就开始了广泛的研究，它是世界上最著名、使用最广泛的加密算法之一。美国国家技术和标准协会（ＮＩＳＴ）每五年将其作为一个美国政府加密标准进行重新审定。 　　ＮＩＳＴ是美国商业部的一个局，以前称为国家标准局（ＮＢＳ）。ＮＩＳＴ颁布他们希望能够适合美国所有计算机系统的标准和指南，并且实施对企业和研究机构的监督，官方标准以ＦＩＰＳ（美国联邦信息处理标准）版本公布。１９８７年，美国国会通过了计算机安全法案，它赋予ＮＩＳＴ以保护敏感、不能公开的美国政府计算机系统信息的权力，并且鼓励ＮＩＳＴ与美国政府其他一些部门和个人企业制定进一步的计算机安全标准。ＤＥＳ的最后一次审定是在１９９３年。然而，ＮＩＳＴ宣称在今年的晚些时候，他们可能不会对ＤＥＳ进行重新审定。 　　ＲＣ５是由美国麻省理工学院的Ｒｏｎ　Ｒｉｖｅｓｔ博士为ＲＳＡ数据安全设计的一个快速分组加密算法。它是一个块长、密钥长度、运算轮数都可变的算法。它的块长可以是３２、６４或１２８位。运算轮数可以从０到２５５轮。密钥长度则可以在０位到２０４８位之间任意选取。这在安全和高效之间提供了极大的灵活性。 #1　　攻击行动 　　“秘密的密钥挑战”竞赛细节公布后，全美的“网虫”们如蛾扑火，纷纷组织攻关小组，都想抢得头功。科罗拉多州的一位叫作Ｒｏｃｋｅ　Ｖｅｒｓｅｒ的程序员苦思冥想了近４０天，终于设计出一个可通过互联网分段运算的密钥穷举攻击程序，用以穷举所有可能的ＤＥＳ密钥，直至找到正确的那一个密钥为止，而且这个计算机程序可以从互联网上分发和下载。 　　Ｖｅｒｓｅｒ把这项计算命名为ＤＥＳＣＨＡＬＬ，采取招募志愿人员的办法协同攻关。每有一名新的志愿者加入，ＤＥＳＣＨＡＬＬ小组就为其分配部分密钥空间让其测试，这样，正确的密钥最终会被某一个志愿者破解。 　　一个５６比特的ＤＥＳ密码的全部密钥穷举数量为７２，０５７，５９４，０３７，９２７，９３６（也就是７．２亿亿）次。 　　大学和研究所的年轻电脑爱好者迅速成为ＤＥＳＣＨＡＬＬ计划的中坚力量，一个非正式的竞争悄悄地在全美各大学展开。据透露，在攻击行动中，单是麻省理工学院，就有２２６台计算机参与ＤＥＳＣＨＡＬＬ计划。众多的佐治亚理工学院的学生们也狂热地加入其中。５月１日，佐治亚理工学院只有２３台ＰＣ机参战，一些网友通过ＢＢＳ发出倡议，“让其他学校瞧瞧”，５月６日就有２６８台机器运行着破译程序，随后，更多的人力、物力投入了这场挑战赛。学生宿舍里的奔腾机整夜地在运转着。 　　另外，在ＤＥＳＣＨＡＬＬ小组向ＤＥＳ发起穷举攻击的同时，从瑞典发起的另一个攻击小组──ＳｏｌＮＥＴ也对ＤＥＳ发起了攻击。由于美国严禁密钥攻击算法出口到除加拿大以外的其他国家，因此ＤＥＳＣＨＡＬＬ计划仅限于在美国和加拿大执行。而ＳｏｌＮＥＴ通过向世界发布他们的软件，也取得了可观的成绩。他们的搜索速度最高达到了每秒３０亿密钥组合，并在不断加快，在竞赛结束时，他们总共搜索了近一亿亿个可能的密钥，约为密钥空间的七分之一。 　　１９９７年６月１７日，即在ＲＳＡ挑战赛公布之后的第１４０天，ＤＥＳＣＨＡＬＬ计划实施的第９６天，晚上１０点３９分，幸运降临到了美国盐湖城Ｉｎｅｔｚ公司的职员Ｍｉｃｈａｅｌ　Ｓａｎｄｅｒｓ身上，当Ｓａｎｄｅｒｓ在他那台主频为奔腾９０ＭＨｚ、１６Ｍ内存的ＰＣ机上成功地解出了ＤＥＳ的明文———Ｔｈｅ　ｕｎｋｎｏｗｎ　Ｍｅｓｓａｇｅ　ｉｓ：“Ｓｔｒｏｎｇ　ｃｒｙｐｔｏｇｒａｐｈｙ　ｍａｋｅｓ　ｔｈｅ　ｗｏｒｌｄ　ａ　ｓａｆｅｒ　ｐｌａｃｅ”（强密码技术使世界变得更安全）时，他知道他终于找到了正确的密钥（８５　５８　８９　１ａ　ｂ０　ｃ８　５１　ｂ６）。根据Ｖｅｒｓｅｒ的诺言，他将和Ｖｅｒｓｅｒ按四六分成，共同分享那一万美元的奖金。 　　加拿大的ＳｏｌＮＥＴ在得知５６比特ＤＥＳ的密码已被攻破后，立即宣布他们将马上组织“突击队”攻击５６比特的ＲＣ５密钥。据悉，全美又有数十个破译小组盯上了ＲＣ５密钥。 #1　　启示 　　对于这次成功的攻击行动，人们至少可得到以下两点启示： 　　１．密码政策面临挑战。这是第一次有人公开声明说他能破译ＤＥＳ加密的消息，并且这项计划是数万名从未见过面的志愿者使用普通的ＰＣ机，利用“空闲”机时来完成的。美国政府和工业界将不得不严肃考虑他们所制定的密码政策。Ｖｅｒｓｅｒ说：“对于一个坚定的攻击者来说，ＤＥＳ已经不再安全”。 　　这项计划证明了互联网的超级计算能力。它没有花费任何额外代价，而仅仅是使用了空闲的计算机机时。想象使用数百万台联接互联网的计算机将会是什么情景！除了用于密码学和数学计算外，超级计算机还可用于其它许多科学领域，Ｖｅｒｓｅｒ说：“也许可以利用互联网发现治疗癌症的新方法，或许互联网将成为每个人的超级计算机！”。