UMAC

En criptografia, un còdic d'autenticació de mensages basat en hashing universal o UMAC és un tipo de còdic d'autenticació de mensages (MAC) que es calcula elegint una funció de hash d'una classe de funcions de hash d'acort a algun procés secret (aleatori) i aplicant-li-la al mensage. El resum resultant o fingerprint es sifra per a ocultar l'identitat de la funció de hash usada. Com en qualsevol còdic MAC, pot usar-se per a verificar simultàneament tant l'integritat de les senyes com l'autenticitat del mensage. Un UMAC té força criptogràfica demostradora i comunament és prou menys computacionalment intensiva que atres MACs. A diferència dels MAC tradicionals, que són serializables, UMAC es pot eixecutar en paralel. Per lo tant, a mida que les màquines continuen oferint més capacitats de processament paralel, la velocitat d'implementació de UMAC aumentarà.

Hashing universal

Digam que la funció de hash s'elegix d'una classe de funcions de hash H, que mapea mensages en D, el conjunt de possibles resums de mensage. A este conjunt li'l crida universal si, per a cada parell distint de mensages, hi ha com a màxim |H|/|D| funcions que les mapean al mateix membre de D.

Açò significa que si un atacant vol reemplaçar un mensage en un atre i, des del seu punt de vista, la funció de hash es va elegir completament a l'encert, la provabilitat de que el UMAC no detecte la seua modificació és de com a molt 1/|D|.

Esta definició, no obstant, no és lo suficientment forta. Si els mensages possibles són 0 i 1, D={0,1}, i H consistix de l'operació identitat i la negació, llavors H és universal. Per un atre costat, si el resum del mensage se sifra per mig d'adició modular, l'atacant pot canviar el mensage i el resum al mateix temps, sense que el receptor s'entere.

Hashing universal fort

Una classe de funcions de hash H que siga bona per a usar farà difícil la tasca d'un atacant d'endevinar el resum correcte d d'un mensage fals f després d'interceptar un mensage a en un resum c. En atres paraules

$P{r}_{h\in H}[h(f)=d|h(a)=c]$

deu ser molt menut, preferentment 1/|D|.

És fàcil construir una classe de funcions de hash quan D és un camp finit. Per eixemple, si |D| és primer, totes les operacions es prenen mòdul |D|. El mensage a es codifica com un vector n-dimensional sobre D (a₁,a₂,..,a_n). Després, H té |D|ⁿ⁺¹ membres, cada cual corresponent a un vector n+1-dimensional sobre D (h₀,h₁,..,h_n). Si definim

$h(a)=h_0+\sum _{i=1}^n{h}_i{a}_i$

podem usar les regles de provabilitat i combinatòria per a demostrar que

$P{r}_{h\in H}[h(f)=d|h(a)=c]=\frac{1}{|D|}$

Si sifrem apropiadament tots els resums (per eixemple per mig d'one-clave pad), un atacant no podrà obtindre res d'ells i la mateixa funció de hash podrà usar-se para totes les comunicacions entre les dos parts. Açò pugues no ser veritat per a sifrat ECB, perque pot ser prou provable que dos mensages produïxquen el mateix valor de hash. Llavors, deuria usar-se algun tipo de vector d'inicialisació, conegut comunament com nonce. És pràctica habitual elegir h₀=f(nonce), a on f també és secreta.

Note's que tenint cantitats massives de poder de còmput no ajuda per a res a l'atacant. Si el receptor llimita la cantitat de falsificacions que accepta (esperant un temps inactiu quan detecta alguna), |D| pot ser 2³² o menor.

Referències

• UMAC ha segut aprovada per l'IETF com una RFC d'informació. És ràpit i basat en l'AES.

Vore també

• Poly1305-AES, un atre MAC veloç, basat en hashing universal fort i en AES.