 |
| Cabecera del mítico artículo de Diffie y Hellman |
En 1976, los profesores Whitfield Diffie y Martin Hellman publicaron un histórico artículo donde sentaron las bases de lo que hoy conocemos como criptografía de clave pública. Voy a explicar las bases del protocolo criptográfico que inventaron, conocido como protocolo de Diffie-Hellman.
Fundamentos matemáticos
El concepto clave es el de raíz primitiva. Dado un número primo p, siempre existe un número entero g menor que él que cumple una curiosa propiedad. Dicha propiedad consiste en que elevando g a todas las potencias entre 1 y p-1, el resto de dividir dicho resultado entre p es el mismo conjunto (desordenado) de números entre 1 y p-1.
Lo vemos mejor con un ejemplo. En la siguiente tabla tenemos en la primera columna todos los números k entre 1 y 22. En la segunda el resultado de 7k. En la tercera columna está el resto (que se anota como mod) de dividir la segunda columna entre 23. Como vemos, la tercera columna es el mismo conjunto de números k, pero desordenados. Decimos entonces que 7 es la raíz primitiva (también llamado generador) de 23:
k b = 7k 7k mod 23
----------------------------------
1 7 7
2 49 3
3 343 21
4 2401 9
5 16807 17
6 117649 4
7 823543 5
8 5764801 12
9 40353607 15
10 282475249 13
11 1977326743 22
12 13841287201 16
13 96889010407 20
14 678223072849 2
15 4747561509943 14
16 33232930569601 6
17 232630513987207 19
18 1628413597910449 18
19 11398895185373143 11
20 79792266297612001 8
21 558545864083284007 10
22 3909821048582988049 1
----------------------------------
1 7 7
2 49 3
3 343 21
4 2401 9
5 16807 17
6 117649 4
7 823543 5
8 5764801 12
9 40353607 15
10 282475249 13
11 1977326743 22
12 13841287201 16
13 96889010407 20
14 678223072849 2
15 4747561509943 14
16 33232930569601 6
17 232630513987207 19
18 1628413597910449 18
19 11398895185373143 11
20 79792266297612001 8
21 558545864083284007 10
22 3909821048582988049 1
Dado cualquier número b perteneciente a la tercera columna, conociendo que g=7 y p=23, decimos que su correspondiente k (primera columna) es su logarítmo discreto (denotado ind7,23). La notación es la siguiente:
k = indg,p(b)
Su utilidad en criptografía deriva del hecho de que el logarítmo discreto de números muy grandes es muy costoso computacionalmente. Si utilizamos un número primo p suficientemente grande, será fácil obtener los valores de b a partir de k, pero casi imposible obtener los diferentes valores de k a partir de los de b.
Supongamos que, conociendo el número primo p y su raíz primitiva g, elegimos al azar dos números XA y XB , menores que p. Después realizamos estas operaciones:
YA = gXA mod p
YB = gXB mod p
Es decir, estamos convirtiendo valores de la primera columna de nuestra tabla en los de la tercera, o sea, lo que antes llamamos operación fácil.
Ahora volvamos a hacer la misma operación, pero usando los resultados anteriores Y en lugar de g:
KAB = YBXA mod p
KBA = YAXB mod p
En este momento podemos aplicar la propiedad conmutativa, es decir, que para cualesquiera números a, b y c se cumple que:
A partir de ello fácilmente se extrae que KAB = KBA. Hemos producido un valor al que llamaremos simplemente K, el cual es derivado de operaciones relativamente fáciles de hacer. Lo interesante de todo esto es que es muy difícil obtener K, aún conociendo p, g, YA e YB, si no se conoce al menos uno de los XA y XB. Esto implicaría resolver el logarítmo discreto (o índice) indg,p, que es lo que antes hallamos casi imposible si p es muy grande.
 |
| Diffie y Hellman recibieron el Premio Turing en 2015 por sus aportaciones en criptografía. |
Protocolo de intercambio de claves
A partir de las propiedades matemáticas explicadas en el apartado anterior, es fácil construir un protocolo de intercambio de claves, donde los datos intercambiados por canales inseguros serían los valores que no importa hacer públicos (p, g, YA e YB), y mantendremos en secreto en un extremo XA y en el otro XB. Usando ambos por separado cada extremo puede obtener K, que será la clave simétrica utilizada para las comunicaciones encriptadas.
El protocolo completo es:
- Ambos extremos Ana y Benito acuerdan un número primo p y su raíz primitiva o generador g. Siguiendo el mismo ejemplo anterior, elegimos p=23 y g=7.
- Cada uno por separado elige un número menor que p al azar. Supongamos que eligen XA=3 y XB=15.
- También por separado computan la función Y = 7X mod 23. En este ejemplo los resultados son: YA=21 e YB=14.
- Ahora intercambian los dos resultados. Ana entrega a Benito su YA, y por su parte Benito entrega a Ana su YB.
- Ambos extremos calculan por separado: K = 143 mod 23 = 7 (en el lado de Ana). K = 2115 mod 23 = 7 (en el lado de Benito).
- Ahora utilizan K=7 como clave simétrica para intercambiar cualquier mensaje.
Como podemos observar, los únicos valores que se han intercambiado (y por lo tanto pueden ser conocidos por un tercero) son p=23, g=7, YA=21, YB=14. Como vimos en el apartado anterior, la clave K=7 no se podría obtener a partir de esos cuatro valores, mientras p sea lo suficientemente grande (bastante más grande que 23, por supuesto).
Normalmente, se llama clave privada o parte privada de la clave a los valores XA y XB, que no son conocidos más que por cada comunicante, y clave pública o parte pública de la clave a YA e YB, que son conocidos por todo el que tenga acceso al medio.
La conjetura de Diffie-Hellman
Las matemáticas implicadas en el protocolo de Diffie-Hellman son muy complejas. Es interesante, sin embargo, saber que el elemento clave es un problema que podemos enunciar simplificadamente como:
"Dado un número generador g y dos valores gx y gy, obtenidos de números aleatorios x e y, ¿cuál es el valor de gxy?"
Diffie y Hellman supusieron que resolver este problema (conocido desde entonces como DHP, Diffie-Hellman Problem) es muy costoso computacionalmente, aunque no lo demostraron. En criptoanálisis se utiliza una variante del mismo (denominada DDHP, Decisional Diffie-Hellman Problem), el cual consiste en saber si gXY es distinguible de un valor generado aleatoriamente. Hasta el momento nadie ha demostrado que no exista una solución factible computacionalmente.
Aunque el método de Diffie-Hellman tal cual no es muy usado actualmente, varios protocolos criptográficos muy utilizados se basan en la misma suposición de que el problema DDHP no se puede resolver.
El ataque del hombre en el medio
El protocolo de Diffie-Hellman es muy resistente a los ataques pasivos, es decir, donde el intruso se limita a escuchar. Sin embargo, tiene una vulnerabilidad importante cuando el atacante es activo y puede modificar los mensajes en el tránsito. Este tipo de ataques se conocen como man-in-the-middle (hombre en el medio).
Efectivamente, si se observa detalladamente el protocolo explicado anteriormente, vemos que el atacante Carlos podría sustituir los valores YA e YB de Ana y Benito por sus propios valores YCA e YCB calculados por él. Ni Ana ni Benito conocían con anterioridad la elección de su comunicante, por lo que no podrán darse cuenta de que en realidad proceden de Carlos. El atacante conoce (porque están en claro) los valores p, g, YA e YB, por lo que puede acordar con cada extremo su propia clave simétrica KAy KB, respectivamente.
El resultado de todo esto es que Carlos puede desencriptar, encriptar y modificar todos los mensajes entre Ana y Benito, haciendolos pasar por mensajes legítimos del otro extremo. Pocos ataques criptográficos pueden ser tan devastadores como éste.
 |
| En la Universidad de Stanford. |
Autoridades de certificación
La problemática del hombre en el medio es común a todos los sistemas de criptografía asimétrica. La solución siempre pasa por encontrar un tercero en el que todos confían para verificar la identidad del los extremos de la comunicación. A esta fuente confiable la llamaremos autoridad de certificación (certification authority). No deja de ser una variante de la forma clásica de identificarse mediante un pasaporte o documento sellado por una autoridad competente. Al fin y al cabo, el pasaporte es aceptado según la confianza que tenga el receptor en la autoridad que lo ha sellado.
En el caso del protocolo Diffie-Hellman, podemos establecer un repositorio centralizado donde los participantes registren la parte pública de sus claves, en el ejemplo YA e YB. Al negociar el inicio de la comunicación, cuando se intercambian claves, Ana y Benito comunicarán con la autoridad para verificar que son las auténticas y no han sido modificadas en el medio. En la práctica algo parecido es lo que ocurre día a día cuando conectamos, por ejemplo, con nuestro banco por Internet. Necesitamos verificar que las páginas que estamos viendo proceden realmente del banco y no de un atacante que quiera quedarse con nuestro dinero.
La solución, en todo caso, es recursiva, dado que el canal que nos comunica con la autoridad también puede ser comprometido por el atacante y por tanto alguien tendrá que haber "certificado al certificador". En la práctica, existen unas pocas autoridades de máximo nivel, que están en manos de empresas (como la famosa Verisign) que todos los comunicantes tienen por confiables universalmente, las cuales a su vez certifican a autoridades más pequeñas a nivel local. Todo esto ha dado lugar a un floreciente negocio que no está exento de peligros.
En un tema del curso estudiaremos cómo funcionan las cadenas de firmantes que verifican la identidad de las personas y los sitios en Internet, así como el funcionamiento de la negociación de conexión con sitios seguros en Internet.
