MAGENTA

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 27 de octubre de 2021; la verificación requiere 1 edición .

MAGENTA  es un cifrado de bloques desarrollado por Michael Jacobson y Klaus Huber para la empresa de telecomunicaciones alemana Deutsche Telekom AG . MAGENTA es la abreviatura de Algoritmo multifuncional para aplicaciones de telecomunicaciones de red y cifrado de propósito general.

Historia

El desarrollo de MAGENTA comenzó en 1990 con los principios básicos descritos en un libro inédito [1] .La idea principal era aplicar una técnica simple, sin tablas mágicas ni constantes, que pudiera realizarse tanto en hardware como en software. Los planes eran desarrollar un chip que pudiera transferir datos a velocidades de hasta 1 Gb/sy ser utilizado para el cifrado de cajeros automáticos . Desafortunadamente, la implementación del hardware no salió a la luz según lo planeado debido a la estrecha aplicación, pero a pesar de esto, la investigación ha demostrado que se puede desarrollar un chip de este tipo [2] . MAGENTA ingresó a la competencia AES en 1998 pero fue eliminada después de la primera ronda. El cifrado estuvo disponible para los participantes de la conferencia solo el día de la presentación, a diferencia de otros cifrados que participaron. Deutsche Telekom utilizó MAGENTA para el cifrado de datos internamente . Cabe señalar que antes de MAGENTA, la transformada rápida de Fourier con fines criptográficos se usaba en 2 cifrados. El nombre específico del primero no se pudo encontrar [3] , fue inventado por Jean-Pierre Wasser y registrado el 2 de junio de 1959. El segundo cifrado es una de las implementaciones del algoritmo A3  : Comp-128.

Cifrado

MAGENTA tiene una estructura de red Feistel . La función de ronda se basa en la transformada rápida de Hadamard[4] , excepto que en lugar de sumar y restar en cada etapa, se aplica la caja S dada por la función f(x) a uno de los términos , y luego se les agrega módulo 2 .

Sea el conjunto .El tamaño de bloque del  texto fuente es de 128 bits. El tamaño de la clave puede tomar 3 valores:

Sea F una función redonda. El cifrado de bloque M se calcula de la siguiente manera:

Redondo una 2 3 cuatro 5 6

clave aplicada		 k 1 k 1 K 2 K 2 k 1 k 1
Redondo una 2 3 cuatro 5 6

clave aplicada		 k 1 K 2 K 3 K 3 K 2 k 1
Redondo una 2 3 cuatro 5 6 7 ocho

clave aplicada		 k 1 K 2 K 3 K 4 K 4 K 3 K 2 k 1

Descifrado

Cabe señalar que la secuencia de partes clave utilizadas es un palíndromo. deja _ Después

[5] [6]

Entonces el descifrado

Función redonda F

El bloque de entrada X con el tamaño de 128 bits de la ronda n con la clave de ronda K n se divide en 2 partes X 1 y X 2 con el tamaño de 64 bits cada una.

X = X 1 X 2

Luego de pasar la ronda, obtenemos X ' = X 2 F(X 2 K n )

De la dependencia de la división en partes de la clave original del número de rondas: la longitud de la parte de la clave utilizada en cada ronda es siempre de 64 bits.

Por lo tanto, la función F toma un argumento de 128 bits y debe devolver un resultado de 64 bits u 8 bytes.

Introducimos funciones auxiliares en términos de las cuales expresamos F:

Función Tamaño de los argumentos aceptados Tamaño del valor devuelto Descripción
f(x) 1 byte 1 byte Devuelve el elemento con el número x en el S-box
A(x, y) 1 byte 1 byte f(x ⊕ f(y))
PE(x, y) 1 byte 2 bytes (A(x, y)A(y, x)) - concatena los resultados de A(x, y) y A(y, x)
P(X) 16 bytes 16 bytes X=X 0 X 1 ...X 14 X 15

(PE(X 0 ,X 8 )PE(X 1 ,X 9 )...PE(X 6 ,X 14 )PE(X 7 ,X 15 )) - concatena los resultados de PE(X i ,X i+ 8 ) i=0...7, X i tiene un tamaño de 1 byte.

T(X) 16 bytes 16 bytes P(P(P(P(X)))) - aplica la función P a X 4 veces.
S(X) 16 bytes 16 bytes (X 0 X 2 X 4 ... X 14 X 1 X 3 X 5 ... X 15 ) - realiza una permutación de los X bytes: primero se escriben los bytes con un número de secuencia par, luego con uno impar.
C(k, X) k∈Ν
X — 16 bytes		 16 bytes Función recursiva:
С(1,X) = T(X))
С(k,X) = T(X ⊕ S(C(k-1,X)))

Esquema de la función P(X) :

Se supone que F es igual a los primeros 8 bytes de S(C(n, (X 2 K n ))), es decir, los bytes C(n, (X 2 K n )) con un número de secuencia par. Inicialmente, n se fijó en 7, pero las pruebas han demostrado que en este caso se puede descifrar el cifrado. Por lo tanto, ponemos n = 3. Como han demostrado las pruebas, esta es la mejor opción, que no permite debilidades criptográficas que afectan a todo el cifrado. De este modo,

Se supone que F es igual a los primeros 8 bytes de S(C(3,(X 2 K n )))

Bloque S

El bloque S se forma de la siguiente manera:

El primer elemento es 1, los subsiguientes están formados por un bit shift a la izquierda del anterior, hasta que 1 va más allá del límite de bytes izquierdo. En consecuencia, el comienzo del bloque es 1 2 4 8 16 32 64 128

256 10 =1 0000 0000 2 , 1 fuera del límite de bytes. En este caso, debe agregar módulo 2 el número desplazado resultante 0000 0000 2 con el número 101 10 \u003d 0110 0101 2 :

0000 0000 2 ⊕ 0110 0101 2 \u003d 0110 0101 2 \u003d 101 10 , es decir, después de 128 habrá 101.

101 10 =0110 0101 2 << 1 = 1100 1010 2 =202 10 , 1 no está fuera del límite, por lo que el siguiente elemento es 202.
202 10 << 1= 1100 1010 2 << 1 = 1001 0100 2 , 1 está fuera de límite:

1001 0100 2 ⊕ 0110 0101 2 = 1111 0001 2 = 241 10 .

Se supone que el último elemento 256 es 0. El resultado es el siguiente S-box:

1 2 4 8 16 32 64 128 101 202 241 135 107 214 201 247 139 115 230 169 55 110 220 221 223 219 211 195 227 163 35 70 140 125 250 145 71 142 121 242 129 103 206 249 151 75 150 73 146 65 130 97 194 225 167 43 86 172 61 122 244 141 127 254 153 87 174 57 114 228 173 63 126 252 157 95 190 25 50 100 200 245 143 123 246 137 119 238 185 23 46 92 184 21 42 84 168 53 106 212 205 255 155 83 166 41 82 164 45 90 180 13 26 52 104 208 197 239 187 19 38 76 152 85 170 49 98 196 237 191 27 54 108 216 213 207 251 147 67 134 105 210 193 231 171 51 102 204 253 159 91 182 9 18 36 72 144 69 138 113 226 161 39 78 156 93 186 17 34 68 136 117 234 177 7 14 28 56 112 224 165 47 94 188 29 58 116 232 181 15 30 60 120 240 133 111 222 217 215 203 243 131 99 198 233 183 11 22 44 88 176 5 10 20 40 80 160 37 74 148 77 154 81 162 33 66 132 109 218 209 199 235 179 3 6 12 24 48 96 192 229 175 59 118 236 189 31 62 124 248 149 79 158 89 178 0

Profundizando en la teoría, podemos resumir: Sea un campo de Galois GF(2 8 ) y un polinomio que especifique este campo  — p(x)=x 8 +x 6 +x 5 +x 2 +1 y sea α un elemento primitivo del campo, p( α)=0. Entonces el elemento f(x) en el S-box con índice x se puede representar como

Propiedades de las funciones utilizadas

f(x)

Durante una ejecución de MAGENTA, la función f(x) se evalúa 2304 veces para claves de 128 y 192 bits y 3072 veces para una clave de 256 bits. Dado que la función representa la parte no lineal del algoritmo, es de particular importancia para el análisis de todo el algoritmo. Se conocen las siguientes propiedades de f(x):

  1. f(x) es una función uno a uno, es decir, una permutación sobre el conjunto B={0,1} 8  — de todos los vectores binarios de ocho bits.
  2. Esta permutación se puede representar como el resultado de 6 ciclos no relacionados de longitud 198 38 9 5 5 y 1. Según el análisis combinatorio, estos valores son "normales" y no difieren significativamente de ciclos similares para permutaciones aleatorias. El único número que queda en su lugar es 161.
  3. ∀x ∈ B y tal que f(x) ∈ {1,2,…127}:

f(x+1) = 2∙f(x), donde ∙ es el producto de números decimales. ∀(x, y)∈B 2 y tal que f(x)∙f(y)∈{1,2,…255} tenemos f((x+y) mod 255) = f(x)∙f ( y)

  1. Si consideramos f(x) como una función vectorial, es decir, f(x) = (f 7 (x), f 6 (x),…f 0 (x)), entonces cada una de las 8 funciones booleanas es no -lineal y de grado 7. También todas las posibles combinaciones XOR no triviales de estas funciones son no lineales. Una representación explícita de estas funciones se puede encontrar aquí. [7] Otra propiedad interesante es que cada función tiene 128 términos.

PE(x, y)

Criptoanálisis

Criptoanálisis diferencial

Resulta que al menos una parte de MAGENTA puede romperse con los métodos de este criptoanálisis. La adición de módulo 2 entre estos elementos se toma como la diferencia entre dos elementos (textos planos o cifrados). Esta definición de la diferencia se debe al uso frecuente de la operación xor en este cifrado. Los índices de las filas de la tabla XOR representan las diversas diferencias entre los textos sin formato y los índices de las columnas representan las diversas diferencias entre los textos cifrados. En la intersección de una diferencia de texto sin formato específica, es decir, un índice de cadena, y una diferencia de cifrado específica, es decir, un índice de columna, se encuentra el número de pares de textos sin formato que satisfacen esta diferencia, cuyas cifras difieren por un índice de columna. La tabla XOR para la función f tiene unas dimensiones de 256*256. La suma de cada fila y columna es 256. El primer elemento de la primera fila (con índice 0), que corresponde a la diferencia cero entre textos sin formato y cifrados, es 256. Todos los demás elementos de la primera fila son 0. De manera similar, todos los elementos de la columna 1, excepto el primero, igual a 256, son 0. De particular interés para el análisis diferencial son los valores grandes: el valor más grande en esta tabla es 8. Ocurre con tales diferencias

Diferencia entre
textos sin formato		 La diferencia entre
cifrados
51 35, 66, 154, 155, 250
102 111, 114, 232, 233, 244
153 96, 97, 115, 229, 247
204 18, 19, 38, 207, 251

Las celdas restantes de la tabla contienen los números 0, 2, 4, 6. La probabilidad de transición máxima para diferencias distintas de cero es . Para la función PE, también se definieron los valores máximos, es igual a 36 para una diferencia en texto sin formato (234, 234) y una diferencia cero en cifras. La máxima probabilidad de transición es ≈ . La máxima probabilidad de transición para la función T es , para C(3,X) es . Dado que el número de pares de cifrado necesarios es mayor que el recíproco de la probabilidad de transición, este tipo de análisis diferencial basado en tablas xor no es aplicable a MAGENTA. Sin embargo, la cuestión de otros tipos permanece abierta.

Criptoanálisis lineal

Se ha calculado una tabla de aproximación lineal para el S-box. [8] . Para las funciones y para cada xor-suma , como para todas las funciones lineales, se determinó cuántos dígitos de los valores de la tabla son consistentes con los dígitos correspondientes de las funciones lineales consideradas. Como resultado se obtuvieron 255 valores entre 0 y 256. La normalización consistió en restar 128. Todos los valores de la tabla estaban en el intervalo [-24;26]. Estos valores corresponden a los esperados para elegidos arbitrariamente . El valor 26 se obtiene con las siguientes combinaciones lineales:

Aplicando el lema sobre la incursión de signos a la función redonda F( , l=12)

El valor resultante es un límite superior en la mejor transformación afín para F. Se necesitan aproximadamente los pares de cifrado de texto sin formato para usar la aproximación lineal afín con probabilidad [8] . Teniendo en cuenta los resultados anteriores, para atacar F necesitas . Por lo tanto, debido a la no linealidad de f(x), MAGENTA no puede ser descifrado por ataques basados ​​en criptoanálisis lineal.

Notas

  1. ↑ K. Huber. Neue Kryptographische Verfahren durch Kombination von Operationen in endlichen Körpern mit der schnellen Walshtransformation. Manuscrito inédito, 1990.
  2. ↑ K. Huber y S. Wolter. Algoritmo MAGENTA de Telekom para cifrado/descifrado en el rango de gigabit/seg. En ICASSP 1996 Conference Proceedings, volumen 6, páginas 3233-3235, 1996.
  3. ↑ JP Vaseur. Verschluesselungsanordnung mit Mischverdrahtung. Deutsches Patentamt Auslegeschrift 1148397, Anmeldetag: 2 de junio de 1959, Auslegeschrift: 9 de mayo de 1963, Anmelder: Compagnie Generale de Telegraphie sans Fil, París.
  4. ↑ S. Y. Kung. Procesadores de matriz VLSI. Prentice Hall, 1988.
  5. ↑ M. Luby y C. Rackoff. Cómo construir permutaciones pseudoaleatorias a partir de funciones pseudoaleatorias. SIAM J. Computing, 17(2):373-386, abril de 1988.
  6. ↑ J. Pieprzyk y B. Sadeghiyan. Design of Hashing Algorithms, volumen 756 de Lecture Notes in Computer Science. Springer, 1993.
  7. ↑ SIT GmbH. Abschlussbericht - Untersuchung eines universellen Kryptoalgorithmus. Informe técnico, SIT GmbH, 1994.
  8. ↑ 1 2 E. Biham. Sobre el criptoanálisis lineal de Matsui. En Proc. EUROCRYPT '94, volumen 658 de Lecture Notes in Computer Science, páginas 81-91, 1995.

Enlaces