Borrador algebraico

Algebraic Eraser ( AE ) ^{[ nota 1 ]} es un protocolo de acuerdo de clave anónima que permite a dos partes, cada una con un par de claves pública-privada AE, establecer un secreto compartido a través de un canal inseguro . ^{[ 1 ]} Este secreto compartido puede usarse directamente como clave o para derivar otra clave que luego puede usarse para cifrar comunicaciones posteriores usando un cifrado de clave simétrica . Algebraic Eraser fue desarrollado por Iris Anshel, Michael Anshel, Dorian Goldfeld y Stephane Lemieux. SecureRF posee patentes que cubren el protocolo ^{[ 2 ]} e intentó sin éxito (hasta julio de 2019) estandarizar el protocolo como parte de ISO/IEC 29167-20, ^{[ 3 ]} un estándar para asegurar dispositivos de identificación por radiofrecuencia y redes de sensores inalámbricos .

Antes de que dos partes puedan establecer una clave, primero deben acordar un conjunto de parámetros, denominados parámetros del conjunto de claves. Estos parámetros comprenden:

• ${\displaystyle N}$, el número de hebras en la trenza,
• ${\displaystyle q}$, el tamaño del campo finito${\displaystyle \mathbb {F} _{q}}$,
• ${\displaystyle M_{*}}$, la matriz semilla NxN inicial en${\displaystyle \mathbb {F} _{q}}$,
• ${\displaystyle \mathrm {T} }$, un conjunto de${\displaystyle N}$elementos en el campo finito${\displaystyle \mathbb {F} _{q}}$(también llamados valores T), y
• ${\displaystyle A,B}$un conjunto de conjugados en el grupo de trenzas diseñados para conmutar entre sí.

La operación fundamental del Borrador Algebraico es una función unidireccional llamada multiplicación E. Dada una matriz, una permutación y un generador de Artin.${\displaystyle \beta }$en el grupo de trenzas y valores T, se aplica la multiplicación E convirtiendo el generador en una matriz de Burau coloreada y permutación de trenzas,${\displaystyle (CB(\beta ),\sigma _{\beta })}$, aplicando la permutación y los valores T, y luego multiplicando las matrices y las permutaciones. El resultado de la multiplicación E es en sí mismo un par de matriz y permutación:${\displaystyle (M',\sigma ')=(M,\sigma _{0})*(CB(\beta ),\sigma _{\beta })}$.

El siguiente ejemplo ilustra cómo establecer una clave. Supongamos que Alice quiere establecer una clave compartida con Bob , pero el único canal disponible podría ser interceptado por un tercero. Inicialmente, Alice y Bob deben acordar los parámetros del conjunto de claves que utilizarán.

Cada parte debe tener un par de claves derivado del conjunto de claves, que consiste en una clave privada (por ejemplo, en el caso de Alice)${\displaystyle (m_{A},\mathrm {B} _{a})}$dónde${\displaystyle m_{A}}$es un polinomio seleccionado aleatoriamente de la matriz semilla${\displaystyle m_{A}=\sum _{i=0}^{N-1}{a_{i}M_{*}^{i}}}$y una trenza, que es un conjunto seleccionado aleatoriamente de conjugados e inversos elegidos de los parámetros del conjunto clave (A para Alice y B para Bob, donde (para Alice)${\displaystyle \mathrm {B} _{a}=\prod _{i=1}^{k}A_{i}^{\pm 1}}$).

A partir de su material de clave privada, Alice y Bob calculan cada uno su clave pública.${\displaystyle (Pub_{A},\sigma _{a})}$y${\displaystyle (Pub_{B},\sigma _{b})}$donde, por ejemplo,${\displaystyle (Pub_{A},\sigma _{a})=(m_{A},id)*b_{a}}$, es decir, el resultado de la multiplicación E de la matriz privada y la permutación identidad con la trenza privada.

Cada parte debe conocer la clave pública de la otra parte antes de la ejecución del protocolo.

Para calcular el secreto compartido, Alice calcula${\displaystyle (S_{ab},\sigma _{ab})=(m_{A}Pub_{B},\sigma _{b})*\mathrm {B} _{a}}$y Bob calcula${\displaystyle (S_{ba},\sigma _{ba})=(m_{B}Pub_{A},\sigma _{a})*\mathrm {B} _{b}}$El secreto compartido es el par matriz/permutación.${\displaystyle (S_{ab},\sigma _{ab})}$, lo cual es igual a${\ Displaystyle (S_ {ba}, \ sigma _ {ba})}$Los secretos compartidos son iguales porque los conjuntos conjugados${\displaystyle A}$y${\displaystyle B}$son elegidos para desplazarse diariamente y tanto Alice como Bob utilizan la misma matriz semilla.${\displaystyle M_{*}}$y valores T${\displaystyle \mathrm {T} }$.

La única información sobre su clave privada que Alice expone inicialmente es su clave pública. Por lo tanto, nadie más que Alice puede determinar la clave privada de Alice, a menos que pueda resolver el problema de búsqueda de separación de conjugación simultánea de Braid Group. La clave privada de Bob es igualmente segura. Nadie más que Alice o Bob puede calcular el secreto compartido, a menos que pueda resolver el problema de Diffie-Hellman .

Las claves públicas pueden ser estáticas (y de confianza, por ejemplo, mediante un certificado) o efímeras. Las claves efímeras son temporales y no necesariamente autenticadas, por lo que, si se requiere autenticación, se deben obtener garantías de autenticidad por otros medios. La autenticación es necesaria para evitar ataques de intermediario (man-in-the-middle) . Si una de las claves públicas de Alice o Bob es estática, se frustran los ataques de intermediario. Las claves públicas estáticas no proporcionan ni confidencialidad directa ni resistencia a la suplantación de identidad por compromiso de clave, entre otras propiedades de seguridad avanzadas. Los titulares de claves privadas estáticas deben validar la otra clave pública y aplicar una función de derivación de clave segura al secreto compartido Diffie-Hellman original para evitar la filtración de información sobre la clave privada estática.

La seguridad de AE ​​se basa en el Problema Generalizado de Búsqueda Simultánea de Conjugación (GSCSP) ^{[ 4 ]} dentro del grupo de trenzas . Este es un problema difícil distinto y diferente del Problema de Búsqueda de Conjugación (CSP), que ha sido el problema difícil central en lo que se denomina criptografía de grupos de trenzas . ^{[ 5 ]} Incluso si el CSP se rompiera de manera uniforme (lo cual no ha ocurrido hasta la fecha), se desconoce cómo esto facilitaría una ruptura del GSCSP.

El primer ataque de Kalka, Teicher y Tsaban muestra una clase de claves débiles cuando${\displaystyle M_{*}}$o${\displaystyle m_{A}}$se eligen aleatoriamente. ^{[ 6 ]} Los autores de Algebraic Eraser publicaron posteriormente una preimpresión sobre cómo elegir parámetros que no sean propensos al ataque. ^{[ 7 ]} Ben-Zvi, Blackburn y Tsaban mejoraron el primer ataque en uno que, según los autores, puede romper los parámetros de seguridad publicados (que afirman proporcionar seguridad de 128 bits) utilizando menos de 8 horas de CPU y menos de 64 MB de memoria. ^{[ 8 ]} Anshel, Atkins y Goldfeld respondieron a este ataque en enero de 2016. ^{[ 9 ]}

Un segundo ataque de Myasnikov y Ushakov, publicado como preimpresión, muestra que los conjugados elegidos con una trenza conjugadora demasiado corta pueden separarse, rompiendo el sistema. ^{[ 10 ]} Este ataque fue refutado por Gunnells, al demostrar que las trenzas conjugadoras de tamaño adecuado no pueden separarse. ^{[ 4 ]}

En 2016, Simon R. Blackburn y Matthew JB Robshaw publicaron una serie de ataques prácticos contra el borrador de enero de 2016 del protocolo inalámbrico ISO/IEC 29167-20, incluyendo la suplantación de una etiqueta objetivo con una cantidad insignificante de tiempo y memoria y la recuperación completa de la clave privada que requiere 2 ⁴⁹ tiempo y 2 ⁴⁸ memoria. ^{[ 11 ]} Atkins y Goldfeld respondieron que agregar un hash o un código de autenticación de mensajes al borrador del protocolo frustra estos ataques. ^{[ 12 ]}

• Intercambio de claves Anshel-Anshel-Goldfeld
• Criptografía basada en grupos
• Criptografía no conmutativa

• Página principal de SecureRF