Chinese Lottery Cryptanalysis Revisited: The Internet as a Codebreaking Tool
RFC 3607
Document | Type | RFC - Informational (September 2003; No errata) | |
---|---|---|---|
Author | Marcus Leech | ||
Last updated | 2015-10-14 | ||
Stream | ISE | ||
Formats | plain text html pdf htmlized bibtex | ||
Stream | ISE state | (None) | |
Consensus Boilerplate | Unknown | ||
Document shepherd | No shepherd assigned | ||
IESG | IESG state | RFC 3607 (Informational) | |
Action Holders |
(None)
|
||
Telechat date | |||
Responsible AD | Steven Bellovin | ||
Send notices to | (None) |
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. 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. 1. Introduction 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. 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. Leech Informational [Page 1] RFC 3607 Chinese Lottery Cryptanalysis Revisited September 2003 2. Dangerous Synergy 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. 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. 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. 3. Winner phone home 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 Leech Informational [Page 2] RFC 3607 Chinese Lottery Cryptanalysis Revisited September 2003 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.Show full document text