Skipjack y el criptoanálisis imposible
Resumen: Presentación de un nuevo método de
criptoanálisis junto con algunos ya conocidos y su aplicación
a una versión casi completa de Skipjack.
En 1990 Eli Biham y
Adi Shamir presentaron el criptoanálisis diferencial, un
método desconocido hasta entonces para el público
(pero no para todo el mundo como veremos después), que
constituyó la base de la mayoría del criptoanálisis
realizado desde entonces. Gracias a él, encontraron un
ataque con texto escogido contra DES que era más eficiente
que la fuerza bruta (probar todas las claves posibles).
El criptoanálisis
diferencial se basa en la observación de pares de texto
cifrado, cuyos textos en claro correspondientes tienen ciertas
diferencias entre sí. Se estudia la evolución de
estas diferencias mientras los textos en claro atraviesan las
16 rondas de DES, al ser encriptados con la misma clave.
Es suficiente escoger
pares de texto en claro con una cierta diferencia. Entonces, usando
las diferencias en los textos cifrados resultantes, se van asignando
probabilidades a las distintas claves posibles. Según se
van analizando más y más pares de texto cifrado,
una clave surgirá como la más posible. Esa es la
clave correcta.
Sin embargo, en el caso
de DES este ataque resultó ser de interés teórico
más que práctico. Al parecer la NSA conocía
antes que nadie el criptoanálisis diferencial que se reservó
para sí, y eligió las S-boxes y el número
de rondas del algoritmo, de modo que fuera resistente a este ataque.
Otro tipo de análisis
posible es el llamado criptoanálisis lineal debido a Mitsuru
Matsui. Este ataque utiliza aproximaciones lineales para describir
la acción de un cifrado de bloque (DES, FEAL...). Aún
era conocido un tipo más de ataque, llamado criptoanálisis
diferencial lineal, que combina los dos anteriormente comentados.
Pues bien, el "último
grito" presentado informalmente en Crypto '98 por Biham,
Biryukov y Shamir se llama criptoanálisis imposible. La
idea básica parece ser buscar diferenciales - diferencias
entre pares de textos en claro que se mantienen con cierta probabilidad
en las diferencias correspondientes de los textos cifrados - imposibles,
que no pueden ocurrir. Resulta ser que estas diferenciales son
más poderosas que las ordinarias y pueden usarse para atacar
algoritmos.
Los tres presentaron
un ataque contra 31 rondas de Skipjack más rápido
que la fuerza bruta. Recordemos que Skipjack tiene 32 rondas así
que parecen estar a sólo un paso del criptoanálisis
satisfactorio de todo el algoritmo. Ya que no es probable que
la NSA haga un algoritmo con 32 rondas sabiendo romper 31 parece
que esta vez Biham y compañía se les han adelantado.
Como se sabe recientemente
se han presentado varios algoritmos candidatos a convertirse en
el AES (Advanced Encryption System) que utilizaría EE.UU.
para sustituir a DES. El tiempo dirá si estos nuevos algoritmos
resultan ser resistentes al criptoanálisis imposible.
Referencias:
Boletín Cryptogram 15/09/98, www.counterpane.com
Applied Cryptography, B.Schneier
Publicado originalmente en el boletín 76 de Kriptopolis.
