Solo hash de curva elíptica

El algoritmo de hash de curva elíptica únicamente (ECOH) se presentó como candidato para SHA-3 en la competencia de funciones hash del NIST . Sin embargo, fue rechazado al comienzo de la competencia debido a que se encontró un segundo ataque de preimagen .

El ECOH se basa en el algoritmo hash MuHASH , que aún no ha sido atacado con éxito . Sin embargo, MuHASH es demasiado ineficiente para su uso práctico y se tuvieron que realizar cambios. La principal diferencia es que donde MuHASH aplica un oráculo aleatorio ^{[ aclaración necesaria ]} , ECOH aplica una función de relleno . Suponiendo oráculos aleatorios, encontrar una colisión en MuHASH implica resolver el problema del logaritmo discreto . MuHASH es, por lo tanto, un hash demostrablemente seguro , es decir, sabemos que encontrar una colisión es al menos tan difícil como algún problema matemático conocido.

ECOH no utiliza oráculos aleatorios y su seguridad no está estrictamente relacionada directamente con el problema del logaritmo discreto, pero aún así se basa en funciones matemáticas. ECOH está relacionado con el problema de Semaev de encontrar soluciones de bajo grado para las ecuaciones polinómicas de suma sobre un cuerpo binario, llamado Problema de Polinomio de Suma . Hasta ahora no se ha dado un algoritmo eficiente para resolver este problema. Aunque no se ha demostrado que el problema sea NP-hard , se supone que tal algoritmo no existe. Bajo ciertas suposiciones, encontrar una colisión en ECOH también puede verse como una instancia del problema de suma de subconjuntos . Además de resolver el Problema de Polinomio de Suma, existe otra forma de encontrar segundas preimágenes y, por lo tanto, colisiones, el ataque de cumpleaños generalizado de Wagner .

ECOH es un buen ejemplo de función hash que se basa en funciones matemáticas (con el enfoque de seguridad demostrable ) en lugar de en la clásica mezcla ad hoc de bits para obtener el hash.

Dado , ECOH divide el mensaje en bloques . Si el último bloque está incompleto, se rellena con un solo 1 y luego con la cantidad apropiada de 0. Sea además una función que asigna un bloque de mensaje y un entero a un punto de curva elíptica. Luego, utilizando la asignación , cada bloque se transforma en un punto de curva elíptica y estos puntos se suman con dos puntos más. Un punto adicional contiene el relleno y depende solo de la longitud del mensaje. El segundo punto adicional depende de la longitud del mensaje y del XOR de todos los bloques de mensajes. El resultado se trunca para obtener el hash .${\estilo de visualización n}$${\estilo de visualización M}$${\estilo de visualización n}$${\displaystyle M_{0},\ldots ,M_{n-1}}$${\estilo de visualización P}$${\estilo de visualización P}$$Estilo de visualización P_{i}}$$Estilo de visualización X_{1}$$Estilo de visualización X_{2}$${\estilo de visualización H}$

${\displaystyle {\begin{aligned}P_{i}&{}:=P(M_{i},i)\\X_{1}&{}:=P'(n)\\X_{2}&{}:=P^{*}(M_{i},n)\\Q&{}:=\sum _{i=0}^{n-1}P_{i}+X_{1}+X_{2}\\R&{}:=f(Q)\end{aligned}}}$

Los dos puntos adicionales se calculan mediante y . suma todos los puntos de la curva elíptica y los dos puntos adicionales. Finalmente, el resultado se pasa a través de una función de transformación de salida f para obtener el resultado hash . Para leer más sobre este algoritmo, consulte "ECOH: el hash de curva elíptica únicamente".${\estilo de visualización P'}$$Estilo de visualización P*$${\estilo de visualización Q}$${\estilo de visualización R}$

Se propusieron cuatro algoritmos ECOH, ECOH-224, ECOH-256, ECOH-384 y ECOH-512. El número representa el tamaño del resumen del mensaje. Se diferencian en la longitud de los parámetros, el tamaño del bloque y en la curva elíptica utilizada. Los dos primeros utilizan la curva elíptica B-283: , con parámetros (128, 64, 64). ECOH-384 utiliza la curva B-409: , con parámetros (192, 64, 64). ECOH-512 utiliza la curva B-571: , con parámetros (256, 128, 128). Puede realizar hashes en mensajes de longitud de bits de hasta .$Estilo de visualización X^{283}+X^{12}+X^{7}+X^{5}+1}$$Estilo de visualización X^{409}+X^{87}+1}$$Estilo de visualización X^{571}+X^{10}+X^{5}+X^{2}+1}$${\estilo de visualización 2^{128}}$

• Incrementalidad : el ECOH de un mensaje se puede actualizar rápidamente, dado un pequeño cambio en el mensaje y un valor intermedio en el cálculo del ECOH.
• Paralelización : Esto significa que el cálculo puede realizarse en sistemas paralelos.${\displaystyle P_{i}}$
• Velocidad : el algoritmo ECOH es aproximadamente mil veces más lento que SHA-1 . Sin embargo, dados los avances en hardware de escritorio hacia la paralelización y la multiplicación sin acarreo , ECOH puede en unos años ser tan rápido como SHA-1 para mensajes largos. Para mensajes cortos, ECOH es relativamente lento, a menos que se utilicen tablas extensas.

Las funciones hash ECOH se basan en funciones matemáticas concretas. Se diseñaron de tal manera que el problema de encontrar colisiones se pudiera reducir a un problema matemático conocido y difícil (el problema de la suma de subconjuntos ). Esto significa que si se pudieran encontrar colisiones, se podría resolver el problema matemático subyacente, que se supone que es difícil e irresoluble en tiempo polinómico . Se sabe que las funciones con estas propiedades son demostrablemente seguras y son bastante únicas entre el resto de funciones hash. Sin embargo, más tarde se encontró una segunda preimagen (y, por lo tanto, una colisión) porque las suposiciones dadas en la prueba eran demasiado sólidas.

Una forma de encontrar colisiones o segundas preimágenes es resolver polinomios de suma de Semaev . Para una curva elíptica dada E, existen polinomios que son simétricos en las variables y que se anulan exactamente cuando se evalúan en las abscisas de los puntos cuya suma es 0 en . Hasta el momento, no existe un algoritmo eficiente para resolver este problema y se supone que es difícil (pero no se ha demostrado que sea NP-duro ).$Estilo de visualización f_{n}$${\estilo de visualización n}$${\estilo de visualización E}$

Más formalmente: Sea un cuerpo finito, una curva elíptica con ecuación de Weierstrass con coeficientes en y el punto del infinito. Se sabe que existe un polinomio multivariable si y solo si existen < tales que . Este polinomio tiene grado en cada variable. El problema es encontrar este polinomio.${\displaystyle \mathbf {F}}$${\estilo de visualización E}$${\displaystyle \mathbf {F}}$${\estilo de visualización O}$${\displaystyle f_{n}(X_{1},\ldots ,X_{N})}$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle (x_{1},y_{1})+\ldots +(x_{n},y_{n})=O}$$Estilo de visualización 2^{n-2}}$

El problema de encontrar colisiones en ECOH es similar al problema de la suma de subconjuntos . Resolver un problema de suma de subconjuntos es casi tan difícil como el problema del logaritmo discreto . Generalmente se supone que esto no es factible en tiempo polinomial . Sin embargo, se debe suponer una heurística significativamente flexible, más específicamente, uno de los parámetros involucrados en el cálculo no es necesariamente aleatorio sino que tiene una estructura particular. Si uno adopta esta heurística flexible, entonces encontrar una colisión ECOH interna puede verse como una instancia del problema de la suma de subconjuntos .

Existe un segundo ataque de preimagen en forma de ataque de cumpleaños generalizado.

Descripción del ataque : Este es un ataque de cumpleaños generalizado de Wagner . Requiere 2 ¹⁴³ tiempo para ECOH-224 y ECOH-256, 2 ²⁰⁶ tiempo para ECOH-384 y 2 ²⁸⁷ tiempo para ECOH-512. El ataque establece el bloque de suma de comprobación en un valor fijo y utiliza una búsqueda de colisión en los puntos de la curva elíptica. Para este ataque tenemos un mensaje M e intentamos encontrar un M' que genere el mismo mensaje. Primero dividimos la longitud del mensaje en seis bloques. Entonces . Sea K un número natural. Elegimos K números diferentes para y definimos por . Calculamos los K puntos de la curva elíptica correspondientes y los almacenamos en una lista. Luego elegimos K valores aleatorios diferentes para , definimos , calculamos y los almacenamos en una segunda lista. Tenga en cuenta que se conoce el objetivo Q. solo depende de la longitud del mensaje que hemos fijado. depende de la longitud y del XOR de todos los bloques de mensajes, pero elegimos los bloques de mensajes de modo que este sea siempre cero. De esta manera queda fijado para todos nuestros intentos.${\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$${\displaystyle (M_{0},M_{1})}$$Estilo de visualización M_{2}$${\displaystyle M_{2}:=M_{0}+M_{1}}$${\displaystyle P(M_{0},0)+P(M_{1},1)+P(M_{2},2)}$${\estilo de visualización (M_{3},M_{4})}$$Estilo de visualización M_{5}:=M_{3}+M_{4}}$${\displaystyle Q-X_{1}-X_{2}-P(M_{3},3)-P(M_{4},4)-P(M_{5},5)}$$Estilo de visualización X_{1}$$Estilo de visualización X_{2}$$Estilo de visualización X_{2}$

Si K es mayor que la raíz cuadrada del número de puntos de la curva elíptica, entonces esperamos una colisión entre las dos listas. Esto nos da un mensaje con: Esto significa que este mensaje conduce al valor objetivo Q y, por lo tanto, a una segunda preimagen, que era la pregunta. La carga de trabajo que tenemos que hacer aquí es dos veces K cálculos de hash parciales. Para obtener más información, consulte "Un segundo ataque de preimagen contra el hash de curva elíptica únicamente (ECOH)".${\displaystyle (M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$${\displaystyle Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}}$

Parámetros reales:

• ECOH-224 y ECOH-256 utilizan la curva elíptica B-283 con aproximadamente puntos en la curva. Elegimos y obtenemos un ataque con complejidad .${\estilo de visualización 2^{283}}$$Estilo de visualización K=2^{142}}$${\estilo de visualización 2^{143}}$
• ECOH-384 utiliza la curva elíptica B-409 con aproximadamente puntos en la curva. La elección da como resultado un ataque con complejidad${\estilo de visualización 2^{409}}$$Estilo de visualización K=2^{205}}$${\estilo de visualización 2^{206}.}$
• ECOH-512 utiliza la curva elíptica B-571 con aproximadamente 10 puntos en la curva. La elección da como resultado un ataque con complejidad.${\estilo de visualización 2^{571}}$$Estilo de visualización K=2^{286}}$${\estilo de visualización 2^{287}.}$

Los comentarios oficiales sobre ECOH incluyeron una propuesta llamada ECOH2 que duplica el tamaño de la curva elíptica en un esfuerzo por detener el segundo ataque de preimagen de Halcrow-Ferguson con una predicción de un rendimiento mejorado o similar.

• Daniel RL Brown, Matt Campagna, Rene Struik (2008). "ECOH: el algoritmo hash de curva elíptica".
• Michael A. Halcrow, Niels Ferguson (2009). "Un segundo ataque de preimagen contra el algoritmo hash de curva elíptica (ECOH)".