jueves, 18 de septiembre de 2014

Diffie-Hellman key agreement

Diffie-Hellman protocol.


Diffie-Hellman key agreement is a technique [1] / protocol that allow to two parties establish a shared secret key by exchanging messages over an insecure open channel. The security of this protocol rests on the Diffie-Hellman problem and the problem of computing discrete logarithms.

This protocol need as input an number prime $p$ and a generator $g$ of $p$, that are known by everyone in the communication channel. We have two users, called Alice and Bob. Alice chooses a random secret $x, 1 < x < p - 1$ and computes $f(x) = g^x\mod p$, and Bob chooses a random secret $y, 1 < y < p - 1$ and computes $f(y) = g^y\mod p$.

Later both Alice and Bob shared their $f(x)$ and $f(y)$ to each other and computes $f(y)^x\mod p$ and $f(x)^y\mod p$, respectively. If the protocol was computes correctly, then $f(x)^y\mod p = f(y)^x\mod p$, that it will be the shared key of Alice and Bob.

Now I imagine that I am a man-in-the-middle who wants hack the communication channel of Alice and Bob, whose $p$ and $g$ are publicly known. Because the channel is insecure, I intercepted $f(x)$ and $f(y)$. Now I want search the values of $x$ and $y$ to obtain the shared key of Alice and Bob.

I know that $\textbf G = \mathbb(Z_{p} - 0, *)$. A brute-force attack to Diffie-Hellman protocol involves iterate the generator and computes $\forall k \in \textbf G: g^k \mod p$ until that the outputs be $f(x)$ or $f(y)$. If it matches to anyone of the two, then $k$ is $x$ or $y$, respectively. Now it is possible for me compute the shared key.

My own implementation of this protocol only receives as input the value of $p$ and computes on its own the generator $g$. Because I just want to show how the protocol works, the program chooses a random $x$ and $y$. Later my implementation hacks the protocol.

The full program (GitHub link) does the following:
  • Primality test of $p$. If $p$ is prime, then the protocol continues.
  • Computes all the generators of $p$ and chooses a random $g$.
  • Chooses a random $x$ (Alice private key) and a random $y$ (Bob private key), $x \neq y$.
  • Computes $f(x) = g^x\mod p$ and $f(y) = g^y\mod p$.
  • Computes $f(x)^y\mod p$ and $f(y)^x\mod p$ (Alice and Bob shared key).
  • If $f(x)^y\mod p = f(y)^x\mod p$, then this output is the $key$.
  • $\forall k \in G$ computes $g^k \mod p$ until it matches $f(x)$ or $f(y)$.
Main function Function that computes $f(x)$, $f(y)$ (evaluarLlave) and the $key$ (construirLlave) Function that hacks the protocol Results References
[1] Menezes et. Al, "Handbook of Applied Cryptography", 1996

2 comentarios:

  1. El jueves regreso para calificar. Hoy en clase explicaré cómo se podría mejorar esto. (Ando con gripa, pero intentaré.)

    ResponderEliminar
  2. Aspectos que ganan puntos:

    +1 written in English
    +1 adequacy of p & g verified
    +1 Alice and Bob are different objects
    +1 Alice and Bob get their keys
    +1 the hacker gets the key
    +1 example runs provided

    Multas que pierden puntos (cosas que ya les he dicho que HAY QUE CUIDAR):

    -1 errores de ortografía y/o gramática

    Advertencias (si se repiten en tareas posteriores, serán multas completas):

    No aplican en tu caso.

    => Obtuviste 6 - 1 = 5 del máximo de 7 puntos.

    Comentarios:

    Esto es un muy mal estilo de programación:

    self.p = p
    self.g = 0
    self.generadores()
    print 'p, g'
    print self.p, self.g

    Repasa lo que es la progra orientada a objetos; tu uso de self no tiene caso.
    No abuses de construcciones; sé modular y respeta la capsulación.

    ResponderEliminar