Salsa20 y el estrechamente relacionado ChaCha son cifrados de flujo desarrollados por Daniel J. Bernstein . Salsa20, el cifrado original, fue diseñado en 2005 y luego enviado al proceso de validación criptográfica de la Unión Europea eSTREAM por Bernstein. ChaCha es una modificación de Salsa20 publicada en 2008. Utiliza una nueva función de ronda que aumenta la difusión y el rendimiento en algunas arquitecturas. [4]
Ambos cifrados se basan en una función pseudoaleatoria basada en operaciones de suma-rotación-XOR (ARX): suma de 32 bits, suma bit a bit (XOR) y operaciones de rotación . La función principal asigna una clave de 256 bits , un nonce de 64 bits y un contador de 64 bits a un bloque de 512 bits del flujo de claves (también existe una versión de Salsa con una clave de 128 bits). Esto le da a Salsa20 y ChaCha la ventaja inusual de que el usuario puede buscar de manera eficiente cualquier posición en el flujo de claves en tiempo constante. Salsa20 ofrece velocidades de alrededor de 4 a 14 ciclos por byte en software en procesadores x86 modernos [5] y un rendimiento de hardware razonable. No está patentado y Bernstein ha escrito varias implementaciones de dominio público optimizadas para arquitecturas comunes [6] .
Internamente, el cifrado utiliza la suma bit a bit ⊕ ( OR exclusivo ), la suma de 32 bits módulo 2 32 ⊞ y las operaciones de rotación de distancia constante <<< sobre un estado interno de dieciséis palabras de 32 bits. El uso exclusivo de operaciones de suma-rotación-xor evita la posibilidad de ataques de tiempo en las implementaciones de software. El estado interno está formado por dieciséis palabras de 32 bits dispuestas como una matriz de 4×4.
El estado inicial se compone de ocho palabras clave ( ), dos palabras de posición de flujo ( ), dos palabras de nonce (esencialmente bits de posición de flujo adicionales) ( ), y cuatro palabras fijas ( ):
Las palabras constantes forman la forma "expand 32-byte k" en ASCII (es decir, las 4 palabras son "expa", "nd 3", "2-by" y "te k"). Este es un ejemplo de un número que no tiene nada bajo la manga . La operación principal en Salsa20 es el cuarto de vuelta QR(a, b, c, d)que toma una entrada de cuatro palabras y produce una salida de cuatro palabras:
b ^= (a + d) <<< 7;c ^= (b + a) <<< 9;d ^= (c + b) <<< 13;a ^= (d + c) <<< 18;
Las rondas impares se aplican QR(a, b, c, d)a cada una de las cuatro columnas de la matriz 4×4, y las rondas pares se aplican a cada una de las cuatro filas. Dos rondas consecutivas (ronda de columnas y ronda de filas) se denominan ronda doble:
// Ronda imparQR( 0, 4, 8, 12) // columna 1QR(5, 9, 13, 1) // columna 2QR(10, 14, 2, 6) // columna 3QR(15, 3, 7, 11) // columna 4// Redondo uniformeQR( 0, 1, 2, 3) // fila 1QR( 5, 6, 7, 4) // fila 2QR(10, 11, 8, 9) // fila 3QR(15, 12, 13, 14) // fila 4
A continuación aparece una implementación en C/C++.
#include <stdint.h> #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b)))) #define QR(a, b, c, d)( \ b ^= ROTL(a + d, 7), \ c ^= ROTL(b + a, 9), \ d ^= ROTL(c + b,13), \ a ^= ROTL(d + c,18)) #define RONDAS 20 void salsa20_block ( uint32_t salida [ 16 ], uint32_t const en [ 16 ]) { int i ; uint32_t x [ 16 ]; para ( i = 0 ; i < 16 ; ++ i ) x [ i ] = en [ i ]; // 10 bucles × 2 rondas/bucle = 20 rondas para ( i = 0 ; i < ROUNDS ; i += 2 ) { // Ronda impar QR ( x [ 0 ], x [ 4 ], x [ 8 ], x [ 12 ]); // columna 1 QR ( x [ 5 ], x [ 9 ], x [ 13 ], x [ 1 ]); // columna 2 QR ( x [ 10 ], x [ 14 ], x [ 2 ], x [ 6 ]); // columna 3 QR ( x [ 15 ], x [ 3 ], x [ 7 ], x [ 11 ]); // columna 4 // Ronda par QR ( x [ 0 ], x [ 1 ], x [ 2 ], x [ 3 ]); // fila 1 QR ( x [ 5 ], x [ 6 ], x [ 7 ], x [ 4 ]); // fila 2 QR ( x [ 10 ], x [ 11 ], x [ 8 ], x [ 9 ]); // fila 3 QR ( x [ 15 ], x [ 12 ], x [ 13 ], x [ 14 ]); // fila 4 } for ( i = 0 ; i < 16 ; ++ i ) salida [ i ] = x [ i ] + entrada [ i ]; } En la última línea, la matriz mixta se agrega, palabra por palabra, a la matriz original para obtener su bloque de flujo de clave de 64 bytes. Esto es importante porque las rondas de mezcla por sí solas son invertibles . En otras palabras, aplicar las operaciones inversas produciría la matriz original de 4 × 4, incluida la clave. Agregar la matriz mixta a la original hace que sea imposible recuperar la entrada. (Esta misma técnica se usa ampliamente en funciones hash desde MD4 hasta SHA-2 ).
Salsa20 realiza 20 rondas de mezcla en su entrada. [1] Sin embargo, también se han introducido variantes de ronda reducida Salsa20/8 y Salsa20/12 que utilizan 8 y 12 rondas respectivamente. Estas variantes se introdujeron para complementar al Salsa20 original, no para reemplazarlo, y funcionan mejor [nota 1] en los puntos de referencia eSTREAM que Salsa20, aunque con un margen de seguridad correspondientemente menor.
En 2008, Bernstein propuso una variante de Salsa20 con nonces de 192 bits llamada XSalsa20. [7] [8] [9] XSalsa20 es demostrablemente seguro si Salsa20 es seguro, pero es más adecuado para aplicaciones donde se desean nonces más largos. XSalsa20 alimenta la clave y los primeros 128 bits del nonce en un bloque de Salsa20 (sin la adición final, que puede omitirse o restarse después de un bloque Salsa20 estándar), y utiliza 256 bits de la salida como la clave para Salsa20 estándar utilizando los últimos 64 bits del nonce y la posición del flujo. Específicamente, los 256 bits de salida utilizados son los correspondientes a las partes no secretas de la entrada: índices 0, 5, 10, 15, 6, 7, 8 y 9.
Salsa20/12 ha sido seleccionado como un diseño de Fase 3 para el Perfil 1 (software) por el proyecto eSTREAM , recibiendo la puntuación de votación ponderada más alta de todos los algoritmos del Perfil 1 al final de la Fase 2. [10] Salsa20 había sido seleccionado previamente como un diseño de Enfoque de Fase 2 para el Perfil 1 (software) y como un diseño de Fase 2 para el Perfil 2 (hardware) por el proyecto eSTREAM, [11] pero no avanzó a la Fase 3 para el Perfil 2 porque eSTREAM consideró que probablemente no era un buen candidato para entornos de hardware con recursos extremadamente limitados. [12]
El comité eSTREAM recomienda el uso de Salsa20/12, la variante de 12 rondas, por "combinar un muy buen rendimiento con un margen de seguridad cómodo". [13]
A partir de 2015 [actualizar], no hay ataques publicados sobre Salsa20/12 o el Salsa20/20 completo; el mejor ataque conocido [3] rompe 8 de las 12 o 20 rondas.
En 2005, Paul Crowley informó de un ataque a Salsa20/5 con una complejidad temporal estimada de 2 165 y ganó el premio Bernstein de 1000 dólares estadounidenses por el "criptoanálisis más interesante de Salsa20". [14] Este ataque y todos los ataques posteriores se basan en criptoanálisis diferencial truncado . En 2006, Fischer, Meier, Berbain, Biasse y Robshaw informaron de un ataque a Salsa20/6 con una complejidad temporal estimada de 2 177 y de un ataque de clave relacionada a Salsa20/7 con una complejidad temporal estimada de 2 217. [15 ]
En 2007, Tsunoo et al. anunciaron un criptoanálisis de Salsa20 que rompe 8 de 20 rondas para recuperar la clave secreta de 256 bits en 2 255 operaciones, utilizando 2 pares de flujo de claves de 11,37 . [16] Sin embargo, este ataque no parece ser competitivo con el ataque de fuerza bruta.
En 2008, Aumasson, Fischer, Khazaei, Meier y Rechberger informaron sobre un ataque criptoanalítico contra Salsa20/7 con una complejidad temporal de 2 151 , y sobre un ataque contra Salsa20/8 con una complejidad temporal estimada de 2 251 . Este ataque hace uso del nuevo concepto de bits de clave neutrales probabilísticos para la detección probabilística de un diferencial truncado. El ataque se puede adaptar para romper Salsa20/7 con una clave de 128 bits. [3]
En 2012, el ataque de Aumasson et al. fue mejorado por Shi et al. contra Salsa20/7 (clave de 128 bits) a una complejidad de tiempo de 2 109 y Salsa20/8 (clave de 256 bits) a 2 250. [ 17]
En 2013, Mouha y Preneel publicaron una prueba [18] de que 15 rondas de Salsa20 eran seguras a 128 bits contra el criptoanálisis diferencial . (En concreto, no tiene ninguna característica diferencial con una probabilidad mayor que 2 −130 , por lo que el criptoanálisis diferencial sería más difícil que el agotamiento de la clave de 128 bits).
En 2008, Bernstein publicó la familia de cifrados ChaCha , estrechamente relacionada , que tiene como objetivo aumentar la difusión por ronda y lograr el mismo rendimiento o ligeramente mejor. [19] El artículo de Aumasson et al. también ataca a ChaCha, logrando una ronda menos (para ChaCha6 de 256 bits con complejidad 2 139 , ChaCha7 con complejidad 2 248 y ChaCha6 de 128 bits dentro de 2 107 ) pero afirma que el ataque no logra romper ChaCha7 de 128 bits. [3]
Al igual que Salsa20, el estado inicial de ChaCha incluye una constante de 128 bits, una clave de 256 bits, un contador de 64 bits y un nonce de 64 bits (en la versión original; como se describe más adelante, una versión de ChaCha de RFC 7539 es ligeramente diferente), organizados como una matriz 4×4 de palabras de 32 bits. [19] Pero ChaCha reorganiza algunas de las palabras en el estado inicial:
La constante es la misma que la de Salsa20 ("expandir k a 32 bytes"). ChaCha reemplaza el cuarto de vuelta de Salsa20 QR(a, b, c, d)por:
a += b; d ^= a; d <<<= 16;c + = d; b ^ = c; b <<<= 12;a += b; d ^= a; d <<<= 8;c + = d; b ^ = c; b <<<= 7;
Tenga en cuenta que esta versión actualiza cada palabra dos veces, mientras que el cuarto de vuelta de Salsa20 actualiza cada palabra solo una vez. Además, el cuarto de vuelta de ChaCha difunde los cambios más rápidamente. En promedio, después de cambiar 1 bit de entrada, el cuarto de vuelta de Salsa20 cambiará 8 bits de salida, mientras que ChaCha cambiará 12,5 bits de salida. [4]
El cuarto de vuelta de ChaCha tiene la misma cantidad de adiciones, xors y rotaciones de bits que el cuarto de vuelta de Salsa20, pero el hecho de que dos de las rotaciones sean múltiplos de 8 permite una pequeña optimización en algunas arquitecturas, incluida x86. [20] Además, el formato de entrada se ha reorganizado para admitir una optimización de implementación de SSE eficiente descubierta para Salsa20. En lugar de alternar redondeos hacia abajo en las columnas y a lo largo de las filas, se realizan hacia abajo en las columnas y a lo largo de las diagonales. [4] : 4 Al igual que Salsa20, ChaCha organiza las dieciséis palabras de 32 bits en una matriz de 4 × 4. Si indexamos los elementos de la matriz de 0 a 15
Entonces una ronda doble en ChaCha es:
// Ronda imparQR(0, 4, 8, 12) // columna 1QR(1, 5, 9, 13) // columna 2QR(2, 6, 10, 14) // columna 3QR(3, 7, 11, 15) // columna 4// Redondo uniformeQR(0, 5, 10, 15) // diagonal 1 (diagonal principal)QR(1, 6, 11, 12) // diagonal 2QR(2, 7, 8, 13) // diagonal 3QR(3, 4, 9, 14) // diagonal 4
ChaCha20 utiliza 10 iteraciones de la ronda doble. [21] A continuación se muestra una implementación en C/C++.
#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b)))) #define QR(a, b, c, d) ( \ a += b, d ^= a, d = ROTL(d, 16), \ c += d, b ^= c, b = ROTL(b, 12), \ a += b, d ^= a, d = ROTL(d, 8), \ c += d, b ^= c, b = ROTL(b, 7)) #define RONDAS 20vacío chacha_block ( uint32_t salida [ 16 ], uint32_t const en [ 16 ]) { int i ; uint32_t x [ 16 ]; para ( i = 0 ; i < 16 ; ++ i ) x [ i ] = en [ i ]; // 10 bucles × 2 rondas/bucle = 20 rondas para ( i = 0 ; i < ROUNDS ; i += 2 ) { // Ronda impar QR ( x [ 0 ], x [ 4 ], x [ 8 ], x [ 12 ]); // columna 1 QR ( x [ 1 ], x [ 5 ], x [ 9 ], x [ 13 ]); // columna 2 QR ( x [ 2 ], x [ 6 ], x [ 10 ], x [ 14 ]); // columna 3 QR ( x [ 3 ], x [ 7 ], x [ 11 ], x [ 15 ]); // columna 4 // Ronda par QR ( x [ 0 ], x [ 5 ], x [ 10 ], x [ 15 ]); // diagonal 1 (diagonal principal) QR ( x [ 1 ], x [ 6 ], x [ 11 ], x [ 12 ]); // diagonal 2 QR ( x [ 2 ], x [ 7 ], x [ 8 ], x [ 13 ]); // diagonal 3 QR ( x [ 3 ], x [ 4 ], x [ 9 ], x [ 14 ]); // diagonal 4 } for ( i = 0 ; i < 16 ; ++ i ) salida [ i ] = x [ i ] + entrada [ i ]; } ChaCha es la base de la función hash BLAKE , finalista en la competencia de funciones hash del NIST , y sus sucesoras más rápidas BLAKE2 y BLAKE3. También define una variante que utiliza dieciséis palabras de 64 bits (1024 bits de estado), con constantes de rotación ajustadas correspondientemente.
Aunque Bernstein no lo anunció, la prueba de seguridad de XSalsa20 se extiende directamente a un cifrado XChaCha análogo . Use la clave y los primeros 128 bits del nonce (en las palabras de entrada 12 a 15) para formar un bloque de entrada ChaCha, luego realice la operación de bloque (omitiendo la adición final). Las palabras de salida 0 a 3 y 12 a 15 (las palabras que corresponden a palabras no clave de la entrada) luego forman la clave utilizada para ChaCha ordinario (con los últimos 64 bits del nonce y 64 bits del contador de bloque). [22]
Aumasson sostiene en 2020 que 8 rondas de ChaCha (ChaCha8) probablemente brindan suficiente resistencia al criptoanálisis futuro para el mismo nivel de seguridad , lo que produce una aceleración de 2,5x. [23] Un ChaCha12 de compromiso (basado en la recomendación de eSTREAM de un Salsa de 12 rondas) [24] también tiene algún uso. [25] La suite de evaluación comparativa eSTREAM incluye ChaCha8 y ChaCha12. [19]
Google había seleccionado ChaCha20 junto con el código de autenticación de mensajes Poly1305 de Bernstein en SPDY , que estaba pensado como reemplazo de TLS sobre TCP . [26] En el proceso, propusieron una nueva construcción de cifrado autenticado que combina ambos algoritmos, que se llama ChaCha20-Poly1305 . ChaCha20 y Poly1305 ahora se utilizan en el protocolo QUIC , que reemplaza a SPDY y es utilizado por HTTP/3 . [27] [28]
Poco después de que Google adoptara TLS, los algoritmos ChaCha20 y Poly1305 también se usaron para un nuevo [email protected]cifrado en OpenSSH . [29] [30] Posteriormente, esto hizo posible que OpenSSH evitara cualquier dependencia de OpenSSL , a través de una opción de tiempo de compilación. [31]
ChaCha20 también se utiliza para el arc4randomgenerador de números aleatorios en los sistemas operativos FreeBSD , [32] OpenBSD , [33] y NetBSD [34] , en lugar del RC4 roto , y en DragonFly BSD [35] para la subrutina CSPRNG del núcleo. [36] [37] A partir de la versión 4.8, el núcleo de Linux utiliza el algoritmo ChaCha20 para generar datos para el dispositivo no bloqueante /dev/urandom . [38] [39] [40] ChaCha8 se utiliza para el PRNG predeterminado en Golang . [41] El CSPRNG de Rust utiliza ChaCha12. [24]
ChaCha20 suele ofrecer un mejor rendimiento que el algoritmo Advanced Encryption Standard (AES) más frecuente en sistemas donde la CPU no cuenta con aceleración AES (como el conjunto de instrucciones AES para procesadores x86). Como resultado, a veces se prefiere ChaCha20 sobre AES en ciertos casos de uso que involucran dispositivos móviles , que en su mayoría usan CPU basadas en ARM . [42] [43] Los aceleradores de hardware especializados para ChaCha20 también son menos complejos en comparación con los aceleradores AES. [44]
ChaCha20-Poly1305 (versión IETF; ver más abajo) es el algoritmo exclusivo utilizado por el sistema VPN WireGuard , a partir de la versión 1 del protocolo. [45]
Se ha publicado una referencia de implementación para ChaCha20 en RFC 7539. La implementación de la IETF modificó el algoritmo publicado de Bernstein al cambiar el nonce de 64 bits y el contador de bloques de 64 bits a un nonce de 96 bits y un contador de bloques de 32 bits. [46] El nombre no se cambió cuando se modificó el algoritmo, ya que es criptográficamente insignificante (ambos forman lo que un criptógrafo reconocería como un nonce de 128 bits), pero el cambio de interfaz podría ser una fuente de confusión para los desarrolladores. Debido al contador de bloques reducido, la longitud máxima del mensaje que se puede cifrar de forma segura con la variante de la IETF es de 2 32 bloques de 64 bytes (256 GiB ). Para aplicaciones donde esto no es suficiente, como el cifrado de archivos o discos, RFC 7539 propone utilizar el algoritmo original con nonce de 64 bits.
El uso de ChaCha20 en IKE e IPsec se ha estandarizado en RFC 7634. La estandarización de su uso en TLS está publicada en RFC 7905.
En 2018, el RFC 7539 quedó obsoleto por el RFC 8439. El RFC 8439 incorpora algunas erratas y agrega consideraciones de seguridad adicionales. [47]
dos de estas constantes son múltiplos de 8; esto permite una rotación de 1 instrucción en CPU Intel Core2 y posteriores utilizando la
instrucción
pshufb
el algoritmo RC4 para generar números aleatorios seguros en el núcleo con Chacha20
Generador de números aleatorios basado en ChaCha para OpenBSD.
La API arc4random(3) heredada de OpenBSD se reimplementó utilizando la PRF ChaCha20, con estado por subproceso.
chacha_encrypt_bytesrandom: reemplazar el pool no bloqueante con un CRNG basado en Chacha20
Cambios con respecto al ChaCha normal. La división del número de secuencia de bloque nonce se cambió de 64:64 a 96:32 [...] El estado de ChaCha20 se inicializa de la siguiente manera: