Algebraic Eraser ( AE ) [nota 1] es un protocolo de acuerdo de clave anónimo 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 encriptar 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 (en 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 .
Parámetros del conjunto de teclas
Antes de que dos partes puedan establecer una clave, primero deben acordar un conjunto de parámetros, llamados parámetros del conjunto de claves. Estos parámetros comprenden:
- , el número de hebras de la trenza,
- , el tamaño del campo finito ,
- , la matriz semilla inicial NxN en ,
- , un conjunto de elementos en el campo finito (también llamados valores T), y
- un conjunto de conjugados en el grupo de trenzas diseñado para conmutar entre sí.
E-multiplicación
La operación fundamental del Borrador Algebraico es una función unidireccional llamada E-multiplicación. Dada una matriz, permutación, un generador de Artin en el grupo de trenzas, y los valores T, se aplica la multiplicación E convirtiendo el generador en una matriz de Burau coloreada y una permutación de trenza,, aplicando la permutación y los valores T, y luego multiplicando las matrices y las permutaciones. La salida de la multiplicación E es en sí misma una matriz y un par de permutación:.
Protocolo de establecimiento de claves
El siguiente ejemplo ilustra cómo hacer un establecimiento clave. Suponga que Alice quiere establecer una clave compartida con Bob , pero el único canal disponible puede ser espiado 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 consta de una clave privada (por ejemplo, en el caso de Alice) dónde es un polinomio seleccionado al azar de la matriz semilla y una trenza, que es un conjunto seleccionado al azar de conjugados e inversos elegidos de los parámetros del conjunto de teclas (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 de 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 son elegidos para viajar y tanto Alice como Bob usan la misma matriz de semillas y 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 que no sea Alice puede determinar la clave privada de Alice, a menos que esa parte pueda resolver el problema de la búsqueda de separación conjugada simultánea de Braid Group. La clave privada de Bob es igualmente segura. Ninguna otra parte que no sea Alice o Bob puede calcular el secreto compartido, a menos que esa parte pueda resolver el problema Diffie-Hellman .
Las claves públicas son estáticas (y de confianza, digamos a través de un certificado) o efímeras. Las claves efímeras son temporales y no necesariamente están autenticadas, por lo que si se desea la autenticación, las garantías de autenticidad deben obtenerse por otros medios. La autenticación es necesaria para evitar ataques man-in-the-middle . Si una de las claves públicas de Alice o Bob es estática, los ataques de intermediario se frustran. Las claves públicas estáticas no brindan secreto hacia adelante ni resistencia a la suplantación de clave comprometida, 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.
Seguridad
La seguridad de AE se basa en el problema de búsqueda conjugada simultánea generalizada (GSCSP) [4] dentro del grupo de trenzas . Este es un problema difícil distinto y distinto del problema de búsqueda conjugada (CSP), que ha sido el problema central en lo que se llama criptografía de grupo de trenzas . [5] Incluso si la CSP se rompe uniformemente (lo que no se ha hecho hasta la fecha), no se sabe cómo esto facilitaría una ruptura del GSCSP.
Ataques conocidos
El primer ataque de Kalka, Teicher y Tsaban muestra una clase de teclas débiles cuando o se eligen al azar. [6] Los autores de Algebraic Eraser siguieron con un preprint sobre cómo elegir parámetros que no son 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 publicitados (que se dice que brindan seguridad de 128 bits) usando 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 de conjugador demasiado corta pueden separarse, rompiendo el sistema. [10] Este ataque fue refutado por Gunnells, al mostrar que las trenzas conjugadoras del 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 por aire ISO / IEC 29167-20, incluida la suplantación de una etiqueta de destino con una cantidad insignificante de tiempo y memoria. y 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 código de autenticación de mensaje o hash al borrador del protocolo anula estos ataques. [12]
Ver también
- Intercambio de claves Anshel-Anshel-Goldfeld
- Criptografía basada en grupos
- Criptografía no conmutativa
Notas
- ^ También conocido como protocolo de acuerdo de clave Burau coloreado ( CBKAP ), protocolo de acuerdo de clave Anshel-Anshel-Goldfeld-Lemieux , protocolo de acuerdo clave de Borrador algebraico ( AEKAP ) y Borrador algebraico Diffie-Hellman ( AEDH ).
Referencias
- ^ Anshel I, Anshel M, Goldfeld D , Acuerdo clave de Lemieux S. , El borrador algebraico y métodos algebraicos de criptografía ligera en criptografía, Contemp. Math., Vol. 418, Amer. Matemáticas. Soc., Providence, RI, 2006, págs. 1-34.
- ^ Dan Goodin (17 de noviembre de 2015). "Por qué Algebraic Eraser puede ser el criptosistema más riesgoso del que nunca has oído hablar" . Ars Technica .
- ^ ISO / IEC AWI 29167-20 - Tecnología de la información - Técnicas de identificación automática y captura de datos - Parte 20: Servicios de seguridad Crypto suite Algebraic Eraser para comunicaciones de interfaz aérea. Borrador de trabajo.
- ^ a b Gunnells PE. Sobre el criptoanálisis del problema de búsqueda conjugada simultánea generalizada y la seguridad del borrador algebraico . 2011
- ^ Dehornoy, Patrick (2004). "Criptografía basada en trenzas". Teoría de grupos, estadística y criptografía . Matemáticas contemporáneas. 360 . Providence, RI: Sociedad Matemática Estadounidense. págs. 5-33. CiteSeerX 10.1.1.10.1759 . doi : 10.1090 / conm / 360/06566 . ISBN 9780821834442. Señor 2105432 .
- ^ Kalka A, Teicher M , Tsaban B (2012). "Expresiones breves de permutaciones como productos y criptoanálisis del borrador algebraico". Avances en Matemática Aplicada . 49 (1): 57–76. arXiv : 0804.0629 . Código bibliográfico : 2008arXiv0804.0629K . doi : 10.1016 / j.aam.2012.03.001 . S2CID 10040122 .
- ^ Goldfield D , Gunnels PE. Derrotando el ataque de álgebra lineal Kalka-Teicher-Tsaban en el borrador algebraico , 2012
- ^ Ben-Zvi, A, Blackburn, Simon R, Tsaban B. (arXiv: 1511.03870 [math.GR]) Un criptoanálisis práctico del borrador algebraico , CRYPTO 2016.
- ^ Anshel I, Atkins D , Goldfeld D , Gunnels PE. (arXiv: 1601.04780 [cs.CR]) Derrotando el ataque de Ben-Zvi, Blackburn y Tsaban en el borrador algebraico , 2016
- ^ Myasnikov AD, Ushakov A. Criptoanálisis del protocolo de acuerdo clave Anshel-Anshel-Goldfeld-Lemieux , 2008
- ^ Simon R. Blackburn; MJB Robshaw (9 de junio de 2016). "Sobre la seguridad del protocolo de autenticación de etiquetas de borrador algebraico". Criptografía aplicada y seguridad de la red . Apuntes de conferencias en informática. 9696 . págs. 3-17. arXiv : 1602.00860 . doi : 10.1007 / 978-3-319-39555-5_1 . ISBN 978-3-319-39554-8. S2CID 371335 .Conferencia internacional sobre criptografía aplicada y seguridad de redes 2016. Volumen 9696 de la serie Lecture Notes in Computer Science pp. 3-17. ( Preimpresión )
- ^ Derek Atkins ; Dorian Goldfeld (25 de febrero de 2016). "Abordar el borrador algebraico Diffie - Protocolo de Hellman Over-the-Air" . Cite journal requiere
|journal=
( ayuda )Archivo ePrint de criptología IACR .
enlaces externos
- Página de inicio de SecureRF