Network Working Group M. Leech
Request for Comments: 3607 Nortel Networks
Category: Informational September 2003
Network Working Group M. Leech
Request for Comments: 3607 Nortel Networks
Category: Informational September 2003
Chinese Lottery Cryptanalysis Revisited: The Internet as a Codebreaking Tool
重新审视中国彩票密码分析：互联网作为破译密码的工具
Status of this Memo
本备忘录的状况
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
本备忘录为互联网社区提供信息。它没有规定任何类型的互联网标准。本备忘录的分发不受限制。
Copyright Notice
版权公告
Copyright (C) The Internet Society (2003). All Rights Reserved.
版权所有（C）互联网协会（2003年）。版权所有。
Abstract
摘要
This document revisits the so-called Chinese Lottery massively-parallel cryptanalytic attack. It explores Internet-based analogues to the Chinese Lottery, and their potentially-serious consequences.
本文将重新讨论所谓的中国彩票大规模并行密码分析攻击。本书探讨了基于互联网的类似中国彩票的现象及其潜在的严重后果。
In 1991, Quisquater and Desmedt [DESMEDT91] proposed an esoteric, but technically sound, attack against DES or similar ciphers. They termed this attack the Chinese Lottery. It was based on a massively-parallel hardware approach, using consumer electronics as the "hosts" of the cipher-breaking hardware.
1991年，Quisquater和Desmedt[DESMEDT91]提出了一种对DES或类似密码的深奥但技术上合理的攻击。他们把这次袭击称为中国彩票。它基于大规模并行硬件方法，使用消费电子产品作为密码破解硬件的“主机”。
In the decade since Quisquater and Desmedt proposed their Chinese Lottery thought experiment, there has been considerable growth in a number of areas that make their thought experiment worth revisiting.
自从奎斯夸特和德斯米德提出他们的中国彩票思维实验以来的十年里，在许多领域有了长足的发展，这使得他们的思维实验值得重新审视。
In 1991, the Internet had approximately 8 million reachable hosts attached to it and in 2002, the number is a staggering 100 million reachable hosts. In the time since the Chinese Lottery paper, computer power available to the average desktop user has grown by a factor of approximately 150.
1991年，互联网上连接了大约800万个可访问主机，2002年，这个数字达到了惊人的1亿个可访问主机。自中国彩票发行以来，普通桌面用户可使用的计算机功率增长了约150倍。
The combined growth of the Internet, and the unstoppable march of Moore's Law have combined to create a dangerous potential for brute-force cryptanalysis of existing crypto systems.
互联网的发展和摩尔定律势不可挡的发展共同创造了对现有密码系统进行暴力密码分析的危险潜力。
In the last few years, several widescsale attacks by so-called Internet Worms [SPAFF91] have successfully compromised and infected surprisingly-large numbers of Internet-attached hosts. In 2001, The Cooperative Association for Internet Data Analysis [CAIDA2001] reported that the Code Red v2 worm was able to infect over 350,000 hosts in its first 14 hours of operation. The payload of the Code Red worm was mischief: the defacement of the host website with a political message. It was bold, brash, and drew attention to itself nearly immediately.
在过去几年中，由所谓的互联网蠕虫[SPAFF91]发起的几次WideCSale攻击成功地破坏并感染了数量惊人的互联网连接主机。2001年，互联网数据分析合作协会（Cooperative Association for Internet Data Analysis）[CAIDA2001]报告说，红色代码v2蠕虫在其运行的头14个小时内能够感染35万多台主机。红色代码蠕虫的有效载荷是恶作剧：用政治信息破坏宿主网站。这是一个大胆、鲁莽的举动，几乎立刻引起了人们的注意。
Consider for a moment, an Internet worm with a darker and ultimately more dangerous purpose: to brute-force cryptanalyse a message, in order to determine the key used with that message. In order for the worm to be successful, it must avoid detection for long enough to build up a significant level of infected systems, in order to have enough aggregate CPU cycles to complete the cryptanalysis. Furthermore, our worm would need to avoid detection for long enough for the cracked key to be useful to the owners of the worm. Recent research [USEN2002] on stealthy worms paints a very dark picture indeed.
考虑一下，一个具有更黑暗和最终更危险目的的网络蠕虫：强力破解密码分析，以确定与该消息一起使用的密钥。为了使蠕虫成功，它必须避免检测足够长的时间，以建立一个显着水平的受感染系统，以便有足够的聚合CPU周期来完成密码分析。此外，我们的蠕虫需要在足够长的时间内避免检测，以便破解的密钥对蠕虫的所有者有用。最近关于隐身蠕虫的研究[USEN2002]确实描绘了一幅非常黑暗的画面。
Even after such a worm is detected it would be nearly impossible to tell whose key the worm was attacking. Any realistic attack payload will have one or two pieces of ciphertext, and some known plaintext, or probable-plaintext characteristics associated with it; hardly enough data to determine the likely victim.
即使在检测到这样的蠕虫之后，也几乎不可能知道蠕虫攻击了谁的密钥。任何实际的攻击有效载荷都会有一个或两个密文，以及一些已知的明文，或与之相关的可能的明文特征；几乎没有足够的数据来确定可能的受害者。
When a given instance of the worm determines the key, it needs to contact the originator in order to give them the key. It has to do this in such a way as to minimize the probability that the originator will get caught.
当给定的蠕虫实例确定密钥时，它需要联系发起人以向其提供密钥。它必须这样做，以尽量减少发起者被抓住的可能性。
One such technique would be for the worm to public-key encrypt the key, under the public key(s) of the originator(s), and place this in some innocuous spot on the website of the compromised host. The worm could also back-propagate so that a number of compromised websites in the topological neighborhood of the worm will also contain the data. The file containing the key would be identified with some unique keyword which the originators occasionally look for using Internet
其中一种技术是让蠕虫使用发起者的公钥对密钥进行公钥加密，并将其放在受损主机网站上的某个无害位置。蠕虫还可能反向传播，因此蠕虫拓扑邻域中的许多受损网站也将包含数据。包含密钥的文件将使用一些独特的关键字进行标识，发起者偶尔会使用Internet查找这些关键字
search engines. The worm could make the process more efficient by using the "keyword registry" services of various Internet search engines.
搜索引擎。通过使用各种互联网搜索引擎的“关键字注册”服务，蠕虫可以使搜索过程更加高效。
Another approach would be to post a (possibly PGP-encrypted) message to several newsgroups, through an anonymous posting service. Similarly, Internet "chat" services like IRC could be used; indeed there's an emerging tradition of using IRC and similar services for real-time, anonymous, control of worms and viruses.
另一种方法是通过匿名发布服务向多个新闻组发布（可能是PGP加密的）消息。类似地，可以使用IRC等互联网“聊天”服务；事实上，使用IRC和类似服务实时、匿名地控制蠕虫和病毒的传统正在兴起。
Any of these methods can be used both to allow the "winning" worm instance to send results and for the originator to send new work for the amassed army of compromised systems.
这些方法中的任何一种都可以用于允许“获胜”的蠕虫实例发送结果，也可以用于发起人为大量受损系统发送新的工作。
Both Internet growth and CPU performance follow a reasonably predictable doubling interval. Performance of computing hardware appears to still be following Moore's Law, in which performance doubles every 1.5 years. Internet growth appears to be following a doubling period of 3 years.
互联网增长和CPU性能都遵循合理可预测的倍增间隔。计算硬件的性能似乎仍然遵循摩尔定律，即性能每1.5年翻一番。互联网的增长似乎是在经历了3年的翻番之后。
By establishing a common epoch for both performance and Internet growth, we can easily determine the likely attack time for any given year, based on a purely arithmetic approach.
通过为性能和互联网增长建立一个共同的时代，我们可以基于纯粹的算术方法轻松确定任何给定年份的可能攻击时间。
A simplifying assumption is that it is indeed possible to construct a suitably-stealthy worm and that it can achieve a steady-state infection of about 0.5% of all attached hosts on the Internet.
一个简化的假设是，确实可以构建一个适当的隐蔽蠕虫，并且它可以实现约0.5%的Internet上所有连接主机的稳态感染。
In 1995, J. Touch, at ISI, published a detailed performance analysis of MD5 [RFC1810]. At that time MD5 software performance peaked at 87mbits/second, or an equivalent of 170,000 single-block MD5 operations per second. In the same year, peak DES performance was about 50,000 setkey/encrypt operations per second.
1995年，ISI的J.Touch发表了一份详细的MD5性能分析[RFC1810]。当时，MD5软件的性能达到了87mbits/秒的峰值，相当于每秒170000次单块MD5操作。同年，DES的峰值性能约为每秒50000次设置密钥/加密操作。
In 1995, the Internet had about 20,000,000 attached hosts. In 2002, there are a staggering 100,000,000 attached hosts.
1995年，互联网有大约20000000个连接主机。2002年，连接的主机数量达到了惊人的100000000台。
A simple C program, given in Appendix A can be used to predict the performance of our hypothetical worm for any given year. Running this program for 2002 gives:
附录A中给出的一个简单的C程序可以用来预测我们假设的蠕虫在任何给定年份的性能。在2002年运行此程序将提供：
Year of estimate: 2002
For a total number of infected hosts of 503968
aggregate performance: MD5 9.79e+11/sec DES 2.88e+11/sec
DES could be cracked in about 1.45 days
Year of estimate: 2002
For a total number of infected hosts of 503968
aggregate performance: MD5 9.79e+11/sec DES 2.88e+11/sec
DES could be cracked in about 1.45 days
DES with 8 character passwords could be cracked in 16.29 minutes MD5 with 64-bit keys could be cracked in about 218.04 days MD5 with 8 character passwords could be cracked in 4.79 minutes
具有8个字符密码的DES可在16.29分钟内破解具有64位密钥的MD5可在约218.04天内破解具有8个字符密码的MD5可在4.79分钟内破解
The numbers given above suggest that an undetected attack against MD5, for a reasonable key length, isn't likely in 2002. A successful attack against DES, however, appears to be a near-certainty.
上面给出的数字表明，对于合理的密钥长度，在2002年不太可能发生针对MD5的未被检测到的攻击。然而，对DES的成功攻击似乎几乎是必然的。
DES has been shown to be weak in the recent past. The success of the EFF machine, described in [EFF98] shows how a massively-parallel hardware effort can succeed relatively economically. That this level of brute-force cryptanalytic strength could be made available without custom hardware is a sobering thought. It is clear that DES needs to be abandoned; in favor of either 3DES or the newer AES [FIPS197].
DES在最近的过去被证明是弱的。[EFF98]中描述的EFF机器的成功表明了大规模并行硬件工作是如何相对经济地成功的。这种强力密码分析能力可以在没有定制硬件的情况下使用，这是一个令人清醒的想法。很明显，DES需要放弃；支持3DES或更新的AES[FIPS197]。
The picture for MD5 (when used in simple MAC constructions) is much brighter. For short messages long keys with MD5 are effectively free, computationally, so it makes sense to use the longest architecturally-practical key lengths with MD5.
MD5的图片（当用于简单的MAC结构时）要亮得多。对于短消息，MD5的长键在计算上是有效的自由键，因此在MD5中使用最长的体系结构实用键长度是有意义的。
Operating system software is becoming more complex and the perpetrators of Internet Worms, Viruses, Trojan Horses, and other malware, are becoming more sophisticated. While their aim has largely been widescale vandalism, it seems reasonable to assume that their methods could be turned to a more focussed and perhaps more sinister activity.
操作系统软件变得越来越复杂，互联网蠕虫、病毒、特洛伊木马和其他恶意软件的肇事者也变得越来越复杂。虽然他们的目标在很大程度上是大规模的故意破坏，但似乎有理由认为他们的方法可以转向更集中、也许更险恶的活动。
As of February 2003, at least one worm, known as W32/Opaserv.A has a payload designed to implement a distributed DES cracker.
截至2003年2月，至少有一个名为W32/Opaserv.A的蠕虫具有设计用于实现分布式DES破解程序的有效负载。
John Morris, of Nortel IS, contributed the idea of anonymous newsgroup posting.
Nortel IS的约翰·莫里斯（John Morris）提出了匿名新闻组发布的想法。
Appendix A: Source Code
附录A：源代码
/*
* This program calculates the performance of a hypothetical
* "Chinese Lottery" brute-force cryptanalysis worm, based on
* the current date, estimates of Internet growth rate and
* Moores Law.
*
*/ #include <stdio.h> #include <math.h> /*
* EPOCH for the calculations
*/ #define EPOCH 1995.0 /*
* Size of the Internet (ca 1995)
*/ #define INTERNET_SIZE 20000000.0
/*
* This program calculates the performance of a hypothetical
* "Chinese Lottery" brute-force cryptanalysis worm, based on
* the current date, estimates of Internet growth rate and
* Moores Law.
*
*/ #include <stdio.h> #include <math.h> /*
* EPOCH for the calculations
*/ #define EPOCH 1995.0 /*
* Size of the Internet (ca 1995)
*/ #define INTERNET_SIZE 20000000.0
/*
* Software MD5 performance (ca 1995)
*/ #define MD5PERF 170000.0
/*
* Software MD5 performance (ca 1995)
*/ #define MD5PERF 170000.0
/*
* Software DES performance (ca 1995)
*/ #define DESPERF 50000.0
/*
* Software DES performance (ca 1995)
*/ #define DESPERF 50000.0
main (argc, argv) int argc; char **argv; {
double yeardiff;
double cryptoperf, multiplier;
double cracktime;
main (argc, argv) int argc; char **argv; {
double yeardiff;
double cryptoperf, multiplier;
double cracktime;
yeardiff = (double)atoi(argv[1]) - EPOCH;
yeardiff = (double)atoi(argv[1]) - EPOCH;
/*
* Moores Law performance double interval is 1.5 years
*/
cryptoperf = yeardiff / 1.5;
cryptoperf = pow(2.0, cryptoperf);
/*
* Moores Law performance double interval is 1.5 years
*/
cryptoperf = yeardiff / 1.5;
cryptoperf = pow(2.0, cryptoperf);
/*
* Some fuzz here--not all hosts will be the fastest available
*/
cryptoperf *= 0.450;
/*
* Some fuzz here--not all hosts will be the fastest available
*/
cryptoperf *= 0.450;
/*
* Internet size doubling interval is every 3 years
*/
multiplier = yeardiff / 3.0;
multiplier = pow(2.0, multiplier);
multiplier *= (INTERNET_SIZE*0.0050);
/*
* Internet size doubling interval is every 3 years
*/
multiplier = yeardiff / 3.0;
multiplier = pow(2.0, multiplier);
multiplier *= (INTERNET_SIZE*0.0050);
fprintf (stderr, "Year of estimate: %d\n", atoi(argv[1]));
fprintf (stderr, "Year of estimate: %d\n", atoi(argv[1]));
fprintf (stdout, "For a total number of infected hosts of %d\n",
(int)multiplier);
fprintf (stdout, "aggregate performance: MD5 %5.2e/sec DES
%5.2e/sec\n",
MD5PERF*cryptoperf*multiplier,
DESPERF*cryptoperf*multiplier);
fprintf (stdout, "For a total number of infected hosts of %d\n",
(int)multiplier);
fprintf (stdout, "aggregate performance: MD5 %5.2e/sec DES
%5.2e/sec\n",
MD5PERF*cryptoperf*multiplier,
DESPERF*cryptoperf*multiplier);
cracktime = pow(2.0, 55.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES could be cracked in about %3.2lf days\n",
cracktime/86400.0);
cracktime = pow(2.0, 55.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES could be cracked in about %3.2lf days\n",
cracktime/86400.0);
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES with 8 character passwords could be cracked in
%3.2lf minutes\n",cracktime/60);
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES with 8 character passwords could be cracked in
%3.2lf minutes\n",cracktime/60);
cracktime = pow(2.0, 64.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 64-bit keys could be cracked in about
%3.2lf days\n", cracktime/86400.0);
cracktime = pow(2.0, 64.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 64-bit keys could be cracked in about
%3.2lf days\n", cracktime/86400.0);
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 8 character passwords could be cracked in
%3.2lf minutes\n", cracktime/60); }
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 8 character passwords could be cracked in
%3.2lf minutes\n", cracktime/60); }
Normative References
规范性引用文件
[DESMEDT91] "Chinese Lotto as an Exhaustive Code-Breaking Machine". J. Quisquater, Y. Desmedt, Computer, v. 24, n. 11, Nov 1991, pp. 14-22.
[DESMEDT91]“中国乐透是一台彻底的破译密码的机器”。J.奎斯夸特，Y.德斯米德，计算机，v。24，n。1991年11月11日，第14-22页。
[RFC1810] Touch, J., "Report on MD5 Performance", RFC 1810, June 1995.
[RFC1810]Touch，J.，“MD5性能报告”，RFC1810，1995年6月。
[EFF98] "Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design", Electronic Frontier Foundation, 1998.
[Eff9]“破解DES：加密研究的秘密，窃听政治和芯片设计”，电子前沿基金会，1998。
[CAIDA2001] "CAIDA Analysis of Code Red"
http://www.caida.org/analysis/security/code-red/
[CAIDA2001] "CAIDA Analysis of Code Red"
http://www.caida.org/analysis/security/code-red/
[SPAFF91] "The Internet Worm Program: An Analysis", Eugene Spafford, 1991.
[SPAFF91]“互联网蠕虫程序：分析”，尤金·斯帕福德，1991年。
[FIPS197] "Advanced Encryption Standard", US FIPS197, November, 2001.
[FIPS197]“高级加密标准”，美国FIPS197，2001年11月。
[USEN2002] "How to 0wn the Internet in Your Spare Time", Proc. 11th Usenix Security Symposium, 2002.
[USEN2002]“如何在业余时间上网”，程序。第11届Usenix安全研讨会，2002年。
Author's Address
作者地址
Marcus D. Leech Nortel Networks P.O. Box 3511, Station C Ottawa, ON Canada, K1Y 4H7
Marcus D.Leech Nortel Networks邮政信箱3511，加拿大渥太华C站，K1Y 4H7
Phone: +1 613-763-9145
EMail: mleech@nortelnetworks.com
Phone: +1 613-763-9145
EMail: mleech@nortelnetworks.com
Full Copyright Statement
完整版权声明
Copyright (C) The Internet Society (2003). All Rights Reserved.
版权所有（C）互联网协会（2003年）。版权所有。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
本文件及其译本可复制并提供给他人，对其进行评论或解释或协助其实施的衍生作品可全部或部分编制、复制、出版和分发，不受任何限制，前提是上述版权声明和本段包含在所有此类副本和衍生作品中。但是，不得以任何方式修改本文件本身，例如删除版权通知或对互联网协会或其他互联网组织的引用，除非出于制定互联网标准的需要，在这种情况下，必须遵循互联网标准过程中定义的版权程序，或根据需要将其翻译成英语以外的其他语言。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assignees.
上述授予的有限许可是永久性的，互联网协会或其继承人或受让人不会撤销。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
本文件和其中包含的信息是按“原样”提供的，互联网协会和互联网工程任务组否认所有明示或暗示的保证，包括但不限于任何保证，即使用本文中的信息不会侵犯任何权利，或对适销性或特定用途适用性的任何默示保证。
Acknowledgement
确认
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC编辑功能的资金目前由互联网协会提供。