sábado, 7 de junio de 2008

Seguridad y encriptación

Aunque se ha publicado más información sobre el criptoanálisis de DES que de ningún otro cifrado de bloque, el ataque más práctico a día de hoy sigue siendo por fuerza bruta. Se conocen varias propiedades criptoanalíticas menores, y son posibles tres tipos de ataques teóricos que, aún requiriendo una complejidad teórica menor que un ataque por fuerza bruta, requieren una cantidad irreal de textos planos conocidos o escogidos para llevarse a cabo, y no se tienen en cuenta en la práctica.

La máquina de crackeado de DES de la Electronic Frontier Foundation contenía 1,536 chips y podía romper una clave DES por fuerza bruta en días — la foto muestra un circuito con varios chips Deep Crack.

La máquina de crackeado de DES de la Electronic Frontier Foundation contenía 1,536 chips y podía romper una clave DES por fuerza bruta en días — la foto muestra un circuito con varios chips Deep Crack.

Ataque por fuerza bruta

Para cualquier tipo de cifrado, el método de ataque más simple es el ataque por fuerza bruta — probando una por una cada posible clave. La longitud de clave determina el número posible de claves, y por tanto la factibilidad del ataque. En el caso de DES, ya en sus comienzos se plantearon cuestiones sobre su longitud de clave, incluso antes de ser adoptado como estándar, y fue su reducido tamaño de clave, más que el criptoanálisis teórico, el que provocó la necesidad de reemplazarlo. Se sabe que la NSA animó, o incluso persuadió a IBM para que redujera el tamaño de clave de 128 bits a 64, y de ahí a 56 bits; con frecuencia esto se ha interpretado como una evidencia de que la NSA poseía suficiente capacidad de computación para romper claves de éste tamaño incluso a mediados de los 70.

Académicamente, se adelantaron varias propuestas de una máquina para romper DES. En 1977, Diffie y Hellman propusieron una máquina con un coste estimado de 20 millones de dólares que podría encontrar una clave DES en un sólo día. Hacia 1993, Wiener propuso una máquina de búsqueda de claves con un coste de un millón de dólares que encontraría una clave en 7 horas. La vulnerabilidad de DES fue demostrada en la práctica en 1998 cuando la Electronic Frontier Foundation (EFF), un grupo dedicado a los derechos civiles en el ciberespacio, construyó una máquina a medida para romper DES, con un coste aproximado de 250000 dólares (véase EFF DES cracker). Su motivación era demostrar que se podía romper DES tanto en la teoría como en la práctica: "Hay mucha gente que no creerá una verdad hasta que puedan verla con sus propios ojos. Mostrarles una máquina física que pueda romper DES en unos pocos días es la única manera de convencer a algunas personas de que realmente no pueden confiar su seguridad a DES." La máquina rompió una clave por fuerza bruta en una búsqueda que duró poco más de 2 días; Más o menos al mismo tiempo, un abogado del Departamento de Justicia de los Estados Unidos proclamaba que DES era irrompible.

Ataques más rápidos que la fuerza bruta

Existen tres ataques conocidos que pueden romper las dieciséis rondas completas de DES con menos complejidad que un ataque por fuerza bruta: el criptoanálisis diferencial (CD), el criptoanálisis lineal (CL) y el ataque de Davies. De todas maneras, éstos ataques son sólo teóricos y no es posible llevarlos a la práctica; éste tipo de ataques se denominan a veces debilidades certificacionales.

  • El criptoanálisis diferencial fue descubierto a finales de los 80 por Eli BihamAdi Shamir, aunque era conocido anteriormente tanto por la NSA como por IBM y mantenido en secreto. Para romper las 16 rondas completas, el criptoanálisis diferencial requiere 247 textos planos escogidos. DES fue diseñado para ser resistente al CD. y
  • El criptoanálisis lineal fue descubierto por Mitsuru Matsui, y necesita 243textos planos conocidos (Matsui, 1993); el método fue implementado (Matsui, 1994), y fue el primer criptoanálisis experimental de DES que se dio a conocer. No hay evidencias de que DES fuese adaptado para ser resistente a este tipo de ataque. Una generalización del CL — el criptoanálisis lineal múltiple — se propuso en 1994 Kaliski and Robshaw), y fue mejorada por Biryukov y otros (2004); su análisis sugiere que se podrían utilizar múltiples aproximaciones lineales para reducir los requisitos de datos del ataque en al menos un factor de 4 (es decir, 241 en lugar de 243). Una reducción similar en la complejidad de datos puede obtenerse con una variante del criptoanálisis lineal de textos planos escogidos (Knudsen y Mathiassen, 2000). Junod (2001) realizó varios experimentos para determinar la complejidad real del criptoanálisis lineal, y descubrió que era algo más rápido de lo predicho, requiriendo un tiempo equivalente a 239–241 comprobaciones en DES.
  • El ataque mejorado de Davies: mientras que el análisis lineal y diferencial son técnicas generales y pueden aplicarse a multitud de esquemas diferentes, el ataque de Davies es una técnica especializada para DES. Propuesta por vez primera por Davies en los 80, y mejorada por Biham and Biryukov (1997). La forma más potente del ataque requiere 250 textos planos conocidos, tiene una complejidad computacional de 250, y tiene un 51% de probabilidad de éxito.

Existen también ataques pensados para versiones del algoritmo con menos rondas, es decir versiones de DES con menos de dieciséis rondas. Dichos análisis ofrecen una perspectiva sobre cuantas rondas son necesarias para conseguir seguridad, y cuánto «margen de seguridad» proporciona la versión completa. El criptoanálisis diferencial-lineal fue propuesto por Langford y Hellman en 1994, y combina criptoanálisis diferencial y lineal en un mismo ataque. Una versión mejorada del ataque puede romper un DES de 9 rondas con 215.8 textos planos conocidos y tiene una complejidad temporal de 229.2 (Biham y otros, 2002).

No hay comentarios: