RC4

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de julio de 2018; las comprobaciones requieren 19 ediciones .

RC4 (del inglés  Rivest cipher 4 o código de Ron ), también conocido como ARC4 o ARCFOUR ( supuesto RC4 ) es un cifrado de flujo ampliamente utilizado en varios sistemas de seguridad de la información en redes informáticas (por ejemplo, en protocolos SSL y TLS , algoritmos de seguridad inalámbrica ) WPAy.Redes WEP ).

El cifrado es desarrollado por RSA Security y requiere una licencia para usarlo .

El algoritmo RC4, como cualquier cifrado de flujo , se basa en un generador de bits pseudoaleatorios . La clave se escribe en la entrada del generador y los bits pseudoaleatorios se leen en la salida. La longitud de la clave puede ser de 40 a 2048 bits [1] . Los bits generados tienen una distribución uniforme .

Las principales ventajas del cifrado:

RC4 es bastante vulnerable si:

Estos factores, así como la forma en que se utiliza, pueden hacer que un criptosistema sea inseguro (como WEP ).

Historia

El cifrado de flujo RC4 fue creado en 1987 por Ronald Rivest de RSA Security . La abreviatura "RC4" significa oficialmente "Rivest cipher 4" o " Rivest cipher " ("4" es el número de versión; consulte RC2 , RC5 , RC6 ; RC1 nunca se publicó; RC3 se desarrolló, pero se encontró una vulnerabilidad en él ), pero a menudo se considera la abreviatura de " código de Ron " (" código de Ron ") [2] .

Durante siete años, el cifrado fue un secreto comercial , y solo se proporcionó una descripción exacta del algoritmo después de firmar un acuerdo de confidencialidad , pero en septiembre de 1994, su descripción se envió de forma anónima a la lista de correo de Cypherpunks [ 3] .  Pronto se publicó una descripción de RC4 en el grupo de noticias de Usenet " sci.crypt ". A partir de ahí, el código fuente llegó a muchos sitios en Internet . El algoritmo publicado produjo textos cifrados en la salida que coincidían con los textos cifrados producidos por el RC4 original. Los propietarios de las copias legales del código fuente de RC4 confirmaron la identidad de los algoritmos con diferencias en la notación y la estructura del programa.

Dado que este algoritmo es conocido, ya no es un secreto comercial . Sin embargo, el nombre "RC4" es una marca registrada de RSA Security . Para evitar posibles reclamos por parte del propietario de la marca , a veces se hace referencia al cifrado como "ARCFOUR" o "ARC4", en referencia al inglés.  un RC4 supuesto es un RC4  "supuesto" (porque RSA Security no ha publicado oficialmente el algoritmo).

El algoritmo de cifrado RC4 se utiliza en algunos estándares y protocolos de cifrado ampliamente utilizados (por ejemplo, WEP , WPA , SSL y TLS ).

RC4 se hizo popular gracias a:

En EE . UU ., la longitud de clave recomendada para uso doméstico es de 128 bits. Un acuerdo entre SPA ( asociación de editores de software )  y el gobierno de EE . UU. permitió la exportación de cifrados RC4 con una longitud de clave de hasta 40 bits. Las sucursales extranjeras de empresas estadounidenses pueden utilizar claves de 56 bits [4] .

Descripción del algoritmo

El núcleo del algoritmo de cifrado de flujo consta de una función: un generador de bits pseudoaleatorios ( gamma ), que produce un flujo de bits clave (flujo de clave, gamma, secuencia de bits pseudoaleatorios).

algoritmo de cifrado.

  1. La función genera una secuencia de bits ( ).
  2. A continuación, la secuencia de bits se concatena con el texto sin formato ( ) por medio de la operación sumatoria módulo dos (xor) . El resultado es un texto cifrado ( ):

.

algoritmo de descifrado.

  1. El flujo de bits de clave (flujo de clave) se vuelve a crear (regenerar) ( ).
  2. El flujo de bits de la clave se agrega al texto cifrado ( ) con la operación " xor " . Debido a las propiedades de la operación xor , la salida es el texto original (sin cifrar) ( ):

RC4 es en realidad una clase de algoritmos definidos por el tamaño del bloque (en adelante S-box ). El parámetro n es la longitud de la palabra para el algoritmo y especifica la longitud del S-box . Por lo general, n = 8, pero para fines de análisis, puede reducirlo. Sin embargo, para mejorar la seguridad, debe aumentar este valor. No hay contradicción en el algoritmo para aumentar el tamaño del S-box . Con un aumento en n , digamos hasta 16 bits, los elementos en el S-box se convierten en 65.536 y, en consecuencia, se incrementará el tiempo de iteración inicial. Sin embargo, la velocidad de cifrado aumentará [5] .

El estado interno de RC4 se representa como una matriz de tamaño 2 n y dos contadores. La matriz se conoce como S-box y se denominará S. Siempre contiene una permutación de los 2n posibles significados de la palabra. Los dos contadores se denotan por iy j.

La inicialización de RC4 consta de dos partes:

  1. Inicialización de S-box ;
  2. Generación pseudoaleatoria de palabras K.

Inicialización de S-box

El algoritmo también se conoce como "algoritmo de programación de claves" o "KSA". Este algoritmo utiliza una clave proporcionada por el usuario, almacenada en Keyy con una longitud de Lbytes. La inicialización comienza con el llenado de la matriz S, luego esta matriz se baraja mediante permutaciones determinadas por la clave. Dado que solo se realiza una acción en S, la afirmación debe sostener que Ssiempre contiene el mismo conjunto de valores que se dio en la inicialización inicial ( S[i] := i ).

para i de 0 a 255 S[i] := yo final para j := 0 para i de 0 a 255 j := ( j + S[i] + Tecla[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 intercambiar S[i] y S[j] final para

Generación de palabras pseudo-aleatorias K

Esta parte del algoritmo se denomina generador de secuencias pseudoaleatorias ( p seudor  andom generation algorithm , PRGA ) . El generador de flujo de claves RC4 permuta los valores almacenados en . En un ciclo RC4, se determina una palabra de n bits del flujo de claves. En el futuro, se agregará la palabra clave módulo dos con el texto sin formato que el usuario desea cifrar y se obtiene el texto cifrado. SK

yo := 0 j := 0 bucle de generación while : yo := ( yo + 1 ) mod 256 j := ( j + S[i] ) mod 256 intercambiar S[i] y S[j] t := ( S[i] + S[j] ) mod 256 K := S[t] palabra K pseudoaleatoria generada (para n = 8 se generará un byte) endwhile

Seguridad

A diferencia de los cifrados modernos (como eSTREAM ), RC4 no usa un nonce (del inglés nonce - "número que solo se puede usar una vez" - un número que solo se puede usar una vez) junto con la clave. Esto significa que si se va a usar una clave a lo largo del tiempo para cifrar múltiples flujos, el sistema criptográfico que usa RC4 debe combinar la clave de ocasión y la clave a largo plazo para producir una clave de flujo para RC4. Una posible solución es generar una nueva clave para RC4 utilizando una función hash de la clave a largo plazo y un nonce . Sin embargo, muchas aplicaciones que usan RC4 simplemente concatenan la clave y el nonce . Debido a esto y a la débil programación de claves utilizada en RC4, la aplicación puede volverse vulnerable [6] [7] [8] . Por lo tanto, ha quedado obsoleto por muchas empresas de software como Microsoft . Por ejemplo, .NET Framework de Microsoft carece de una implementación de RC4.

Aquí se considerarán algunos ataques al cifrado y los métodos de protección contra ellos.

La investigación de Roose y la recuperación de la clave de la permutación

En 1995, Andrew Roos observó experimentalmente que el primer byte del flujo de claves está correlacionado con los primeros tres bytes de la clave, y los primeros bytes de la permutación después del algoritmo de programación de claves ( ing  . KSA ) están correlacionados con alguna combinación lineal . de bytes clave [9] . Estos sesgos no se probaron hasta 2007, cuando Paul, Rafi y Maitrae demostraron que la clave y el flujo de claves están correlacionados. Además, Paul y Maitre demostraron la correlación de la permutación y la clave. Este último trabajo también utiliza la correlación de permutación de clave para generar el primer algoritmo de recuperación de clave completo a partir de la última permutación después de KSA, sin hacer suposiciones sobre la clave y el vector de inicialización ( IV , vector inicial ) . Este algoritmo tiene una probabilidad de éxito constante a lo largo del tiempo, que es la raíz cuadrada de la complejidad de la fuerza bruta. Se ha trabajado mucho últimamente en recuperar la clave del estado interno de RC4.   

Ataque de Fluhrer, Mantin y Shamir (FMS)

En 2001, Fluhrer, Mantin y Shamir publicaron un artículo sobre la vulnerabilidad del programa clave RC4. Demostraron que los primeros bytes de un flujo de claves entre todas las claves posibles no son aleatorios. A partir de estos bytes, es posible con una alta probabilidad obtener información sobre la clave de cifrado utilizada. Y si una clave a largo plazo y un nonce simplemente se unen para crear una clave de cifrado RC4, esta clave a largo plazo se puede obtener analizando una cantidad suficientemente grande de mensajes cifrados con esta clave [10] . Esta vulnerabilidad y algunos efectos relacionados se aprovecharon para romper el cifrado WEP en redes inalámbricas IEEE 802.11 . Esto mostró la necesidad de reemplazar WEP lo antes posible , lo que condujo al desarrollo de un nuevo estándar de seguridad inalámbrica, WPA .

El criptosistema puede volverse inmune a este ataque descartando el comienzo del flujo de claves. Por lo tanto, el algoritmo modificado se llama "RC4-drop[n]", donde n es el número de bytes desde el comienzo del flujo de claves que se descartará. Se recomienda utilizar n = 768, una estimación conservadora es n = 3072[11] [12] .

El ataque se basa en la debilidad del vector de inicialización . Conociendo la primera palabra pseudoaleatoria Ky mlos bytes de la clave de entrada Key, utilizando una debilidad en el algoritmo de generación de palabras pseudoaleatorias K, se puede obtener m + 1el byte de la clave de entrada. Repitiendo los pasos se obtiene la clave completa. Al atacar WEP , n = 8 IVtiene la forma (B; 255; N), donde B - de 3 a 8, y Ncualquier número. Para determinar unas 60 variantes de N, se necesitarían unos 4 millones de paquetes para ser interceptados. [diez]

Ataque de Klein

En 2005, Andreas Klein presentó un análisis del cifrado RC4 en el que señaló la fuerte correlación entre la clave y el flujo de claves RC4. Klein analizó los ataques en la primera ronda (similar al ataque PMS), en la segunda ronda y sus posibles mejoras. También sugirió algunos cambios en el algoritmo para mejorar la fuerza del cifrado. En particular, argumenta que si invierte la dirección del ciclo en el algoritmo de programación clave, puede hacer que el cifrado sea más resistente a ataques como FMS [1] .

Problema combinatorio

En 2001, Adi Shamir e Itzhak Mantin fueron los primeros en plantear un problema combinatorio relacionado con el número de posibles entradas y salidas del cifrado RC4. Si de todos los 256 elementos posibles del estado interno del cifrado, se conocen xelementos del estado ( x ≤ 256), entonces, si asumimos que los elementos restantes son cero, el número máximo de elementos que puede obtener el algoritmo determinista en las próximas 256 rondas también es igual a x. En 2004 esta suposición fue probada por  Souradyuti Paul y Bart Preneel [ 13 ] . 

El ataque de Vanhof y Pissens (2015)

En el verano de 2015, Mathy Vanhoef y Frank Piessens de la Universidad de Lovaina en Bélgica demostraron un ataque real al protocolo TLS , que utiliza RC4 para cifrar los datos transmitidos [14] . La idea de hackear se basa en el principio MITM . Al incrustarse en un canal de transmisión de datos, el atacante genera una gran cantidad de solicitudes al servidor, obligándolo a devolver cookies en respuesta , encriptadas con la misma clave. Con aproximadamente 9x2 2 27 ~ 2 30 {texto simple, texto cifrado} a mano, el atacante pudo recuperar la clave y, por lo tanto, las cookies cifradas según los métodos estadísticos de Fluhrer-McGrew y ABSAB con una probabilidad del 94 %. El tiempo práctico empleado fue de unas 52 horas, mientras que la estimación superior del tiempo requerido en el momento de la demostración fue de unas 72 horas [15] .

Mods RC4

Anteriormente, se consideraban ataques basados ​​en la correlación de los primeros bytes del texto cifrado y la clave. Estas debilidades del algoritmo se pueden resolver descartando la parte inicial del texto cifrado [16] . Es seguro descartar los primeros 256, 512, 768 y 1024 bytes. Se llevaron a cabo estudios del comienzo del texto cifrado para mostrar la falta de fiabilidad de un cierto número de primeros bytes, lo que puede llevar a que un atacante obtenga una clave de cifrado. Se han propuesto varias modificaciones de RC4 que realizan la tarea de mejorar la seguridad al usar el algoritmo: RC4A, VMPC , RC4+.

RC4A

En 2004 vio la luz el trabajo de Souradyuti Paul y Bart Preneel, que proponían una modificación del RC4A [17] .

Para RC4A, se utilizan dos cajas S en lugar de una, como en RC4, indicadas por S₁y S₂. Para ellos, se utilizan dos contadores, j₁respectivamente j₂. El contador i, como para RC4, se usa en singular para todo el algoritmo. El principio de ejecución del algoritmo sigue siendo el mismo, pero hay una serie de diferencias:

  1. S₁es un parámetro para S₂.
  2. Para una iteración, es decir, para un aumento de índice i, se generan dos bytes de texto cifrado.

Algoritmo:

yo := 0 j₁ := 0 j₂ := 0 bucle de generación while : yo := yo + 1 j₁ := ( j₁ + S₁[i] ) mod 256 intercambiar S₁[i] y S₁[j₁] I₂ := ( S₁[i] + S₁[j₁] ) módulo 256 salida  := S₂[I₂] j₂ = ( j₂ + S₂[i] ) módulo 256 intercambiar S₂[i] y S₂[j₂] I₁ = ( S₂[i] + S₂[j₂] ) módulo 256 salida  := S₁[I₁] endwhile

La velocidad de cifrado de este algoritmo se puede aumentar mediante la paralelización .

RC4+

En 2008, se desarrolló y propuso la modificación RC4+. Los autores Subhamoy Maitra y Goutam Paul modificaron la inicialización del S-box (KSA+) utilizando codificación de 3 niveles. Además, se modificó el algoritmo de generación de palabras pseudoaleatorias (PRGA+) [18] .

Algoritmo:

Todas las operaciones aritméticas se realizan mod 256. Los símbolos "<<" y ">>" denotan cambios de bit a la izquierda y la derecha, respectivamente. El símbolo "⊕" denota la operación " O exclusivo " mientras Ciclo de generación: yo := yo + 1 a := S[yo] j := j + un b := S[j] S[i] := b (intercambiado S[i] y S[j]) S[j] := un c := S[ i<<5 ⊕ j>>3 ] + S[ j<<5 ⊕ i>>3 ] salida ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ] endwhile

Implementación

Muchos cifrados de flujo se basan en registros de desplazamiento de retroalimentación lineal ( LFSR ) .  Esto hace posible lograr implementaciones de alta eficiencia del cifrado en forma de un circuito integrado (implementación de hardware), pero complica la implementación de software de dichos cifrados. Dado que el cifrado RC4 no usa LFSR y se basa en operaciones de bytes, es conveniente implementarlo en el software. Una implementación típica ejecuta de 8 a 16 instrucciones de máquina por byte de texto, por lo que una implementación de software del cifrado debería ser rápida [19] .

Criptosistemas y protocolos usando RC4

La palabra "(variable)" significa que RC4 es uno de varios algoritmos de cifrado que puede utilizar el sistema.

Véase también

Notas

  1. ↑ 1 2 Klein A. Attacks on the RC4 stream cipher  (indefinido)  // Diseños, códigos y criptografía. - 2008. - T. 48 , N º 3 . - S. 269-286 . -doi : 10.1007/ s10623-008-9206-6 .
  2. ↑ Preguntas frecuentes de Rivest (enlace descendente) . Consultado el 15 de octubre de 2009. Archivado desde el original el 15 de julio de 2017. 
  3. ↑ Gracias, Bob Anderson . Lista de correo de Cypherpunks (9 de septiembre de 1994). Consultado el 28 de mayo de 2007.
  4. ↑ Laboratorios RSA - 3.6.2 ¿Qué es RC2?
  5. ↑ Bruce Schneier. Criptografía aplicada. segunda edicion. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Copia archivada (enlace no disponible) . Consultado el 16 de octubre de 2013. Archivado desde el original el 16 de noviembre de 2012. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Teclas débiles en RC4 (enlace descendente) . Consultado el 7 de noviembre de 2012. Archivado desde el original el 18 de junio de 2012. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Debilidades en el algoritmo de programación clave de RC4  (neopr.)  // Apuntes de clase en informática. - 2001. - T. 2259 . - S. 1-24 . -doi : 10.1007 / 3-540-45537-X_1 . Archivado desde el original el 7 de septiembre de 2008.
  11. ↑ I. Mironov. (No tan) mezclas aleatorias de RC4  (neopr.)  // Apuntes de clase en informática. - 2002. - T. 2442 . - S. 304-319 . -doi : 10.1007/ 3-540-45708-9_20 .
  12. ↑ "RC4-drop(nbytes)" . Base de datos de " Nomenclatura de algoritmos criptográficos estándar ".
  13. ↑ Souradyuti Paul, Bart Preneel. Una nueva debilidad en el generador RC4 Keystream y un enfoque para mejorar la seguridad del cifrado  //  Apuntes de clase en informática: revista. - 2004. - vol. 3017 . - pág. 245-259 . -doi : 10.1007/ b98177 .
  14. ↑ RC4 NO MÁS
  15. ↑ Los piratas informáticos mostraron un método práctico para piratear RC4
  16. ↑ Ilya Mironov (2002-06-01), (No tan) Mezclas aleatorias de RC4 , Avances en criptología - CRYPTO 2002 , vol. 2442, Apuntes de conferencias sobre informática, Springer-Verlag, p. 304–319, archivo Cryptology ePrint: Informe 2002/067, ISBN 3-540-44050-X , doi : 10.1007/3-540-45708-9_20 
  17. ↑ Souradyuti Paul y Bart Preneel (2004), Una nueva debilidad en el generador de flujo de claves RC4 y un enfoque para mejorar la seguridad del cifrado , Cifrado de software rápido, FSE 2004 , vol. 3017, Lecture Notes in Computer Science, Springer-Verlag, p. 245–259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), Análisis de RC4 y propuesta de capas adicionales para un mejor margen de seguridad , Progreso en criptología - INDOCRYPT 2008 , vol. 5365, Lecture Notes in Computer science, Springer-Verlag, p. 27–39, Cryptology ePrint Archive: Informe 2008/396, ISBN 3-540-89753-4 , doi : 10.1007/978-3-540-89754-5_3 
  19. ↑ Laboratorios RSA - 3.6.3 ¿Qué es RC4?
  20. ↑ Respuestas archivadas el 24 de marzo de 2010 en Wayback Machine a las preguntas de los usuarios del navegador Opera mini .
  21. ↑ RFC 4757 . Los tipos de cifrado kerberos RC4- HMAC utilizados por Microsoft Windows .
  22. ↑ Software PDF y PDF/A | Herramientas PDF AG | Tecnología Premium PDF Archivado el 3 de noviembre de 2005.
  23. ↑ El procedimiento de encriptación de Skype se expone parcialmente . www.h-online.com. Consultado el 8 de julio de 2010. Archivado desde el original el 6 de noviembre de 2012.

Enlaces

 Criptosistemas simétricos
Cifrados de flujo
Red Feistel
red SP
Otro