martes, 28 de febrero de 2017

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 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
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 Xy 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 ab y c se cumple que:
Propiedad conmutativa
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 pgYA 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 (pgYA 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:
  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 XA=3 y XB=15.
  3. También por separado computan la función Y = 7X mod 23. En este ejemplo los resultados son: YA=21 e YB=14.
  4. Ahora intercambian los dos resultados. Ana entrega a Benito su YA, y por su parte Benito entrega a Ana su YB.
  5. 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).
  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=23g=7YA=21YB=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 DHPDiffie-Hellman Problem) es muy costoso computacionalmente, aunque no lo demostraron. En criptoanálisis se utiliza una variante del mismo (denominada DDHPDecisional 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 pgYA e YB, por lo que puede acordar con cada extremo su propia clave simétrica KAKB, 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.

sábado, 18 de febrero de 2017

TCP/IP (13): Adaptación a IPv6


En el anterior artículo cantábamos las bondades de IPv6, y al mismo tiempo nos lamentábamos de que su implantación no sea aún total. Hoy vamos a estudiar cómo es la adaptación de IPv4 a IPv6 y las dificultades que encierra.

El rediseño de las cabeceras y de las propias direcciones hacen incompatibles los protocolos IPv4 y IPv6. Los nodos que implementen distintas versiones no pueden comunicarse directamente entre ellos. Para paliar este problema se han previsto distintas técnicas y adaptaciones transitorias:

Transcripción directa de direcciones

Cada dirección IPv4 tiene una dirección IPv6 equivalente, convertible fácilmente. El prefijo ::ffff: indica una dirección IPv4 traducida a IPv6. Los últimos 32 bits (que serían dos grupos hexadecimales) corresponden a la propia dirección IPv4. Para mayor comodidad, se acepta la notación híbrida, dejando la dirección IPv4 en su formato original, como en el siguiente ejemplo:

150.200.1.10

se traduce en

::ffff:150.200.1.10

También existe la transcripción inversa (dirección IPv6 a IPv4), pero lógicamente no puede hacerse de uno a uno, al ser mayor el espacio de direcciones IPv6. Ciertos bloques de direcciones IPv4 se han reservado para mapear direcciones IPv6.

Doble pila

Los nodos que soportan IPv6 lo hacen normalmente mediante una doble pila o una pila híbrida, de manera que puedan manejar paquetes de ambos protocolos. Todos los sistemas operativos modernos lo incorporan por defecto para facilitar la transición.

Hay que tener en cuenta que, aunque el sistema operativo soporte IPv6, no siempre el software de aplicación puede hacer uso de él. Será necesario en ese caso actualizar ese software a una versión superior que sí lo soporte.

Servidores proxy

Se pueden usar servidores específicos a nivel de aplicación (proxies) para dar acceso a los nodos que sólo soportan IPv6 a servidores remotos que sólo soportan IPv4. Esto se puede hacer mediante mecanismos específicos denominados NAT64 y DNS64.

Tunneling

Cuando un nodo o red IPv6 tiene que atravesar otra red que sólo soporta IPv4 para alcanzar sus destinos se les llama nodo o red aislados. En este caso, han de usarse técnicas de tunneling (encapsulado de paquetes) para atravesar la ruta. En este caso IPv4 (o incluso UDP) funciona como una especie de capa de enlace entre nodos IPv6. Las técnicas son variadas según los fabricantes.

También existe el tunneling de IPv4 dentro de IPv6, para equipos que no soportan doble pila, pero se usa mucho menos.



Tunneling automático

En contraposición al tunneling usado para atravesar otras redes, los mecanismos de tunneling automático proveen un mecanismo de transición para conectividad entre nodos IPv4 e IPv6. Se han desarrollado varias técnicas, de las cuales vamos a profundizar en las más extendidas: 6to4 y Teredo.

6to4

Es el método recomendado por el RFC 3056. Se determinan los extremos del túnel mapeando ciertas direcciones IPv4 llamadas anycast (direcciones que representan a determinados nodos dentro de cualquier red, es decir, obvian la parte netid de la dirección).

Este sistema tiene la ventaja de que no necesita la colaboración de los proveedores de Internet. Funciona automáticamente sobre la red IPv4. Sólo es necesario que el router que da acceso a la red soporte el uso del prefijo especial 2002::/16.

Cuando un paquete IPv4 entra en la red IPv6, el router convierte su dirección IP a una con el prefijo 2002::/16. A la salida de la red, la dirección se puede volver a convertir a su forma original.

Una buena pregunta que tienes que estar haciéndote es qué podemos hacer si la dirección de destino es IPv6 y no se puede convertir a IPv4. En ese caso, el paquete se envía a la dirección anycast 192.88.99.1. En el otro extremo de la red, confiamos en que algún router esté escuchando esa dirección y pueda encontrar al destino.

Un inconveniente importante de este mecanismo es que la dirección IP del nodo que envía el paquete no puede ser privada (colisionaría con cualquier otra en la red de destino). 

Teredo

Teredo es un mecanismo de tunneling que no necesita que la dirección origen sea pública, lo que lo hace más universal.

En este caso se utiliza UDP como medio de encapsulamiento. Tiene la ventaja sobre 6to4 de poder atravesar enrutadores que estén usando NAT (un mecanismo de traducción de direcciones entre redes que explicamos en otro artículo de esta serie).
Los equipos Windows (a partir de Vista) incluyen ambas técnicas por defecto. Los equipos Linux sólo incorporan 6to4 por defecto y Teredo se puede instalar aparte.