UMAC

Este artículo trata sobre un código de autenticación criptográfico. Para la organización atlética, vea Conferencia Atlética del Medio Oeste Superior . Para la universidad de Macao, consulte Universidad de Macao .

Este artículo necesita la atención de un experto en criptografía . El problema específico es: confusión entre UMAC como concepto general y el algoritmo RFC 4418 UMAC; Necesito que alguien divida esto en "hash universal en MAC" y "UMAC y amigos". Consulte la página de discusión para obtener más detalles. WikiProject Cryptography puede ayudar a reclutar a un experto. ( Septiembre de 2019 )

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 de acuerdo con algún proceso secreto (aleatorio) y aplicándolo al mensaje. . El resumen o huella dactilar resultante se cifra luego 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 .

Un tipo específico de UMAC, también comúnmente denominado solo UMAC , se especifica en RFC 4418, tiene una fuerza criptográfica demostrable y generalmente es mucho menos intensivo en computación 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. VMAC proporciona una variante estrechamente relacionada de UMAC que está optimizada para arquitecturas de 64 bits , que se ha enviado al IETF como borrador ( draft-krovetz-vmac-01 ) pero nunca recibió suficiente atención para convertirse en un RFC estandarizado.

Antecedentes

Hash universal

Artículo principal: hash universal

Digamos que la función hash se elige de una clase de funciones hash H, que mapea mensajes en D, el conjunto de posibles resúmenes de mensajes. Esta clase se llama universal si, para cualquier par de mensajes distintos, hay como máximo | H | / | D | funciones que los mapean 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 se eligió de forma completamente aleatoria, la probabilidad de que el UMAC no detecte su modificación es como máximo de 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 , H es universal. Pero incluso si el resumen está encriptado por adición modular, el atacante puede cambiar el mensaje y el resumen al mismo tiempo y el receptor no notaría la diferencia.

Hash fuertemente universal

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

${\displaystyle \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 luego como un vector n- dimensional sobre D ( a ₁ , a ₂ , ..., a _n ). H entonces tiene | D | ^{n +1} miembros, cada uno correspondiente a un  vector ( n + 1) -dimensional sobre D ( h ₀ ,h ₁ , ..., h _n ). Si dejamos

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

podemos usar las reglas de probabilidades y combinatoria para demostrar que

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

Si encriptamos correctamente todos los resúmenes (por ejemplo, con un bloc de notas de un solo uso ), un atacante no puede aprender nada de ellos y se puede usar la misma función hash para todas las comunicaciones entre las dos partes. Esto puede no ser cierto para el cifrado ECB porque es muy probable que dos mensajes produzcan el mismo valor hash. Entonces debería usarse 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 (durmiendo cada vez que detecta una), | D | puede ser de 2 ³² o menos.

Ejemplo

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

Código de idioma C (original)

/ * DUBIOUS: Esto no parece tener nada que ver con la (probablemente larga) definición de RFC *. Este es probablemente 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 en * uni. picadillo. * / #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 )  {     / * Obtiene un nuevo secreto por cada tres bytes. * /    if  ( byteCnt -  ==  0 )  {  s1  =  * secret ++ ;  s2  =  * secreto ++ ;  s3  =  * secreto ++ ;  byteCnt  =  2 ;  }  byte  =  * msg ++ ;    / * Cada byte del mensaje controla si un poco de los secretos se convierte en el hash. 、     * * No entiendo el punto sobre mantener su orden por debajo de 24, porque con una cosa de 3 bytes      *, por definición, solo tiene 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 un bit secreto se utiliza. * /  if  ( byte  &  1 )  {        r1  ^ =  s1 ;  / * (seg >> 16) y 0xff * /  r2  ^ =  s2;  / * (seg >> 8) & 0xff * /  r3  ^ =  s3 ;  / * (seg) & 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 por debajo de 24 (?!) * /  uchar  doSub  =  s3  &  0x80 ;       s3  << =  1 ;  si  ( s2  y  0x80 )  s3  | =  1 ;  s2  << =  1 ;  si  ( s1  y  0x80)  s2  | =  1 ;  s1  << =  1 ;      if  ( doSub )  {  / * 0b0001 1011 -> * /  s1  ^ =  0x1B ;  / * x ^ 24 + x ^ 4 + x ^ 3 + x + 1 [16777243 - no es un primo] * /  }  }  / * para cada bit en el mensaje * /  }  / * para cada byte en el mensaje * /  * resultado ++  ^ =  r1 ;  * resultado ++  ^ =  r2 ;  * resultado ++  ^ =  r3 ; }

Código de lenguaje C (revisado)

#define uchar uint8_t #define swap32 (x) ((x) & 0xff) << 24 | ((x) y 0xff00) << 8 | ((x) y 0xff0000) >> 8 | (x) & 0xff000000) >> 24) / * Esto es lo mismo, pero agrupado (generando un mejor ensamblaje y demás).  Todavía es malo y nadie ha explicado por qué es tan universal. * / void  UHash24Ex  ( uchar  * msg ,  uchar  * secret ,  size_t  len ,  uchar  * result ) {  uchar  byte ,  read ;  uint32_t  sec  =  0 ,  ret  =  0,  contenido  =  0 ; while  ( len  >  0 )  {  / * Lee tres en un fragmento. * /  contenido  =  0 ;  switch  ( read  =  ( len  > =  3  ?  3  :  len ))  {  caso  2 :  contenido  | =  ( uint32_t )  msg [ 2 ]  <<  16 ;  / * FALLTHRU * /  caso  1 :  contenido  | =  ( uint32_t )  msg [ 1]  <<  8 ;  / * FALLTHRU * /  case  0 :  contenido  | =  ( uint32_t )  msg [ 0 ];  }  len  - =  leer ;  msg  + =  leer ;    / * Obtiene un nuevo secreto por cada tres bytes. * /  seg  =  ( uint32_t )  secreto [ 2 ]  <<  16  |  ( uint32_t )  secreto [ 1 ]  <<  8  |  ( uint32_t )  secreto [ 0 ];  secreto  + =  3 ; / * El gran compresor. * /  for  ( bitCnt  =  0 ;  bitCnt  <  24 ;  bitCnt ++ )  {  / * Una dependencia de datos dura para 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 cambios. * /  seg  << =  1 ;  si  ( sec  & 0x01000000 )  seg  ^ =  0x0100001B ;  sec  & =  0x00ffffff ;  }  / * para cada bit en el mensaje * /  }  / * para cada 3 bytes en el mensaje * /  result [ 0 ]  ^ =  ret  &  0xff ;  resultado [ 1 ]  ^ =  ( ret  >>  8 )  &  0xff ;  resultado [ 2 ]  ^ =  ( ret  >>  16 )  &  0xff ; }

NH y RFC UMAC

NH

Las funciones de la familia de funciones hash sin nombre anterior ^{[ cita requerida ]} fuertemente universal usan n multiplica 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. ^[1] Para mayor velocidad, UMAC utiliza la familia de funciones hash NH. NH está diseñado específicamente para usar instrucciones SIMD y, por lo tanto, UMAC es la primera función MAC optimizada para SIMD. ^[2]

La siguiente familia de hash es universal: ^[2]${\displaystyle 2^{-w}}$

${\displaystyle \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.

Prácticamente, NH se realiza en números enteros sin signo. Todas las multiplicaciones son mod 2 ^ w , todas las adiciones mod 2 ^ w / 2 y todas las entradas como son un vector de medias palabras ( enteros de -bit). Luego, el algoritmo usará multiplicaciones, donde estaba el número de medias palabras en el vector. Por lo tanto, el algoritmo se ejecuta a una "tasa" de una multiplicación por palabra de entrada.${\displaystyle w/2=32}$${\displaystyle \lceil k/2\rceil }$${\displaystyle k}$

RFC 4418

RFC 4418 hace mucho para envolver NH para que sea un buen UMAC. La rutina general UHASH ("Función Hash Universal") produce una longitud variable de etiquetas, que corresponde al número de iteraciones (y la longitud total 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 (trozos de 1024 bytes -> hash de 8 bytes concatenados) usa 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, y 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 reordena para tomar una forma de:

Y = 0para (i = 0; i <t; i + = 8) hacer Y = Y + _64 ((M_ {i + 0} + _32 K_ {i + 0}) * _64 (M_ {i + 4} + _32 K_ {i + 4})) Y = Y + _64 ((M_ {i + 1} + _32 K_ {i + 1}) * _64 (M_ {i + 5} + _32 K_ {i + 5})) Y = Y + _64 ((M_ {i + 2} + _32 K_ {i + 2}) * _64 (M_ {i + 6} + _32 K_ {i + 6})) Y = Y + _64 ((M_ {i + 3} + _32 K_ {i + 3}) * _64 (M_ {i + 7} + _32 K_ {i + 7}))final para

Esta definición está diseñada para alentar a los programadores a usar instrucciones SIMD en la acumulación, ya que es probable que solo los datos con cuatro índices de distancia no se coloquen en el mismo registro SIMD y, por lo tanto, se multipliquen más rápido en forma masiva. En una máquina hipotética, simplemente podría traducirse a:

Montaje hipotético

movq  $ 0 ,  regY  ; Y = 0 movq  $ 0 ,  regI  ; i = 0 bucle: agregue  reg1 , regM , regI ; reg1 = M + yo agrego reg2 , regM , regI vldr.4x32 vec1 , reg1 ; cargar 4x32bit vals 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 agrega  regY ,  regY ,  reg3  ; regY = regY + reg3 agregar  regI ,  regI ,  $ 8 cmp  regI ,  regT jlt  loop

Ver también

• Poly1305 es otro MAC rápido basado en hash fuertemente universal.

Referencias

1. Thorup, Mikkel (2009). Hash de cadena para palpado 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 . Archivado (PDF) desde el original el 12 de octubre de 2013. , sección 5.3
2. Negro, 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".

Enlaces externos

• Ted Krovetz. "UMAC: Autenticación de mensajes rápida y probadamente segura" .

• "El uso de UMAC en el protocolo de capa de transporte SSH: draft-miller-secsh-umac-01.txt" . IETF . 2007-09-03.