Member of The Internet Defense League Últimos cambios
Últimos Cambios
Blog personal: El hilo del laberinto Geocaching

Ataque al RC4

Última Actualización: 24 de Enero de 2002 - Martes

En Julio de 2001, los reputados criptógrafos Scott Fluhrer, Itsik Mantin y Adi Shamir publicaron un artículo describiendo una vulnerabilidad en el algoritmo de cifrado RC4. Según ella, se puede recuperar la clave empleada si la inicialización del algoritmo cumple determinadas premisas, muy comunes, y se interceptan el suficiente número de mensajes.

En un primer momento no le dí demasiada importancia, por entender que se trataba de un ataque particular en el contexto WEP (protocolo de cifrado para redes inalámbricas). Me descargué el documento y durmió mucho tiempo en mi disco duro, a la espera de que tuviese un momento para echarle un vistazo fondo.

Cuando por fin se me ocurrió curiosearlo, descubrí con pavor que el ataque era muy general, abarcando cualquier uso de RC4 que emplee una inicialización de clave normal. Ello incluye la mayoría de los productos criptográficos que usen dicho algoritmo, incluyendo el proyecto CipherSaber y mi propio programa BulletProof.

En este artículo hago un resumen del artículo original y comento algunas de las soluciones propuestas por la comunidad criptográfica.

El artículo original detalla dos ataques diferentes sobre RC4. El primero de ellos se basa en patrones invariantes. Es decir, existen patrones que, de existir en la clave, se propagan también al estado interno del algoritmo, debilitándolo considerablemente. El segundo ataque describe la recuperación de la clave secreta, cuando la clave del algoritmo se deriva de la concatenación de dicha clave secreta y un vector inicial público y conocido.

Con la primera vulnerabilidad, el resultado es que los primeros bytes generados por RC4 pueden resultar muy predecibles. Dado que BulletProof emplea sólo tantos bytes como longitud del mensaje a cifrar, y dicho mensaje es típicamente muy corto, somos vulnerables.

La segunda vulnerabilidad permite recuperar la parte secreta de la clave RC4 recopilando un gran número de mensajes y vectores iniciales (si la clave RC4 total es la concatenación de la clave secreta y el vector inicial). BulletProof es menos vulnerable a este ataque debido a que para que sea práctico se requiere recopilar un gran número (millones) de mensajes y vectores iniciales, algo que no es muy factible en el entorno IRC al que se orienta BulletProof.

Estas vulnerabilidades son graves y minan considerablemente tanto la confianza en RC4 como la fiabilidad de los productos que lo utilicen.

Existen, no obstante, algunas sugerencias hechas por la comunidad criptográfica internacional que permiten seguir utilizando RC4 de forma segura (al menos hasta que se descubran nuevos ataques), y sin una pérdida demasiado importante de eficiencia.

Dado que el problema del primer ataque reside en la predictibilidad de los primeros bytes RC4, una posibilidad es descartarlos. Es decir, no empezamos a utilizar la salida RC4 desde el primer byte, sino desde el byte "n". El número de bytes iniciales que desaprovechamos supone un compromiso entre la eficiencia de arranque del sistema, y la seguridad.

El segundo problema se puede solucionar simplemente evitando que el atacante obtenga segmentos largos de la clave RC4, que es lo que consigue con los vectores iniciales y la concatenación típica entre la clave secreta y dichos vectores iniciales. Una opción sería reemplazar el concatenado por una función hash, por ejemplo. Lamentablemente el uso de una función hash puede suponer una carga considerable en la inicialización RC4, ya que suelen ser funciones lentas, sobre todo si lo comparamos con la inicialización RC4 estándar.

En general, debido a la rapidez y eficiencia de RC4, resulta preferible descartar los, por ejemplo, primeros 256 bytes generados, que descartar 64 bytes para eliminar el primer problema y calcular un hash para eliminar el segundo. Si descartamos el suficiente número de bytes iniciales, estaremos protegidos contra los dos ataques. El problema es... ¿cuántos bytes descartar?.

El propio autor del algoritmo RC4, Ron Rivest, nos da algunas pistas:

[...]
In protocols such as WEP, it is often necessary to generate different RC4 keys from different messages (or packets) from a common base key. A method frequently suggested to obtain the keys is to add or concatenate a counter to the base key. The key-scheduling algorithm of RC4 has been widely recognized to be rather lightweight for this purpose, particularly when the initial few bytes of plaintext are easily predictable.

RSA Security has discouraged such key derivation methods, recommending instead that users consider strengthening the key scheduling algorithm by pre-processing the base key and any counter or initialization vector by passing them through a hash function such as MD5. Alternatively, weaknesses in the key scheduling algorithm can be prevented by discarding the first 256 output bytes of the pseudo-random generator before beginning encryption. Either or both of these techniques suffice to defeat the new attacks on WEP and WEP2.
[...]
As can be seen from these two examples, the applicability of the new attacks to existing applications utilizing RC4-based encryption schemes depends on the details. Applications which pre-process the encryption key and IV by using hashing and/or which discard the first 256 bytes of pseudo-random output should be considered secure from the proposed attacks.
[...]

Ron nos confirma que basta con aplicar descarte de valores iniciales o una función hash. No es preciso que empleemos las dos posibilidades simultaneamente.

Como nota curiosa, RC4 se utiliza en el protocolo SSL, pero de forma segura, ya que se emplea hashing.

A modo de curiosidad, veamos las implicaciones, a nivel de tiempo de ejecución, entre las diferentes opciones. Recordemos que BulletProof está programado en Python. Las pruebas de rendimiento se hacen sobre un procesador UltraSparc a 143 Mhz, muy anticuado para los estándares actuales, pero que sirve de ejemplo:

 Tiempo de inicialización
del algoritmo
Inicialización RC4 estándar
(clave de 18 caracteres)
10 milisegundos
Hash MD570 microsegundos
Hash SHA-180 microsegundos
Descarte de 256 bytes21 milisegundos

Este contexto contradice el comentario anterior de que resulta más rentable descartar bytes a trabajar con funciones hash lentas. La razón de ello es muy simple: en Python las funciones hash son módulos programados en C a los que se accede a través de su interfaz Python, mientras que mi rutina RC4 no está optimizada para velocidad y, además, está programada en Python, no en C, por razones de portabilidad.

Con estos datos, la decisión respecto a BulletProof está clara. Ver los comentarios a la versión 1.123.


Historia

  • 24/Ene/02: Primera versión de este documento.



Python Zope ©2002 jcea@jcea.es

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS