RC4

En criptografía, RC4 (Rivest Cipher 4, también conocido como ARC4 o ARCFOUR, que significa Presunto RC4, ver más abajo) es una secuencia cifrar. Si bien es notable por su simplicidad y velocidad en el software, se han descubierto múltiples vulnerabilidades en RC4, lo que lo vuelve inseguro. Es especialmente vulnerable cuando no se descarta el comienzo del flujo de claves de salida, o cuando se utilizan claves no aleatorias o relacionadas. Los usos particularmente problemáticos de RC4 han dado lugar a protocolos muy inseguros como WEP.

A partir de 2015, se especula que algunas agencias criptológicas estatales pueden tener la capacidad de descifrar RC4 cuando se usa en el protocolo TLS. IETF ha publicado RFC 7465 para prohibir el uso de RC4 en TLS; Mozilla y Microsoft han emitido recomendaciones similares.

Se han realizado varios intentos para fortalecer RC4, en particular Spritz, RC4A, VMPC y RC4⁺.

Historia

RC4 fue diseñado por Ron Rivest de RSA Security en 1987. Aunque oficialmente se denomina 'Rivest Cipher 4', el acrónimo RC se entiende alternativamente como 'Ron's Code'. #34; (ver también RC2, RC5 y RC6).

RC4 fue inicialmente un secreto comercial, pero en septiembre de 1994, se publicó una descripción anónima en la lista de correo de Cypherpunks. Pronto se publicó en el grupo de noticias sci.crypt, donde Bob Jenkins lo rompió en cuestión de días. A partir de ahí, se extendió a muchos sitios en Internet. Se confirmó que el código filtrado era genuino, ya que se descubrió que su salida coincidía con la del software propietario que utiliza RC4 con licencia. Debido a que el algoritmo es conocido, ya no es un secreto comercial. El nombre RC4 es una marca comercial, por lo que a menudo se hace referencia a RC4 como ARCFOUR o ARC4 (que significa supuesto RC4) para evitar problemas de marca. RSA Security nunca ha lanzado oficialmente el algoritmo; Sin embargo, Rivest se vinculó al artículo de Wikipedia en inglés sobre RC4 en sus propias notas del curso en 2008 y confirmó la historia de RC4 y su código en un artículo de 2014.

RC4 pasó a formar parte de algunos protocolos y estándares de cifrado de uso común, como WEP en 1997 y WPA en 2003/2004 para tarjetas inalámbricas; y SSL en 1995 y su sucesor TLS en 1999, hasta que RFC 7465 lo prohibió para todas las versiones de TLS en 2015, debido a que los ataques RC4 debilitaban o rompían el RC4 utilizado en SSL/TLS. Los principales factores del éxito de RC4 en una gama tan amplia de aplicaciones han sido su velocidad y simplicidad: las implementaciones eficientes tanto en software como en hardware fueron muy fáciles de desarrollar.

Descripción

RC4 genera un flujo de bits pseudoaleatorios (un flujo de claves). Al igual que con cualquier cifrado de flujo, estos se pueden usar para el cifrado combinándolo con el texto sin formato utilizando bit a bit exclusivo o; el descifrado se realiza de la misma manera (ya que exclusivo o con datos dados es una involución). Esto es similar al pad de un solo uso, excepto que se utilizan bits pseudoaleatorios generados, en lugar de una secuencia preparada.

Para generar el flujo de claves, el cifrado utiliza un estado interno secreto que consta de dos partes:

1. Una permutación de los 256 bytes posibles (denotado "S" abajo).
2. Dos punteros índice de 8 bits (denotados "i" y "j").

La permutación se inicializa con una clave de longitud variable, normalmente entre 40 y 2048 bits, mediante el algoritmo programación de claves (KSA). Una vez realizado esto, se genera el flujo de bits mediante el algoritmo de generación pseudoaleatorio (PRGA).

Algoritmo de programación de claves (KSA)

El algoritmo de programación de claves se utiliza para inicializar la permutación en la matriz "S". "longitud de clave" se define como el número de bytes en la clave y puede estar en el rango 1 ≤ longitud de clave ≤ 256, típicamente entre 5 y 16, correspondiente a una longitud de clave de 40 a 128 bits. Primero, la matriz "S" se inicializa a la permutación de identidad. Luego, S se procesa para 256 iteraciones de manera similar a la PRGA principal, pero también se mezcla en bytes de la clave al mismo tiempo.

para i desde 0 a 255
S[i]:= i
endforJ:= 0
para i desde 0 a 255
j:= (j + S[i] + key[i mod keylength]) mod 256
swap values of S[i] and S[j]
endfor

Algoritmo de generación pseudoaleatoria (PRGA)

La etapa de búsqueda de RC4. El byte de salida se selecciona buscando los valores de S[i] y S[j], añadiéndolos juntos modulo 256, y luego utilizando la suma como índice en S; S(S[i] + S[j]) se utiliza como un byte de la corriente clave K.

Para tantas iteraciones como sean necesarias, la PRGA modifica el estado y genera un byte del flujo de claves. En cada iteración, la PRGA:

• incrementos i;
• mira hacia arriba it elemento de S, S[i], y añade eso a j;
• intercambios de valores S[i] y S[j], entonces utiliza la suma S[i] + S[j(modulo 256) como índice para buscar un tercer elemento S (el valor del torrente clave K infra);
• entonces bitwise exclusivo ORed (XORed) con el siguiente byte del mensaje para producir el siguiente byte de cifertexto o texto plano.

Cada elemento de S se intercambia con otro elemento al menos una vez cada 256 iteraciones.

i:= 0
J:= 0
mientras GeneratingOutput:
i:= (i + 1) mod 256
j:= (j + S[i]) mod 256
swap values of S[i] and S[j]
K:= S[i] + S[j]) mod 256]
producción K
terminar

Por lo tanto, esto produce un flujo de K[0], K[1],... que se someten a XOR con texto sin formato para obtener el texto cifrado. Entonces texto cifrado[l] = texto sin formato[l] ⊕ K[l].

Generadores de números aleatorios basados en RC4

Varios sistemas operativos incluyen arc4random, una API originado en OpenBSD que brinda acceso a un generador de números aleatorios originalmente basado en RC4. En OpenBSD 5.5, lanzado en mayo de 2014, arc4random era modificado para usar ChaCha20. Las implementaciones de arc4random en FreeBSD, NetBSD y libbsd de Linux también usan ChaCha20. Según las páginas del manual enviadas con el sistema operativo, en la versión de 2017 de los sistemas operativos macOS e iOS, Apple reemplazó RC4 con AES en su implementación de arc4random. Las páginas man para el nuevo arc4random incluyen el acrónimo "A Replacement Call for Random" para ARC4 como mnemotécnico, ya que proporciona mejores datos aleatorios que rand().

Los nuevos generadores de números aleatorios propuestos a menudo se comparan con el generador de números aleatorios RC4.

Varios ataques a RC4 pueden distinguir su salida de una secuencia aleatoria.

Implementación

Muchos cifrados de flujo se basan en registros de desplazamiento de retroalimentación lineal (LFSR), que, si bien son eficientes en hardware, lo son menos en software. El diseño de RC4 evita el uso de LFSR y es ideal para la implementación de software, ya que solo requiere manipulaciones de bytes. Utiliza 256 bytes de memoria para la matriz de estado, S[0] a S[255], k bytes de memoria para la clave, clave[0] a clave[k−1], y variables enteras, i, j y K. Se puede realizar una reducción modular de algún valor módulo 256 con un AND bit a bit con 255 (lo que equivale a tomar el byte de orden inferior del valor en cuestión).

Vectores de prueba

Estos vectores de prueba no son oficiales, pero son convenientes para cualquiera que pruebe su propio programa RC4. Las claves y el texto sin formato son ASCII, el flujo de claves y el texto cifrado están en hexadecimal.

Seguridad

A diferencia de un cifrado de flujo moderno (como los de eSTREAM), RC4 no toma un nonce separado junto con la clave. Esto significa que si se va a utilizar una única clave a largo plazo para cifrar de forma segura varios flujos, el protocolo debe especificar cómo combinar el nonce y la clave a largo plazo para generar la clave de flujo para RC4. Un enfoque para abordar esto es generar un "fresco" Clave RC4 mediante el hash de una clave a largo plazo con un nonce. Sin embargo, muchas aplicaciones que usan RC4 simplemente concatenan key y nonce; El programa de clave débil de RC4 da lugar a ataques de clave relacionada, como el ataque Fluhrer, Mantin y Shamir (que es famoso por romper el estándar WEP).

Debido a que RC4 es un cifrado de flujo, es más maleable que los cifrados de bloque comunes. Si no se utiliza junto con un código de autenticación de mensajes (MAC) seguro, el cifrado es vulnerable a un ataque de intercambio de bits. El cifrado también es vulnerable a un ataque de cifrado de flujo si no se implementa correctamente.

Sin embargo, cabe destacar que RC4, al ser un cifrado de flujo, fue durante un período de tiempo el único cifrado común inmune al ataque BEAST de 2011 en TLS 1.0. El ataque aprovecha una debilidad conocida en la forma en que se utiliza el modo de encadenamiento de bloques de cifrado con todos los demás cifrados admitidos por TLS 1.0, que son todos cifrados de bloque.

En marzo de 2013, hubo nuevos escenarios de ataque propuestos por Isobe, Ohigashi, Watanabe y Morii, así como por AlFardan, Bernstein, Paterson, Poettering y Schuldt que utilizan nuevos sesgos estadísticos en la tabla de claves RC4 para recuperar texto sin formato con una gran cantidad de Cifrados TLS.

El uso de RC4 en TLS está prohibido por RFC 7465 publicado en febrero de 2015.

Roos' sesgos y reconstrucción clave a partir de la permutación

En 1995, Andrew Roos observó experimentalmente que el primer byte del flujo de clave se correlaciona con los primeros tres bytes de la clave, y los primeros bytes de la permutación después de la KSA se correlacionan con alguna combinación lineal de los bytes de la clave. Estos sesgos permanecieron sin explicación hasta 2007, cuando Goutam Paul, Siddheshwar Rathi y Subhamoy Maitra demostraron la correlación clave-cadena y, en otro trabajo, Goutam Paul y Subhamoy Maitra demostraron las correlaciones permutación-clave. El último trabajo también usó las correlaciones permutación-clave para diseñar el primer algoritmo para la reconstrucción completa de la clave a partir de la permutación final después del KSA, sin ninguna suposición sobre la clave o el vector de inicialización. Este algoritmo tiene una probabilidad de éxito constante en un tiempo, que es la raíz cuadrada de la complejidad de la búsqueda exhaustiva de claves. Posteriormente, se han realizado muchos otros trabajos sobre la reconstrucción de claves a partir de los estados internos de RC4. Subhamoy Maitra y Goutam Paul también demostraron que los sesgos de tipo Roos aún persisten incluso cuando se consideran índices de permutación anidados, como S[S[i]] o S[S[S[i]]]. Estos tipos de sesgos se utilizan en algunos de los métodos de reconstrucción clave posteriores para aumentar la probabilidad de éxito.

Salidas sesgadas de la RC4

El flujo de claves generado por el RC4 está sesgado en diversos grados hacia ciertas secuencias, lo que lo hace vulnerable a ataques distintivos. El mejor ataque de este tipo se debe a Itsik Mantin y Adi Shamir, quienes demostraron que el segundo byte de salida del cifrado estaba sesgado hacia cero con una probabilidad de 1/128 (en lugar de 1/256). Esto se debe al hecho de que si el tercer byte del estado original es cero y el segundo byte no es igual a 2, entonces el segundo byte de salida siempre es cero. Tal sesgo se puede detectar observando solo 256 bytes.

Souradyuti Paul y Bart Preneel de COSIC demostraron que el primer y el segundo byte del RC4 también estaban sesgados. El número de muestras necesarias para detectar este sesgo es de 2²⁵ bytes.

Scott Fluhrer y David McGrew también mostraron ataques que distinguían el flujo de claves del RC4 de un flujo aleatorio dado un gigabyte de salida.

La caracterización completa de un solo paso de RC4 PRGA fue realizada por Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra y Goutam Paul. Teniendo en cuenta todas las permutaciones, demostraron que la distribución de la salida no es uniforme dados i y j y, como consecuencia, la información sobre j siempre se filtra en la salida.

Fluhrer, Mantin y Shamir atacan

En 2001, Fluhrer, Mantin y Shamir hicieron un descubrimiento nuevo y sorprendente: sobre todas las claves RC4 posibles, las estadísticas de los primeros bytes del flujo de claves de salida son claramente no aleatorias y filtran información sobre la clave. Si la clave nonce y la clave a largo plazo simplemente se concatenan para generar la clave RC4, esta clave a largo plazo se puede descubrir analizando una gran cantidad de mensajes cifrados con esta clave. Este y otros efectos relacionados se usaron luego para romper el cifrado WEP ('privacidad equivalente por cable') que se usa con las redes inalámbricas 802.11. Esto provocó una lucha por un reemplazo basado en estándares para WEP en el mercado 802.11 y condujo al esfuerzo IEEE 802.11i y WPA.

Los protocolos pueden defenderse de este ataque descartando la parte inicial del flujo de claves. Tal algoritmo modificado se llama tradicionalmente "RC4-drop[n]", donde n es el número de bytes de flujo de clave inicial que se eliminan. El SCAN predeterminado es n = 768 bytes, pero un valor conservador sería n = 3072 bytes.

El ataque de Fluhrer, Mantin y Shamir no se aplica a SSL basado en RC4, ya que SSL genera las claves de cifrado que utiliza para RC4 mediante hashing, lo que significa que diferentes sesiones SSL tienen claves no relacionadas.

El ataque de Klein

En 2005, Andreas Klein presentó un análisis del cifrado de flujo RC4, que mostraba más correlaciones entre el flujo de claves RC4 y la clave. Erik Tews, Ralf-Philipp Weinmann y Andrei Pychkine utilizaron este análisis para crear aircrack-ptw, una herramienta que descifra RC4 de 104 bits utilizada en WEP de 128 bits en menos de un minuto. Mientras que el ataque de Fluhrer, Mantin y Shamir usó alrededor de 10 millones de mensajes, aircrack-ptw puede descifrar claves de 104 bits en 40 000 cuadros con un 50 % de probabilidad, o en 85 000 cuadros con un 95 % de probabilidad.

Problema combinatorio

Itsik Mantin y Adi Shamir plantearon por primera vez un problema combinatorio relacionado con el número de entradas y salidas del cifrado RC4 en 2001, según el cual, del total de 256 elementos en el estado típico de RC4, si x el número de elementos (x ≤ 256) son solo conocidos (todos los demás elementos se pueden suponer vacíos), entonces el número máximo de elementos que se pueden producir de forma determinista es también x en las próximas 256 rondas. Esta conjetura se descartó en 2004 con una prueba formal dada por Souradyuti Paul y Bart Preneel.

Ataque de Royal Holloway

En 2013, un grupo de investigadores de seguridad del Grupo de Seguridad de la Información de Royal Holloway, Universidad de Londres, informó de un ataque que puede volverse efectivo utilizando solo 2³⁴ mensajes cifrados. Si bien aún no es un ataque práctico para la mayoría de los propósitos, este resultado es lo suficientemente cercano a uno que ha llevado a la especulación de que es plausible que algunas agencias criptológicas estatales ya tengan mejores ataques que hacen que RC4 sea inseguro. Dado que, a partir de 2013, una gran cantidad de tráfico TLS usa RC4 para evitar ataques a cifrados de bloque que usan encadenamiento de bloques de cifrado, si estos hipotéticos mejores ataques existen, entonces esto haría que la combinación de TLS con RC4 sea insegura contra tales atacantes en un gran número de escenarios prácticos.

En marzo de 2015, el investigador de Royal Holloway anunció mejoras en su ataque, proporcionando un ataque 2²⁶ contra contraseñas cifradas con RC4, como se usa en TLS.

Ataque de bar mitzvah

En la conferencia Black Hat Asia 2015, Itsik Mantin presentó otro ataque contra SSL mediante el cifrado RC4.

NO MÁS ataque

En 2015, los investigadores de seguridad de KU Leuven presentaron nuevos ataques contra RC4 tanto en TLS como en WPA-TKIP. Apodado Monitoreo de Numerosas Ocurrencias & El ataque Recovery Exploit (NOMORE), es el primer ataque de este tipo que se demostró en la práctica. Su ataque contra TLS puede descifrar una cookie HTTP segura en 75 horas. El ataque contra WPA-TKIP puede completarse en una hora y permite que un atacante descifre e inyecte paquetes arbitrarios.

Variantes RC4

Como se mencionó anteriormente, la debilidad más importante de RC4 proviene del programa clave insuficiente; los primeros bytes de salida revelan información sobre la clave. Esto se puede corregir simplemente descartando una parte inicial del flujo de salida. Esto se conoce como RC4-dropN, donde N suele ser un múltiplo de 256, como 768 o 1024.

Se han realizado varios intentos para fortalecer RC4, en particular Spritz, RC4A, VMPC y RC4⁺.

RC4A

Souradyuti Paul y Bart Preneel han propuesto una variante RC4, a la que llaman RC4A.

RC4A utiliza dos matrices de estado S1 y S2, y dos índices j1 y j2. Cada vez que se incrementa i, se generan dos bytes:

1. Primero, el algoritmo básico RC4 se realiza utilizando S1 y j1, pero en el último paso, S1[i]+S1[j1] es buscado en S2.
2. Segundo, la operación se repite (sin aumentos i nuevamente) S2 y j2, y S1[S2[i]+S2[j2]] es la salida.

Por lo tanto, el algoritmo es:

Todo aritmético se realiza modulo 256i:= 0
j1:= 0
j2:= 0
mientras GeneratingOutput:
i:= i + 1
j1:= j1 + S1[i]
swap values of S1[i] and S1[j1]
 Producto S2[S1[i] + S1[j1]]
j2:= j2 + S2[i]
swap values of S2[i] and S2[j2]
 Producto S1[S2[i] + S2[j2]]
terminar

Aunque el algoritmo requería la misma cantidad de operaciones por byte de salida, existe un mayor paralelismo que RC4, lo que brinda una posible mejora de la velocidad.

Aunque es más fuerte que RC4, este algoritmo también ha sido atacado, con Alexander Maximov y un equipo de NEC desarrollando formas de distinguir su salida de una secuencia verdaderamente aleatoria.

VMPC

La composición de permutación modificada de forma variable (VMPC) es otra variante de RC4. Utiliza un programa de teclas similar al RC4, con j:= S[(j + S[i] + key[i mod keylength]) mod 256] iterando 3 × 256 = 768 veces en lugar de 256, y con una opción 768 iteraciones adicionales para incorporar un vector inicial. La función de generación de salida opera de la siguiente manera:

Toda aritmética se realiza modulo 256.i:= 0
mientras GeneratingOutput:
a:= S[i]
J:= S[j + a]

 Producto S[S[j] + 1]
Swap S[i] y S[j] ()b:= S[j]; S[i]:= b; S[j]:= a))i:= i + 1
terminar

Esto fue atacado en los mismos documentos que RC4A, y se puede distinguir dentro de los 2³⁸ bytes de salida.

RC4+

RC4⁺ es una versión modificada de RC4 con un cronograma de teclas de tres fases más complejo (toma aproximadamente tres veces más que RC4, o lo mismo que RC4-drop512), y un programa más complejo función de salida que realiza cuatro búsquedas adicionales en la matriz S para cada salida de byte, lo que lleva aproximadamente 1,7 veces más tiempo que el RC4 básico.

Todo aritmético modulo 256. .. y > son de izquierda y derecha, ⊕ es exclusivo ORmientras GeneratingOutput:
i:= i + 1
a:= S[i]
j:= j + a

Swap S[i] y S[j] ()b:= S[j]; S[j]:= S[i]; S[i]:= b;)c:= S[i observado]5 ⊕ j título3] + S[j seleccionado 5  i i título3]
 Producto (S[a+b] + S[c⊕0xAA])
terminar

Este algoritmo no se ha analizado de forma significativa.

Rocíe

En 2014, Ronald Rivest dio una charla y coescribió un artículo sobre un rediseño actualizado llamado Spritz. Se publicó un acelerador de hardware de Spritz en Secrypt, 2016 y muestra que, debido a las múltiples llamadas anidadas requeridas para producir bytes de salida, Spritz funciona con bastante lentitud en comparación con otras funciones hash como SHA-3 y la implementación de hardware más conocida de RC4.

El algoritmo es:

Todo aritmético se realiza modulo 256mientras GeneratingOutput:
i:= i + w
j:= k + S[j + S[i]
k:= k + i + S[j]
swap values of S[i] and S[j]
 Producto z:= S[j + S[i + S[z + k]]]
terminar

El valor w es relativamente primo para el tamaño de la matriz S. Entonces, después de 256 iteraciones de este ciclo interno, el valor i (incrementado por w cada iteración) ha tomado todos los valores posibles 0...255, y cada byte en la matriz S se ha intercambiado al menos una vez.

Al igual que otras funciones de esponja, Spritz se puede usar para crear una función hash criptográfica, un generador de bits aleatorios deterministas (DRBG), un algoritmo de cifrado que admite el cifrado autenticado con datos asociados (AEAD), etc.

En 2016, Banik e Isobe propusieron un ataque que puede distinguir Spritz del ruido aleatorio.

Protocolos basados en RC4

• WEP
• TKIP (algoritmo predeterminado para WPA, pero se puede configurar para utilizar AES-CCMP en lugar de RC4)
• Encriptación de protocolo BitTorrent
• Microsoft Office XP (insecución segura ya que no hay cambios cuando los documentos se modifican)
• Microsoft Point-to-Point Encryption
• Seguridad de la capa de transporte / Sockets Layer (fue opcional y luego se prohibió el uso de RC4 en RFC 7465)
• Secure Shell (opcional)
• Protocolo de escritorio remoto (opcionalmente)
• Kerberos (opcionalmente)
• SASL Mechanism Digest-MD5 (optionally, histórico, obsoleto en RFC 6331)
• Gpcode.AK, un virus informático a principios de junio de 2008 para Microsoft Windows, que toma documentos como rehenes para el rescate oscureciendo con RC4 y RSA-1024 cifrado
• PDF
• Skype (en forma modificada)

Cuando un protocolo está marcado con "(opcionalmente)", RC4 es uno de los múltiples cifrados que el sistema puede configurar para usar.