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 utilizando 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 (a julio de 2019) estandarizar el protocolo como parte de ISO/IEC 29167-20, [3] un estándar para proteger 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:
La operación fundamental del Borrador Algebraico es una función unidireccional llamada E-multiplicación. Dada una matriz, una permutación, un generador de Artin en el grupo de trenzas y valores T, se aplica la E-multiplicación convirtiendo el generador en una matriz de Burau coloreada y una permutación de trenzas, , aplicando la permutación y los valores T, y luego multiplicando las matrices y las permutaciones. El resultado de la E-multiplicación es en sí mismo un par de matriz y permutación: .
El siguiente ejemplo ilustra cómo establecer una clave. Supongamos que Alice quiere establecer una clave compartida con Bob , pero el único canal disponible puede estar interceptado por un tercero. Inicialmente, Alice y Bob deben ponerse de acuerdo sobre 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), donde es un polinomio seleccionado aleatoriamente de la matriz de semillas y una trenza, que es un conjunto seleccionado aleatoriamente de conjugados e inversos elegidos entre los parámetros del conjunto de claves (A para Alice y B para Bob, donde (para Alice) ).
A partir de su material de clave privada, Alice y Bob calculan cada uno su clave pública y donde, por ejemplo, , es decir, el resultado de la E-multiplicación 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 y Bob calcula . El secreto compartido es el par matriz/permutación , que es igual a . Los secretos compartidos son iguales porque los conjuntos conjugados y se eligen para conmutar y tanto Alice como Bob usan la misma matriz semilla y los mismos valores T .
La única información sobre su clave privada que Alice expone inicialmente es su clave pública. Por lo tanto, ninguna otra parte aparte de Alice puede determinar la clave privada de Alice, a menos que esa parte pueda resolver el problema de búsqueda por separación por conjugación simultánea del grupo Braid. La clave privada de Bob es igualmente segura. Ninguna otra parte aparte de Alice o Bob puede calcular el secreto compartido, a menos que esa parte pueda resolver el problema de Diffie-Hellman .
Las claves públicas son estáticas (y confiables, por ejemplo, a través de un certificado) o efímeras. Las claves efímeras son temporales y no necesariamente autenticadas, por lo que si se desea la autenticación, se deben obtener garantías de autenticidad por otros medios. La autenticación es necesaria para evitar ataques de intermediarios . Si una de las claves públicas de Alice o Bob es estática, se frustran los ataques de intermediarios. Las claves públicas estáticas no proporcionan ni confidencialidad hacia adelante ni resiliencia a la suplantación de identidad por vulneración de claves, entre otras propiedades de seguridad avanzadas. Los titulares de claves privadas estáticas deben validar la otra clave pública y deben aplicar una función de derivación de clave segura al secreto compartido Diffie-Hellman sin procesar para evitar filtrar información sobre la clave privada estática.
La seguridad de AE se basa en el Problema de Búsqueda de Conjugación Simultánea Generalizada (GSCSP) [4] dentro del grupo trenzado . Este es un problema difícil distinto y distinto 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 grupo trenzado . [5] Incluso si el CSP se rompe de manera uniforme (lo que no se ha hecho hasta la fecha), no se sabe 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 se eligen o de forma aleatoria. [6] Los autores de Algebraic Eraser continuaron con una versión preliminar sobre cómo elegir parámetros que no sean propensos al ataque. [7] Ben-Zvi, Blackburn y Tsaban mejoraron el primer ataque para convertirlo en uno que, según afirman los autores, puede romper los parámetros de seguridad publicitados (que se dice que proporcionan 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 se pueden separar, rompiendo el sistema. [10] Este ataque fue refutado por Gunnells, al demostrar que las trenzas conjugadoras de tamaño adecuado no se pueden separar. [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, incluida la suplantación de una etiqueta de destino con una cantidad insignificante de tiempo y memoria y la recuperación completa de la clave privada que requiere 2,49 de tiempo y 2,48 de memoria. [11] Atkins y Goldfeld respondieron que agregar un hash o un código de autenticación de mensajes al borrador del protocolo derrota estos ataques. [12]
