Tarea 3 Hack del algoritmo de Diffie-Hellman

Introducción

El algoritmo de Diffie-Hellman nos permite acordar una clave secreta entre dos máquinas através de un canal inseguro y enviando únicamente dos mensajes.

La clave secreta resultante no puede ser descubierta por un atacante, aunque éste obtenga los dos mensajes enviados por el protocolo. La principal aplicación de éste protocolo es acordar una clave simétrica con la que posteriormente cifrar las comunicaciones entre dos máquinas.

Procedimiento

Alice y Bob desean ponerse de acuerdo sobre una clave para comunicarse criptográficamente, y sólo disponen de un canal al que tiene acceso Eve. Eve tiene interceptadas las comunicaciones entre Alice y Bob.

Alice---------------------------------------(Eve)----------------------------------------Bob

Alice y Bob deciden que la clave será una potencia modular y lo primero es ponerse de acuerdo sobre la base de la potencia y el módulo. Éstos números serán g(un número generador) y p(un número primo). Eve toma nota de éstos números.

Alice y Bob eligen dos números x y y que mantienen en secreto, éstos números serán sus claves privadas, Eve no conoce éstos números. Tampoco Alice conoce el de Bob ni Bob conoce el de Alice.

Alice calcula la potencia (g^a)mod p  y se la envía a Bob, a lo que también Eve toma nota de éste número.

Bob hace lo mismo con Alice; calcula la potencia (g^b)mod p la envía a Alice, también Eve toma nota de éste número.

Y ahora podemos analizar la situación apuntando qué es lo que conoce cada quién.

Alice: Conoce el valor de su número "x" y el número que le ha enviado Bob "Y".

Bob: Conoce el valor de su número "y" y el número que le ha enviado Alice "X".

Eve: Conoce los valores de "X" y "Y" que interceptó dentro de la comunicación.

Alice eleva su clave privada "x" al número que ha recibido de Bob y obtiene Y^x que es lo mismo que (g^y)^x = g^xy.

Bob eleva su clave privada "y" al número que ha recibido de Alice y obtiene X^y que es lo mismo que (g^x)^y = g^yx.

Y como g^xy  = g^yx , Alice y Bob tienen el mismo número.

Eve no puede calcular éste número ya que sólo tiene el valor de  "X" y "Y"

Aquí se muestra la descripción muy gráfica del protocolo de Diffie-Hellman, en el programa se toman los valores de éste ejemplo para verificar su correcta funcionalidad.

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

En el programa se intenta hackear el algoritmo, averiguando el valor de "x" y "y" desde Eve, de quién estamos seguros que no los conoce, ni tiene acceso a ellos.

En el código observamos cómo Eve hackea el algoritmo, utilizando al inicio supuestos x y y hasta encontrar los que son congruentes con el resultado de las operaciones de (X^y)%p y (Y^x)%p sustituyendo el valor del generador por X y Y.

En la ejecución del programa se muestra que Eve realmente logra Hackear el algoritmo.

ramsmunoz@ramsmunoz-Lenovo-B470:~/Escritorio$ python Diffie.py
primo: 23
generador: 5
Turno de Alice
x: 6
Turno de Bob
y: 15
Turno de Alice
x: 6
Alice recibe: 8
Bob cifrado= 262144
Turno de Bob
y: 15
Bob recibe: 19
Alice cifrada= 15181127029874798299
Eve conoce: X, Y, g, p
Se encontro que x de Alice= 6
Se encontro que y de Bob= 15

Dentro del programa, se le tiene que recordar el valor de x a Alice y el valor de y a Bob, al momento del segundo turno en la función de Alice y Bob, fue importante que se quedara así para cumplir realmente que sólo se tenga acceso a "x" y a "y" dentro de sus respectivas funciones.

No existe el modo automático dentro del programa, para la generación de números primos y los generadores, pidiendo al usuario la cantidad de dígitos. Lo cual se puede hacer, generando en una función números primos aleatoriamente, según un mínimo y un máximo estipulado, tomando el que concuerde con el número de cifras ingresado por el usuario, y después encontrar nuestro g, para próximamente pasar a nuestro algoritmo de Diffie-Hellman.

Conclusiones

Se puede observar que el algoritmo de Diffie-Hellman no es completamente seguro, ya que con el programa estamos mostrando su vulnerabilidad, pero se sabe que cuando se trata de números primos muy grandes, éste desafía la capacidad de procesamiento de las computadoras o sistemas distribuidos que intenten atacarlo.

Referencias

Autor: Javier Campos Título: "El algoritmo de Diffie-Hellman" Fecha: 22 de julio del 2011 URL: http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/
Autor: Jesús García de Jalón de la Fuente Campos Título: "Protocolo Diffie-Hellman" Fecha: 02 de noviembre del 2009 URL: http://www.slideshare.net/fivefingers/protocolo-de-diffiehellman
URL de github: https://gist.github.com/ramonesteban/3617622