Check out the new USENIX Web site.

Network Randomization Protocol:
A Proactive Pseudo-Random Generator

Chee-Seng Chow and Amir Herzberg

IBM T.J. Watson Research Center
Yorktown Heights, NY 10598



A major security threat to any security solutions based on a centralized server is the possibility of an adversary gaining access to and taking control of the server. The adversary may then learn secrets, corrupt data, or send erroneous messages. In practice, such an adversary may be more prevalent than one would like to admit. It may be a malicious hacker, a virus in an application program, or an unscrupulous system administrator. Proactive security is a novel approach to the server security problem. It uses the distribution of data and control to multiple servers and periodic refreshes between servers. By distributing data and control, one or more servers may be compromised without compromising the system. Periodic refreshes between servers allow a compromised server to "recover" after the attacker leaves, thereby contributing to the system security. A fraction (in some cases all) of the servers must be compromised simultaneously in order to compromise the system. This paper describes the Network Randomization Protocol (NRP) --- a proactive protocol for generating cryptographically secure pseudo-random numbers. The protocol is designed for operation in the Internet and includes defenses against clogging attacks. Issues related to the design and implementation of the protocol are discussed. As virtually no cryptographic task is possible without a source of randomness or pseudo-randomness, NRP is an important basic building block for many cryptographic functions. Furthermore, it serves to illustrate the main ideas and intuitions of proactive security.

Download the full text of this paper in ASCII (40,283 bytes),
POSTSCRIPT (182,705 bytes),
and PDF (157,975 bytes) form.

To Become a USENIX Member, please see our Membership Information.