CAST-256

CAST-256
Creador	Carlisle Adams Stafford Tavares
Creado	1998
publicado	1998
Tamaño de clave	128, 160, 192, 224 o 256 bits
Tamaño de bloque	128 bits
Número de rondas	48
Tipo de	Red Feistel

CAST-256 (o CAST6 ) en criptografía es un algoritmo de cifrado simétrico de bloques basado en la red Feistel , publicado en junio de 1998 como candidato para la competencia AES . El algoritmo fue desarrollado por especialistas de la empresa canadiense Entrust Technologies.

Información básica

Este algoritmo se basa en el algoritmo CAST-128 anterior . Ambos cifrados se basan en la metodología CAST propuesta por Carlisle Adams . Carlisle Adams) y Stafford Tavares ( ing. Stafford Tavares), cuyas dos primeras letras forman el nombre de la metodología. Hayes Howard y Michael Wiener también participaron en la creación del "diseño" del cifrado .

CAST-256 está construido con los mismos elementos que CAST-128, incluidas las cajas S, pero el tamaño del bloque se duplica a 128 bits. Esto afecta las propiedades de difusión y la seguridad del cifrado.

RFC 2612 establece que CAST-256 es de uso gratuito en todo el mundo con fines comerciales y no comerciales.

Características y estructura del algoritmo

El algoritmo cifra la información en bloques de 128 bits y utiliza varios tamaños de clave de cifrado fijos: 128, 160, 192, 224 o 256 bits.

Hay 48 rondas en el algoritmo CAST-256. Considere la primera mitad del cifrado. Un bloque de entrada de 128 bits se puede dividir en cuatro subbloques de 32 bits A en , B en , C en y D en . Se añade el subbloque Cin módulo 2 con Din modificado en función de la función de ronda f. Como resultado, obtenemos un subbloque D out . Después de desplazar los subbloques de entrada a la derecha una posición, obtenemos cuatro subbloques de salida: A out , B out , C out y D out . Para la segunda mitad del cifrado, se considera el desplazamiento de los subbloques una posición hacia la izquierda.

Las funciones no lineales S j (donde 1 < j < 4) son sustituciones de la tabla (S-box) 8x32 (como resultado, un valor de entrada de 8 bits se reemplaza por uno de 32 bits). Debido a su naturaleza no lineal, las funciones S son parte integral de la seguridad de un cifrado.

Las operaciones "b", "c" y "d" son operaciones de suma y resta que se realizan en módulos de operandos de 32 bits . La operación "a" es la superposición del subbloque de entrada de 32 bits y la subclave de 32 bits (llamada subclave de máscara). Esta operación, usando una de 3 operaciones ("b", "c" o "d"), realiza una rotación dependiendo de la subclave de 5 bits (llamada subclave de desplazamiento). Las funciones de ronda CAST-256 difieren entre rondas porque la combinación de operaciones usadas para "a", "b", "c" y "d" es diferente. $2^{32}$

Matemáticamente, una función redonda típica se ve así:

W = ((K_{m_i}+X_i) \lll K_{r_i}) ~~~(1)

Y_i = (( S_1 \left [ W_1 \right ] \oplus S_2 \left [ W_2 \right ] )+S_3 \left [ W_3 \right ]-S_4 \left [ W_4 \right ]

donde X i representa los datos de entrada de 32 bits, W j son los datos de entrada de 8 bits en la función S j , K mi y K ri representan la subclave de máscara y la subclave de desplazamiento respectivamente, Y i , son los datos de salida de 32 bits , después de la acción de la función de ronda, las operaciones “+” y “-”, representan suma y resta, respectivamente, módulo 2. La notación “ ” representa el desplazamiento a la izquierda de V con respecto a U. W, X i , Y i y K mi , todos ellos representan subbloques de 32 bits. Kri tiene una longitud de 5 bits. El descifrado se realiza por analogía con el cifrado, con la única diferencia de que las subclaves se utilizan en orden inverso. $\oplus$ $V \ ll U$

Propiedades diferenciales

Un criterio importante para un cifrado criptográfico es la no degeneración: la propiedad de que todos los bits de salida dependen de todos los bits de entrada y viceversa. La influencia de los bits de entrada sobre los bits de salida se denomina difusión. La no degeneración de la función redonda es probable, ya que toda función S no es degenerada.

Tenga en cuenta que la operación XOR no es degenerada, ya que solo un bit de cada subbloque afecta el bit de salida. Al considerar las propiedades diferenciales de CAST-256, encontramos que el subbloque de salida D out en la primera ronda depende de todos los bits de entrada del subbloque D in . Los bits de salida de los subbloques A out , B out y C out son independientes de los correspondientes bits de entrada de los subbloques A in , B in y C in .

Como resultado, obtenemos una tabla (tabla No. 1), que muestra la dependencia del cifrado de datos de salida en las rondas especificadas. Sean cuatro subbloques de entrada de 32 bits A in , B in , C in y D in correspondientes a P 1 , P 2 , P 3 y P 4 .

Tabla No. 1: Dependencia de la cifra en la ronda

Redondo
Redondo	dependencias
una	$P_{3}$ ( ) $P_{4}$
2	$P_2$ ( , ) $P_{3}$ $P_{4}$
3	$P_1$ ( , , ) $P_2$ $P_{3}$ $P_{4}$
cuatro	$P_{4}$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
5	$P_{3}$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
6	$P_2$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
7	$P_1$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$

Después de una ronda, los bits correspondientes al subbloque de texto sin formato P3 ya no degeneran en los bits de texto sin formato transformados del subbloque P4 . De manera similar, después de dos rondas, el subbloque P 2 no degenera en los bits de P 3 y P 4 transformados . Después de la ronda 4 , el subbloque correspondiente al subbloque P4 depende de todos los bits de todos los subbloques de texto. Después de la ronda 7, obtenemos la dependencia completa de los bits de salida de la entrada, ya que los cuatro subbloques P 1 , P 2 , P 3 y P 4 dependen de todos los bits del texto sin formato transformado.

Defensa contra el criptoanálisis lineal

El criptoanálisis lineal utiliza la construcción de relaciones entre el texto sin formato, el texto cifrado y la clave que son válidas con alta probabilidad en la función de recifrado circular. El principio fundamental del criptoanálisis lineal es la búsqueda de aproximaciones en la forma:

P_{i_1} \oplus P_{i_2} \oplus... \oplus P_{i_a} \oplus C_{j_1} \oplus C_{j_2} \oplus... \oplus C_{i_b} = K_{k_1} \ oplus K_{k_2} \oplus... \oplus K_{k_c} ~~~(2)

donde i 1 , i 2 ,…, i a son las posiciones de bits del texto sin formato P, j 1 , j 2 ,…, j b son las posiciones del texto cifrado C y k 1 , k 2 ,…, k c son las posiciones de la clave K. La probabilidad de proporciones para el cifrado de rondas se evalúa de la siguiente manera:

|p_L - \frac{1}{2}| \leqslant 2^{a-1}\cdot|p_B - \frac{1}{2}|~~~(3)

donde p L es la probabilidad de que se cumpla la expresión lineal (2), p B es la probabilidad de la mejor aproximación lineal de cualquier función S y a es el número de funciones S que participan en la aproximación lineal. La resistencia al criptoanálisis lineal depende estrictamente de la expresión límite de probabilidad lineal general (también denominada "intervalo lineal"). Los ataques lineales se construyen sobre la base de una expresión lineal que involucra bits de texto sin formato y texto cifrado (como se muestra en el lado izquierdo de (2)). En el lado derecho de la igualdad (2), se calcula la suma XOR de los bits clave. Esto requiere aproximadamente el siguiente número de textos sin formato:

N_L = |p_L - \frac{1}{2}|^{-2}~~~~~~~~~~~~~~~~(4)

La mejor aproximación lineal está determinada por:

|p_B - \frac{1}{2}| = \frac{2^{m-1}-NL_min}{2^{m}} ~~~(5)

donde m es el número de bits de texto de entrada y NL min es la no linealidad de la función S. Para las funciones S de CAST-256, m = 8 y NL min = 74. En cada ronda, el bit de datos de salida de la función de ronda es XOR la suma de todos los bits de los 4 subbloques de datos de entrada (cada subbloque de talla M). Por tanto, la aproximación lineal de los bits de salida debe consistir en aproximaciones lineales de los bits de todos los subbloques de entrada. En la práctica, la probabilidad de aproximaciones lineales CAST-256 es mucho mayor que 1/2.

Sea a = r para un cifrado de r rondas. Para r = 48, NL min = 74, el número de textos sin formato conocidos necesarios para el criptoanálisis lineal es de aproximadamente . Tenga en cuenta que esto es casi igual al número total de textos sin formato dados ( ) y va en contra de la practicidad de un ataque lineal a ese cifrado. $2^{122}$ $2^{128}$

Se puede obtener una estimación más precisa del número de textos sin formato para el criptoanálisis lineal del cifrado CAST considerando la unión de funciones S en la función redonda. Debido a la unión de funciones S como resultado de la operación XOR, la no linealidad de la caja S NL min (que consiste en funciones S) es superior a 74. Considere una caja S de 32x32, entonces m= 32 y a=r/4 (ya que estamos aproximando las funciones de ronda cada 4ta ronda). Por lo tanto, obtenemos la cantidad de textos sin formato necesarios para el criptoanálisis lineal de un cifrado de 48 rondas, más de (mayor que la cantidad de textos sin formato dados). La evidencia experimental sugiere que la combinación de una función S mediante operaciones como la suma o la resta en lugar de XOR puede aumentar aún más la no linealidad de la caja S. $2^{176}$

Protección contra el criptoanálisis diferencial

El criptoanálisis diferencial se basa en el estudio de la transformación de las diferencias entre valores cifrados en diferentes rondas de cifrado. Los cifrados de bloque son resistentes al criptoanálisis diferencial si hay un solo par de diferencias en cada ronda para las diferencias dadas en los textos sin formato de entrada y los textos cifrados de salida. Tales diferencias se llaman características. Como regla, las diferencias son más efectivas en el caso de considerar el XOR de dos bloques de datos. En un buen cifrado, la probabilidad de todas las diferencias debería ser , donde N es el tamaño del bloque. Para obtener una característica común en la entrada y la característica correspondiente en la salida XOR, se compila una serie de características que dependen de los datos de entrada, salida que sufrieron la operación XOR en cada ronda. $2^{{-N}}$

El análisis aquí se basa en las suposiciones de que todas las claves de ronda son independientes y que la salida XOR (el resultado obtenido después de la operación XOR de la entrada) correspondiente a una entrada XOR particular (entrada) es independiente entre rondas. Bajo tales condiciones, la característica de ronda r se representa como:

p_{w_r} = \prod_{i=1}^{r} p_i ~~~(6)

donde p i es la probabilidad de que las diferencias de salida XOR correspondan a las diferencias de entrada XOR en la ronda i .

El cifrado CAST-256 de ronda R que se muestra en la Tabla n.º 2 se basa en una enumeración de características de 4 rondas.

Tabla n.º 2: El mejor rendimiento de ronda r de un cifrado de ronda R

(0, 0, 0, ) $\Delta$	$[ingresar ~XOR~ a~ ronda ~1]$
$0\flecha izquierda\Delta$	$[la ronda 1]$
$0\flechaizquierda0$	$[la ronda 2]$
$0\flechaizquierda0$	$[ronda 3]$
$0\flechaizquierda0$	$[ronda 4]$
(0, 0, 0, ) $\Delta$	$[ingresar ~XOR~ a~ redondear~ 5]$
$0\flecha izquierda\Delta$	$[ronda 5]$
$0\flechaizquierda0$	$[ronda 6]$
$0\flechaizquierda0$	$[ronda 7]$
$0\flechaizquierda0$	$[ronda 8]$
$...$	$repetir ~ hasta ~ R/2 ~ rondas$
(0, 0, 0, ) $\Delta$	$[ingresar ~XOR~ para ~redondear~ R/2+1]$
$0\flecha izquierda\Delta$	$[ronda R/2+1]$
$0\flechaizquierda0$	$[ronda R/2+2]$
$0\flechaizquierda0$	$[ronda R/2+3]$
$0\flechaizquierda0$	$[ronda R/2+4]$
$...$	$repetir ~hasta~ hasta~ r~ rondas$

Vector XOR (0, 0, 0, ) de diferencias dadas, para 4 subbloques de entrada de 32 bits, donde los primeros 3 subbloques (A in , B in y C in ) tienen cero diferencias XOR, y el 4to subbloque de entrada (D in en ronda) tiene alguna diferencia XOR distinta de cero, . $\Delta$ $\Delta$

La tabla muestra las características del cifrado de ronda R general, la entrada XOR de la ronda R/2 + 1 es un vector en el que la diferencia de uno de los subbloques no es igual a cero, y las diferencias de los restantes tres sub-bloques son iguales a cero. El vector (0, 0, 0, ) presentado en la tabla corresponde al cifrado CAST-256 con R = 48. $\Delta$

Una diferencia de entrada XOR distinta de cero corresponde a una diferencia de salida XOR cero cada 4.ª ronda de la característica en la Tabla 2 (como se muestra en las rondas 1, 5, etc.). La probabilidad de que las diferencias de texto sin formato dadas y las diferencias de texto cifrado dadas correspondan a un solo par de diferencias, para CAST . Esto se basa en el hecho de que las cuatro funciones S en la función de ronda CAST son inyectivas y el XOR de los pares de texto sin formato y texto cifrado tienen diferencias iguales a 0. Como resultado de que la función de ronda usa una combinación de operaciones como suma y restando, la probabilidad de la existencia de un par se reducirá diferencias entre textos sin formato y textos cifrados. El mejor rendimiento de la ronda r, como se muestra en la Tabla n.º 2 y en función de las suposiciones descritas anteriormente, está determinado por la probabilidad: $p\leqslant 2^{-14}$

p_{w_r}\leqslant(2^{-14})^{r/4}~~~~(4)

En particular, para una característica de 40 rondas (que potencialmente podría usarse para atacar un cifrado de 48 rondas), la probabilidad debe ser menor o igual a . Por lo tanto, la cantidad de textos sin formato necesarios para este ataque debe ser mayor que para un cifrado de 48 rondas (sustancialmente mayor que la cantidad de textos sin formato para un tamaño de bloque de 128 bits). $2^{-140}$ $2^{140}$

Extensión clave

El procedimiento de expansión de claves es más complicado que el cifrado de datos en sí. Sea la matriz de claves k = (ABCDEFGH) un bloque de 256 bits, donde los fragmentos A, B,…,H tienen cada uno 32 bits de longitud. Sea "k ← w i (k)", donde w( ) es una función de extensión y se puede representar de la siguiente forma: $\cdot$

G = G \o más f_1(H, t_{r_0}, t_{m_0})

F = F \o más f_2(G, t_{r_1}, t_{m_1})

mi = mi \o más f_3(F, t_{r_2}, t_{m_2})

D = D \o más f_1(E, t_{r_3}, t_{m_3})

C = C \oplus f_2(D, t_{r_4}, t_{m_4})

segundo = segundo \o más f_3(C, t_{r_5}, t_{m_5})

A = A \o más f_1(B, t_{r_6}, t_{m_6})

H = H \omás f_2(A, t_{r_7}, t_{m_7})

Como resultado de 4 transformaciones de 5 bits menos significativos, se forman subclaves de desplazamiento: $k^{(i)}_r \leftarrow k$

k^{(i)}_{r_0} = 5LSB(A), k^{(i)}_{r_1} = 5LSB(C), k^{(i)}_{r_2} = 5LSB(E) , k^{(i)}_{r_3} = 5LSB(G)

donde 5LSB(x) significa la generación de los 5 bits menos significativos como resultado de la operación x. Las subclaves de enmascaramiento se forman de manera similar : $k^{(i)}_m \leftarrow k$

k^{(i)}_{m_0} = H, k^{(i)}_{m_1} = F, k^{(i)}_{m_2} = D, k^{(i)}_ {m_3} = segundo

Implementación del procedimiento de ampliación de claves

Cada ronda de la función de expansión clave utiliza 8 variables adicionales y . $T^{(i)}mj$ $T^{(i)}rj$

1. Inicialización

cm = 2^{30}\sqrt{2} = 5A827999_16

mm = 2^{30}\sqrt{3} = 6ED9EBA1_16

cr=19

Señor = 17

Sea = Tmij, = Trij. $T^{(i)}mj$ $T^{(i)}rj$

para(i=0; i<24; i++) para(j=0; j<8; j++){ Tmij = Cm cm = (cm + mm)mod2^32 Trij = Cr Cr = (Cr + Mm)mod32 }

2. Tecla de extensión:

k = ABCDEFGH = 256 bits de la clave inicial K. Sea « » « », « » « », « » « », « » « »

k\flecha izquierda w_{2_i}(k)

\sim

W2i(k)

k \leftarrow w_{2i+1}(k)

\sim

W2i+1(k)

k^{i}_r\flecha izquierda k

\sim

kr

k^{i}_m \leftarrow k

\sim

kilómetros

para(j=0; j<12; j++){ W2i(k) W2i+1(k) kr kilómetros }

Si el tamaño de clave k es inferior a 256 bits, los fragmentos de clave "extra" se consideran cero:

(|K| =128) \Flecha derecha\,(E = F = G = H = 0)

(|K| =160) \Flecha derecha\, (F = G = H = 0)

(|K| =192) \Flecha derecha\, (G = H = 0)

(|K| =224) \Flecha derecha\, (H = 0)

Ventajas y desventajas del algoritmo

Como resultado de un análisis exhaustivo en la primera etapa de la competencia AES, no solo se estudiaron las propiedades criptográficas, como la resistencia a ataques conocidos, la ausencia de claves débiles, buenas propiedades estadísticas, sino también aspectos prácticos de implementación: optimización de Se revelaron la velocidad de ejecución del código en varias arquitecturas (desde PC hasta tarjetas inteligentes e implementaciones de hardware), la posibilidad de optimizar el tamaño del código, la posibilidad de paralelización, las siguientes ventajas y desventajas del cifrado CAST-256.

Las principales ventajas son:

sin vulnerabilidades.
la capacidad de realizar rápidamente la expansión clave, es decir, durante la operación de codificación, pero no la decodificación.

Se encontraron una serie de deficiencias en el algoritmo, por lo que no ingresó a la segunda ronda de la competencia:

la velocidad de cifrado del algoritmo es baja en comparación con una serie de algoritmos: participantes en la competencia, incluidos todos los finalistas de la competencia.
Altos requisitos de memoria operativa y volátil.

Literatura

Serguéi Panasenko. Algoritmos de cifrado . - San Petersburgo: BHV-Petersburg, 2009. - P. 134-141. — 576 págs. — ISBN 978-5-9775-0319-8 . (Ruso)

Enlaces

Criptosistemas simétricos
Cifrados de flujo	A3 A5 A8 decimal F-FCSR Grano HC-256 KCipher-2 MICKEY MUGI LUCIO Félix RC4 Conejo SELLO NIEVE SOSEMANES Salsa20 STRUMOK trivium VMPC
Red Feistel	GOST 28147-89 (Magma) pez globo Camelia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFÍA Cobra ACUERDO DES DESX DFC E2 en RUPT FEAL HPC OCURRENCIA KASUMI Khafre Keops LOKI97 MacGuffin MARTE MALLA MISTY1 NuevoDES NDS RC5 RC6 SEMILLA Simón sinople listado SM4 Partícula TÉ XTEA XXTEA Raiden RTEA DES triple Dos peces
red SP	Saltamontes 3 vías A B C ARIA AES (Rijndael) Akelarre Anubis BaseRey bajo omático Cinturón CRIPTON diamante2 grand cru Hierocripta-3 Hierocripta-L1 KHAZAD Kalyna Lucifer presente Arcoíris MÁS SEGURO TIBURÓN CUADRADO Serpiente tres peces
Otro	RANA NUSH REDOC SC2000 SHACAL Cifrado CS