Chinese Lottery Cryptanalysis Revisited: The Internet as a Codebreaking Tool (RFC3607)
Original Publication Date: 2003-Sep-01
Included in the Prior Art Database: 2003-Sep-12
Internet Society Requests For Comment (RFCs)
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.
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 (C) The Internet Society (2003). All Rights Reserved.
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
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
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
Even after such a worm is detected it would be nearly impossible to
tell whose key...