RC4
| ||||||
En criptografía RC4 es el cifrado de flujo software más utilizado y se utiliza en los protocolos populares como Secure Sockets Layer y WEP. Mientras que destaca por su sencillez y rapidez en el software, RC4 tiene debilidades que argumentan en contra de su uso en los nuevos sistemas. Es especialmente vulnerables cuando el comienzo de la secuencia de claves de salida no se descarta, o cuando no aleatoria o claves relacionadas se utilizan; algunas maneras de utilizar RC4 puede conducir a criptosistemas muy inseguros tales como WEP.
Historia
RC4 fue diseñado por Ron Rivest de RSA Security en 1987 - Mientras se denomina oficial "Rivest Cipher 4" las siglas RC se entiende como alternativa a colocarse para el "Código de Ron". RC4 fue inicialmente un secreto comercial, pero en septiembre de 1994 una descripción de la misma se forma anónima envió a la lista de correo cypherpunks. Pronto se publicará en el grupo de noticias sci.crypt, y de allí a muchos sitios en el Internet. El código filtrado se confirmó que era genuina como se encontró su salida para que coincida con la de software propietario utilizando licencia RC4 - Debido a que se conoce el algoritmo, ya no es un secreto comercial. El nombre RC4 es una marca registrada, por lo RC4 se conoce como ARCFOUR o ARC4 a menudo para evitar problemas de marcas. RSA Security no ha lanzado oficialmente el algoritmo; Rivest ha, sin embargo, vinculada a un artículo de Wikipedia en Inglés RC4 en sus propias notas del curso. RC4 se ha convertido en parte de algunos protocolos y normas de cifrado de uso común, como WEP y WPA para tarjetas inalámbricas y TLS.
Los principales factores en el éxito de RC4 sobre una amplia gama de aplicaciones tales son su velocidad y simplicidad, implementaciones eficientes en software y hardware son muy fáciles de desarrollar.
Descripción
RC4 genera una secuencia pseudoaleatoria de bits. Como con cualquier cifrado de flujo, estos pueden ser utilizados para el cifrado mediante la combinación con el texto plano usando exclusiva relativa a bits-o; se lleva a cabo el descifrado de la misma manera. Para generar la cadena de claves, el sistema de cifrado hace uso de un estado interno secreto que consta de dos partes:
- Una permutación de todas las posibles 256 bytes.
- Dos triples de índice de 8 bits.
La permutación se inicializa con una clave de longitud variable, típicamente entre 40 y 256 bits usando el algoritmo de clave-programación. Una vez que esto se ha completado, se genera la corriente de bits utilizando el algoritmo de generación de seudo-aleatoria.
El algoritmo de clave de programación
El algoritmo de clave-programación se utiliza para inicializar la permutación de la matriz de "S". "KeyLength" se define como el número de bytes de la clave y puede estar en el intervalo 1 = KeyLength = 256, típicamente entre 5 y 16, que corresponde a una longitud de clave de 40 a 128 bits. En primer lugar, la matriz de "S" se inicializa a la permutación de identidad. S se procesa a continuación para 256 iteraciones de una manera similar a la PRGA principal, pero también se mezcla en bytes de la clave al mismo tiempo.
- para i entre 0 y 255
- S: = i
- endfor
- j: = 0 para el i de 0 a 255
- j: = mod 256 valores de canje de S y S
- endfor
El algoritmo de generación pseudo-aleatoria
Por lo que se necesitan muchas iteraciones, el PRGA modifica el estado y emite un byte de la cadena de claves. En cada iteración, los incrementos PRGA I, busca el elemento i de S, S, y añade que con j, intercambia los valores de S, y S, y luego usa la suma S + S como un índice para buscar un tercer elemento de S, el cual se hace un XOR con el siguiente byte del mensaje para producir el siguiente byte de texto cifrado sea o texto plano. Cada elemento de S se intercambia con otro elemento, al menos, una vez cada 256 iteraciones.
- i: = 0 j: = 0
- mientras Generating
- Output: i: = mod 256
- j: = mod 256 valores de canje de S y SK: = S salida de K
- ENDWHILE
Implementación
Muchos cifrados de flujo se basan en registros de desplazamiento lineal de retroalimentación, que, aunque eficiente en hardware, lo son menos en el software. El diseño de RC4 evita el uso de LFSR, y es ideal para la implementación de software, ya que sólo requiere manipulaciones byte. Se utiliza 256 bytes de memoria para el conjunto de estado, S a S, k bytes de memoria para las variables clave, clave a través de clave, y número entero, i, j, y K. La realización de una reducción modular de algún valor del módulo 256 se puede hacer con un AND bit a bit con 255.
Vectores de prueba
Estos vectores de prueba no son oficiales, pero conveniente para cualquier prueba de su propio programa de RC4. Las claves y texto plano son ASCII, la cadena de claves y el cifrado están en hexadecimal.
Seguridad
A diferencia de una cifra de la corriente moderna, RC4 hace falta ser un nonce separado junto a la tecla. Esto significa que si una clave única a largo plazo va a ser utilizada para cifrar con seguridad múltiples arroyos, el sistema criptográfico debe especificar la manera de combinar el nonce y la clave a largo plazo de generar el flujo de clave de RC4 - un enfoque para hacer frente a esto es generar una clave RC4 "fresco" por el hash una clave a largo plazo con un nonce. Sin embargo, muchas aplicaciones que utilizan RC4 simplemente clave y nonce concatenan; débil horario clave de RC4 a continuación, da lugar a una variedad de problemas graves.
Porque es un sistema de cifrado RC4 arroyo, que es más maleable que cifras del bloque común. Si no se usa junto con un fuerte código de autenticación de mensaje y cifrado es vulnerable a un ataque de bit-flipping. Es de destacar, sin embargo, que RC4, ser un cifrado de flujo, es el único sistema de cifrado común que es inmune al ataque BESTIA 2011 en TLS 1.0, que explota una debilidad conocida en el modo de encadenamiento de bloques de cifrado manera se utiliza con todos los de la otra sistemas de cifrado compatibles con TLS 1.0, que son todos los cifrados de bloque.
En 2013 se produjo un nuevo escenario de ataque propuesto por Alfardan, Bernstein, Paterson, Poettering y Schuldt que utiliza nuevos sesgos estadísticos en RC4 tabla de claves para recuperar texto plano con un gran número de encriptación TLS
Sesgos Roos y reconstrucción fundamental de permutación
En 1995, Andrew Roos observó experimentalmente que el primer byte de la cadena de claves se correlaciona con los primeros tres bytes de la clave y los primeros pocos bytes de la permutación después de la KSA se correlaciona con alguna combinación lineal de los bytes de la clave. Estos sesgos se mantuvieron sin probar hasta 2007, cuando Goutam Paul, Siddheshwar Rathi y Subhamoy Maitra demostraron la correlación clave keystream y en otra obra Goutam Pablo y Subhamoy Maitra probaron las correlaciones clave permutación. Este último trabajo también utiliza las correlaciones clave permutación para diseñar el primer algoritmo de reconstrucción de la llave completa de la permutación final después de la KSA, sin ninguna suposición sobre la tecla o IV. Este algoritmo tiene una probabilidad constante de éxito en un tiempo que es la raíz cuadrada de la complejidad de la búsqueda exhaustiva clave. Posteriormente, muchos otros trabajos se han realizado en la reconstrucción de los estados clave interna RC4. Subhamoy y Maitra Goutam Paul también mostraron que los sesgos de tipo Roos persisten incluso cuando se tiene en cuenta los índices de permutación anidadas, como S o S]. Estos tipos de sesgos se utilizan en algunos de los métodos de reconstrucción más tarde clave para incrementar la probabilidad de éxito.
Salidas sesgadas de la RC4
El flujo de clave generada por el RC4 es parcial en diversos grados hacia determinadas secuencias por lo que es vulnerable a los ataques distintivos. El mejor ataque de ese tipo se debe a Itsik Mantin y Adi Shamir, que mostró que el segundo byte de salida del sistema de cifrado fue sesgada hacia cero con una probabilidad de 1/128. Esto es debido 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 es siempre cero. Este sesgo puede ser detectada mediante la observación de sólo 256 bytes.
Souradyuti Paul y Bart Preneel de COSIC mostraron que también eran parciales del primer y el segundo bytes del RC4. El número de muestras requeridas para detectar este sesgo es de 225 bytes. Fluhrer de Scott y David McGrew también mostraron este tipo de ataques, que distinguen el flujo de clave del RC4 de una corriente aleatoria dado un gigabyte de salida.
La caracterización completa de un solo paso de RC4 PRGA se realizó por Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra y Goutam Paul. Teniendo en cuenta todas las permutaciones que demuestran que la distribución de la salida no es uniforme dado i y j, y como consecuencia de ello, la información acerca de j siempre se filtró en la salida.
Fluhrer, Mantin y Shamir ataque
En 2001, un nuevo y sorprendente descubrimiento fue hecho por Fluhrer, Mantin y Shamir: más de todas las posibles llaves RC4, la estadística de los primeros bytes del flujo de clave de salida son fuertemente no-al azar, la filtración de información acerca de la clave. Si la clave a largo plazo y nonce simplemente se concatenan para generar la clave RC4, esta clave a largo plazo pueden ser descubiertos mediante el análisis de un gran número de mensajes encriptados con esta clave. Este y otros efectos se utilizaron para romper el cifrado WEP se utiliza con redes inalámbricas 802.11. Esto causó un revuelo por un reemplazo basada en estándares para WEP en el mercado de 802,11, y llevó a los esfuerzos IEEE 802.11i y WPA.
Los criptosistemas pueden defender contra este ataque descartando la parte inicial de la cadena de claves. Tal un algoritmo modificado se denomina tradicionalmente "RC4-drop", donde n es el número de bytes corriente de clave iniciales que se eliminan. El valor predeterminado es SCAN n = 768 bytes, aunque un valor conservador sería n = 3.072 bytes.
El ataque Fluhrer, Mantin y Shamir no se aplica a RC4 basado en SSL, ya que SSL genera las claves de cifrado que utiliza para RC4 de hash, lo que significa que las diferentes sesiones SSL tienen teclas independientes.
El ataque de Klein
En 2005, Andreas Klein presentó un análisis del sistema de cifrado de flujo RC4 mostrando más correlaciones entre el RC4 de cadenas de claves y la clave. De Erik Tews, Ralf-Philipp Weinmann, y Andrei Pychkine utilizar este análisis para crear aircrack-PTW, una herramienta que se agrieta de 104 bits RC4 utiliza 128-bit WEP en menos de un minuto. Considerando que el Fluhrer, Mantin, y Shamir ataque utiliza unos 10 millones de mensajes, aircrack-PTW puede romper claves de 104 bits en 40.000 marcos con un 50% de probabilidad, o 85.000 marcos con 95% de probabilidad.
Problema de combinatoria
Un problema combinatorio relacionado con el número de entradas y salidas del sistema de cifrado RC4 fue planteada por primera vez por Itsik Mantin y Adi Shamir en 2001, por lo que, de un total de 256 elementos en el estado típico de RC4, aunque sólo se conocen x número de elementos a continuación, el número máximo de elementos que se pueden producir de manera determinista también es x en los próximos 256 rondas. Esta conjetura fue puesto a descansar en el año 2004 con una demostración formal dada por Souradyuti Paul y Bart Preneel.
Variantes RC4
Como se mencionó anteriormente, la debilidad más importante de RC4 proviene del programa de claves insuficiente; los primeros bytes de salida revelan información acerca de la clave. Esto se puede corregir simplemente descartando una parte inicial de la secuencia de salida. Esto se conoce como RC4-dropN, donde N es normalmente un múltiplo de 256, como por ejemplo 768 o 1024. Se han hecho una serie de intentos para fortalecer RC4, en particular RC4A, VMPC, y RC4 +.
RC4A
Souradyuti Paul y Bart Preneel han propuesto una variante RC4, que ellos llaman RC4A. RC4A emplea dos conjuntos de estado S1 y S2, y dos índices j1 y j2. Cada vez que se incrementa, se generan dos bytes: En primer lugar, el algoritmo básico RC4 se realiza utilizando S1 y j1, pero en el último paso, S1 + S1 se busca en S2. En segundo lugar, la operación se repite en S2 y j2, y S1] es la salida.
Así, el algoritmo es:
- Toda la aritmética se realiza módulo 256 i: = 0: j1 j2 = 0: = 0 mientras GeneratingOutput: i: = i + 1 J1: = j1 + valores de canje de salida S1 S1 S1 y S2]: = j2 j2 + valores de canje S2 de S2 y S2 S1 de salida] ENDWHILE
Aunque el algoritmo requiere el mismo número de operaciones por byte de salida, hay una mayor paralelismo de RC4, proporcionando una posible mejora de la velocidad. Aunque más fuerte que RC4, este algoritmo también ha sido atacado, con Alexander Maximov y un equipo del NEC desarrollar maneras de distinguir a su salida de una secuencia verdaderamente aleatoria.
VMPC
"Modificado variablemente Composición Permutación" es otra variante de RC4. Se utiliza el mismo esquema de claves como RC4, pero la iteración 768 veces en lugar de 256, y con un opcional de 768 iteraciones adicionales para incorporar un vector inicial. Escrito para resaltar la similitud con RC4 tanto como sea posible, la función de generación de salida funciona de la siguiente manera:
- Toda la aritmética se lleva a cabo en módulo 256. i: = 0 mientras GeneratingOutput: a: = S j: = S b: = Salida de S SS: b =
S: = ai: = i + 1 ENDWHILE
Este fue atacado en los mismos periódicos como RC4A.
RC4 +
RC4 + es una versión modificada de RC4 con un horario de clave de tres fases más complejas, y una función de salida más complejo que lleva a cabo cuatro búsquedas adicionales en la matriz S para cada salida de bytes, teniendo aproximadamente 1.7 mientras básica RC4.
Toda la aritmética módulo 256 - <> están a la izquierda y desplazamiento a la derecha,? es exclusiva o mientras GeneratingOutput: i: = i + 1 a: = S j: = j + ab: SS =: = b S: = c: S = salida + S? S ENDWHILE
Este algoritmo no ha sido analizada de manera significativa..
Sistemas criptográficos basados en RC4
- WEP
- WPA
- Cifrado del protocolo BitTorrent
- Microsoft Point a Point Encryption
- Secure Sockets Layer
- Secure Shell
- Remote Desktop Protocol
- Kerberos
- Mecanismo SASL Digest-MD5
- Gpcode.ak, un virus junio 2008 equipo temprano para Microsoft Windows, que lleva a los documentos rehenes para pedir rescate por obscurecer con cifrado RC4 y RSA-1024
- Skype
Si un criptosistema se marca con "", RC4 Es una de varias cifras el sistema se puede configurar para usar.
Enlaces internos
- SSL
- Comprobación de redundancia cíclica
- International Data Encryption Algorithm (IDEA)
- Criptografía simétrica
