Fecha: 14 Agosto 2000


Una de las primeras cuestiones que el usuario novato de PGP (o, en general, de cualquier sistema de cifrado) se plantea es: ¿qué tamaño de clave debo elegir? Hay muchas recomendaciones pululando por ahí. Pero las pomposas declaraciones sobre "sistemas criptográficos inviolables" que a veces se oyen por ahí no deben engañarnos de un hecho fundamental: con una sola excepción (la llamada libreta de uso único, OTP), no existe un solo algoritmo criptográfico que sea inviolable. Incluso si no hay manera de efectuar ataques criptoanalíticos (es decir, si no podemos obtener información adicional sobre el cifrado mediante un análisis en profundidad), cualquier sistema de claves puede "reventarse" mediante el sencillo sistema de probar todas las claves posibles.

Es como una caja fuerte. Suponiendo que haya sido diseñada a prueba de ataques (sopletes, explosivos) y que no pueda adivinarse de ninguna manera la combinación (por ejemplo, con un estetoscopio o poniendo la oreja, como vemos en las películas), el ladrón no tendrá más remedio que probar todas las combinaciones. Con tiempo suficiente podrá lograr su objetivo ... aunque si le lleva un millón de años, "ese tiempo suficiente" resulta excesivo.

Elegir una clave demasiado larga puede ralentizar innecesariamente los proceso de cifrado y de descifrado, aunque con los ordenadores actuales no suele haber problema. Más peliagudo sería escoger una clave demasiado breve, ya que eso nos pondría a merced de potenciales atacantes. Los paranoicos de la seguridad, y en general aquellos que usan cifrado de datos para evitar que los malos de la película (reales o potenciales) accedan a sus secretillos, no verán con agrado que sus claves sean de longitud insuficiente.

¿Cómo conseguirlo? Pues razonando y haciendo algunos números. Y como estamos en un Taller de Criptografía y nos gusta comprobar las cosas por nuestra cuenta, vamos a sacar las herramientas y a destripar el asunto. Los lectores con fobia a las matemáticas pasarán un par de malos tragos, ya que es necesario hacer números, pero confío en no hacérselo demasiado duro de roer.

Este estudio se divide en dos partes. En el presente Informe plantearemos la situación al día de hoy. En el siguiente, intentaremos extrapolar los resultados hacia los próximos años.

Y ahora, llave inglesa, tenazas y al ataque.


Precedentes

En 1977 los creadores del algoritmo RSA propusieron un reto. Cifraron un texto con su nuevo sistema y retaron al mundo a que lo descifrase (dicho reto apareció en la revista Investigación y Ciencia de 1977, aunque no recuerdo el mes). Los autores creían que no se podría hacer en menos de 40.000 billones de años. En 1993 se consiguió, mediante un conjunto de cálculos que llevó unos ocho meses. !Diablos! Esto sí que es una metedura de pata. Bueno, supongamos que los autores estaban algo despistados; al fin y al cabo, era el primer uso de su algoritmo y no había datos experimentales sobre su resistencia a un ataque real. Pero ....

Pero una y otra vez se ha comprobado que el tiempo necesario para "destripar" un mensaje cifrado ha sido menor que el que se presuponía según la teoría. Eso se debe a dos factores fundamentales. El primero es la creciente capacidad de cómputo de los ordenadores modernos. La máquina con la que usted está leyendo este texto hubiera pasado hace dos décadas por un superordenador, y ciertamente sobrepasa con mucho las posibilidades de máquinas dedicadas en el pasado a tareas tales como poner un hombre en la luna o diseñar las primeras bombas de hidrógeno.

El segundo factor, que afecta muy especialmente a los algoritmos de clave asimétrica, es de tipo teórico. A lo largo de los años se han descubierto procesos algorítmicos cada vez más eficaces para la resolución de los problemas matemáticos en que se basan los sistemas de cifrado asimétrico. Especialmente destacados son los avances en la factorización de números primos (necesarios para atacar algoritmos asimétricos como el RSA). Un ejemplo. En 1994 se consiguió factorizar un número de 129 dígitos mediante la llamada criba cuadrática polinómica; cinco años más tarde, merced al nuevo sistema de criba de campo numérico, se factorizó un número de 140 dígitos ... con menos de la mitad de la potencia de cálculo.

Es quizá por ello que muchas predicciones del pasado han quedado en ridículo. Por desgracia, no podemos predecir cuándo aparecerá un algoritmo de factorización nuevo. Pero algo podremos hacer. También hemos de tener en cuenta el aumento en la potencia de cálculo de los ordenadores, que parece no tener fin. No es lo mismo atacar un algoritmo de clave asimétrica (como el RSA) que uno de clave simétrica (como DES o IDEA). Y por último, hemos de estimar la capacidad de ataque de nuestros supuestos enemigos.

Os creía que esto iba a ser fácil, ¿eh? Pues os equivocáis, amiguitos. Sin embargo, que no cunda el pánico. Planteemos los problemas uno por uno. El primero es obvio: si usamos cifrado de datos, es para protegernos; pero ¿de quién?


¿Quién es el enemigo?

La mayoría de nosotros tenemos pocos enemigos, pero supongamos que existen. Porque haberlos, haylos. Los hackers curiosos están a la orden del día. En el extremo opuesto, grandes hermanos como el ahora conocido sistema de espionaje electrónico Echelon nos acecha noche y día. Y entre medias, los directores o jefes de empresas pueden tener suspicacias respecto a sus competidores. Hay tantos enemigos como podamos imaginarnos.

El problema es que necesitamos saber de qué son capaces. Este es el primer escollo a la hora de determinar el grado de protección que necesitamos. Para solventarlo, aquí propongo cuatro tipos de ataque, con una estimación de su posible capacidad de cálculo. Supondremos que cada uno de ellos dispone de un conjunto de ordenadores o sistemas informáticos en general, y que están dispuestos a utilizarlos contra nuestros secretos sin importar el valor de éstos. Con ello me saltaré un principio de la seguridad, que establece que el grado de protección ha de estar en función de los bienes que protejamos. Es decir, no haré cuentas sobre lo que contiene nuestros mensajes cifrados. Puede ser la lista de la compra, la fórmula de la Coca-Cola o los números de la cuenta suiza de Bill Gates. No importa aquí; el caso es que los malos van a por todas.

Para empezar, algunas definiciones. Usaremos la capacidad de cálculo de cualquier sistema informático, y la expresaremos en diferentes unidades. La principal es la cantidad de operaciones (es decir, pasos sencillos como sumas o restas) que pueden efectuarse: las llamaremos operaciones o instrucciones. Como esta cantidad depende de cuánto tiempo estemos usando nuestras máquinas, tendremos en cuenta la "velocidad de cálculo": el número de operaciones por unidad de tiempo, que se denomina flop; se suele usar el múltiplo megaflop (Mflop: millón de operaciones por segundo). Podemos someramente establecer que un flop se corresponde a un paso del reloj del ordenador.

Es decir, un Pentium a 450 MHz (mega-ciclos) ejecutaría 450 millones de operaciones por segundo, con una velocidad de 450 Mflops. Para medir la cantidad de operaciones se utiliza también una unidad denominada Mflop-año, que es el número de operaciones ejecutadas en un año a una velocidad de un Mflop. Tomaremos el convenio de: 1 Mflop-año : 3*10^13 (3 por 10 elevado a trece) operaciones.

Y ahora vamos con nuestros atacantes. El primero lo denomino ataque pirata, y es el efectuado por el típico listillo de la informática que tiene a su disposición un par de ordenadores para hacer con ellos lo que quiera. Dos ordenadores a unos 500 MHz daría una velocidad de cómputo de unos 1.000 megaflops, o 10^9 operaciones por segundo. Es posible imaginar escenarios en los que podría acumular más capacidad de cálculo (con más ordenadores, o accediendo a los recursos informáticos de una universidad), pero para empezar me parece una cantidad razonable.

En segundo lugar, está el ataque corsario. Con esto quiero denotar un atacante con mayores recursos, como una red de computación u ordenadores especialmente construidos para reventar claves. Este ataque requiere un esfuerzo organizado y costoso. Como "atacante corsario" tomaré un ejemplo: el de la EFF (Electronic Frontier Foundation). Esta entidad construyó un "reventador" de claves DES para demostrar la creciente vulnerabilidad de dicho algoritmo frente a atacantes decididos. A un coste de unos 40 millones de pesetas, su DES-cracker consiguió descifrar un mensaje (cifrado con DES) en un ataque combinado con una red de ordenadores de todo el mundo (coordinados bajo el nombre de Distributed.net). El número de claves posibles en el algoritmo DES, junto con el tiempo necesario para probar cada clave, concuerda con una velocidad de cálculo de unos 10^14 flops, unos cuatro órdenes de magnitud superior a las posibilidades del atacante pirata. Este "corsario" era benigno, pero no resulta descabellado imaginar esfuerzos similares para obtener secretos bancarios o comerciales.

En tercer lugar, tenemos el ataque mafioso. Lo imagino como un esfuerzo tipo "corsario", pero a mayor nivel, hecho por un atacante con grandes recursos (un grupo mafioso, un gran banco o empresa) capaz de gastarse varios miles de millones de pesetas en un gran ataque. A un coste por flop similar al del corsario, podemos suponerle una capacidad de cálculo por unidad de tiempo de unos 10^14 flops. Téngase en cuenta que esta es, aproximadamente, la velocidad de cálculo del mayor ordenador del mundo en la actualidad; sin embargo, es posible obtener velocidades similares en sistemas específicamente diseñados basados en hardware. Es decir, una máquina específicamente construida para descifrar mensajes puede tener la misma velocidad de cálculo que un ordenador multiuso mucho más caro.

Y, por último, presentamos el Ataque MIB. Es la abreviatura en inglés de Hombres de Negro (Men in Black), y lo uso para designar al atacante definitivo, con fondos casi ilimitados en material y dinero. El atacante MIB más poderoso existente es posiblemente la Agencia de Seguridad Nacional (NSA) norteamericana, dedicada al espionaje electrónico y la ruptura de claves, que dispone de un presupuesto del orden del billón de pesetas. Supongamos que no tienen nada mejor que hacer que construir un superdescifrador y lanzarlo contra nuestros secretos. De acuerdo, resulta difícil imaginar un escenario semejante, pero eso nos dará una cota superior a la potencia de cálculo disponible en un ataque (descartando, eso sí, un "ataque alienígena"). Aumentemos la capacidad de los Hombres de Negro en dos órdenes de magnitud respecto al ataque mafioso: tendremos así un total de 10^18 operaciones por segundo (flops).

La capacidad total de cálculo dependerá tanto de la potencia del atacante como del tiempo que esté dispuesto a dedicar sus esfuerzos. ¿Se pasarán un siglo atacando, o tendrán bastante con una semana? De nuevo supongo que los atacantes no tienen nada mejor que hacer, de manera que pueden dedicarse un buen rato a su tarea. Pero tampoco pueden estar un siglo en ello (bueno, poder pueden, pero ¿a quién le importan sus mensajes secretos después de muerto). Así que daré esta regla para los ataques:

Como puede verse, a pesar del gran número de ordenadores que contribuyen, las capacidades y velocidades de cálculo no llegan a las de un ataque corsario. Resulta difícil imaginar esfuerzos coordinados en Internet a nivel voluntario, de manera que los ataques criptográficos que se puedan efectuar por medio de Internet no requieren un tratamiento especial: los incluiremos en la modalidad de ataques corsario... o, en un caso extremo, un ataque mafioso. En cualquier caso, esfuerzos distribuidos como los mencionados apoyan mi hipótesis de que un año de ataque no es descabellado: el proyecto RC5 lleva funcionando sin interrupción desde hace casi tres años.


Los objetos del deseo (I): claves simétricas

Ya sabemos cómo son los atacantes. Ahora, veamos qué van a hacer con tanta potencia de computación. Vamos a examinar la fortaleza de algoritmos en clave simétrica y asimétrica. Y comenzaremos con los primeros. Los algoritmos en clave simétrica son aquellos que utilizan la misma clave para cifrar que para descifrar. Ejemplos: DES, IDEA, CAST, 3-DES (o Triple-DES), Blowfish, RC2, RC4, RC5.

En la mayoría de los algoritmos en clave simétrica utilizados no hay ataques criptoanalíticos dignos de ese nombre, es decir, no hay atajos. Eso significa que no hay más remedio que probar todas las posibles claves, en busca de la correcta. El tamaño de las claves de los algoritmos se da en bits. Por ejemplo, las claves del algoritmo IDEA son de 128 bits, lo que significa que hay un total de 2^128 claves posibles ... que tendremos que comprobar, una por una.

En principio, no habría más que tomar la capacidad de cálculo C y tomar su logaritmo en base dos. Ese número nos dará la longitud máxima de clave que podemos tratar. El motivo es que un algoritmo con clave de longitud x tiene 2^x claves posibles; así, si igualamos el número de claves al número de operaciones (2^x = C) tenemos que x=Log2(C). Esto presupone que basta una operación (es decir, un ciclo del reloj del ordenador) para comprobar una clave.

Lo ilustraremos con un ejemplo. El atacante pirata tiene un total de 3*10^17 operaciones. El logaritmo en base dos de esta cantidad es aproximadamente 58. Eso significa que podrá reventar, en un año de esfuerzo, claves con longitud de hasta 58 bits. En efecto, a una tasa de una operación por clave, necesitaríamos 2^58 operaciones para probar todas las claves. Y 2^58 es aproximadamente igual a 3*10^17. ¿Lo vais pillando? Los demás atacantes podrían reventar sistemas de claves simétricas con longitud máxima de 71 (~=log2(3*10^21)), 78 (~=log2(3*10^23)) y 85 (~=log2(3*10^25)); el símbolo ~= significa "aproximadamente igual a", y eliminamos las cifras decimales redondeando por exceso.

En realidad, he hecho trampa. He supuesto que cada clave puede comprobarse en un solo ciclo de reloj, de forma que nº operaciones = nº de claves comprobadas. En realidad no es así. El número de ciclos (operaciones) por clave varía entre los 144 del veloz algoritmo Blowfish y los 864 del lento Triple-DES, pasando por los 288 de DES (véase por ejemplo esta tabla de Bruce Schneier. Como es una cifra que varía de un algoritmo a otro, haremos una pequeña simplificación: supondremos que cada algoritmo precisa de 200 operaciones por clave.

¿Por qué 200? Es una cantidad razonable, promedio aproximado de diversos algoritmos. En realidad, el más lento de los algoritmos usados habitualmente (TripleDES) es unas seis veces más lento que el rápido Blowfish. Esto significa que preocuparse por uno u otro importa relativamente poco: el esfuerzo computacional para reventar una clave TripleDES de x bits es similar al de una clave Blowfish de x+2.6 bits. Así tomaremos un valor promedio y despreciaremos de las diferencias entre los diversos algoritmos. Añadiré que 200 ciclos/clave corresponde bastante bien con los datos obtenidos en un experimento de "reto" (challenge) denominado DES Challenge III. En ese caso, basta rehacer los cálculos anteriores, sólo que haciendo no el logaritmo en base 2 de C (capacidad de cálculo) sino de C/200. Con esta corrección, los atacantes pirata, corsario, mafioso y MIB tendrán a su alcance el reventar claves de hasta 51, 64, 71 y 77 bits, respectivamente. Cuando el número de bits no sea un número entero, redondearemos por exceso.

A ver, ¿quién se ha perdido? Uf, cuantas manos levantadas. Bueno, no os preocupéis. Lo importante es que, basándonos en el potencial de los diversos atacantes, podemos calcular la cantidad máxima de claves que pueden comprobar y, en consecuencia, la longitud mínima que ha de tener nuestra clave simétrica.

Como conclusión de los cálculos anteriores, el tamaño mínimo de clave (x) que nos garantiza seguridad frente a un atacante con capacidad de cálculo C viene dado por la expresión x = Log2(C/200). Haremos unos cuantos cálculos en breve, y los sintetizaremos en una tabla. Pero antes vamos a ocuparnos de la gran estrella en la criptografía moderna: las claves asimétricas.


Los objetos del deseo (II): claves asimétricas

En el caso de la criptografía asimétrica (o de clave pública), la situación es mucho más compleja. Cada algoritmo es diferente de los demás y exige un tratamiento especial. Felizmente, los dos algoritmos más usados (RSA y Diffie-Hellman, o D-H) son semejantes en fortaleza. Esto quiere decir que un ataque a un algoritmo RSA precisaría de una capacidad de cálculo similar al de un ataque a un algoritmo D-H con idéntica longitud de clave. Eso nos permitirá centrarnos en el algoritmo RSA, cuya resistencia yace en la dificultad de factorizar (descomponer en factores primos) números grandes. Vamos, pues, a examinar el estado actual de la guerra de la factorización.

Pero antes, un aviso importante. Se cree que el problema de atacar claves RSA está regido por la dificultad en factorizar números grandes, pero NO ha sido demostrado y NO podemos descartar que existan ataques (desconocidos hasta ahora, pero posibles) más sencillos y rápidos. También se cree que los algoritmo RSA y DH son similares en fortaleza (como mencioné en el párrafo anterior), pero tampoco ha sido demostrado. A falta de otra cosa, compartiremos las suposiciones de la comunidad criptográfica. Avisados quedáis.

Muy bien, ¿cómo esta la cuestión de la factorización de un número N? Este número será la base del algoritmo de cifrado RSA; la clave será ese número N (no exactamente, pero casi), y diremos que esa clave es de "x bits" cuando ese número es del orden de 2^x; fijaos que digo "del orden" para no meternos en más profundidades. Nos saltaremos los detalles matemáticos y diremos simplemente que la factorización del número N, con el algoritmo más rápido conocido en la actualidad (la Criba de Campo Numérico, CCN) nos permitiría la factorización usando una cantidad de cálculos que denominaremos L(N) y que es aproximadamente igual a: