Poli1305

Poly1305 requiere una clave secreta de 16 bytes.${\displaystyle r}$y un${\displaystyle L}$-mensaje de bytes${\displaystyle m}$y devuelve un hash de 16 bytes.${\displaystyle \operatorname {Poly1305} _{r}(m)}$. Para ello, Poly1305: ^{[ 2 ] [ 1 ]}

1. Intérpretes${\displaystyle r}$como un entero de 16 bytes en formato little-endian .
2. Rompe el mensaje${\displaystyle m=(m[0],m[1],m[2],\dotsc ,m[L-1])}$en bloques consecutivos de 16 bytes.
3. Interpreta los bloques de 16 bytes como enteros little-endian de 17 bytes, añadiendo un byte 1 a cada bloque de 16 bytes, que se utilizarán como coeficientes de un polinomio.
4. Evalúa el polinomio en el punto${\displaystyle r}$módulo el primo${\displaystyle 2^{130}-5}$.
5. Reduce el resultado módulo${\displaystyle 2^{128}}$codificado en little-endian devuelve un hash de 16 bytes.

Los coeficientes${\displaystyle c_{i}}$del polinomio${\displaystyle c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r}$, dónde${\displaystyle q=\lceil L/16\rceil }$, son:

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

con la excepción de que, si${\displaystyle L\not \equiv 0{\pmod {16}}}$, entonces:

$${\displaystyle 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 llave secreta${\displaystyle r=(r[0],r[1],r[2],\dotsc ,r[15])}$está restringido a tener los bytes${\displaystyle r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}}$, es decir , tener sus cuatro bits superiores libres; y tener los bytes${\displaystyle r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}}$, es decir , tener sus dos bits inferiores libres. Por lo tanto, hay${\displaystyle 2^{106}}$distintos valores posibles de${\displaystyle r}$.

Si${\displaystyle s}$es una cadena secreta de 16 bytes interpretada como un entero little-endian, entonces

$${\displaystyle a:={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$$

se denomina autenticador del mensaje${\displaystyle m}$Si un remitente y un destinatario comparten la clave secreta de 32 bytes${\displaystyle (r,s)}$de antemano, elegido uniformemente al azar, entonces el remitente puede transmitir un mensaje autenticado${\displaystyle (a,m)}$Cuando el destinatario recibe un supuesto mensaje autenticado${\displaystyle (a',m')}$(que puede haber sido modificado en la transmisión por un adversario), pueden verificar su autenticidad probando si

$${\displaystyle a'\mathrel {\stackrel {?}{=}} {\bigl (}\operatorname {Poly1305} _{r}(m')+s{\bigr )}{\bmod {2}}^{128}.}$$ Sin conocimiento de${\displaystyle (r,s)}$, el adversario tiene probabilidad${\displaystyle 8\lceil L/16\rceil /2^{106}}$de encontrar alguno${\displaystyle (a',m')\neq (a,m)}$Eso pasará la verificación.

Sin embargo, la misma clave${\displaystyle (r,s)}$no debe reutilizarse para dos mensajes. Si el adversario se entera

$${\displaystyle {\begin{aligned}a_{1}&={\bigl (}\operatorname {Poly1305} _{r}(m_{1})+s{\bigr )}{\bmod {2}}^{128},\\a_{2}&={\bigl (}\operatorname {Poly1305} _{r}(m_{2})+s{\bigr )}{\bmod {2}}^{128},\end{aligned}}}$$

para${\displaystyle m_{1}\neq m_{2}}$ellos pueden restar

$${\displaystyle a_{1}-a_{2}\equiv \operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2}){\pmod {2^{128}}}}$$

y encontrar una raíz del polinomio resultante para recuperar una pequeña lista de candidatos para el punto de evaluación secreto.${\displaystyle r}$y desde ahí el panel secreto${\displaystyle s}$El adversario puede entonces utilizar esto para falsificar mensajes adicionales con alta probabilidad.

La propuesta original Poly1305-AES ^{[ 2 ]} utiliza la estructura Carter-Wegman ^{[ 4 ] [ 5 ]} para autenticar muchos mensajes tomando${\displaystyle a_{i}:=H_{r}(m_{i})+p_{i}}$ser el autenticador en el i- ésimo mensaje${\displaystyle m_{i}}$, dónde${\displaystyle H_{r}}$es una familia de hash universal y${\displaystyle p_{i}}$es un valor hash aleatorio uniforme independiente que sirve como una clave de un solo uso para ocultarlo. Poly1305-AES utiliza AES-128 para generar${\displaystyle p_{i}:=\operatorname {AES} _{k}(i)}$, dónde${\displaystyle i}$está codificado como un entero little-endian de 16 bytes.

Específicamente, una clave Poly1305-AES es un par de 32 bytes.${\displaystyle (r,k)}$de un punto de evaluación de 16 bytes${\displaystyle r}$, como se indicó anteriormente, y una clave AES de 16 bytes.${\displaystyle k}$El autenticador Poly1305-AES en un mensaje${\displaystyle m_{i}}$es

$${\displaystyle a_{i}:={\bigl (}\operatorname {Poly1305} _{r}(m_{i})+\operatorname {AES} _{k}(i){\bigr )}{\bmod {2}}^{128},}$$

donde las cadenas de 16 bytes y los enteros se identifican mediante la codificación little-endian. Tenga en cuenta que${\displaystyle r}$se reutiliza entre mensajes.

Sin conocimiento de${\displaystyle (r,k)}$, el adversario tiene una baja probabilidad de falsificar cualquier mensaje autenticado que el destinatario acepte como genuino. Supongamos que el adversario ve${\displaystyle C}$mensajes e intentos autenticados${\displaystyle D}$falsificaciones, y puede distinguir${\displaystyle \operatorname {AES} _{k}}$de una permutación aleatoria uniforme con ventaja en la mayoría de los casos${\displaystyle \delta }$. (A menos que AES esté roto,${\displaystyle \delta }$es muy pequeña.) La probabilidad de éxito del adversario en una sola falsificación es como máximo:

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

El número de mensaje${\displaystyle i}$Nunca debe repetirse con la misma clave.${\displaystyle (r,k)}$Si es así, el adversario puede recuperar una pequeña lista de candidatos para${\displaystyle r}$y${\displaystyle \operatorname {AES} _{k}(i)}$, como con el autenticador de un solo uso, y utilizarlo para falsificar mensajes.

El cifrado autenticado NaCl utiliza un número de mensaje.crypto_secretbox_xsalsa20poly1305${\displaystyle i}$con el cifrado de flujo XSalsa20 para generar un flujo de claves por mensaje , cuyos primeros 32 bytes se toman como una clave Poly1305 de un solo uso.${\displaystyle (r_{i},s_{i})}$y el resto se utiliza para cifrar el mensaje. Luego utiliza Poly1305 como autenticador de un solo uso para el texto cifrado del mensaje. ^{[ 6 ]}

ChaCha20-Poly1305 utiliza los primeros 32 bytes de la salida del cifrado de flujo ChaCha para generar una clave Poly1305 de un solo uso, descarta los siguientes 32 bytes y utiliza el resto para cifrar el mensaje. ^{[ 8 ]} También se ha descrito XChaCha20-Poly1305, que utiliza XChaCha en lugar de ChaCha o XSalsa20. ^{[ 10 ]}

Con un autenticador de un solo uso${\displaystyle a={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$la probabilidad de éxito del adversario en cualquier intento de falsificación${\displaystyle (a',m')}$en un mensaje${\displaystyle m'}$de hasta${\displaystyle L}$bytes es:

$${\displaystyle {\begin{aligned}\Pr[&a'=\operatorname {Poly1305} _{r}(m')+s\mathrel {\mid } a=\operatorname {Poly1305} _{r}(m)+s]\\&=\Pr[a'=\operatorname {Poly1305} _{r}(m')+a-\operatorname {Poly1305} _{r}(m)]\\&=\Pr[\operatorname {Poly1305} _{r}(m')-\operatorname {Poly1305} _{r}(m)=a'-a]\\&\leq 8\lceil L/16\rceil /2^{106}.\end{aligned}}}$$

Aquí la aritmética dentro de la${\displaystyle \Pr[\cdots ]}$se considera que está en${\displaystyle \mathbb {Z} /2^{128}\mathbb {Z} }$por simplicidad.

Para NaCl crypto_secretbox_xsalsa20poly1305 y ChaCha20-Poly1305 , la probabilidad de éxito del adversario en la falsificación es la misma para cada mensaje de forma independiente que para un autenticador de un solo uso, más la ventaja distintiva del adversario.${\displaystyle \delta }$contra XSalsa20 o ChaCha como funciones pseudoaleatorias utilizadas para generar la clave por mensaje. En otras palabras, la probabilidad de que el adversario tenga éxito en una sola falsificación después${\displaystyle D}$intentos de mensajes hasta${\displaystyle L}$bytes es como máximo:

$${\displaystyle \delta +{\frac {8D\lceil L/16\rceil }{2^{106}}}.}$$

La seguridad de Poly1305-AES contra la falsificación se deriva de la estructura Carter - Wegman - Shoup, que instancia un autenticador Carter - Wegman con una permutación para generar el bloc de notas por mensaje. ^{[ 12 ]} Si un adversario ve${\displaystyle C}$mensajes e intentos autenticados${\displaystyle D}$falsificaciones de mensajes de hasta${\displaystyle L}$bytes, y si el adversario tiene ventaja distintiva como máximo${\displaystyle \delta }$frente a AES-128 como una permutación pseudoaleatoria , entonces la probabilidad de que el adversario tenga éxito en cualquiera de las${\displaystyle D}$Las falsificaciones son como máximo: ^{[ 2 ]}

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

Por ejemplo, suponiendo que los mensajes son paquetes de hasta 1024 bytes; que el atacante ve 2⁶⁴ ^mensajes autenticados con una clave Poly1305-AES; que el atacante intenta la asombrosa cantidad de 2⁷⁵ ^{falsificaciones} ; y que el atacante no puede romper AES con una probabilidad superior a δ; entonces, con una probabilidad de al menos 0,999999 − δ, los 2⁷⁵ mensajes ^son rechazados.