RESEARCH CONTRIBUTIONS
Programming
Techniques and
Data Structures
Ellis Horowitz
Editor
How to Expose
an Eavesdropper
RONALD
L
RIVEST
and ADI
SHAMIR
ABSTRACT:
We present a new protocol for establishing
secure communications over an insecure communications
channel in the absence of trusted third parties or
authenticated keys. The protocol is an improvement over
the simpler protocol in which the communicating parties
exchanged their public encryptiort keys and used them to
encrypt messages. It forces a potential eavesdropper—if he
wants to understand the messages—to reveal his existence
by modifying and serioiisly garbling the communication.
1.
INTRODUCTION
Public-key cryptosystems [1, 2] with central directories
that authenticate and distribute the keys give their
users a high degree of protection. However, for large,
loosely organized and continuously changing networks
(telephones, home computers, electronic mail, etc.), a
central directory is almost impossible to maintain, and
the communicating parties have to rely on local, inse-
cure directories or they have to exchange their public
keys themselves. The purpose of this paper is to suggest
a new communications protocol that protects the net-
work members against eavesdroppers even in this case.
An application we have in mind is one in which two
company executives Who can recognize each other's
voice but who do not have each other's key want to
communicate via a scrambled telephone line. All the
key exchanges and encryption/decryption parts of the
This research was partially supported by NSF Grant No. MCS-8006938.
© 1984 ACM 0001-0782/84/0400-0393 75(t
protocol are handled automatically, and the two execu-
tives are aware only of each other's unscrambled voice.
2.
THE EAVESDROPPER SCENARIO
Consider the following eavesdropper scenario. We de-
fine an eavesdropper to be someone who Wants to mon-
itor the communication between two parties without
tampering with the data and without exposing his ex-
istence. He may modify the ciphertext stream in atiy
manner whatsoever (deleting, delaying, substituting, or
inserting ciphertexts) as lohg as he does not change the
cleartexts received by the communicating parties. Note
that, in the context of a public-key cryptosystem, a
successful eavesdropper must actively participate in the
key-exchange protocol; but, if he wants to monitor the
communications for a long period of time, he would
have to try to behave as transparently as possible, since
any trace he leaves in the cleartexts is likely to arous6
suspicion.
A well-known and serious problem with unauthenti-
cated public-key exchange protocols is that the commu-
nication between the two parties, A and B, can be trans-
parently monitored by an eavesdropper, C, who inserts
into the communication line an encryption/decryption
device as follows:
KA KC
T
c
KB
April 1984 Volume 27 Number 4 Communications of the ACM 393