MAC de dos pistas

Two-Track-MAC es un código de autenticación de mensajes diseñado para verificar la autenticidad e integridad de los datos transmitidos. En otras palabras, podemos asegurarnos de que los datos se transfirieron desde la fuente correcta y que su contenido no cambió durante la transferencia.

Propósito principal : Evitar que los mensajes sean modificados por un tercero durante la transmisión. Ejemplos de mensajes son los pagos bancarios electrónicos o los sistemas de control automatizado para objetos en movimiento.

Desarrolladores : Bart van Rompay , Bert den Boer .

Historial de creación

El algoritmo Two-Track-MAC fue elegido para el proyecto NESSIE (Nuevos Algoritmos Europeos de Firma Electrónica) en noviembre de 2000 y fue concebido como un análogo más rápido y confiable de los algoritmos MAC disponibles en ese momento. Bart van Rompay de la Universidad de Lovaina (Katholieke Universiteit Leuven) - Bélgica y Bert den Boer de debis AG (Alemania) participaron en el desarrollo .

Descripción

Two-Track-MAC se basa en la función hash RIPEMD-160 . La peculiaridad radica en el cifrado del mensaje a lo largo de dos caminos independientes (indicados como L y R en la figura ). Este enfoque le permite aumentar el tamaño del estado interno. Como resultado, obtenemos más valores posibles de la función de encriptación interna. Esto hace posible complicar los ataques basados en la enumeración de todos los valores posibles.

En comparación con MDx-MAC, que también se basa en RIPEMD-160, Two-Track-MAC es mucho más eficiente para mensajes cortos (512 o 1024 bits) y también más eficiente para mensajes largos.

Otra ventaja importante de TTMAC es la capacidad de cambiar rápidamente la clave de cifrado. Esto le permite aumentar la estabilidad del sistema, sin reducir la velocidad. Con un cambio de clave bastante frecuente, un atacante no podrá recopilar una gran cantidad de pares de código de mensaje-MAC, lo que reduce en gran medida la probabilidad de adivinar la clave o el código MAC.

Cómo funciona

Como ya se señaló, Two-Track-MAC tiene dos bloques de transformación paralelos L(K,M) y R(K,M) , que aceptan el mensaje M y la clave K como entrada . Como resultado, cada uno de los bloques funciona de forma independiente y crea dos representaciones diferentes ( A y B en la figura) de los mismos datos.

Suponga primero que el tamaño del mensaje M es de 512 bits. El tamaño de clave K siempre es fijo y es de 160 bits. Para complicar las transformaciones , L(K,M) genera cinco palabras de 32 bits ( ) ${\ estilo de visualización A_{0},A_{1},A_{2},A_{3},A_{4))$ . Es decir, divide formalmente la versión aún preliminar de la clave en 5 partes del mismo tamaño. De manera similar, el conjunto ( ) ${\ estilo de visualización B_{0},B_{1},B_{2},B_{3},B_{4}}$ da la salida de la función R(K,M) . Luego estas palabras se restan módulo . Este es un tipo de mezcla de dos valores para llevar a una longitud fija de 160 bits. Resultado final: ) , donde . En realidad, esto es para lo que se hizo todo. E es el código de autenticación de mensajes M . $2^{{32}}$ ${\ estilo de visualización E=~~(E_{0},E_{1},E_{2},E_{3},E_{4))$ $E_{i}=A_{i}-B_{i}~~mod~~2^{32},~~i=0,1,2,3,4$

Si el mensaje supera los 512 bits, entonces M se divide en bloques , donde tiene una longitud de 512 bits. Como resultado del proceso, realizamos las mismas operaciones en cada bloque, mezclándolos uno por uno. Un mensaje con una longitud no múltiplo de 512 se rellena con ceros y unos hasta el tamaño que necesitamos. ${\displaystyle M=M_{1}M_{2}M_{3}...M_{n))$ $Mi}$

Más sobre la mezcla de resultados L y R

Después de que cada rama del algoritmo procese el siguiente bloque del mensaje, los resultados deben transformarse de alguna manera para que la salida tenga una longitud de clave fija. Consideremos este proceso con más detalle.

Introduzcamos la notación: $A=(A_{0},A_{1},A_{2},A_{3},A_{4})=L^{(}K,M_{1})$

$B=(B_{0},B_{1},B_{2},B_{3},B_{4})=R^{(}K,M_{1})$

A continuación, creamos dos bloques de 160 bits y . Estos bloques se llenan con varias combinaciones con la salida de las funciones L y R. A saber: $C=(C_{0},C_{1},C_{2},C_{3},C_{4})$ $D=(D_{0},D_{1},D_{2},D_{3},D_{4})$

${\displaystyle C_{2}=A_{3}-B_{0))$ ,

${\displaystyle C_{3}=A_{4}-B_{1))$ ,

$C_{0}=(A_{1}+A_{4})-B_{3}$ ,

${\displaystyle C_{1}=A_{2}-B_{4))$ ,

${\displaystyle D_{1}=(A_{4}+A_{2})-B_{0))$ ,

${\displaystyle D_{2}=A_{0}-B_{1))$ ,

$D_{3}=A_{1}-B_{2}$ ,

${\displaystyle D_{4}=A_{2}-B_{3))$ ,

${\displaystyle D_{0}=A_{3}-B_{4))$ .

No olvides que todas las sumas y restas se hacen en módulo . $2^{32}$

Cuando el mensaje tiene más de 512 bits, se ingresarán los bloques C y D recibidos en lugar de la clave para el siguiente bloque de mensaje. Esto continúa hasta que hayamos leído todo el mensaje.

Convencionalmente, todo el proceso de creación de un código de autenticidad se puede representar como:

$HL(1)=A=L^{*}(K,M1)$

$HR(1)=B=R^{*}(K,M1)$

luego se repite el proceso, con la única diferencia de que la clave es el resultado del cálculo anterior.

${\ estilo de visualización (A, B) -> (C, D)}$

$HL(i)=A=L^{*}(C,M_{i})$

$HR(i)=B=R^{*}(D,M_{i})$

En la última iteración, intercambiamos los datos de entrada por R y L. Esto se hace para aumentar la fuerza del código de autenticación. Los últimos son Two-track-MAC. ${\ estilo de visualización HL (n)}$ $HR(n)$

Pseudocódigo

A continuación se muestra el pseudocódigo del algoritmo.

C_{0}:=K_{0};C_{1}:=K1;C_{2}:=K_{2};C_{3}:=K_{3};C_{4}:= K_{4};D_{0}:=K_{0};D_{1}:=K_{1};D_{2}:=K_{2};D_{3}:=K_{3};D_ {4}:=K_{4};

FOR i:= 0 TO n-1 { IF (i!=n-1) FOR j:= 0 TO 79 { ; } else FOR j:= 0 TO 79 { } IF (i != n-1) { } } ;

A_{0}:=C_{0};A_{1}:=C_{1};A_{2}:=C_{2};A_{3}:=C_{3};A_{4 }:=C_{4};

B_{0}:=D_{0};B_{1}:=D_{1};B_{2}:=D_{2};B_{3}:=D_{3};B_{4 }:=D_{4};

T:=rol_{s(j)}(A_{0}\oplus f(j,A_{1},A_{2},A_{3})\oplus M_{i}[r(j) ]\oplus c(j))\oplus A_{4}

A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=rol_{10}(A_{2});A_{2}:=A_{ 1};A_{1}:=T;

T:=rol_{s^{'}(j)}(B_{0}\oplus f(79-j,B_{1},B_{2},B_{3})\oplus M_{i }[r^{'}(j)]\oplus c^{'}(j))\oplus B_{4};

B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{ 1};B_{1}:=T;

T:=rol_{s(j)}(A_{0}\oplus f(j,A_{1},A_{2},A_{3})\oplus M_{i}[r(j) ]\oplus c(j))\oplus A_{4}

A_{0}:=A_{4};A_{4}:=A_{3};A_{3}:=rol_{10}(A_{2});A_{2}:=A_{ 1};A_{1}:=T;

T:=rol_{s^{'}(j)}(B_{0}\oplus 79-j,B_{1},B_{2},B_{3})\oplus M_{i}[ r^{'}(j)]\o más c^{'}(j))

B_{0}:=B_{4};B_{4}:=B_{3};B_{3}:=rol_{10}(B_{2});B_{2}:=B_{ 1};B_{1}:=T;

A_{0}:=A_{0}\ominus C_{0};A_{1}:=A_{1}\ominus C_{1};A_{2}:=A_{2}\ominus C_ {2};A_{3}:=A_{3}\ominus C_{3}

{\displaystyle A_{4}:=A_{4}\ominus C_{4))

B_{0}:=B_{0}\ominus D_{0};B_{1}:=B_{1}\ominus D_{1};B_{2}:=B_{2}\ominus D_ {2};B_{3}:=B_{3}\ominus D_{3}

B_{4}:=B_{4}\ominus D_{4};

C_{2}:=A_{3}\ominus B_{0};C_{3}:=A_{4}\ominus B_{1};C_{4}:=A_{0}\ominus B_ {2};C_{0}:=(A_{1}/oplusA_{4})\ominus B_{3}

{\displaystyle C_{1}:=A_{2}\ominus B_{4))

D_{1}:=(A_{4}\oplus A_{2})\ominus B_{0};D_{2}:=A_{0}\ominus B_{1};D_{3}: =A_{1}\ominus B_{2}

{\displaystyle D_{4}:=A_{2}\ominus B_{3};D_{0}:=A_{3}\ominus B_{4))

E_{0}:=A_{0}\ominus B_{0};E_{1}:=A_{1}\ominus B_{1};E_{2}:=A_{2}\ominus B_ {2};E_{3}:=A_{3}\ominus B_{3};

{\displaystyle E_{4}:=A_{4}\ominus B_{4))

Aclaraciones y posibles implementaciones

Explica la notación utilizada en el pseudocódigo TTMAC y analiza la viabilidad de implementarlo.

${\ estilo de visualización f (j, x, y, z)}$ es una función no lineal que trabaja con bits. Para diferentes j realiza diferentes operaciones en x, y, z. A saber:

$f(j; x; y; z) = x \otimes y \otimes z ~~~~~~~~~~~~~ (0 \le j \le 15)$
$f(j; x; y; z) = (x \cuña y) \lor (\neg x \cuña z)~~~ (16 \le j \le 31)$
$f(j; x; y; z) = (x \lor \neg y) \otimes z ~~~~~~~~~~ (32 \le j \le 47 )$
$f(j; x; y; z) = (x \land z) \lor (y \land \neg z)~~~~ (48 \le j \le 63)$
$f(j; x; y; z) = x \otimes (y \lor \neg z)~~~~~~~~~ (64 \le j \le 79)$

Por ejemplo, en C es conveniente representar estas funciones como macros [1] :

#define F1(x, y, z) (x ^ y ^ z) #define F2(x, y, z) (z ^ (x & (y^z))) #define F3(x, y, z) (z ^ (x | ~y)) #define F4(x, y, z) (y ^ (z & (x^y))) #define F5(x, y, z) (x ^ (y | ~z))

Los símbolos denotan constantes cuyos valores están determinados por el rango j: $c(j),c^{'}(j)$

c(j) = 00000000x ${\ estilo de visualización (0 \ leq j \ leq 15)}$
c(j) = 5A827999x ${\ estilo de visualización (16 \ leq j \ leq 31)}$
c(j) = 6ED9EBA1x ${\ estilo de visualización (32 \ leq j \ leq 47)}$
c(j) = 8F1BBCDCx ${\ estilo de visualización (48 \ leq j \ leq 63)}$
c(j) = A953FD4Ex ${\ estilo de visualización (64 \ leq j \ leq 79)}$
c'(j) = 50A28BE6x ${\ estilo de visualización (0 \ leq j \ leq 15)}$
c'(j) = 5C4DD124x ${\ estilo de visualización (16 \ leq j \ leq 31)}$
c'(j) = 6D703EF3x ${\ estilo de visualización (32 \ leq j \ leq 47)}$
c'(j) = 7A6D76E9x ${\ estilo de visualización (48 \ leq j \ leq 63)}$
c'(j) = 00000000x ${\ estilo de visualización (64 \ leq j \ leq 79)}$

Las funciones r(j) yr' dan uno de los 16 bloques posibles en los que se divide el mensaje original. Dado que los bloques tienen un tamaño de 512 bits, r(j) puede tomar valores de 0 a 15. Donde r(j) = 0 (r'(j) = 0) significa bits 0…15, y r(j) = 15 (r'(j) = 15) son los bits 495…511 respectivamente.

r(j) = j para $(0\le j\le 15)$
r(16..31) = 7; cuatro; 13; una; diez; 6; quince; 3; 12; 0; 9; 5; 2; catorce; once; ocho
r(32..47) = 3; diez; catorce; cuatro; 9; quince; ocho; una; 2; 7; 0; 6; 13; once; 5; 12
r(48..63) = 1; 9; once; diez; 0; ocho; 12; cuatro; 13; 3; 7; quince; catorce; 5; 6; 2
r(64..79) = 4; 0; 5; 9; 7; 12; 2; diez; catorce; una; 3; ocho; once; 6; quince; 13
r'(0..15) = 5; catorce; 7; 0; 9; 2; once; cuatro; 13; 6; quince; ocho; una; diez; 3; 12
r'(16..31) = 6; once; 3; 7; 0; 13; 5; diez; catorce; quince; ocho; 12; cuatro; 9; una; 2
r'(32..47) = 15; 5; una; 3; 7; catorce; 6; 9; once; ocho; 12; 2; diez; 0; cuatro; 13
r'(48..63) = 8; 6; cuatro; una; 3; once; quince; 0; 5; 12; 2; 13; 9; 7; diez; catorce
r'(64..79) = 12; quince; diez; cuatro; una; 5; ocho; 7; 6; 2; 13; catorce; 0; 3; 9; once

Ejemplo: Sea el mensaje:

M = "Hashing universal optimizado por software y autenticación de mensajes".

Asignemos un código específico a cada carácter:

"S", "o", "f", "t", "w", "a", "r", "e", "-", "o", "p", "t", "i" " ", "m", "yo", "z" 83, 111, 102, 116, 119, 97, 114, 101, 45, 111, 112, 116, 105, 109, 105, 122 "e", "d", " ", "u", "n", "i", "v", "e", "r", "s", "a", "l", " ", "posee" 101, 100, 32, 117, 110, 105, 118, 101, 114, 115, 97, 108, 32, 104, 97, 115 "h", "i", "n", "g", " ", "a", "n", "d", " ", "m", "e", "s", "s", "años" 104, 105, 110, 103, 32, 97, 110, 100, 32, 109, 101, 115, 115, 97, 103, 101 " ", "a", "u", "t", "h", "e", "n", "t", "i", "c", "a", "t", "i" , "en", "." 32, 97, 117, 116, 104, 101, 110, 116, 105, 99, 97, 116, 105, 111, 110, 46

En representación binaria, el texto del mensaje contendrá 512 ceros y unos. Luego se divide en 16 bloques de 32 bits:

M_{0}=

= (01010011 01101111 01100110 01110100) = (01110111 01100001 01110010 01100101) = (00101101 01101111 01110000 01110100) = (01101001 01101101 01101001 01111010) = (01100101 01100100 00100000 01110101) = (01101110 01101001 01110110 01100101) = (01110010 01110011 01100001 01101100) = (00100000 01101000 01100001 01110011) = (01101000 01101001 01101110 01100111) = (00100000 01100001 01101110 01100100) = (00100000 01101101 01100101 01110011) = (01110011 01100001 01100111 01100101) = (00100000 01100001 01110101 01110100) = (01101000 01100101 01101110 01110100) = ( 01101001 01100011 01100001 01110100) = (01101001 01101111 01101110 00101110)

{\ estilo de visualización M_ {1} =}

{\ estilo de visualización M_ {2} =}

M_{3}=

M_{4}=

M_{5}=

M_{6}=

M_{7}=

M_{8}=

M_{9}=

M_{10}=

M_{11}=

M_{12}=

M_{13}=

M_{14}=

M_{15}=

Como resultado, la función devolverá: (00100000 01101000 01100001 01110011). A dará el tercer bit, es decir, 1. ${\ estilo de visualización METRO (r (16))}$ $M_{2}(r(16))$

s(j) y - dan el número de bit para la operación de rotación de bit rol. $s^{'}(j)$

s(0..15) = 11; catorce; quince; 12; 5; ocho; 7; 9; once; 13; catorce; quince; 6; 7; 9; ocho
s(16..31) = 7; 6; ocho; 13; once; 9; 7; quince; 7; 12; quince; 9; once; 7; 13; 12
s(32..47) = 11; 13; 6; 7; catorce; 9; 13; quince; catorce; ocho; 13; 6; 5; 12; 7; 5
s(48..63) = 11; 12; catorce; quince; catorce; quince; 9; ocho; 9; catorce; 5; 6; ocho; 6; 5; 12
s(64..79) = 9; quince; 5; once; 6; ocho; 13; 12; 5; 12; 13; catorce; once; ocho; 5; 6
s'(0..15) = 8; 9; 9; once; 13; quince; quince; 5; 7; 7; ocho; once; catorce; catorce; 12; 6
s'(16..31) = 9; 13; quince; 7; 12; ocho; 9; once; 7; 7; 12; 7; 6; quince; 13; once
s'(32..47) = 9; 7; quince; once; ocho; 6; 6; catorce; 12; 13; 5; catorce; 13; 13; 7; 5
s'(48..63) = 15; 5; ocho; once; catorce; catorce; 6; catorce; 6; 9; 12; 9; 12; 5; quince; ocho
s'(64..79) = 8; 5; 12; 9; 12; 5; catorce; 6; ocho; 13; 6; 5; quince; 13; once; once

De hecho, todas las expresiones descritas anteriormente están tomadas del algoritmo hash RIPEMD-160 . Es por eso que RIPEMD-160 es la base para Two-Track-MAC.

Se ha incluido una implementación del algoritmo TTMAC en la biblioteca criptográfica Crypto++ [2] .

Ejemplos

Demostremos un ejemplo de cómo funciona el algoritmo para varios datos de entrada. El primer parámetro es una clave de 160 bits. El segundo parámetro es el mensaje a enviar. En la salida, obtenemos un código de autenticación de 160 bits.

TTMAC(K,M) = TTMAC(00000000000000000000000000000000000000000,"") = 46724343BDDF4A150009046D4CBF16F2A6378073 TTMAC(K,M) = TTMAC(0000000000000000000000000000000000000000,"Hola Mundo") = 5C8350FEEA6922C4E79F262A72603AA7F99C381D TTMAC(K,M) = TTMAC(00000000000000000000000000000000000000001,"1") = 8B91136B35096C30C58FA17D7ADE882DBC1CC482

Problemas de uso

El código de autenticación resultante le permite verificar que los datos no han cambiado de ninguna manera desde que fueron creados, transmitidos o almacenados por una fuente confiable. Existen varios esquemas que realizan este tipo de verificación.

Por ejemplo, dos partes que confían entre sí acordaron de antemano usar una clave secreta que solo ellos conocen. Esto garantiza la autenticidad de la fuente y del mensaje. La desventaja de este enfoque es obvia. Hay una necesidad de dos partes que confíen la una en la otra.

También es posible compartir el código de autenticación de mensajes junto con la función de cifrado simétrico según uno de los esquemas: $E_{k_{1}}(M,TTMAC_{k_{2}}(M))$

$(E_{k_{1}}(M),TTMAC_{k_{2}}(M))$

$(E_{k_{1}}(M),TTMAC_{k_{2}}(E_{k_{1}}(M)))$

Este enfoque implica una diferencia en las claves y , así como una diferencia en los algoritmos de cifrado y cálculo de MAC. De lo contrario, existe la posibilidad de correlaciones adicionales que pueden usarse para rechazar claves. ${\ Displaystyle k_ {2}}$ $k_{1}$

En particular, TTMAC se puede utilizar para la "autenticación de transacciones". Esto significa que el mensaje se confirma por su unicidad y transmisión oportuna. Este tipo de autenticación brinda la capacidad de proteger contra la reutilización de mensajes transmitidos anteriormente, lo cual es necesario en los casos en que una amenaza puede tener consecuencias no deseadas.

Seguridad

El éxito de los ataques a Two-Track-MAC depende de la complejidad de la clave k, que debe tener una longitud de 160 bits, la longitud del código de salida m, que puede ser de 32,64,... y 160 bits, y la longitud l de el estado interno, que es de 320 bits.

La primera posibilidad es enumerar todas las claves posibles. Si es posible recoger la clave, entonces el atacante tiene la capacidad de falsificar cualquier mensaje. Para una clave de longitud k y un código de salida de longitud m, dicho ataque requiere intentos y pares conocidos (texto, MAC) para probar. Dado que el tamaño del estado interno de TTMAC es de 360 bits, la probabilidad de calcular el valor del código de autenticidad se reduce a , en comparación con RIPEMD-160. ${\ estilo de visualización 2 ^ {k}}$ ${\frac{k}{m))$ ${\ estilo de visualización 2^{160}}$ ${\ estilo de visualización 2^{80}}$

La búsqueda de las llamadas [Colisión|colisiones] requiere el conocimiento de pares (texto,MAC), donde l es la longitud del estado interno. De hecho, este resultado se deriva de la paradoja de los "cumpleaños". Para detectar colisiones internas mediante la investigación de colisiones externas, se requiere el orden establecido de texto-MAC. Además, el riesgo se puede reducir al reducir la vida útil de la clave. $2^{\frac{l}{2}}$ ${\ estilo de visualización 2 ^ {lm}}$

Los resultados se muestran en la tabla:

Tipos de ataque	intentos	Posible éxito	parejas famosas
encontrar una llave	${\ estilo de visualización 2^{160}}$	${\frac{160}{m))$
adivinanzas MAC		${\ Displaystyle {\ frac {1} {2 ^ {m}}}}$
Ataque basado en la paradoja del cumpleaños			${\ estilo de visualización 2^{160}}$

Eficiencia computacional

La cantidad de operaciones para TTMAC es solo un pequeño porcentaje mayor que la cantidad de operaciones requeridas para el cálculo de RIPEMD-160. Comparemos el código RIPEMD-160 y TTMAC altamente optimizado. El primero requiere 1013 ciclos por bloque, y para el mismo grado de optimización TTMAC necesitará alrededor de 1044 ciclos por bloque. Esto se logra mediante el diseño inicial del algoritmo para una operación rápida en dispositivos informáticos.

Véase también

Notas

↑ implementación de macros . - código fuente. Archivado desde el original el 1 de julio de 2012.
↑ La estructura de la implementación del algoritmo TTMCA (inglés) ? . — Cripto++ TTMAC. Archivado desde el original el 1 de julio de 2012. (indefinido)

Literatura

A. P. Alferov, A. Yu. Zubov, A. S. Kuzmin, A. V. Cheremushkin Fundamentos de criptografía: una guía de estudio. 3ra ed. - M.: Helios APB, 2005 - 480c., Ill.
Stinson, DR (Douglas Robert), 1956 - Criptografía: teoría y práctica / DR Stinson. pags. cm. — (Matemáticas discretas y su aplicación) Incluye referencias bibliográficas e índice. ISBN 0-8493-8521-0 .