UMAC

De Viquipèdia
Dreceres ràpides: navegació, cerca

A criptografia, un codi d'autenticació de missatges Segons hashing universal o UMAC és un tipus de codi d'autenticació de missatges (MAC) que es calcula escollint una funció de hash d'una classe de funcions de hash d'acord a algun procés secret (aleatori) i aplicant-la al missatge. El resum resultant o fingerprint es xifra per ocultar la identitat de la funció de hash utilitzada. Com amb qualsevol codi MAC, es pot utilitzar per verificar simultàniament tant la integritat de les dades com l'autenticitat del missatge. Un UMAC té força criptogràfica demostrable i comunament és bastant menys computacionalment intensiva que altres MACs.

Hashing Universal[modifica | modifica el codi]

Diguem que la funció de hash es tria d'una classe de funcions de hash H, que mapeja missatges en D, el conjunt de possibles resums de missatge. A aquest conjunt se l'anomena universal si, per a cada parell diferent de missatges, hi ha com a màxim|H|/|D|funcions que les mapean al mateix membre del Sr

Això significa que si un atacant vol reemplaçar un missatge amb un altre i, des del seu punt de vista, la funció de hash es va triar completament a l'atzar, la probabilitat que el UMAC no detecti la seva modificació és de com a màxim 1/|D|.

Aquesta definició, però, no és prou forta. Si els missatges possibles són 0 i 1, D ={0,1}, i H consisteix de l'operació identitat i la negació, aleshores H és universal. D'altra banda, si el resum del missatge es xifra mitjançant addició modular, l'atacant pot canviar el missatge i el resum al mateix temps, sense que el receptor s'assabenti.

Hashing universal forta[modifica | modifica el codi]

Una classe de funcions de hash H que sigui bona per utilitzar farà difícil la tasca d'un atacant d'endevinar el resum correcte d d'un missatge fals f després d'interceptar un missatge a amb un resum c . En altres paraules

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

ha de ser molt petit, preferentment 1/|D|.

<! - Say the combination of the hash function and the encryption function is chosen from a class M. We must require that for any two DISTINCT messages a and b and two (possibly equal) digests c and d , the number of members of M that map a to c and b to d must of the order|M|/|D|. -->

És fàcil construir una classe de funcions de hash quan D és un camp finit. Per exemple, si|D|es cosí, totes les operacions es prenen mòdul|D|. El missatge a es codifica com un vector a-dimensional sobre D (a 1 , a 2 ,.., a < sub> n ). Després, H té|D| n+1 membres, cadascú corresponent a un vector n+1- dimensional sobre D (h 0 , h 1 ,.., h n ). Si definim

 H (a) = h_0+\sum_{i = 1}^n h_ia_i

podem utilitzar les regles de probabilitat i combinatòria per demostrar que

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

Si xifrem apropiadament tots els resums (per exemple mitjançant one-time pad), un atacant no podrà obtenir res d'ells i la mateixa funció de hash podrà utilitzar per a totes les comunicacions entre les dues parts . Això pot ser veritat per xifrar ECB, perquè pot ser bastant probable que dos missatges produeixin el mateix valor de hash. Llavors, hauria de fer servir algun tipus de vector d'inicialització, conegut comunament com nonce. És pràctica habitual triar h 0 = f (nonce), on f també és secreta.

Noti's que tenint quantitats massives de poder de còmput no ajuda per res a l'atacant. Si el receptor limita la quantitat de falsificacions que accepta (esperant un temps inactiu quan detecta alguna),|D|pot ser 2 32 o menor.

Referències[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

  • Poly1305-AES, un altre MAC veloç, basat en hashing universal forta i en AES.