The authors of this paper are Ronald L. Rivest and Adi Shamir. Rive...
In other words, the main goal of this protocol is to make it harder...
**There is no** central authority (at a global level) that distribu...
In this case **transparent** means that for `A` and `B` their commu...
Here the authors describe a typical man-in-the-middle attack where ...
Why does C have to create a new message MA'? Can't C decrypt E_KC(M...
This is a very important note. This protocol only works if `A` and ...
It’s important to understand that this scheme forces the eavesdropp...
**Baud rate** is the rate at which information is transferred in a ...
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
Research Contributions
When
A
wants
to
communicate with B, C replaces both
the public key, KA, that
A
sends
to
B
and the
public
key, KB, that
B
sends to
A by his
own public key,
KC
(or
by
a
pair
of
keys,
KC and
KC",
if
the keys contain
an
identifying prefix). Whenever
A
sends
an
encrypted
message EKC(MA)
to
B,
C
intercepts
it,
decrypts
it in
order
to
read
MA,
and
then reencrypts
it
as EKB[MA)
before sending
it to
B.
Messages, MB, sent
by
B
to
A
are
handled
in a
similar way.
The communicating parties
can try to
trap C by send-
ing their public keys again
for
verification
as
part
of
the
cleartexts they exchange.
If
C
is
not
allowed
to
change
such messages,
he
may
get
into trouble. To avoid this
technical difficulty,
we
allow eavesdroppers
to
change
all
the
key-related portions
of
messages
and
assume
that they
are
clever enough
to
detect them
in
real time.
One
can
almost prove that when
all the
communica-
tion lines between
A and
B
are
controlled
by
C, this
cryptanalytic attack cannot
be
foiled. If
A
and
B cannot
authenticate
the
keys they receive,
KC
looks just
as
legal
as
KA
and
KB.
Since
all of
C's actions
are
transpar-
ent,
A and
B
cannot possibly distinguish between
a
scenario
in
which C exists
and a
scenario
in
which
C
does
not
exist. Yet,
we
claim that
a
simple change
in
the communications protocol
can
dramatically reduce
the danger posed
by
eavesdroppers.
We note that
no
such protocol
can be
perfect since
it
is conceivable that
C
could pretend
to be
B
sufficiently
well that
A
would have
no
means
of
determining that
he was talking
to
C rather than
B.
This possibility
is
of
particular concern when
A and
B
are
merely machines.
However,
the net
effect
of
the protocol
to be
proposed
is
that any authentication provided by A's a
priori
knowl-
edge
of
B's communication patterns, knowledge
or
voice
is
used
to
expose
the
would-be eavesdropper.
This
is a
feature that
the
ordinary "exchange
of
public
keys"
protocols does
not
possess, since there, C
can
successfully eavesdrop without
any
a
priori
knowledge
about
A
and
B.
3.
THE
"INTERLOCK" PROTOCOL
After
A
and
B
have exchanged their public keys, they
exchange
a
pair
of
data blocks, MA and
MB,
as
follows:
1.
A encrypts MA under
KB
but
sends
B
only
the
first
half
of
the bits
of
the resulting ciphertext EKB(MA).
2.
B
encrypts
MB
under
KA
and
sends
A
the
first
half of
EKA{MB].
3.
A sends
B
the second half EKB{MA).
4.
B
sends
A
the second half of EKA(MB).
5.
A and
B
concatenate the two halves of
EKA(MB)
and
EKB(MA),
respectively,
and
use their secret
decryption keys
to
read
the
messages.
Each side performs
a
step
in
this protocol only after
he
receives
the
information sent
by the
other side
in the
previous step.
Assuming that
the
opponent, C, succeeded
in
replac-
ing
KA
and
KB
by
KC,
let us
examine
his
situation after
Step
1
has
been executed.
He
has,
at his
disposal,
the
first half
of
EKC{MA),
but
this
is not
enough
to
read MA.
He must send
B
something, otherwise,
the
communica-
tion will
be
terminated
and he
will discover nothing
about MA
and
MB.
If
he sends
B
the
same half cipher-
text
he
received from A,
B
will later
try to
decrypt
it
with
the
"wrong"
key and
will
get
garbage. C is thus
forced
to
behave nontransparently
and to
invent
a new
message,
MA'
(which probably
has
nothing
to
do with
MA),
to
encrypt
it
under
KB,
and to
send
the
first half of
EKB(MA') to
B.
Similarly,
he is
forced
to
replace
the
unknown MB
by
another message MB'
in
Step 2. By
the
time
he
discovers
the
true values of
MA
and
MB
in
Steps 3
and
4,
it is too
late
to
change
MA' and MB',
since
he is
already committed
to the
first halves
of
their
ciphertexts. Therefore,
any
attempt
by
C
to read
MA
and
MB
will either garble
or
completely change
the
communication between
A
and
B.
Instead
of
transmitting
the
two halves
of
the cipher-
text separately
as
proposed here, other two-part meth-
ods could
be
used
as
long
as the
transmission
of
the
first part effectively commits
the
sender
to the
final
cleartext although
the
cleartext cannot
be
computed
without
the use of
the second half as well. Further-
more,
the
first part must depend
on th e
recipient's pub-
lic
key in
such
a
manner that
an
enemy could
not
modify
the
first part
so as to
depend
on
his own public
key instead.
For
example,
the
first part could
be a
"cryptographic checksum"
or
"one-way function"
of
the
ciphertext,
and the
second part could
be the
ciphertext
itself.
However, more bits
are
exchanged
by the
parties
in this variant than
in the
original interlock protocol.
4.
GENERALIZATIONS
If
A
and
B
want
to
exchange
n
blocks
of
information,
they
can
repeat
the
interlock protocol
for
each pair of
blocks. A sophisticated opponent
can try to use the
following delaying technique:
1.
During
the
first cycle through
the
protocol,
C
sends
A
and
B
dummy messages MB'
and MA',
and records
the
actual messages
MB^
and
A1A|.
2.
During
the ;th
cycle, C sends
A
and
B
the
properly
translated versions
of
the ciphertexts
of
MB,_i
and
AM,_r
and
records
the new
messages,
MBj
and
MAi.
3.
The last pair
of
blocks,
MB,,
and
MAn,
are
lost
since
A
and
B
do not
expect
any
more messages
after
the «th
cycle.
While this mode
of
attack reduces
the
interference
of
C with
the
communication between
A
and
B,
it can be
detected
by the
communicating parties since
the
mes-
sages they send
and the
messages they receive
are out
of
phase:
If
A
poses
a
question
to
B
during cycle
i,
B
receives
it
only during cycle i-I-
1, and the
response
he
sends during cycle ;-I-
2 is
received by
A
only during
cycle
/'
+ 3. Assuming that each message contains both
a question
and an
answer
to t he
previous question,
it is
easy
to
show that
C
cannot interleave
his
exchanges
with
A
and
B
in a
way that will look transparent
to
394 Communications
of
the ACM
April 1984 Volume
27
Number
4
Abstracts
both
of
them,
and the
delays
he is
forced
to
introduce
are likely
to
arouse suspicion.
The interlock protocol requires that,
at the
beginning
of each cycle, both
A and
B
are
ready
to
transmit mean-
ingful messages
(a
"full-duplex" communication
pat-
tern).
More common
is a
"half-duplex" mode
in
which
the parties alternate
in the
transmission
of
messages,
and where each message
may
depend upon
the mes-
sage just received from
the
other party.
In
this mode
of
operation,
it is
harder
to
expose
an
eavesdropper since
a message sent
by one
party must become decipherable
before
any
meaningful response
is
expected from
the
recipient
of the
message.
The
only
way an
eavesdrop-
per
can be
detected
in
this case
is by
timing
the
delay
between questions
and
answers.
If
a question takes
t
seconds
to
transmit
(at a
fixed Baud rate which cannot
be changed
by the
eavesdropper),
and if the
eavesdrop-
per
can
start translating
it
only when
the
transmission
is complete, (e.g., when
the
ciphertext
is
superen-
crypted
by a
temporary
key
which
is
revealed
at the
end
of the
transmission),
the the
translation adds
at
least
t
seconds
to the
transmission delay. This extra
delay
can be
detected
if the
question must
be
answered
not sooner than
s
seconds
and not
later than
s + t
seconds after
it has
been posed,
for
some fixed
but
arbitrary
s.
One mode
of
operation
in
which
the
existence
of an
eavesdropper cannot
be
exposed
is a
one-way commu-
nication
in
which
A
wants
to
send B
a
message
but
does
not expect
(or
cannot receive)
any
response.
It is
clear
that without having authenticated information about
A's
key or
exact transmission time,
the
translation
of
the ciphertext
by
C cannot
be
detected.
REFERENCES
1.
Diffie. W. and Hellman. M. New directions in cryptography. /£££
Trans.
Inf. Theory. (Nov. 1976).
2.
Rivest. R.. Shamir. A. and Adelman. L. A method for obtaining
digital signatures and public-key cryptosystems. Commun. ACM 21.
(Feb.
1978).
CR Categories and Subject Descriptors: C.2.0 (Computer-Communi-
cation Networks]: General—security and
protection
General Term: Security
Additional Key Words and Phrases: cryptography, cryptographic
protocols
Received 4/82: revised
10/83:
accepted 11/83
Author's Present Address: Ronald L. Rivest. Laboratory for Computer
Science. Massachusetts Institute of Technology. 545 Technology Square.
Cambridge. MA 02139: Adi Shamir. Applied Mathematics. The Weiz-
mann Institute of Science. Rehovot. Israel.
Permission to copy without fee all or part of this material is granted
provided that the copies are not made or distributed for direct commer-
cial advantage, the ACM copyright notice and the title ofthe publication
and its date appear, and notice is given that copying is by permission of
the Association for Computing Machinery. To copy otherwise, or to
republish. requires a fee and/or specific permission.
Abstracts from Other ACM Publications
ACM
Transactions on
Programming
Languages and Systems
April issue
Using Time Instead
of
Timeout
for
Fault-Tolerant Distributed
Systems
Leslie Lamport
A general method is described for implementing a distributed system
with any desired degree of fault-tolerance. Instead of relying upon ex-
plicit timeouts, processes execute a simj>ie clock-driven algorithm. Reli-
able clock synchronization and a solution to the Byzantine generals
problem are assumed.
For Correspondence: L. Lamport. Computer Science Laboratory. SRI In-
ternational. 333 Ravenswood Ave.. Menlo Park. CA 94025.
"Hoare Logic"
of
CSP,
and A il
That
Leslie Lamport
and
Fred B. Schneider
Ceneralized Hoare Logic is a formal logical system for deriving invari-
ance properties of programs. It provides a uniform way to describe a
variety of methods for reasoning about concurrent programs, including
noninterference, satisfaction, and cooperation proofs. We describe a sim-
ple meta-rule ofthe Generalized Hoare Logic—the Decomposition Prin-
ciple—and show how all these methods can be derived using it.
For Correspondence: L. Lamport. Computer Science Laboratory. SRI In-
ternational. 333 Ravenswood Ave.. Menlo Park. CA 94025.
Communicating Sequential Processes
for
Centraliied
and
Distributed Operating System Design
M.
Elizabeth C. Hull
and R. M.
McKeag
How the notation of Communicating Sequential Processes may bo used
in the design cf an operating system is demonstrated. Furthermore, how
such an approach assists in the design and development of a system
distributed over a network of computers is shown. The technique uses a
well-defined design methodology.
For Correspondence: M.E.C. Hull. School of Computer Science. Ulster
Polytechnic. Shore Road. Newtownabbey. Co Antrim BT37 OQB. North
Ireland.
Giobai Data Fiow Analysis Problems Arising
in
Locally Least-Cost
Error Recovery
Roland Backhouse
Locally least-cost error recovery is a technique for recovering from syn-
tax errors by editing the input string at the point of error detection. A
scheme for its implementation is recursive descent parsers, which in
principle embodies a process of passing a parameter to
each
procedure in
the parser for
each
terminal symbol in the grammar, has heen suggested.
For this scheme to be practical it is vital that as much parameterization
as possible is eliminated from tho recursive descent parser. This optimi-
zation problem and how it may be split into three separate global data
flow analysis problems—classifying terminal symbols and the so-called
min and max follow cost problems—are discussed. Tbe max follow cost
problem is a particularly difficult one to solve. Tho application of Gaus-
sian elimination to its solution is shown by expressing it as a continuous
data flow problem, and is also related to an "idiosyncratic" data flow
problem arising in the optimization of very high level languages. Classi-
fying terminal symbols is also difficult since the problem is unsolvable
in general. However, for the class of LL(1) grammars, the problem is
shown to be expressible as a distributive data flow problom and so may
be solved using, say. Gauss-Seidel iteration.
For Correspondence: R. Backhouse. Dept. of Computer Science. Univer-
sity of Essex. Wivenhoe Park. Colchester C04 3SQ. U.K.
Aprill984 Volume
27
Number
4
Communications
of the ACM 395
In other words, the main goal of this protocol is to make it harder for an attacker to perform a transparent man in the middle attack. In a man-in-the-middle (MitM) attack a malicious entity can eavesdrop on the communication between two entities without those entities being able to tell they are being eavesdropped on.
**Baud rate** is the rate at which information is transferred in a communication channel. It could be expressed for instance as bits per second.
Here the authors describe a typical man-in-the-middle attack where the eavesdropper essentially acts as a relay, reading the content of the messages before sending them to the destination.
In this case **transparent** means that for `A` and `B` their communication looks *exactly* the same regardless of whether or not `C` is eavesdropping.
It’s important to understand that this scheme forces the eavesdropper to behave in a non-transparent way. In other words, the eavesdropper ends up having to modify the cleartext of the messages being exchanged between `A` and `B` if he actually wants listen in on the conversation. Whereas before the eavesdropper would essentially act as a relay.
Since the eavesdropper is actually modifying the content of the messages being sent, `B` should be able to distinguish messages composed by `A` from messages composed by the eavesdropper `C`.
Why does C have to create a new message MA'? Can't C decrypt E_KC(MA) and encrypt MA with E_KB and send B half of that ciphertext?
The authors of this paper are Ronald L. Rivest and Adi Shamir. Rivest and Shamir (along with Leonard Adleman) invented the RSA cryptosystem and are arguably two of the most famous and influential cryptographers of our age. In 2002 they received the Turing Award.
[Adi Shamir](https://en.wikipedia.org/wiki/Adi_Shamir) is an Israeli cryptographer. Shamir received a BSc in Mathematics from the Tel Aviv University in 1973 and a PhD in Computer Science from the Weismann Institute in Rehovot, Israel in 1977.
[Ronald Rivest](https://en.wikipedia.org/wiki/Ron_Rivest) is an American cryptographer. He received a BSc in Mathematics from Yale University in 1969 and a PhD in Computer Science from Stanford in 1974. He is a member of MIT’s Computer Science and Artificial Intelligence Laboratory.
*Leonard Adleman, Adi Shamir and Ron Rivest (from left to right)*
This is a very important note. This protocol only works if `A` and `B` share knowledge of each other that `C` is not able to emulate. *E.g.* Tone of voice, patterns in text, etc.
As the author’s point out, this condition is more problematic if `A` and `B` are just computers.
**There is no** central authority (at a global level) that distributes email addresses to entities. If you want to get somebody’s email address there is no global directory you can refer to.
On the other hand, **there is** a central authority that distributes SSL certificates to websites. This way, when you connect to `https://www.amazon.com` you can be sure that you are connecting to Amazon’s servers and not to servers belonging to somebody pretending to be amazon.