El algoritmo de hash solo de curva elíptica (ECOH) se presentó como candidato para SHA-3 en la competencia de la función hash del NIST . Sin embargo, fue rechazada al comienzo de la competencia ya que se encontró un segundo ataque de pre-imagen .
General | |
---|---|
Diseñadores | Daniel RL Brown, Matt Campagna, Rene Struik |
Publicado por primera vez | 2008 |
Derivado de | MuHASH |
Detalle | |
Tamaños de resumen | 224, 256, 384 o 512 |
Mejor criptoanálisis público | |
Segunda imagen previa |
El ECOH se basa en el algoritmo hash MuHASH , que aún no ha sido atacado con éxito . Sin embargo, MuHASH es demasiado ineficaz para un uso práctico y se tuvieron que hacer cambios. La principal diferencia es que cuando 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 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, sin embargo, todavía se basa en funciones matemáticas. ECOH está relacionado con el problema de Semaev de encontrar soluciones de bajo grado a las ecuaciones polinomiales sumatorias sobre el campo binario, llamado Problema polinomial sumatorio . Hasta ahora no se ha proporcionado un algoritmo eficaz para resolver este problema. Aunque no se ha demostrado que el problema sea NP-hard , se supone que tal algoritmo no existe. Bajo ciertos supuestos, encontrar una colisión en ECOH también puede verse como una instancia del problema de la suma de subconjuntos . Además de resolver el problema del 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 la clásica mezcla ad hoc de bits para obtener el hash.
El algoritmo
Dado , ECOH divide el mensaje dentro bloques . Si el último bloque está incompleto, se rellena con un solo 1 y luego el número apropiado de 0. Sea ademásser una función que mapea un bloque de mensaje y un número entero a un punto de curva elíptica. Luego usando el mapeo, cada bloque se transforma en un punto de curva elíptica, y estos puntos se suman junto con dos puntos más. Un punto adicionalcontiene el relleno y depende solo de la longitud del mensaje. El segundo punto adicionaldepende de la longitud del mensaje y del XOR de todos los bloques de mensajes. El resultado se trunca para obtener el hash..
Los dos puntos extra se calculan mediante y . suma todos los puntos de la curva elíptica y los dos puntos extra juntos. 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 solamente" .
Ejemplos de
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 por la longitud de los parámetros, el tamaño del bloque y la curva elíptica utilizada. Los dos primeros utilizan la curva elíptica B-283:, con parámetros (128, 64, 64). ECOH-384 usa la curva B-409:, con parámetros (192, 64, 64). ECOH-512 usa la curva B-571:, con parámetros (256, 128, 128). Puede codificar mensajes con una longitud de bits de hasta.
Propiedades
- Incrementalidad : 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 de ECOH.
- Paralelizabilidad : esto significa el cálculo de la se puede hacer en sistemas paralelos.
- Velocidad : el algoritmo ECOH es unas mil veces más lento que SHA-1 . Sin embargo, dados los desarrollos en el hardware de escritorio hacia la paralelización y la multiplicación sin acarreo , ECOH puede ser en unos pocos años tan rápido como SHA-1 para mensajes largos. Para mensajes cortos, ECOH es relativamente lento, a menos que se utilicen tablas extensas.
Seguridad de ECOH
Las funciones hash de ECOH se basan en funciones matemáticas concretas. Fueron diseñados de manera que el problema de encontrar colisiones debería reducirse a un problema matemático conocido y difícil (el problema de la suma de subconjuntos ). Significa que si uno pudiera encontrar colisiones, sería capaz de resolver el problema matemático subyacente que se supone que es difícil e irresoluble en tiempo polinomial . Las funciones con estas propiedades se conocen como probadamente seguras y son bastante únicas entre el resto de funciones hash. Sin embargo, más tarde se encontró una segunda imagen previa (y por lo tanto una colisión) porque las suposiciones dadas en la prueba eran demasiado fuertes.
Polinomio de suma de Semaev
Una forma de encontrar colisiones o segundas preimágenes es resolviendo polinomios de suma de Semaev . Para una curva elíptica E dada, existen polinomios que son simétricos en variables y que desaparecen exactamente cuando se evalúan en abscisas de puntos cuya suma es 0 en . Hasta ahora, no existe un algoritmo eficiente para resolver este problema y se supone que es difícil (pero no se ha demostrado que sea NP-hard ).
Más formalmente: dejemos ser un campo finito, ser una curva elíptica con la ecuación de Weierstrass que tiene coeficientes en y sea el punto del infinito. Se sabe que existe un polinomio multivariable si y solo si existen < tal que . Este polinomio tiene gradoen cada variable. El problema es encontrar este polinomio.
Discusión de seguridad demostrable
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 de logaritmos discretos . Generalmente se asume 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 interna de ECOH 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.
Segundo ataque de preimagen
Descripción del ataque : este es un ataque de cumpleaños generalizado de Wagner . Requiere 2 143 tiempo para ECOH-224 y ECOH-256, 2 206 tiempo para ECOH-384, y 2 287 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 y tratamos de encontrar una M ' que tenga 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 definir por . Calculamos los K puntos correspondientes de la curva elípticay guárdelos en una lista. Luego elegimos K valores aleatorios diferentes para, definir , calculamos y guárdelos en una segunda lista. Tenga en cuenta que se conoce el objetivo Q. solo depende de la longitud del mensaje que hayamos arreglado. depende de la longitud y el XOR de todos los bloques de mensajes, pero elegimos los bloques de mensajes de manera que siempre sea cero. Por lo tanto, se fija para todos nuestros intentos.
Si K es mayor que la raíz cuadrada del número de puntos en 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 previo a la imagen contra el hash de curva elíptica únicamente (ECOH)" .
Parámetros reales:
- ECOH-224 y ECOH-256 utilizan la curva elíptica B-283 con aproximadamente puntos en la curva. Nosotros elegimos y consigue un ataque con complejidad .
- ECOH-384 utiliza la curva elíptica B-409 con aproximadamente puntos en la curva. Elegir da un ataque con complejidad
- ECOH-512 utiliza la curva elíptica B-571 con aproximadamente puntos en la curva. Elegir da un ataque con complejidad
ECOH2
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 rendimiento mejorado o similar.
Referencias
- Daniel RL Brown, Matt Campagna, Rene Struik (2008). "ECOH: el hash de curva elíptica solamente" .
- Michael A. Halcrow, Niels Ferguson (2009). "Un segundo ataque de preimagen contra el hash de curva elíptica solamente (ECOH)" .