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.

	def AliceDescifrar(Y, x): #Funcion que descifra el mensaje de Bob
	resultado=Y**x #Se eleva el mensaje de Bob al exponente del x de Alice
	Bob = Y
	print "Alice recibe: "+str(Bob) #Se imprime lo que recibe alice
	print "Bob cifrado= "+str(resultado) #Se imprime el texto cifrado
	return
	def BobDescifrar(X, y): #Funcion que desicra el mensaje de Alice
	resultado=X**y #se eleva el mensaje de Alice al exponente del y de Bob
	Alice= X
	print "Bob recibe: "+str(Alice) #Se imprime lo que recibe Bob
	print "Alice cifrada= "+str(resultado) #Se imprime el texto cifrado
	return
	def AliceCifrar(primo, generador, turno, Y): #Funcion utilizada para cifrar el valor x de alice
	x=primo
	#if turno==0:
	print "Turno de Alice"
	while x>=primo:
	x=int(raw_input("x: ")) #se pide el valor de x y no sale del ciclo hasta que sea menor que el numero primo
	Y=((generador**x)%primo) #se hace la operacion de cifrado
	if turno==1:
	AliceDescifrar(Y, x) #en el turno 1 se descifra el mensaje
	return Y #devolvemos Y para Bob
	def BobCifrar(primo, generador, turno, X): #Funcion utilizada para cifrar el valor y de Bob
	y=primo
	#if turno==0:
	print "Turno de Bob"
	while y>=primo:
	y=int(raw_input("y: ")) #se pide el valor de y y no sale del ciclo hasta que sea menor que el numero primo
	X=((generador**y)%primo) #se hace la operacion de cifrado
	if turno==1:
	BobDescifrar(X, y) #en el turno 1 se descifra el mensaje
	return X #devolvemos X para Alice
	def Eve(X, Y, g, p): #Hackeo de Eve algoritmo basado en el siguiente URL: https://gist.github.com/ramonesteban/3617622
	print "Eve conoce: X, Y, g, p" #se muestra todo lo que intercepto Eve
	x = y = 0
	A = B = 0
	f1 = f2 =0 #se igualan a 0 todos los valores para que el algoritmo comience
	while A!= X or B != Y or r1 != r2: #mientras que cada uno sea diferente con su pareja se hace el ciclo
	if A!=X: #si la pareja A y X son diferentes
	x+=1 #se aumenta el supuesto valor de x en uno
	A = g**x%p #se obtiene la A a partir de la formula de cifrado con el supuesto x
	if B != Y: #si la pareja B y Y son diferentes
	y+=1 #se aumenta el supuesto valor de y en uno
	B= g**y%p #se obtiene la B a partir de la formula de cifrado con el supuesto y
	r1= Y**x%p #se obtiene r1 con la misma formula utilizando el mensaje de Alice en lugar del generador
	r2= X**y%p #se optiene r2 con la misma formula utilizando el mensaje de Bob en lugar del generador
	print "Se encontro que x de Alice= "+str(x) #cuando sale del ciclo ya habra encontrado x y lo imprime
	print "Se encontro que y de Bob= "+str(y) #cuando sale del ciclo ya habra encontrado y y lo imprime
	return #termina el Hackeo de Eve
	def main():
	p= int(raw_input("primo: ")) #se pide un numero primo
	g= int(raw_input("generador: ")) #se pide un generador
	turno=0 #se igualan los valores iniciales a 0
	Y=0
	X=0
	while turno<=1: #se utiliza un ciclo para controlar los turnos entre Alice y Bob
	X=AliceCifrar(p, g, turno, Y)
	Y=BobCifrar(p, g, turno, X)
	turno+=1
	Eve(X, Y, g, p) #se llama la funcion de alice despues de realizar la comunicacion
	main()

view raw Diffie.py hosted with ❤ by GitHub

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