Diffie y Hellman

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 7^k. 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 = 7^k              7^k 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

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 ind_7,23). La notación es la siguiente:

k = ind_g,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 X_A y X_B , menores que p. Después realizamos estas operaciones:

Y_A = g^X_A mod p

Y_B = g^X_B 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:

K_AB = Y_B^X_A mod p

K_BA = Y_A^X_B 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 K_AB = K_BA. 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, Y_A e Y_B, si no se conoce al menos uno de los X_A y X_B. Esto implicaría resolver el logarítmo discreto (o índice) ind_g,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, Y_A e Y_B), y mantendremos en secreto en un extremo X_A y en el otro X_B. Usando ambos por separado cada extremo puede obtener K, que será la clave simétrica utilizada para las comunicaciones encriptadas.

El protocolo completo es:

1. 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.
2. Cada uno por separado elige un número menor que p al azar. Supongamos que eligen X_A=3 y X_B=15.
3. También por separado computan la función Y = 7^X mod 23. En este ejemplo los resultados son: Y_A=21 e Y_B=14.
4. Ahora intercambian los dos resultados. Ana entrega a Benito su Y_A, y por su parte Benito entrega a Ana su Y_B.
5. Ambos extremos calculan por separado: K = 14³ mod 23 = 7 (en el lado de Ana). K = 21¹⁵ mod 23 = 7 (en el lado de Benito).
6. 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, Y_A=21, Y_B=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 X_A y X_B, que no son conocidos más que por cada comunicante, y clave pública o parte pública de la clave a Y_A e Y_B, 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 g^x y g^y, obtenidos de números aleatorios x e y, ¿cuál es el valor de g^xy?"

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 g^XY 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 Y_A e Y_B de Ana y Benito por sus propios valores Y_CA e Y_CB 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, Y_A e Y_B, por lo que puede acordar con cada extremo su propia clave simétrica K_Ay K_B, 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 Y_A e Y_B. 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.