hash - paso - ¿Hay un punto fijo MD5 donde md5(x)== x?
que es md5 y sha1 (7)
Aunque no tengo una respuesta de sí / no, supongo que es "sí" y además hay tal vez 2 ^ 32 puntos fijos (para la interpretación de la cadena de bits, no la interpretación de la cadena de caracteres). Estoy trabajando activamente en esto porque parece un rompecabezas impresionante y conciso que requerirá mucha creatividad (si no te conformas con la búsqueda de fuerza bruta de inmediato).
Mi enfoque es el siguiente: tratarlo como un problema de matemáticas. Tenemos 128 variables booleanas y 128 ecuaciones que describen las salidas en términos de las entradas (que se supone que coinciden). Al conectar todas las constantes de las tablas en el algoritmo y los bits de relleno, mi esperanza es que las ecuaciones se puedan simplificar enormemente para producir un algoritmo optimizado para el caso de entrada de 128 bits. Estas ecuaciones simplificadas pueden luego programarse en un lenguaje agradable para una búsqueda eficiente, o tratarse abstractamente de nuevo, asignando bits individuales a la vez, vigilando las contradiciones. ¡Solo necesita ver algunos bits de la salida para saber que no coincide con la entrada!
¿Hay un punto fijo en la transformación MD5, es decir, existe x tal que md5(x) == x ?
Como el hash es irreversible, sería muy difícil de entender. La única forma de resolver esto sería calcular el hash en cada salida posible del hash, y ver si se te ocurre una coincidencia.
Para elaborar, hay 16 bytes en un hash MD5. Eso significa que hay 2 ^ (16 * 8) = 3.4 * 10 ^ 38 combinaciones. Si se tardó 1 milisegundo en calcular un hash en un valor de 16 bytes, se necesitarían 10790283070806014188970529154.99 años para calcular todos esos valores hash.
Como una suma de MD5 es de 128 bits de longitud, cualquier punto fijo necesariamente también tendría que tener 128 bits de longitud. Suponiendo que la suma MD5 de cualquier cadena se distribuye uniformemente sobre todas las sumas posibles, entonces la probabilidad de que una cadena dada de 128 bits sea un punto fijo es 1/2 128 .
Por lo tanto, la probabilidad de que ninguna cadena de 128 bits sea un punto fijo es (1 - 1/2 128 ) 2 128 , por lo que la probabilidad de que haya un punto fijo es 1 - (1 - 1/2 128 ) 2 128 .
Dado que el límite como n va al infinito de (1 - 1 / n ) n es 1 / e , y 2 128 es ciertamente un número muy grande, esta probabilidad es casi exactamente 1 - 1 / e ≈ 63.21%.
Por supuesto, no hay aleatoriedad realmente involucrada, ya sea que haya un punto fijo o no. Pero, podemos estar 63.21% seguros de que hay un punto fijo. (Además, tenga en cuenta que este número no depende del tamaño del espacio de claves; si las sumas de MD5 fueran 32 bits o 1024 bits, la respuesta sería la misma, siempre que supere los 4 o 5 bits).
Estrictamente hablando, dado que la entrada de MD5 tiene una longitud de 512 bits y la salida es de 128 bits, diría que eso es imposible por definición.
Hay dos interpretaciones, y si se permite elegir cualquiera, la probabilidad de encontrar un punto fijo aumenta a 81.5%.
- Interpretación 1: ¿el MD5 de una salida MD5 en binario coincide con su entrada?
- Interpretación 2: ¿coincide el MD5 de una salida MD5 en hexadecimal con su entrada?
Mi intento de fuerza bruta encontró un prefijo de 12 y 12 coincidencias de sufijo.
prefijo 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762
sufijo 12: df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78
Publicación del blog: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN
Probablemente, pero encontrarlo tomaría más tiempo de lo que tenemos o involucraría comprometer MD5.