CBC-MAC

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 2 de enero de 2020; las comprobaciones requieren 4 ediciones .

La criptografía CBC MAC  -in es una tecnología para construir un código de autenticación de mensajes a partir de un cifrado de bloque . El mensaje se cifra utilizando algún algoritmo de cifrado de bloques en modo CBC para crear una cadena de bloques con la regla de que cada bloque depende del cifrado adecuado (correcto) del anterior. Esta interdependencia garantiza que un cambio en cualquier bit del texto sin formato dará como resultado un cambio en el bloque cifrado final de una manera que no se puede predecir o calcular si no se conoce la clave de cifrado del bloque .

Se utilizó (con sustitución como E del algoritmo DES ) como el estándar del gobierno de EE . UU.  - DAA .

Información de referencia

El algoritmo CBC MAC es un método bien conocido para generar un código de autenticación de mensajes  basado en un cifrado de bloque . 

Bellare, Kilian y Rogaway demostraron la seguridad ( security ) del algoritmo para una longitud de mensaje fija de m * n bits, donde n es la longitud del cifrado de bloque base E.

Sin embargo, es bien sabido que MAC CBC no es seguro a menos que se fije la longitud del mensaje. Así, se han propuesto varias variantes del algoritmo para una longitud de mensaje variable. Primero se propuso la inserción de imitación cifrada (EMAC) , se obtiene cifrando el valor CBC MAC con E y una nueva clave . Eso es

,

donde M es el mensaje,  es la clave CBC MAC y  es el valor CBC MAC del mensaje. Más tarde, M. Petrank y Rackoff demostraron que EMAC es seguro si la longitud del mensaje es un múltiplo de n (Vaudenay, utilizando la teoría de la descorrelación , publicó otra prueba). Sin embargo, EMAC requiere dos programaciones clave para el cifrado de bloque base E.

Además, Black y Rogaway propusieron XCBC, que requiere solo un programa clave del cifrado de bloque base E. XCBC proporciona tres claves: una clave del cifrado de bloque K1 y dos claves de n bits cada una. XCBC se describe mediante el siguiente diagrama

La tabla muestra una comparación de longitudes de clave.

XCBC TMAC OMAC
Longitud de clave (k + 2n) bits (k + n) bits k bits

Si para algún m > 0, entonces XCBC se calcula exactamente como CBC MAC, excepto por la operación XOR ("o exclusivo") de la clave (n bits) hasta que se cifra el último bloque.

De lo contrario, (donde ) se agrega a M y XCBC se calcula exactamente como el MAC CBC para el mensaje recibido. Excepto para XORing otra clave (n bits) hasta que se cifra el último bloque. Sin embargo, la desventaja de XCBC es que requiere tres claves, es decir, un total de (k + 2n) bits. Como resultado, Kurosawa e Iwata propusieron un CBC MAC (TMAC) de dos claves. TMAC acepta dos claves, que suman (k + n) bits: la clave de cifrado de bloque y la clave (n bits). TMAC se obtiene de XCBC moviendo (o reemplazando) con , donde u es una constante distinta de cero y "•" denota multiplicación en . Como ya se mencionó, OMAC ( one-key CBC MAC ) acepta solo una clave K del cifrado de bloque E. La longitud de la clave, k bits, es mínima, ya que el cifrado base debe contener una clave K, que consta de k bits en cualquier caso. .

OMAC

OMAC es el nombre principal de OMAC1 y OMAC2. OMAC1 se obtiene de XCBC reemplazando por alguna constante u distinta de cero en , donde L viene dada por la siguiente expresión: . OMAC2 se obtiene de manera similar utilizando . Podemos calcular , y eficientemente con un solo turno y XOR en y , respectivamente. OMAC1 (resp. OMAC2) se describe mediante el siguiente diagrama:


1. Si para algún m > 0, entonces OMAC se calcula exactamente como CBC MAC, excepto por la operación XOR antes de que se cifre el último bloque. 2. De lo contrario, (donde ) se agrega a M y OMAC se calcula exactamente como el CBC MAC para el mensaje recibido M, excepto por la operación XOR para (resp. antes del cifrado del último bloque.

Además, en TMAC, la clave es parte de la clave, mientras que en OMAC, L no es parte de la clave y se genera a partir de K. Esta preservación de la longitud de la clave hace que la seguridad de OMAC sea mucho más difícil de probar que la de TMAC, como se muestra a continuación. . En la Figura 2, sea M[1] = . Entonces L es la salida del primero . L siempre vuelve a aparecer en el último bloque. Básicamente, tal reutilización de L conduciría a un punto muerto en la prueba de seguridad. (En modo OCB y PMAC, también se usa como clave hash universal. Sin embargo, L aparece como la salida de algún bloque interno con una probabilidad insignificante). Sin embargo, hemos demostrado que OMAC es tan seguro como XCBC, donde el análisis de seguridad es un ejemplo de seguridad absoluta [1]. Además, OMAC recibió todas las demás propiedades positivas con las que XCBC (y TMAC) estaban dotados. Por lo tanto, el área OMAC es {0,1}, se necesita un programa de clave única del cifrado de bloque base E y llamadas de cifrado de bloque (referencias).

Notación

Para el conjunto A, x←A significa que x se elige aleatoriamente de A, y la elección de cualquier valor del conjunto A es equiprobable. Si a, b (∈ {0, 1}*) son cadenas del mismo tamaño, entonces a ⊕ b es su operación XOR bit a bit. Si a, b (∈ {0, 1}*) no son cadenas iguales, entonces a ◦ b denota su concatenación . (Para simplificar, se introduce la siguiente notación: ab:= a ◦ b). Para una cadena de n bits ∈ {0, 1}*, denota << 1 = cadena de n bits que se desplaza 1 bit a la izquierda, mientras tanto denota una >> 1 = cadena de n bits que se desplaza un bit a la derecha. Si a ∈ {0, 1}* es una cadena, entonces |a| denote su longitud en bits. Para cualquier bit, la cadena a ∈ {0, 1}* es tal que |a| ≤ n, definamos , donde la cadena vacía cuenta como un bloque.

CBC MAC

El cifrado de bloque E es una función E :  ×  → , donde cada E(K, •) = EK(•) es una permutación de , a su vez es un conjunto de claves posibles, y n es la longitud del bloque. CBC MAC [6, 7] es el algoritmo más simple y mejor conocido para hacer un MAC a partir de un cifrado de bloque E. Sea el mensaje M = M[1] ◦M[2] ◦ … ◦M[m], donde | M [1]| = |M[2]| = … = |M[m]| = norte Entonces CBCK(M), CBC MAC del mensaje M, dada la clave K, se define como Y [m], donde Y [i] = EK(M[i] ⊕ Y [i − 1]) para i = 1, … ,my Y[0] = . Bellare, Kilian y Rogaway han probado la seguridad de CBC MAC para una longitud de mensaje fija de mn bits.

Campo punteado

Podemos considerar el punto a en cualquiera de las siguientes formas: (1) como un punto abstracto en el campo a ; (2) como una cadena de n bits ∈ ; (3) como un polinomio formal con coeficientes binarios. Para agregar 2 puntos a , considere la operación XOR bit a bit sobre ellos. Denota esta operación por a ⊕ b. Para multiplicar dos puntos, fijamos algún polinomio f(u) con coeficientes binarios y grado n. Para mayor precisión, elegimos lexicográficamente el primer polinomio entre los mismos polinomios de grado n que tienen el mínimo número de coeficientes. Enumeramos algunos de estos polinomios para n = 64, para n = 128 y para n = 256. Para multiplicar dos puntos a ∈ y b ∈ , consideramos a y b como polinomios y , el resultado de la operación c(u), donde se suman y multiplican los coeficientes de GF(2), y se toma el resto de la separación de c(u) por f(u). Además, es especialmente fácil multiplicar un punto a ∈ por u. Por ejemplo, si n = 128, también basta con dividir el punto a ∈ entre u, teniendo en cuenta que a se multiplica por el recíproco de u en el campo: . Por ejemplo,






Diseño básico de la familia OMAS

La familia OMAC está definida por un cifrado de bloques E : KE ×  → , una constante Cst de n bits, una función hash universal H :  × X → y dos constantes únicas , ∈ X, donde X es el dominio finito de la función H . H, y debe satisfacer la siguiente condición: (las constantes son aleatorias. Escribamos HL(•) para H(L, •).


1. Para cualquier y ∈ , el número L ∈ es tal que HL( ) = y como máximo para algunos suficientemente pequeños . 2. Para cualquier y ∈ , el número L ∈ es tal que HL( ) = y como máximo para algunos suficientemente pequeños . 3. Para cualquier y ∈ , el número L ∈ es tal que HL( ) ⊕ HL( ) = y como máximo para algunos suficientemente pequeños . 4. Para cualquier y ∈ , el número L ∈ es tal que HL( ) ⊕L = y como máximo para algunos suficientemente pequeños . 5. Para cualquier y ∈ , el número L ∈ es tal que HL( ) ⊕L = y como máximo para algunos suficientemente pequeños . 6. Para cualquier y ∈ , el número L ∈ es tal que HL( ) ⊕ HL(Cst2) ⊕ L = y como máximo para algunos suficientemente pequeños .




El siguiente es un pseudocódigo que describe la familia OMAC.

Algorithm
L ← ;
Y [0] ← ;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
Y [i] ← );
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;

El algoritmo de la familia OMAC se ilustra en la Fig. 3, donde (•) se define en (1). El espacio clave K de la familia OMAC: . Toma un valor clave K ∈ y un mensaje M ∈ {0, 1}*, y devuelve una cadena de la región .

Especificación propuesta

En OMAC1 establecemos Cst = , (x) = L•x, = u y = , donde "•" significa multiplicación en . , y son equivalentes. OMAC2 es similar a OMAC1 excepto por . , y son equivalentes. Además, , y se pueden calcular de manera eficiente con un cambio y una operación XOR de y , respectivamente, como se muestra en (2) y (3). Es fácil ver que las condiciones en la Sec. 3 se realizan en OMAC1 y OMAC2. OMAC1 y OMAC2 se ilustran en la Figura 2 y se describen a continuación: 1. Para OMAC1:


Algorithm
L ← ;
Y [0] ← ;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
if |M[m]| = n
then X[m] ← X[m] ⊕ ;
else Y[i] ← E_k(X[i]);
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;


1. Para OMAC2:

Algorithm
L ← ;
Y [0] ← ;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
if |M[m]| = n
then X[m] ← X[m] ⊕ ;
else Y[i] ← E_k(X[i]);
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;

Seguridad de la familia OMAC

Definición de seguridad

Sea Perm(n) el conjunto de todas las permutaciones de , y sea P una permutación aleatoria si P es una muestra aleatoria de Perm(n). La seguridad de un cifrado de bloque E se puede cuantificar como , la ventaja máxima que un adversario A puede obtener cuando intenta extraer (con una clave K elegida al azar) de una permutación aleatoria P(•) cuando se permiten los tiempos de consulta t y q ( que es cualquiera ). Esta ventaja se define como sigue. Digamos que el cifrado de bloque E es seguro si es esencialmente pequeño. De manera similar, el algoritmo MAC es F :  ×  → , donde  es un conjunto de claves, luego escribimos para F(K, •). Digamos que el adversario rompe si A vuelve , donde A nunca pide M. Entonces definimos ventaja como

donde el máximo se toma sobre todos los adversarios que "trabajan" no más del tiempo t, no hacen más de q solicitudes y cada solicitud no más de μ bits. Diremos que el algoritmo MAC está protegido (seguro) si el valor es despreciable. Denote por Rand(∗, n) el conjunto de todas las funciones desde {0, 1}* hasta . Este conjunto está dado por una medida de probabilidad bajo el supuesto de que un elemento aleatorio R del conjunto Rand(∗, n) está conectado o asociado con cada fila M ∈ {0, 1}* de la fila aleatoria R(M)∈ . A continuación, definimos la ventaja como donde se obtiene el máximo de todos los adversarios que "trabajan" en un tiempo no superior a t, no realizan más de q solicitudes y cada solicitud no supera los μ bits. Entonces podemos decir que el algoritmo MAC es pseudoaleatorio si el valor es insignificante (viprf está configurado para Función pseudoaleatoria de entrada de longitud variable: funciones pseudoaleatorias de entrada de longitud variable). Sin pérdida de generalidad, se supone que los adversarios nunca realizan solicitudes fuera del dominio y tampoco repiten solicitudes.

A continuación, presentamos los principales teoremas (sus formulaciones sin demostraciones).

Lema 5.1 (Lema principal de la familia OMAC). Suponga que H, Cst1 y Cst2 satisfacen las condiciones Sec. 3 para algunos despreciablemente pequeños , y también sea Cst una constante arbitraria de n bits. Suponga también que se utiliza una permutación aleatoria P ∈ Perm(n) en la familia OMAC (familia OMAC) como cifrado de bloque base. Sea A un adversario que hace no más de q solicitudes, y cada solicitud no más de nm bits. (m es el número máximo de bloques en cada consulta). Sea m ≤ 2n/4. Entonces donde . Los siguientes resultados se aplican tanto a OMAC1 como a OMAC2. Primero, hemos obtenido el siguiente lema reemplazando є = 2−n en el Lema 5.1.

Lema 5.2 (Lema principal de la familia OMAC). Supongamos que se usa una permutación aleatoria P ∈ Perm(n) en OMAC como un cifrado de bloque base. Sea A un adversario que realiza como máximo q solicitudes, y cada solicitud es como máximo nm bits. Sea m ≤ 2n/4. A continuación, mostramos que OMAC es pseudoaleatorio si el cifrado de bloque subyacente E es seguro.

Observación 5.1. Sea E :  ×  → el cifrado de bloque base que se usa en OMAC. Luego , donde t' = t + O(mq) y q' = mq + 1. Finalmente, mostramos que OMAC está protegido como el algoritmo aMAC de la Observación 5.1 en el sentido usual. Teorema 5.1. Sea E : KE ×  → el cifrado de bloque base utilizado en OMAC. Entonces , donde t' = t + O(mq) y q' = mq + 1.


Análogos

La mayoría de las tecnologías para construir un código de autenticación de mensajes se representan como una función hash del mensaje enviado y una clave específica que el remitente y el destinatario conocen, estas incluyen: RIPE-MAC, IBC-MAC, UMAC, VMAC. Fundamentalmente, CBC-MAC se diferencia de MAC en el uso de un cifrado de flujo (usando un generador de números pseudoaleatorios, el flujo de información se divide en dos flujos que se envían por separado), pero la desventaja son los cambios débiles con un pequeño cambio en el mensaje. Considere también Poly1305-AES, donde se usa una clave de 128 bits para AES como clave, un código de complemento a dos de 106 bits y también se crea una generación pseudoaleatoria de 128 bits. Como desventaja de CBC-MAC, puede indicar menos seguridad y, como ventaja, menos demanda de recursos informáticos.

Notas

Literatura