Vulnerability to Attack

An interested third party (party T) has been monitoring the messages passing backward
and forward. T knows g and n from message 1. If T could compute x and y, he would
have the secret key. T only has gx mod n and so cannot find x. No practical algorithm for
computing discrete logarithm modules from a very large prime number is known.

An example (using small numbers for practicality) will show the process:
 The primes chosen by the parties are n = 47, g = 3.
 Party A picks x= 8, and party B picks y = 10; both of these are kept secret.
 A’s message to B is (47, 3, 28), because 38 mod 47 is 28 (that is, 38 = 6561:
6561/47 = 139.5957447 and 0.5957447 × 47 = 28).
 B’s message to A is (17).
 A computes 178 mod 47, which is 4.
 B computes 2810 mod 47, which is 4.
 A and B have both determined that the secret key is 4.
 Party T (the intruder) has to solve the equation (not too difficult for these sized
numbers but impossibly long—in time—for long numbers): 3x mod 47 = 28.
If the intruder T can insert himself in the message channel at key exchange commencement,
he can control the communication, as follows (see also Figure 9.5):
 When party B gets the triple, (47, 3, 28), how does he know it is from A and not
T? He doesn’t!
 T can exploit this fact to fool A and B into thinking that they are communicating
with each other.
 While A and B are choosing x and y, respectively, T independently chooses a
value z.
 A sends message 1 intended for B. T intercepts it and sends message 2 to B,
using the correct g and n (which are public) but with z instead of x.
 T also sends message 3 back to A.
 B sends message 4 to A, which T also intercepts and keeps.

All parties now do the modular arithmetic:
 Party A computes the secret key as gxz mod n, and so does T (for messages
to A).
 Party B computes gyz mod n, and so does T (for messages to B).
 Party A believes he is communicating with B so establishes a session key (with
T). B does the same. Every message that A and B sends is now intercepted by T
and can be stored, modified, deleted, and so forth. Party A and B now believe
they are communicating securely with each other.
This attack process is known as the bucket brigade attack or the man-in-the-middle
attack. Generally, more complex algorithms are used to defeat this attack method. 216