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