MARTE (criptografía)

MARTE
Creador	Carolyn Barwick, Don Calderero
Creado	1998 _
publicado	1998 _
Tamaño de clave	128-448 bits
Tamaño de bloque	128 bits
Número de rondas	32
Tipo de	Red Feistel

MARS es un cifrado candidato AES desarrollado por IBM , que creó DES en un momento . IBM dice que el algoritmo MARS se basa en los 25 años de experiencia criptoanalítica de la empresa y, junto con su alta fortaleza criptográfica, el cifrado permite una implementación eficiente incluso dentro de las limitaciones de las tarjetas inteligentes .

Don Coppersmith , uno de los autores del cifrado Lucifer ( DES ), conocido por una serie de artículos sobre criptología, participó en el desarrollo del cifrado : mejorando la estructura de las cajas S frente al criptoanálisis diferencial , el método rápido de multiplicación de matrices ( Algoritmo de Coppersmith-Winograd ), criptoanálisis RSA . Además de él, Carolyn Barwick , Edward D'Evignon , Rosario Genaro , Shai Halevi , Charanjit Jutla , Steven M. Matyas Jr. participaron en el desarrollo del algoritmo . , Luke O'Connor , Mohamed Perevyan , David Safford , Nevenko Zunich .

De acuerdo con las reglas de la competencia AES , los participantes podrían realizar cambios menores en sus algoritmos. Aprovechando esta regla, los autores de MARSa cambiaron el procedimiento de expansión de claves, lo que permitió reducir los requerimientos de no volátiles y RAM . A continuación se proporcionará una versión modificada del algoritmo.

Según los resultados de la competencia AES , MARS llegó a la final pero perdió ante Rijndael . Después del anuncio de los resultados (19 de mayo de 2000), el equipo de desarrollo formó su propia opinión sobre el concurso AES [1] , donde comentaron sobre las afirmaciones de su creación.

MARS ahora se distribuye en todo el mundo bajo una licencia libre de regalías .

Breve descripción del algoritmo

MARS es un cifrado simétrico de bloques con una clave secreta. El tamaño del bloque para el cifrado es de 128 bits, el tamaño de la clave puede variar de 128 a 448 bits inclusive (múltiplos de 32 bits). Los creadores buscaron combinar la velocidad de codificación y la fuerza del cifrado en su algoritmo. El resultado es uno de los algoritmos más potentes de la competencia AES .

El algoritmo es único en el sentido de que utilizó casi todas las tecnologías existentes utilizadas en criptoalgoritmos, a saber:

operaciones más simples ( suma , resta , exclusiva o )
sustituciones usando una tabla de sustitución
desplazamiento cíclico fijo
cambio cíclico dependiente de datos
módulo de multiplicación 2 32
blanqueamiento clave

El uso de doble barajado presenta una dificultad para el criptoanálisis , que algunos atribuyen a las desventajas del algoritmo. Al mismo tiempo, por el momento no existen ataques efectivos al algoritmo, aunque algunas claves pueden generar subclaves débiles.

Estructura del algoritmo

Los autores del cifrado partieron de las siguientes suposiciones:

Elección de operaciones . MARS fue diseñado para ser utilizado en las computadoras más avanzadas del día. Para lograr el mejor desempeño defensivo, se incluyeron en él las operaciones más "fuertes" apoyadas en ellos. Esto permitió una mayor proporción de seguridad por instrucción para diferentes implementaciones de cifrado.
La estructura de la cifra . Veinte años de experiencia en el campo de la criptografía llevaron a los creadores del algoritmo a la idea de que cada ronda de cifrado desempeña un papel para garantizar la seguridad del cifrado. En particular, podemos ver que la primera y la última ronda suelen ser muy diferentes de las rondas intermedias ("centrales") del algoritmo en términos de protección contra ataques criptoanalíticos. Así, al crear MARSa, se utilizó una estructura mixta, donde la primera y última ronda de encriptación difieren significativamente de las intermedias.
Análisis _ Lo más probable es que un algoritmo con una estructura heterogénea pueda soportar mejor los métodos criptoanalíticos del futuro que un algoritmo con todas las rondas idénticas. Los desarrolladores del algoritmo MARS le dieron una estructura muy heterogénea: las rondas del algoritmo son muy diferentes entre sí.

El cifrado MARS utilizó los siguientes métodos de cifrado:

Trabajar con palabras de 32 bits . Todas las operaciones se aplican a palabras de 32 bits. es decir, toda la información original se divide en bloques de 32 bits. (si el bloque resultó ser más corto, entonces se amplió a 32 bits)
Red Feistel . Los creadores del cifrado creían que esta era la mejor combinación de velocidad de cifrado y fuerza criptográfica. MARS utiliza una red Feistel Tipo 3.
Simetría del algoritmo . Para la resistencia del cifrado a varios ataques, todas sus rondas se hicieron completamente simétricas , es decir, la segunda parte de la ronda es una repetición especular de su primera parte.

La estructura del algoritmo MARS se puede describir de la siguiente manera:

Clave previa: los subbloques A, B, C, D de 32 bits se superponen con 4 fragmentos de la clave extendida k 0 ...k 3 por módulo 2 32 ;
Se realizan 8 rondas de mezcla directa (sin la participación de la clave de cifrado);
Se realizan 8 rondas de criptoconversión directa;
Se realizan 8 rondas de transformación criptográfica inversa; [2]
Se realizan 8 rondas de retromezclado, también sin la participación de la clave de cifrado;
La superposición final de fragmentos de la clave extendida k 36 ...k 39 por la operación de resta módulo 2 32 .

Mezcla directa

En la primera fase, cada palabra de datos se superpone con una palabra clave y luego hay ocho rondas de mezcla según la red de Feistel del tercer tipo, junto con una mezcla adicional. En cada ronda, usamos una palabra de datos (llamada palabra fuente) para modificar otras tres palabras (llamadas palabras objetivo). Tratamos los cuatro bytes de la palabra original como índices en dos S-boxes, S 0 y S 1 , cada uno de los cuales consta de 256 palabras de 32 bits, y luego XOR o agregamos los datos de S-box correspondientes en otras tres palabras.

Si los cuatro bytes de la palabra original son b 0 , b 1 , b 2 , b 3 (donde b 0 es el primer byte y b 3 es el byte alto), entonces usamos b 0 , b 2 como índices en el bloque S 0 y bytes b 1 , b 3 , como índices en el S-box S 1 . Primero XOR S 0 a la primera palabra objetivo y luego agregue S 1 a la misma palabra. También agregamos S 0 a la segunda palabra objetivo y bloqueamos XOR-S 1 a la tercera palabra objetivo. Finalmente, rotamos la palabra original 24 bits a la derecha.

En la siguiente ronda, rotamos las cuatro palabras que tenemos: la primera palabra objetivo actual se convierte en la siguiente palabra fuente, la segunda palabra objetivo actual se convierte en la nueva primera palabra objetivo, la tercera palabra objetivo se convierte en la segunda palabra objetivo siguiente y la la palabra de origen actual se convierte en la tercera palabra de destino.

Además, después de cada una de las cuatro rondas, agregamos una de las palabras objetivo a la palabra original. Específicamente, después de las rondas primera y quinta, agregamos la tercera palabra objetivo nuevamente a la palabra original, y después de las rondas segunda y sexta, agregamos la primera palabra objetivo nuevamente a la palabra original. El motivo de estas operaciones de mezcla adicionales es eliminar algunos criptoataques diferenciales simples en la fase de mezcla para romper la simetría en la fase de mezcla y obtener un flujo rápido.

Pseudocódigo 1. // Primera superposición de una clave en los datos 2. 3.

para ~i ~= ~0 ~a ~3 ~do

D \izquierda [ yo \derecha ] = D[i] + K[i]

4. // Luego 8 rondas de mezcla directa 5. // usa D[0] para modificar D[1]; D[2]; D[3]

para ~i = ~0 ~a ~7 ~do

6. // accede a 4 cajas S 7.8.9.10 ._ _ _

D \left [1 \right] = D[1] \oplus S0[ ~byte bajo ~de ~D[0] ]

D \left [ 1 \right ] = D[1] + S1[ ~2do ~byte ~de ~D[0] ]

D \left [ 2 \right ] = D[2] + S0[ ~3er ~byte ~de ~D[0] ]

D[3] = D[3] \oplus S1[ ~alto ~byte ~de ~D[0] ]

11. // y gira la palabra original a la derecha 12

D[0] = D[0]\ggg 24

13. // también hacer operaciones de mezcla adicionales 14. 15. // añade D[3] a la palabra original

si ~i ~= ~0 ~o ~4 ~entonces

D \izquierda [ 0 \right ] = D[0] + D[3]

16. 17. // añade D[1] a la palabra original

si ~i ~= ~1 ~o ~5 ~entonces

D \izquierda [0 \derecha] = D[0] + D[1]

18. // gira la matriz D[ ] 19.20 .

(D[3]; D[2]; D[1]; D[0]) \leftarrow (D[0]; D[3]; D[2]; D[1])

{\ Displaystyle final para}

Núcleo criptográfico

El núcleo criptográfico de MARS es una red Feistel de tipo 3 que contiene 16 rondas. En cada ronda, usamos la función clave E, que es una combinación de multiplicaciones, rotaciones y llamadas de S-box. La función toma como entrada una palabra de datos, y devuelve tres palabras, con lo que posteriormente se realizará la operación de suma o XOR a otras tres palabras de datos. Además, la palabra fuente se gira 13 bits a la izquierda.

Para proporcionar una resistencia seria a los criptoataques, los tres valores de salida de la función E (O 1 , O 2 , O 3 ) se utilizan en las primeras ocho rondas y en las últimas ocho rondas en diferentes órdenes. En las primeras ocho rondas, agregamos O 1 y O 2 a la primera y segunda palabra objetivo, respectivamente, y XOR O 3 a la tercera palabra objetivo. Para las últimas ocho rondas, agregamos O 1 y O 2 a la tercera y segunda palabra objetivo, respectivamente, y XOR O 3 a la primera palabra objetivo.

Pseudocódigo 1. // Haz 16 rondas de encriptación usando la clave 2. 3. 4. 5. 6. // primeras 8 rondas de conversión directa

para ~i ~= ~0 ~a ~15 ~do

(out1; ~out2; ~out3) ~= ~E-función(D[0]; ~K[2i + 4]; ~K[2i + 5])

D[0] = D[0]\lll 13

D[2] = D \izquierda [ 2 \derecha ] + fuera2

si ~i ~< ~8 ~entonces

7. 8. 9. // luego 8 rondas de transformación inversa

D[1] = D \izquierda [ 1 \derecha ] + salida1

D[3] = D[3] \omás salida3

{\ estilo de visualización más}

10. 11. 12.

D[3] = D \izquierda [ 3 \derecha ] + salida1

D[1] = D[1] \omás salida3

{\ Displaystyle final si}

13. // gira la matriz D[ ] 14. 15.

(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[0]; ~D[3]; ~D[2]; ~D[1])

{\ Displaystyle final para}

E-función

La función E toma una palabra de datos como entrada y usa dos palabras clave más, produciendo tres palabras como salida. En esta función, usamos tres variables temporales, denominadas L, M y R (para izquierda, centro y derecha).

Inicialmente, establecemos R en el valor de la palabra original desplazada 13 bits a la izquierda y establecemos M en la suma de las palabras originales y la primera palabra clave. Luego usamos los primeros nueve bits de M como índice de una de las 512 cajas S (que se obtiene combinando S 0 y S 1 mediante mezcla de fases) y almacenamos en L el valor de la caja S correspondiente.

Luego multiplicamos la segunda palabra clave por R, almacenando el valor en R. Luego rotamos R 5 posiciones a la izquierda (de modo que los 5 bits altos se conviertan en los 5 bits bajos de R después de la rotación). Luego usamos XOR R en L, y también observamos los cinco bits inferiores de R para determinar la cantidad de cambio (de 0 a 31), y giramos M hacia la izquierda en esa cantidad. Luego, rotamos R otras 5 posiciones hacia la izquierda y XOR L en L. Finalmente, nuevamente observamos los 5 bits menos significativos de R como la cantidad de rotación y rotamos L esa cantidad hacia la izquierda. Así, el resultado de la función E son 3 palabras (en orden): L, M, R.

Pseudocódigo 1. // usa 3 variables temporales L; METRO; R 2. //añadir la primera palabra clave

M = ~entrada + ~tecla1

3. // multiplicar por la segunda palabra clave, que debe ser par

R = (en \lll 13) \otimes key2

4. 5. // tomar S-caja

i = ~más bajos ~9 ~bits ~de ~M

L = S \izquierda [ yo \derecha ]

6. 7. // estos bits describen la cantidad de rotación posterior

R = R\lll 5

r = ~5 bits más bajos ~de ~R

8. // primera rotación por variable

METRO = METRO

9. 10. 11. 12. // estos bits describen la cantidad de rotación posterior

L = L \o más R

R = R\lll 5

L = L \o más R

r = ~5 bits más bajos ~de ~R

13. // segunda rotación variable

L = L \lll r

catorce.

salida (L; ~M; ~R)

Mezcla inversa

La reproducción aleatoria hacia atrás es casi lo mismo que la reproducción aleatoria hacia adelante, excepto por el hecho de que los datos se procesan en orden inverso. Es decir, si combinamos la mezcla directa e inversa para que sus salidas y entradas se conecten en orden inverso (D[0] adelante y D[3] atrás, D[1] adelante y D[2] atrás), entonces no vería el resultado de la mezcla. Al igual que en la mezcla directa, aquí también usamos una palabra de origen y tres palabras de destino. Considere los primeros cuatro bytes de la palabra original: b 0 , b 1 , b 2 , b 3 . Usaremos b 0 , b 2 como índice de la caja S - S 1 y b 1 b 3 para S 0 . Hagamos XOR S 1 [b 0 ] en la primera palabra objetivo, restemos S 0 [b 3 ] de la segunda palabra, restemos S 1 [b 2 ] de la tercera palabra objetivo y luego XOR S 0 [b 1 ] también para la tercera palabra objetivo. Finalmente, rotamos la palabra original 24 lugares a la izquierda. Para la siguiente ronda, rotamos las palabras disponibles para que la primera palabra objetivo actual se convierta en la siguiente palabra fuente, la segunda palabra objetivo actual se convierta en la primera palabra objetivo, la tercera palabra objetivo actual se convierta en la segunda palabra objetivo y la palabra fuente actual se convierte en la tercera palabra objetivo. Además, antes de una de las cuatro rondas "especiales", restamos una de las palabras objetivo de la palabra fuente: antes de la cuarta y octava ronda, restamos la primera palabra objetivo; antes de la tercera y séptima ronda, restamos la tercera palabra objetivo de la palabra fuente.

Pseudocódigo 1. // Haz 8 rondas de retromezclado 2.

para ~i ~= ~0 ~to ~7 ~do

3. // operaciones de mezcla adicionales 4. 5. //restar D[3] de la palabra original

si ~i ~= ~2 ~o ~6 ~entonces

D[0] = D[0] - ~D[3]

6. 7. // restamos D[1] de la palabra original

si ~i ~= ~3 ~o ~7 ~entonces

D[0] = D[0] - ~D[1]

8. // se refieren a los cuatro elementos de S-boxes 9. 10. 11. 12.

D[1] = D[1] \oplus S1[ ~byte bajo ~de ~D[0] ]

D[2] = D[2] - ~S0[ ~alto ~byte ~de ~D[0] ]

D[3] = D[3] \oplus S1[ ~3er ~byte ~de ~D[0] ]

D[3] = D[3] - ~S0[ ~2do ~byte ~de ~D[0] ]

13. // y gira la palabra original a la izquierda catorce.

D[0] = D[0]\lll 24

15. // gira la matriz D[] 16. 17.

(D[3]; D[2]; D[1]; D[0]) \leftarrow (D[0]; D[3]; D[2]; D[1])

{\ Displaystyle final para}

18. // Resta la palabra clave 19.20 .

para ~i ~= ~0 ~a ~3 ~do

D[i] = D[i] - ~K[36 + i]

Descifrado

El proceso de decodificación es el inverso del proceso de codificación. El código de descifrado es similar (pero no idéntico) al código de cifrado.

Mezcla directa 1. // Superposición de clave inicial 2. 3.

para ~i ~= ~0 ~a ~3 ~do

D\izquierda [ yo \derecha ] = D[i] + K[36 + i]

4. // Luego haz 8 rondas de mezcla directa 5.

para ~i ~= ~7 ~abajo ~a ~0 ~do

6. // gira la matriz D[] 7.

(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])

8. // y gira la palabra original a la derecha 9.

D[0] = D[0]\ggg 24

10. // accede a 4 elementos de S-boxes 11. 12. 13. 14.

D[3] = D[3] \oplus S0[ ~2do ~byte ~de ~D[0] ]

D[3] = D[3] + S1[ ~3er ~byte ~de ~D[0] ]

D[2] = D[2] + S0[ ~alto ~byte ~de ~D[0] ]

D[1] = D[1] \oplus S1[ ~byte bajo ~de ~D[0] ]

15. // mezcla adicional 16. 17. // añade D[3] a la palabra original

si ~i ~= ~2 ~o ~6 ~entonces

D[0] = D\izquierda [ 0 \derecha ] + D[3]

18. 29. // añade D[1] a la palabra original

si ~i ~= ~3 ~o ~7 ~entonces

D[0] = D\izquierda [ 0 \derecha ] + D[1]

veinte.

{\ Displaystyle final para}

Núcleo criptográfico 1. // Ejecuta 16 rondas usando la tecla de superposición 2.

para ~i ~= ~15 ~hasta ~0 ~do

3. // gira la matriz D[] 4. 5. 6. 7. 8. // últimas 8 rondas en orden directo

(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])

D[0] = D[0] \ggg 13

(salida1; ~salida2; ~salida3) = función E(D[0]; ~K[2i + 4]; ~K[2i + 5])

D[2] = D \izquierda [ 2 \derecha ] - fuera2

si ~i ~< ~8 ~entonces

9. 10. 11. // primeras 8 rondas en orden inverso

D[1] = D\izquierda [ 1 \derecha ] - salida1

D[3] = D[3] \omás salida3

{\ estilo de visualización más}

12. 13. 14. 15.

D[3] = D\izquierda [ 3 \derecha ] - salida1

D[1] = D[1] \omás salida3

{\ Displaystyle final si}

{\ Displaystyle final para}

Mezcla inversa 1. // Haz 8 rondas de retromezclado 2.

para ~i ~= ~7 ~abajo ~a ~0 ~do

3. // Rota la matriz D[] cuatro

(D[3]; ~D[2]; ~D[1]; ~D[0]) \leftarrow (D[2]; ~D[1]; ~D[0]; ~D[3])

5. // operaciones de mezcla adicionales 6. 7. // restamos D[3] de la palabra original

si ~i ~= ~0 ~o ~4 ~entonces

D[0] = D\izquierda [ 0\derecha ] - D[3]

8. 9. // restamos D[1] de la palabra original

si ~i ~= ~1 ~o ~5 ~entonces

D[0] = D\izquierda [ 0 \derecha] - D[1]

10. // Gira la palabra original a la izquierda once.

D[0] = D[0]\lll 24

12. // se refieren a los cuatro elementos de S-boxes 13. 14. 15. 16. 17.

D[3] = D[3] \oplus S1[ ~alto ~byte ~de ~D[0] ]

D[2] = D[2] - S0[ ~3er ~byte ~de ~D[0] ]

D[1] = D[1] - S1[ ~2do ~byte ~de ~D[0] ]

D[1] = D[1] \oplus S0[ ~byte bajo ~de ~D[0] ]

{\ Displaystyle final para}

18. // resta una subclave de los datos 19.20 .

para ~i ~= ~0 ~a ~3 ~do

D[i] = D\izquierda [i\derecha] - K[i]

Características del algoritmo

Bloques S

Al crear un S-box S, sus elementos fueron generados por un generador pseudoaleatorio, después de lo cual se probaron varias propiedades lineales y diferenciales. Se generaron S-boxes pseudoaleatorios con los siguientes parámetros:

$yo = 0\ldots102; j = 0\ldots4, S[5i+j] = \mathrm{SHA-1}(5i \vert c1 \vert c2 \vert c3)$

(dónde está la j-ésima palabra en la salida SHA-1 ) Aquí se considera que i es un entero sin signo de 32 bits, y c1, c2, c3 son algunas constantes. En la implementación de IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (que son la notación binaria de la parte fraccionaria de y respectivamente). c3 se cambió hasta que se encontraron cajas S con propiedades adecuadas. SHA-1 funciona en flujos de datos y usa little endian. $SHA-1(j)$ $mi$ $\Pi$

Propiedades de S-box

Propiedades diferenciales .

S-box no debe contener palabras que contengan solo 0 o 1
Cada dos S-boxes S 0 , S 1 deben diferir entre sí en al menos 3 de 4 bytes (dado que esta condición es extremadamente improbable para S-boxes pseudoaleatorios, uno de los dos S-boxes se modifica)
Un S-box no contiene dos elementos tales que o $S[i], S[j](i \neq j)$ $S\left[i\right] = S\left[j\right]; S \izquierda [ yo \derecha ] = -S \izquierda [ j \derecha ]$ $S\izquierda [i\derecha] = -S\izquierda [j\derecha]$
La caja S no contiene dos pares de elementos cuyas diferencias xor sean iguales y dos pares de elementos cuya diferencia ordenada sea igual a
Cada dos elementos del S-box deben diferir en al menos 4 bits

El requisito #4 no se cumplió en la implementación de IBM para AES, pero se corrigió inmediatamente después de la final. Se ha observado que los siguientes elementos están presentes en las cajas S, en contra de este requisito [3] :

XOR	Sustracción
$S[27] \oplus S[101] = S[292] \oplus S[360] = 0x117f1a43$	$S \izquierda [ 13 \derecha ] - S[138] = S[364]-S[297] = 0x75082c89$
$S[27] \oplus S[292] = S[101] \oplus S[360] = 0x2b05b22a$	$S \izquierda [ 19 \derecha ] -S[168] = S[509] -S[335] = 0x0b7fc4bd$
$S[27] \oplus S[360] = S[101] \oplus S[292] = 0x3a7aa869$	$S \izquierda [49 \derecha] -S[97] = S[142]-S[392] = 0x725ca4be$
	$S \izquierda [ 131 \derecha ] -S[333] = S[348]-S[211]= 0xc73689fe$
	$S \izquierda [ 13 \derecha ] -S[364] = S[138] -S[297] = 0x86dedc7c$
	$S \izquierda [ 131 \derecha ] -S[348] = S[333]-S[211]= 0x22492124$
	$S \izquierda [ 19 \derecha ] -S[509] = S[168] -S[335] = 0x9ce0ed93$
	$S \izquierda [49 \derecha] -S[142] = S[97] -S[392] = 0x5d91f03a$

Propiedades lineales

Relación de compensación: . Es necesario que esta expresión sea mayor que al menos $\izquierda | Pr_x[paridad(S[x]) = 0] - 1/2 \right |$ $1/32$
Compensación de un bit: esta expresión debe ser mayor que al menos $\forall j \left | Pr_x[S[x]_j = 0] - 1/2 \right |$ $1/30$
Compensación de dos bits: . Es necesario que esta expresión sea mayor que al menos $\forall j \left | Pr_x[S[x]_j \oplus S[x]_{j+1} = 0] - 1/2 \right |$ $1/30$
Correlación de un bit : . Es necesario minimizar esta expresión entre todas las S-boxes posibles que satisfagan los puntos anteriores $\forall i,j \left | Pr_x [S[x]_j = x_i] - 1/2 \right |$

Extensión clave

el procedimiento de expansión de claves expande la matriz dada de claves k[], que consta de n palabras de 32 bits (donde n es un número entero de 4 a 14) en una matriz K[] de 40 elementos. La clave original no tiene que seguir ninguna estructura. Además, el procedimiento de expansión de clave garantiza las siguientes propiedades de la palabra clave utilizada en la multiplicación en el núcleo criptográfico del algoritmo:

los dos bits menos significativos de la palabra clave siempre serán unos
ninguna de las palabras clave contendrá diez ceros o unos consecutivos

Describamos el algoritmo de expansión clave.

Primero, la matriz se reescribe completamente en una matriz intermedia que consta de 15 elementos. $k[]$ $T[]$ $T[0 \ldots n-1] = k[0 \ldots n-1]; T[n] = n; T[n + 1 \ldots 14] = 0$
Luego se repite este proceso 4 veces. En cada iteración, se generan 10 palabras clave extendidas. variable que muestra el número de iteración actual (0 para la primera iteración, 1 para la segunda, etc.) $j$
1. La matriz T[] se convierte de acuerdo con la siguiente regla: $i = 0 \ldots 14, T[i] = T[i] \oplus ((T[i - 7 \mod 15] \oplus T[i - 2 \mod 15]) \lll 3) \oplus (4i + j)$
2. A continuación, barajamos la matriz usando 4 rondas de la Red Feistel Tipo 1. Repetimos la siguiente operación cuatro veces: $T[]$ $T[i] = (T[i] + S[bajo ~9 ~bits ~de ~T[i - 1 \mod 15]]) \lll 9; i = 0.1\ldots14$
3. A continuación, tomamos diez palabras de la matriz T[] y las insertamos como las próximas diez palabras en la matriz K[], mezclando nuevamente: $K[10j + i] = T[4i \mod 15]; i = 0.1\ldots9$
Finalmente, repasamos las dieciséis palabras utilizadas para la multiplicación (K[5],K[7]…K[35]) y las modificamos para que coincidan con las dos propiedades descritas anteriormente.
1. Escribimos los dos bits menos significativos de K[i], según la fórmula , y luego escribimos en lugar de estos dos bits uno, . $j = K[i]\tierra 3$ $w = K[i]\lor 3$
2. Recogemos una máscara M para los bits w que pertenecen a secuencias de diez o más ceros o unos. Por ejemplo, si y solo si pertenece a una secuencia de 10 o más elementos idénticos. Luego restablecemos (los ponemos a 0) los valores de aquellos M que están al final de las secuencias cero o uno, así como los que están en los bits altos y bajos. Por ejemplo, que nuestra palabra se vea así: (la expresión o significa que 0 o 1 se repetirán en la palabra i veces). Entonces la máscara M quedará así: . Entonces reseteamos los bits en 4, 15, 16, 28 posiciones, es decir $M_l=1$ $w_l$ $w = 0^{3}1^{13}0^{12}1011$ $0^yo$ $1^yo$ $0^{3}1^{25}0^{4}$ $M = 0^{4}1^{11}001^{10}0^{5}$
3. Además, para la corrección, usamos una tabla de cuatro palabras B[]. Todos los elementos de la tabla B se seleccionan de tal forma que para ellos y para todos sus turnos cíclicos se cumpla la propiedad de que no tengan siete 0 o 1 consecutivos. En la implementación de IBM se utilizó la tabla . Luego, los dos bits escritos j se usan para seleccionar una palabra de la tabla B, y los cinco bits menos significativos de la palabra K[i-1] se usan para rotar sus elementos, $B[] = \izquierda \{ 0xa4a8d57b,0x5b5d193b, 0xc8a8309b, 0x73f9a978 \derecha \}$ $p = B[j] \lll (más bajos ~5 ~bits ~de ~K[i-1]).$
4. Finalmente, el patrón p es XORed a la palabra original, teniendo en cuenta la máscara M: . Vale la pena señalar que los 2 bits menos significativos de M son 0, entonces los dos bits menos significativos de la palabra final serán unos, y el uso de la tabla B permite garantizar que no habrá 10 0 o 1 consecutivos en el palabra $K[i] = w \oplus (p \land M)$

Ventajas y desventajas del algoritmo

El cifrado era candidato a AES , luego de algunos cambios menores durante la primera ronda de la competencia, relacionados con un cambio en el procedimiento de expansión clave, MARS pasó con éxito a la final.

En la final de la competencia, MARS tuvo una serie de deficiencias:

Estructura compleja . La compleja estructura heterogénea del algoritmo dificultó no solo su análisis, sino también su implementación.
Implementación . Hubo problemas al implementar el cifrado en plataformas que no admitían operaciones de rotación y multiplicación de 32 bits por un número arbitrario de bits.
Recursos limitados . La imposibilidad de implementar el algoritmo en hardware con pocos recursos de memoria operativa o no volátil .
protección _ MARS demostró estar mal protegido contra ataques de tiempo de ejecución y consumo de energía.
Extensión de clave . MARS fue peor que los otros finalistas de AES a la hora de respaldar la expansión clave sobre la marcha.
Paralelización . Es posible paralelizar solo una pequeña parte del algoritmo.

A pesar de todas estas deficiencias, la comisión de expertos destacó una de las principales ventajas de este algoritmo: su simetría. Según las deficiencias identificadas, MARS, como se esperaba, no se convirtió en el ganador de AES.

Respuesta a los analistas de AES

Después del anuncio de los resultados de la competencia AES, el equipo de MARS publicó su revisión de toda la competencia. Cuestionó los criterios de evaluación de la competencia. Creían que la principal característica del cifrado debía ser precisamente la fiabilidad y su resistencia (por ejemplo, a los ataques de fuerza bruta) y respondían a todas las afirmaciones del jurado sobre su algoritmo.

1. MARS no es adecuado para la implementación de hardware Entre las quejas sobre el cifrado se encuentran su difícil implementación de hardware, lo que podría generar la carga de Internet, así como la introducción de esquemas de gran tamaño.

Los desarrolladores afirman que su implementación es capaz de operar a una velocidad de 1,28 Gbps, lo cual es aceptable para Internet, y el costo de sus chips puede ser alto ($13 por un chip de 12 Gbps o $1 por uno de 1 Gbps), pero en su el precio caerá significativamente en el futuro.

2. MARS no es adecuado para la implementación en dispositivos con poca memoria Para la implementación en tarjetas SMART, los algoritmos tienen solo 128 bytes de memoria. Para el procedimiento de expansión de claves, MARS requiere 512 bytes.

Los desarrolladores creen que no hay razón para implementar AES en un recurso de memoria baja tan vulnerable como las tarjetas inteligentes, ya que todos estos recursos se pueden convertir fácil y rápidamente en sistemas de clave pública.

3. MARS no es adecuado para la implementación en FPGA MARS no es adecuado para la implementación en plataformas donde no se permite la rotación (dependiendo de factores externos).

Los desarrolladores señalan que este problema no es fatal, pero lleva un poco de tiempo adaptar el algoritmo a esta plataforma.

4. La expansión de la llave MARS es una operación muy pesada

Los desarrolladores afirman que esta es una declaración ridícula. Afirman tener la proporción "ideal" entre memoria adicional por clave y rendimiento (25 bytes por clave)

En conclusión, los desarrolladores dan su análisis de los algoritmos de los participantes de AES, según los resultados de los cuales MARS, junto con Serpent , fue el mejor candidato para el título de AES. [una]

Análisis de seguridad de algoritmos

Actualmente no hay ataques efectivos a este algoritmo. Aunque tiene varias debilidades [1] :

Las subclaves con una gran cantidad de ceros o unos repetidos pueden dar lugar a ataques efectivos contra MARS, ya que se generarán subclaves débiles en función de ellas.
Los dos bits menos significativos usados en la multiplicación son siempre 1. Por lo tanto, siempre hay dos bits de entrada que no cambian durante el proceso de multiplicación de claves, así como dos bits de salida que son independientes de la clave.

Literatura

Panasenko S. P. Algoritmos de cifrado. Libro de referencia especial - San Petersburgo. : BHV-SPb , 2009. - S. 65-68, 219-228. — 576 pág. — ISBN 978-5-9775-0319-8

Notas

↑ 1 2 3 Investigación criptográfica . Consultado el 13 de noviembre de 2011. Archivado desde el original el 16 de mayo de 2006. (indefinido)
↑ Las etapas 3 y 4 se llaman el "núcleo criptográfico" del algoritmo MARS
↑ Investigación de criptografía . Consultado el 14 de noviembre de 2011. Archivado desde el original el 23 de mayo de 2009. (indefinido)

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