[SC] 4. Hacking Diffie-Hellman Protocol

INTRODUCTION

"The Diffie-Hellman algorithm was published in 1976 (named after its creators, Whitfield Diffie and Martin Hellman) can stablish a secret key between two machines via an insecure channel and only sending two messages. The resulting secret key can't be discovered by an attacker, even if it gets the two messages sent by the protocol. The main application of this protocol is to agree on a symmetric key with later encrypt communications between two machines.

The values of "p" and "g" are public and any attacker can know these, but this is not a vulnerability. Although an attacker knew these values and capture the two messages sent between machines A and B, would not be able to figure out the secret key.

If the value of "p" and "g" are small, is possible to hack the protocol, but current implementations of the Diffie-Hellman protocol uses very large prime numbers, which prevents an attacker to calculate the values of "a" and "b". The "g" need not be large, and in practice its value is 2 or 5."

Translated from http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/

EXCERCISE

This week we have to hack a Diffie-Hellman protocol used by two classmates (Alice and Bob). They "encrypt" their communication using the following data:

• p = 31
• g = 15
• X = 23
• Y = 23

The formulas are:

• X = g^x mod p
• Y = g^y mod p 
• k = Y^x mod p 
• k = X^y mod p

So, I have to recover "x", "y", "k".

For this task, I did a "brute force attack", calculating all the posibles values of "x" and "y"

To speed up this task, I write a little python code:

p = 31
g = 15
X = 23
Y = 23

for i in range(p):
    X2 = (g**i)%p
    Y2 = (g**i)%p

    if(X2 == X):
        print "X = %d, X2 = %d, i = %d" %(X, X2, i)
    if(Y2 == Y):
        print "Y = %d, Y2 = %d, i = %d" %(Y, Y2, i)

And this is the output:

X = 23, X2 = 23, i = 7
Y = 23, Y2 = 23, i = 7
X = 23, X2 = 23, i = 17
Y = 23, Y2 = 23, i = 17
X = 23, X2 = 23, i = 27
Y = 23, Y2 = 23, i = 27

In this case, the posible values of "x" and "y" are the same, next, I use these values to calculate "k" using the following python code:

x = [7,17,27]
y = [7,17,27]

for i in x:
    for j in y:
        k = (g**(i*j))%p
        print "k = %d" %(k)

And this is the output:

k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29
k = 29

We can see that all the values of "x" and "y", and even all the combinations can be used to broke the communication, and we can see that the secret key (value of k) is 29.

References

• http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/