Exercise $1(($Wo$)$Man$-$in$-$the$-$Middle$)$

Work in teams $^(1)$ of $3.$ One person plays Alice, one person plays Bob, and one person plays Eve. Alice

and Bob would like to perform a Diffie$-$Hellman key exchange to agree on a shared value securely$,$

but Eve is able to intercept their communication. We will conduct a two$-$phase experiment as

follows. In the first phase:

Choose $($together$)$ a small prime p$,$ say in the order of $2^(20),$ and a random element g inF$\_($p$)^(**).$

These values are public. Having set up the protocol, from now on$,$ all the computations in

the experiment will take place in F$\_($p$).$

Alice and Bob choose secret exponents a and b and compute their respective public values

A$=$g$^($a$)$ and B$=$g$^($b$).$

Eve chooses her own exponent e and computes E$=$g$^($e$).$

Alice and Bob proceed to exchange their public values, but Eve intercepts: in practice, Alice

and Bob send their public values to Eve instead.

Eve then sends E to both Alice and Bob.

Thinking that the exchange has been performed properly, Alice and Eve finish up the protocol

by computing E$^($a$)$ and E$^($b$),$ respectively.

The setup is now complete, Alice and Bob believe they have safely performed a key exchange, and

therefore can begin communicating securely$.$ Instead, we will show that Eve is able to not only

intercept, but also read, and even modify encrypted messages! Thus, in the second phase:

Agree $($together$)$ on a simple cipher that will be used to encrypt and decrypt messages. For

the purposes of this experiment, this could even be a one$-$time pad, since we're only going to

be encrypting once.

Agree $($together$)$ on a hash function H that will be used to produce keys for the cipher. The

hash function should be public, and its output length depends on the cipher chosen, of course.

Alice and Bob compute H on $($what they believe is$)$ the shared value to obtain a symmetric

key K for the cipher. Note that, instead, Alice and Bob do not have a shared value, so when

they hash, they obtain different keys, say K$\_($a$)$ and K$\_($b$).$

Eve will instead compute H on A$^($e$)$ and B$^($e$)$ and obtain K$\_($a$)$ and K$\_($b$),$ which will be used for

communicating with Alice and Bob, respectively.

Alice chooses a random message string $^(2),$ encrypts it using her key K$\_($a$)$ and sends it to Bob.

Eve intercepts, so in practice, Alice sends her ciphertext to Eve instead.

Eve decrypts the ciphertext using K$\_($a$),$ reads the message, modifies it as she pleases, then

re$-$encrypts it using K$\_($b$)$ and sends it to Bob.

Bob receives the ciphertext from Eve $($believing it comes from Alice$),$ then decrypts it using

his key K$\_($b$)$ and recovers the $($modified$)$ message. We have just shown that an adversary that is able to intercept messages is able to perform a very

dangerous and insidious attack. The adversary is able to read and modify messages as she pleases.

Even worse, without any means of authentication, the legitimate parties have no way to even

notice that communication was tampered with! We have just shown that an adversary that is able to intercept messages is able to perform a very dangerous and insidious attack. The adversary is able to read and modify messages as she pleases. Even worse, without any means of authentication, the legitimate parties have no way to even notice that communication was tampered with!