Poly1305

Poly1305 és una família de hash universal dissenyada per Daniel J. Bernstein per utilitzar-la en criptografia.

Xifratge ChaCha20-Poly1305

Com amb qualsevol família de hash universal, Poly1305 es pot utilitzar com a codi d'autenticació de missatges d'una sola vegada per autenticar un missatge únic mitjançant una clau secreta compartida entre remitent i destinatari, de manera similar a com es pot utilitzar un bloc d'un sol ús. per ocultar el contingut d'un sol missatge mitjançant una clau secreta compartida entre remitent i destinatari.

Originalment, Poly1305 es va proposar com a part de Poly1305-AES, un autenticador Carter – Wegman que combina el hash Poly1305 amb AES-128 per autenticar molts missatges mitjançant una única clau curta i números de missatge diferents. Poly1305 es va aplicar posteriorment amb una clau d'un sol ús generada per a cada missatge mitjançant XSalsa20 al xifratge autenticat NaCl crypto_secretbox_xsalsa20poly1305, i després utilitzant ChaCha al xifratge autenticat ChaCha20-Poly1305 desplegat en TLS. l'internet.

Descripció

Definició de Poly1305

Poly1305 pren una clau secreta de 16 bytes $r$ i un $L$ missatge -byte $m$ i retorna un hash de 16 bytes $\operatorname {Poly1305} _{r}(m)$. Per fer-ho, Poly1305:

1. Interpreta com un nombre enter de 16 bytes little-endian.
2. Trenca el missatge en fragments consecutius de 16 bytes.
3. Interpreta els fragments de 16 bytes com a nombres enters little-endians de 17 bytes afegint un 1 byte a cada fragment de 16 bytes, per utilitzar-los com a coeficients d'un polinomi.
4. Avalua el polinomi en el punt mòdul el primer.
5. Redueix el mòdul del resultat codificat en little-endian retorna un hash de 16 bytes.

Els coeficients $c_{i}$ del polinomi $c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r$, on $q=\lceil L/16\rceil$, són:

$$c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},$$

amb l'excepció que, si $L\not \equiv 0{\pmod {16}}$, llavors:

$$c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[L-1]+2^{8(L{\bmod {1}}6)}.$$

La clau secreta $r=(r[0],r[1],r[2],\dotsc ,r[15])$ està restringit a tenir els bytes $r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}$, és a dir, tenir els seus quatre bits principals clars; i tenir els bytes $r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}$, és a dir, per tenir els seus dos bits inferiors clars. Així n'hi ha $2^{106}$ diferents valors possibles de $r$.

Seguretat

La seguretat de Poly1305 i els seus derivats contra la falsificació es deu a la seva probabilitat de diferència limitada com a família hash universal : si $m_{1}$ i $m_{2}$ són missatges de fins a $L$ bytes cadascun, i $d$ és qualsevol cadena de 16 bytes interpretada com un nombre enter little-endian, doncs

$$\Pr[\operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2})\equiv d{\pmod {2^{128}}}]\leq {\frac {8\lceil L/16\rceil }{2^{106}}},$$

on $r$ és una clau aleatòria Poly1305 uniforme.  : Teorema 3.3, pàg. 8 

Aquesta propietat de vegades s'anomena $\epsilon$ -quasi-Δ-universalitat acabada $\mathbb {Z} /2^{128}\mathbb {Z}$, o $\epsilon$ -AΔU, on $\epsilon =8\lceil L/16\rceil /2^{106}$ en aquest cas.