Browse Prior Art Database

Chinese Lottery Cryptanalysis Revisited: The Internet as a Codebreaking Tool (RFC3607)

IP.com Disclosure Number: IPCOM000019351D
Original Publication Date: 2003-Sep-01
Included in the Prior Art Database: 2003-Sep-12
Document File: 9 page(s) / 15K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

M. Leech: AUTHOR

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 23% of the total text.

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...