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 ${\mathrm{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\equiv ̸0(\mathrm{mod}16)$, llavors:

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

La clau secreta $r=(r[0],r[1],r[2],\dots ,r[15])$ està restringit a tenir els bytes $r[3],r[7],r[11],r[15]\in \{0,1,2,\dots ,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,\dots ,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$$\mathrm{Pr}[{\mathrm{Poly1305}}_r(m_1)-{\mathrm{Poly1305}}_r(m_2)\equiv d(\mathrm{mod}{2}^{128})]\le \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 $ϵ$ -quasi-Δ-universalitat acabada $\mathbb{Z}/2^{128}\mathbb{Z}$, o $ϵ$ -AΔU, on $ϵ=8\lceil L/16\rceil /2^{106}$ en aquest cas.