T3 - Diffie-Hellman Protocol

The Diffie-Hellman Protocol

Whitfield Diffie and Martin Hellman developed the first public-key algorithm, the Diffie-Hellman protocol. All participants (e. g. Alice and Bob) construct the key together. The use of one-way functions in the creation of the key provides the basic security that the protocol needs. However, Diffie-Hellman is still insecure due to its vulnerability to a man in the middle attack.

A one-way function can be computed, relatively, easily, without difficulty, but it is very difficult to recover the arguments of the function before computed. This is, for any x, calculating f(x) is easy, but recovering x, for any f(x) is extremely hard. In Diffie-Hellman we compute modular exponentiation, because modular logarithms are, by far, more difficult to calculate.

Generating (and distributing) the key requires to follow the next algorithm:

1. Alice and Bob choose a prime number p and a generator g ∈ Zp. These numbers can be publicly chosen.
P → Large prime
g → generator Zp

2. Alice, secretly, chooses a number x modulo p and sends f(x) to Bob, publicly.

f(x) = g ^x mod p

3. Bob, secretly, chooses a number y modulo p and sends f(y) to Alice, publicly.

f(y) = g ^ymod p

4. Alice and Bob compute the key for the session:

K = f(x) ^y mod p = f(y)^x mod p.

This works because (g ^x ) ^y= (g ^y) ^x, and for x != y, f(x) != f(y).

The Diffie-Hellman protocol in python

First of all, a prime p and a generator g are chosen at random, or pseudo random.

p = createPrime(16) # Calls to a function to create a prime
g = createGenerator(p) # Calls to a function to create a generator
print "p =", p, "| g =", g

To be a generator, g must satisfy the next requirement:

ꓯi < (p – 1) s.t. i | (p – 1), gⁱ != 1

In other words, we compute gⁱ mod p for each factor i of (p – 1) and if none of those values is 1, then g is a generator. The code in python goes as follows:

def isGenerator(g, p): # Proves if g is a generator
   i = 2
   while i < (p - 1):
      if (p - 1) % i == 0 and modularExp(g, i, p) == 1: # Computes the power
         return False # Returns False if g is not a generator, so we have to select other g
      i += 1
   return True

The function modularExp(base, exponent, modulo) is imported from the file modularExp.py. Basically, returns the result of raising a number (base) to a power (exponent) in a specified modulus modulo.

def modularExp(base, exponent, modulo):
   res = 1
   pot = base % modulo
   while exponent > 0:
      if exponent % 2 == 1:
         res = (res * pot) % modulo
      exponent = exponent >> 1
      pot = (pot * pot) % modulo
   return res

Then, the participants are created. They use p and g to compute f(x) or f(y), respectively.

Alice = Person(p, g)
Bob = Person(p, g)

The class Person is defined in person.py. In the constructor, x is selected and the function is calculated. The method getKey(self, fy, p) computes the key with the f(y) sent by the other party. The other methods, getFx() and showKey(), return f(x) and the key respectively (obviously, this is only to demonstrate the protocol).

def __init__(self, p, g):
      self._x = randint(2, p-1) # x is chosen
      self._function = modularExp(g, self._x, p) #Here is where f(x) is computed

def getKey(self, fy, p):
      self._key = modularExp(fy, self._x, p) # The key is calculated, as in the explanation above.

In dhp.py:

fx = Alice.getFx() # The call to the method for Alice
fy = Bob.getFx() # The call to the method for Bob
print "Fx = ", fx
print "Fy = ", fy

Alice.getKey(Bob.getFx(), p)
Bob.getKey(Alice.getFx(), p)

print "Key Alice = ", Alice.showKey()
print "Key Bob = ", Bob.showKey()

Hacking the key

A hacker already knows p, g, f(x) and f(y), because they were made public. So, in order to obtain the key, the hacker, instead of calculating the logarithm for f(x) or f(y), computes the modular exponentiation k = gⁱ mod p, for all i < p. If the exponentiation yields a value k equal to f(x) or f(y), then the hacker can get the key by raising f(y) or f(x), respectively, to the power i modulo p.

def hack(p, g, fx, fy):
   i = 2
   while i < p:
      k = modularExp(g, i, p) # Tries to get f(x) or f(y)
      if k == fx: # If he gets f(x), then the key is f(y)^i modulo p
         K = modularExp(fy, i, p)
         print "Hacked. The key is: ", K, "| x =", i
         return K
      if k == fy: # If he gets f(y), then the key is f(x)^i modulo p
         K = modularExp(fx, i, p)
         print "Hacked. The key is: ", K, "| y =", i
         return K
      i += 1

Running the script, implementing the Diffie-Hellman protocol as well as a brute-force attack against it. Although the size of p is 16 bits, a new size of p can be specified in the prompt.

Tamaño de p = 16 bits
victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Diffie - Hellman Protocol$ python dhp.py
p = 5531 | g = 3964
Fx = 696
Fy = 430
Key Alice = 2336
Key Bob = 2336
Hacked. The key is: 2336 | y = 3513

Tamaño de p = 10 bits
victor@victor-HP-G42-Notebook-PC:~/Documents/Homework/Cryptography/Diffie - Hellman Protocol$ python dhp.py 10
p = 661 | g = 559
Fx = 142
Fy = 15
Key Alice = 613
Key Bob = 613
Hacked. The key is: 613 | x = 8
All the files are in github.com

References

Schneier, B. (1996). Applied Cryptography, Second Edition: Protocols, Algorithms and Source Code in C. John Wiley and Sons, Inc.