UMAC

En criptografía , un código de autenticación de mensajes basado en hash universal , o UMAC , es un tipo de código de autenticación de mensajes (MAC) calculado eligiendo una función hash de una clase de funciones hash según algún proceso secreto (aleatorio) y aplicándola al mensaje. El resumen o huella digital resultante se cifra para ocultar la identidad de la función hash utilizada. Al igual que con cualquier MAC, se puede utilizar para verificar simultáneamente tanto la integridad de los datos como la autenticidad de un mensaje . A diferencia de los MAC tradicionales, que son serializables , UMAC se puede ejecutar en paralelo . Por lo tanto, a medida que las máquinas sigan ofreciendo más capacidades de procesamiento en paralelo, aumentará la velocidad de implementación de UMAC. ^[1]

Un tipo específico de UMAC, también conocido comúnmente como UMAC , se especifica en RFC 4418, tiene una fuerza criptográfica demostrable y suele ser mucho menos intensivo en términos computacionales que otros MAC. El diseño de UMAC está optimizado para arquitecturas de 32 bits con soporte SIMD , con un rendimiento de 1 ciclo de CPU por byte (cpb) con SIMD y 2 cpb sin SIMD. Una variante estrechamente relacionada de UMAC que está optimizada para arquitecturas de 64 bits es la proporcionada por VMAC , que se ha enviado a la IETF como borrador ( draft-krovetz-vmac-01 ) pero nunca recibió suficiente atención para convertirse en un RFC estandarizado.

Fondo

Hashing universal

Digamos que la función hash se elige de una clase de funciones hash H, que asigna los mensajes a D, el conjunto de posibles resúmenes de mensajes. Esta clase se denomina universal si, para cualquier par de mensajes distinto, hay como máximo |H|/|D| funciones que los asignan al mismo miembro de D.

Esto significa que si un atacante quiere reemplazar un mensaje por otro y, desde su punto de vista, la función hash fue elegida completamente al azar, la probabilidad de que el UMAC no detecte su modificación es como máximo 1/|D|.

Pero esta definición no es lo suficientemente fuerte: si los mensajes posibles son 0 y 1, D={0,1} y H consiste en la operación de identidad y no en , H es universal. Pero incluso si el resumen está cifrado mediante adición modular, el atacante puede cambiar el mensaje y el resumen al mismo tiempo y el receptor no sabría la diferencia.

Hashing fuertemente universal

Una clase de funciones hash H que sea útil hará que sea difícil para un atacante adivinar el resumen correcto d de un mensaje falso f después de interceptar un mensaje a con resumen c . En otras palabras,

\Pr_{h\in H}[h(f)=d|h(a)=c]\,

debe ser muy pequeño, preferiblemente 1/| D |.

Es fácil construir una clase de funciones hash cuando D es un campo . Por ejemplo, si | D | es primo , todas las operaciones se toman módulo | D |. El mensaje a se codifica entonces como un vector n -dimensional sobre $D (a 1, a 2, ..., a n)$ . H tiene entonces | D | ^{n +1} miembros, cada uno correspondiente a un vector $(n + 1)$ -dimensional sobre $D (h 0, h 1, ..., h n)$ . Si dejamos

h(a)=h_{0}+\sum _{i=1}^{n}{h_{i}}{a_{i}}

Podemos usar las reglas de probabilidades y combinatoria para demostrar que

\Pr _{h\in H}[h(f)=d|h(a)=c]={1 \sobre |D|}

Si ciframos correctamente todos los resúmenes (por ejemplo, con un block de un solo uso ), un atacante no puede aprender nada de ellos y se puede utilizar la misma función hash para todas las comunicaciones entre las dos partes. Esto puede no ser cierto para el cifrado ECB porque puede ser bastante probable que dos mensajes produzcan el mismo valor hash. Entonces se debe utilizar algún tipo de vector de inicialización , que a menudo se denomina nonce . Se ha convertido en una práctica común establecer h ₀ = f (nonce), donde f también es secreto.

Tenga en cuenta que tener una gran cantidad de potencia informática no ayuda en absoluto al atacante. Si el destinatario limita la cantidad de falsificaciones que acepta (suspendiéndose cada vez que detecta una), | D | puede ser 2 ³² o menor.

Ejemplo

La siguiente función C genera un UMAC de 24 bits. Supone que secretes un múltiplo de 24 bits, msgno es más largo que secrety resultya contiene los 24 bits secretos, p. ej., f(nonce). Nonce no necesita estar contenido en msg.

Código en lenguaje C (original)

/* DUDOSO: Esto no parece tener nada que ver con la (probablemente larga) definición del RFC. Probablemente sea un ejemplo del concepto general de UMAC. * ¿Quién diablos de 2007 (Nroets) elige 3 bytes en un ejemplo? * * Tenemos que mover esto junto con una mejor definición de str. uni. hash a * uni. hash. */ #define uchar uint8_t void UHash24 ( uchar * msg , uchar * secret , size_t len , uchar * result ) { uchar r1 = 0 , r2 = 0 , r3 = 0 , s1 , s2 , s3 , byteCnt = 0 , bitCnt , byte ; while ( len -- > 0 ) { /* Obtener un nuevo secreto por cada tres bytes. */ if ( byteCnt -- == 0 ) { s1 = * secret ++ ; s2 = * secret ++ ; s3 = * secret ++ ; byteCnt = 2 ; } byte = * msg ++ ; /* Cada byte del msg controla si un bit de los secretos llega al hash.、     *  * No entiendo el punto sobre mantener su orden por debajo de 24, porque con una cosa de 3 bytes      * por definición solo contiene polinomios de orden 0-23. El código "sec" tiene un  * comportamiento idéntico, aunque todavía estamos haciendo MUCHO trabajo para cada bit  */ for ( uchar bitCnt = 0 ; bitCnt < 8 ; bitCnt ++ ) { /* El último bit controla si se usa un bit secreto. */ if ( byte & 1 ) { r1 ^= s1 ; /* (seg >> 16) y 0xff */ r2 ^= s2 ; /* (seg >> 8) y 0xff */ r3 ^= s3 ; /* (seg ) y 0xff */ }                                                                                                    byte >>= 1 ; /* siguiente bit. */ /* y multiplicar secreto con x (es decir, 2), restando (por XOR)  el polinomio cuando sea necesario para mantener su orden bajo 24 (?!) */ uchar doSub = s3 & 0x80 ; s3 <<= 1 ; if ( s2 & 0x80 ) s3 |= 1 ; s2 <<= 1 ; if ( s1 & 0x80 ) s2 |= 1 ; s1 <<= 1 ; if ( doSub ) { /* 0b0001 1011 --> */ s1 ^= 0x1B ; /* x^24 + x^4 + x^3 + x + 1 [16777243 -- no es primo] */ } } /* para cada bit del mensaje */ } /* para cada byte del mensaje */ * resultado ++ ^= r1 ; * resultado ++ ^= r2 ; * resultado ++ ^= r3 ; }

Código de lenguaje C (revisado)

#define uchar uint8_t #define swap32(x) ((x) & 0xff) << 24 | ((x) & 0xff00) << 8 | ((x) & 0xff0000) >> 8 | (x) & 0xff000000) >> 24) /* Esto es lo mismo, pero agrupado (generando un mejor ensamblaje y esas cosas).  Sigue siendo malo y nadie ha explicado por qué es fuertemente universal. */ void UHash24Ex ( uchar * msg , uchar * secret , size_t len , uchar * result ) { uchar byte , read ; uint32_t sec = 0 , ret = 0 , content = 0 ;                       mientras ( len > 0 ) { /* Leer tres en un fragmento. */ contenido = 0 ; switch ( leer = ( len >= 3 ? 3 : len )) { caso 2 : contenido |= ( uint32_t ) msg [ 2 ] << 16 ; /* FALLTHRU */ caso 1 : contenido |= ( uint32_t ) msg [ 1 ] << 8 ; /* FALLTHRU */ caso 0 : contenido |= ( uint32_t ) msg [ 0 ]; } len -= leer ; msg += leer ;                                                      /* Obtener un nuevo secreto por cada tres bytes. */ seg = ( uint32_t ) secret [ 2 ] << 16 | ( uint32_t ) secret [ 1 ] << 8 | ( uint32_t ) secret [ 0 ]; secret += 3 ;                  /* El gran compresor. */ for ( bitCnt = 0 ; bitCnt < 24 ; bitCnt ++ ) { /* Una dependencia de datos difícil de eliminar: la salida depende  * del intermedio.  * Realmente no funciona con tablas de bytes CRC. */ if ( byte & 1 ) { ret ^= sec ; } byte >>= 1 ; /* siguiente bit. */ /* Registro de desplazamiento. */ sec <<= 1 ; if ( sec & 0x01000000 ) sec ^= 0x0100001B ; sec &= 0x00ffffff ; } /* para cada bit del mensaje */ } /* para cada 3 bytes del mensaje */ result [ 0 ] ^= ret & 0xff ; result [ 1 ] ^= ( ret >> 8 ) & 0xff ; resultado [ 2 ] ^= ( ret >> 16 ) & 0xff ; }

NH y el RFC UMAC

NUEVA HAMPSHIRE

Las funciones de la familia de funciones hash fuertemente universales sin nombre ^{[ cita requerida ]} mencionadas anteriormente utilizan n multiplicaciones para calcular un valor hash.

La familia NH reduce a la mitad el número de multiplicaciones, lo que se traduce aproximadamente en una aceleración del doble en la práctica. ^[2] Para lograr velocidad, UMAC utiliza la familia de funciones hash NH. NH está diseñada específicamente para usar instrucciones SIMD y, por lo tanto, UMAC es la primera función MAC optimizada para SIMD. ^[1]

La siguiente familia hash es -universal: ^[1] $Estilo de visualización 2-w$

\operatorname {NH} _{K}(M)=\left(\sum _{i=0}^{(n/2)-1}((m_{2i}+k_{2i}){ \bmod {~}}2^{w})\cdot ((m_{2i+1}+k_{2i+1}){\bmod {~}}2^{w})\right){\bmod { ~}}2^{2w}

dónde

El mensaje M se codifica como un vector n -dimensional de palabras de w -bits ( m ₀ , m ₁ , m ₂ , ..., m _n-1 ).
La clave intermedia K se codifica como un vector n+1 -dimensional de palabras de w -bits ( k ₀ , k ₁ , k ₂ , ..., k _n ). Un generador pseudoaleatorio genera K a partir de una clave secreta compartida.

En la práctica, NH se realiza con números enteros sin signo. Todas las multiplicaciones son mod 2^ w , todas las sumas mod 2^ w /2 y todas las entradas son un vector de medias palabras ( números enteros de 0,016 bits). El algoritmo utilizará entonces multiplicaciones, donde era el número de medias palabras en el vector. Por lo tanto, el algoritmo se ejecuta a una "velocidad" de una multiplicación por palabra de entrada. $w/2=32$ $\lceil k/2\rceil$ ${\estilo de visualización k}$

RFC 4418

RFC 4418 hace mucho por encapsular NH para convertirlo en un buen UMAC. La rutina UHASH ("Función Hash Universal") general produce una longitud variable de etiquetas, que corresponde a la cantidad de iteraciones (y las longitudes totales de claves) necesarias en las tres capas de su hash. Se utilizan varias llamadas a una función de derivación de claves basada en AES para proporcionar claves para los tres hashes con clave.

La capa 1 (fragmentos de 1024 bytes -> hashes de 8 bytes concatenados) utiliza NH porque es rápido.
La capa 2 reduce todo a 16 bytes utilizando una función POLY que realiza aritmética de módulo primo, donde el primo cambia a medida que aumenta el tamaño de la entrada.
La capa 3 convierte la cadena de 16 bytes en una longitud fija de 4 bytes. Esto es lo que genera una iteración.

En RFC 4418, NH se reorganiza para adoptar la forma siguiente:

Y = 0 para (i = 0; i < t; i += 8) termina  para ${\begin{aligned}{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+0}+_{32}K_{i+0})*_{64}(M_{i+4}+_{32}K_{i+4}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+1}+_{32}K_{i+1})*_{64}(M_{i+5}+_{32}K_{i+5}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+2}+_{32}K_{i+2})*_{64}(M_{i+6}+_{32}K_{i+6}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+3}+_{32}K_{i+3})*_{64}(M_{i+7}+_{32}K_{i+7}))}}\end{alineado}}$

Esta definición está diseñada para alentar a los programadores a utilizar instrucciones SIMD en la acumulación, ya que es probable que los datos que tienen cuatro índices de diferencia no se coloquen en el mismo registro SIMD y, por lo tanto, sean más rápidos de multiplicar en bloque. En una máquina hipotética, podría traducirse simplemente a:

Asamblea hipotética

movq $ 0 , regY ; Y = 0 movq $ 0 , regI ; i = 0 bucle: suma reg1 , regM , regI ; reg1 = M + i suma reg2 , regM , regI vldr.4x32 vec1 , reg1 ; carga valores de 4x32 bits desde la memoria *reg1 a vec1 vldr.4x32 vec2 , reg2 vmul.4x64 vec3 , vec1 , vec2 ; vec3 = vec1 * vec2 uaddv.4x64 reg3 , vec3 ; suma horizontalmente vec3 en reg3 suma regY , regY , reg3 ; regY = regY + reg3 suma regI , regI , $ 8 cmp regI , regT jlt bucle

Véase también

Poly1305 es otra MAC rápida basada en un hash fuertemente universal.

Referencias

^ abc Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999). UMAC: autenticación de mensajes rápida y segura (PDF) . Avances en criptología (CRYPTO '99) . Archivado desde el original (PDF) el 10 de marzo de 2012., Ecuación 1 y también sección 4.2 “Definición de NH”.
^ Thorup, Mikkel (2009). Hashing de cadenas para sondeo lineal. Proc. 20.º Simposio ACM-SIAM sobre algoritmos discretos (SODA) . Págs. 655–664. CiteSeerX 10.1.1.215.4253 . doi :10.1137/1.9781611973068.72. ISBN . 978-0-89871-680-1. Archivado (PDF) del original el 12 de octubre de 2013., sección 5.3

Enlaces externos

Ted Krovetz. "UMAC: autenticación de mensajes rápida y demostrablemente segura".

Miller, Damien; Valchev, Peter (3 de septiembre de 2007). "El uso de UMAC en el protocolo de capa de transporte SSH: draft-miller-secsh-umac-01.txt". IETF .