# How to Expose an Eavesdropper

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/how-to-expose-an-eavesdropper

- **Authors:** Ronald L. Rivest, Adi Shamir
- **Published:** 1984
- **Topic:** Computer Science
- **Original:** https://www.dropbox.com/s/55la039xl7k17j6/rivest1984.pdf?dl=1
- **Pages:** 3
- **Annotations:** 9 comments in 9 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/how-to-expose-an-eavesdropper

## Annotations

### Annotation 1 (page 1)

Beside the passage: “RONALD L RIVEST and ADI SHAMIR”

**Annotation** by João Batalha (2016-08-30):

> 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.
>
> ![adi and rivest](http://i.imgur.com/h7NyzVR.jpg)
> *Leonard Adleman, Adi Shamir and Ron Rivest (from left to right)*

### Annotation 2 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2016-08-30):

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

### Annotation 3 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2016-08-30):

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

### Annotation 4 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2016-08-30):

> In this case **transparent** means that for `A` and `B` their communication looks *exactly* the same regardless of whether or not `C` is eavesdropping.

### Annotation 5 (page 2)

Beside the passage: “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 …”

**Annotation** by João Batalha (2016-08-30):

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

### Annotation 6 (page 2)

Beside the passage: “first half of EKC{MA), but this is not enough to read MA. He must send B something, otherwise, the communication will be terminated and he will discover nothing about MA and MB. If he sends B the same half ciphertext he received from A, B will later try to decrypt it with the "wrong" key and will get garbage. C is …”

**Annotation** by Ali Sajjad (2021-08-09):

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

### Annotation 7 (page 2)

Beside the passage: “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 …”

**Annotation** by João Batalha (2016-08-30):

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

### Annotation 8 (page 2)

Beside the passage: “first half of EKC{MA), but this is not enough to read MA. He must send B something, otherwise, the communication will be terminated and he will discover nothing about MA and MB. If he sends B the same half ciphertext he received from A, B will later try to decrypt it with the "wrong" key and will get garbage. C is …”

**Annotation** by João Batalha (2016-08-30):

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

### Annotation 9 (page 3)

Beside the passage: “The interlock protocol requires that, at the beginning of each cycle, both A and B are ready to transmit meaningful messages (a "full-duplex" communication pattern). 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 message …”

**Annotation** by João Batalha (2016-08-30):

> **Baud rate** is the rate at which information is transferred in a communication channel. It could be expressed for instance as bits per second.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

RESEARCH CONTRIBUTIONS

Programming Techniques and Data Structures

Ellis Horowitz Editor

How to Expose

an Eavesdropper

RONALD [Annotation 1] 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 [Annotation 2] 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 [Annotation 3] central directory is almost impossible to maintain, and the communicating parties have to rely on local, insecure directories or they have to exchange their public keys themselves. The purpose of this paper is to suggest [Annotation 4] a new communications protocol that protects the network 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 executives are aware only of each other's unscrambled voice.

2. THE EAVESDROPPER SCENARIO Consider the following eavesdropper scenario. We define an eavesdropper to be someone who Wants to monitor the communication between two parties without tampering with the data and without exposing his existence. 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 unauthenticated public-key exchange protocols is that the communication between the two parties, A and B, can be transparently 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

#### Page 2

Research Contributions

When [Annotation 5] 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 sending 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 communication 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 transparent, 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 [Annotation 7] 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 knowledge 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 replacing 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 communication will be terminated and he will discover nothing about MA and MB. If he sends B the same half ciphertext 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, [Annotation 6] 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 ciphertext separately as proposed here, other two-part methods 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. Furthermore, the first part must depend on th e recipient's public 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 [Annotation 8] 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 messages 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

#### Page 3

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 meaningful messages (a "full-duplex" communication pattern). 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 message 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 eavesdropper can be detected in this case is by timing the delay between questions and answers. If a question takes t seconds [Annotation 9] to transmit (at a fixed Baud rate which cannot be changed by the eavesdropper), and if the eavesdropper can start translating it only when the transmission is complete, (e.g., when the ciphertext is superencrypted 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 communication 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-Communication 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 Weizmann 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 commercial 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 explicit timeouts, processes execute a simj>ie clock-driven algorithm. Reliable clock synchronization and a solution to the Byzantine generals problem are assumed. For Correspondence: L. Lamport. Computer Science Laboratory. SRI International. 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 invariance 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 simple meta-rule ofthe Generalized Hoare Logic—the Decomposition Principle—and show how all these methods can be derived using it. For Correspondence: L. Lamport. Computer Science Laboratory. SRI International. 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 syntax 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 optimization 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 Gaussian 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. Classifying 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. University of Essex. Wivenhoe Park. Colchester C04 3SQ. U.K.

Aprill984 Volume 27 Number 4 Communications of the ACM 395

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/how-to-expose-an-eavesdropper. More annotated papers: https://fermatslibrary.com/llms.txt
