¿Qué transformación md5? ¿El matemático (de cualquier cadena de bits a 128 bits) o el de cualquier cadena de bytes a una cadena hexadecimal de 32 caracteres (el práctico)? No es obvio que las respuestas para ambos sean las mismas ...
Rafał Dowgird
4
Bueno, son la misma respuesta, ¿verdad? Sabemos que no existe una x que no sea de 128 bits de longitud para la cual md5(x) == x, porque md5(x)tiene una longitud de 128 bits. Por lo tanto, hay un punto fijo en md5 para una entrada de tamaño arbitrario si y solo si hay un punto fijo en md5 en el dominio de 128 bits.
el paul
1
No creo que sean la misma respuesta, ya que para la práctica cadena hexadecimal de 32 caracteres es una elección arbitraria si representa los dígitos hexadecimales en mayúsculas [AF] o en minúsculas [af]. Ambas representaciones corresponden al mismo número de 128 bits pero producirán diferentes hashes cuando se proporcionen como entradas a MD5. Entonces, la probabilidad de que haya un punto fijo en cualquiera de las representaciones es de hecho1-(1/e)*(1/e) ≈ 86.47%
Dušan
Respuestas:
138
Dado que una suma MD5 tiene una longitud de 128 bits, cualquier punto fijo también tendría que tener una longitud de 128 bits. Suponiendo que la suma MD5 de cualquier cadena se distribuye de manera uniforme sobre todas las sumas posibles, entonces la probabilidad de que cualquier cadena de 128 bits dado es un punto fijo es 1 / 2 128 .
Por lo tanto, la probabilidad de que ninguna cadena de 128 bits es un punto fijo es (1 - 1 / 2 128 ) 2 128 , por lo que la probabilidad de que hay un punto fijo es 1 - (1 - 1 / 2 128 ) 2 128 .
Dado que el límite cuando n llega al infinito de (1 - 1 / n ) n es 1 / e , y 2 128 es sin duda un número muy grande, esta probabilidad es casi exactamente 1 - 1 / e ≈ 63,21%.
Por supuesto, no hay aleatoriedad realmente involucrada, o hay un punto fijo o no lo hay. Pero podemos tener un 63,21% de confianza en 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 MD5 fueran de 32 bits o 1024 bits, la respuesta sería la misma, siempre que sea mayor que 4 o 5 bits).
¿Puede realmente suponer que la suma MD5 de cualquier cadena se distribuye uniformemente entre todas las sumas posibles?
Ori Pessach
13
Si. Los números grandes y modulos forman una distribución aproximadamente aleatoria. Si no lo hicieran, tendrías constantes colisiones. La naturaleza de md5 obliga a que su salida se distribuya aleatoriamente.
Stefan Kendall
2
Usé
1
Aquí tienes una insignia de oro.
Dennis
Excepto que md5 es determinista, no aleatorio.
PyRulez
13
Mi intento de fuerza bruta encontró una coincidencia de 12 prefijos y 12 sufijos.
Lo siento ... No he guardado la publicación del blog y la copia de seguridad de Google + no me funciona. Pero aquí está mi proyecto de github: github.com/thomasegense/MD5FixPointSearch
Thomas Egense
¿Está seguro de esto? Prefijo 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762 Usé el md5sumcomando linux, obtuve un resultado diferente
ThunderPhoenix
No estoy seguro de que esté usando el md5sum correcto entonces. También puede confirmarlo en línea aquí: onlinemd5.com
Thomas Egense
11
Dado que el hash es irreversible, sería muy difícil de descifrar. La única forma de resolver esto sería calcular el hash en cada salida posible del hash y ver si se le ocurrió 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 tarda 1 milisegundo en calcular un hash en un valor de 16 bytes, se necesitarían 10790283070806014188970529154,99 años para calcular todos esos hash.
Es cierto, si tuvieras que probar todos . Pero solo tendría que probar todas las entradas posibles para verificar que no haya un punto fijo. Si hay un punto fijo (y la respuesta de Adam Rosenfield sugiere que podría haberlo), entonces todo lo que se necesita es una suposición afortunada.
Naaff
La función es irreversible en el sentido de que no tiene inversa matemática, sin embargo, esto solo significa que para una salida dada puede haber más de una entrada. En general, el espacio de entradas para una salida dada sería infinito, pero si sabe que comenzó como un valor de 128 bits, puede reducir las posibilidades. Existe la posibilidad de "trabajar al revés" si no trata la función como una caja negra, sino que lee la especificación y aplica algo de pensamiento matemático.
rndmcnlly
2
@Naaff: "solo tienes que probar todas las entradas posibles", y esto es más fácil que probar todos los hash, ¿cómo? Todo lo contrario, ya que varias entradas posibles pueden formar un hash en la misma salida.
Piskvor salió del edificio el
1
@Piskvor: No entendiste lo que quería decir Naaff (también me tomó un minuto). Una forma más clara de decirlo sería "Solo si no hay un punto fijo, deberá intentar probar todas las entradas posibles (desde el espacio 2 ^ 128)". En otras palabras, solo tiene que probar todas las posibilidades si ninguna funciona antes. Entonces 1.08e28 años, ¡o una suposición afortunada!
P papá
"Si tardó 1 milisegundo en calcular un hash". Las GPU modernas pueden calcular miles de millones de hashes por segundo, mucho más rápido que esto. Pero aún así, llevaría mucho tiempo.
markasoftware
0
Si bien no tengo una respuesta de sí / no, mi conjetura es "sí" y, además, tal vez haya 2 ^ 32 de esos puntos fijos (para la interpretación de cadena de bits, no para la interpretación de cadena de caracteres). Estoy trabajando activamente en esto porque parece un rompecabezas increíble y conciso que requerirá mucha creatividad (si no te conformas con la búsqueda de fuerza bruta de inmediato).
Mi enfoque es el siguiente: trátelo como un problema matemático. 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, espero que las ecuaciones se puedan simplificar en gran medida para producir un algoritmo optimizado para el caso de entrada de 128 bits. Estas ecuaciones simplificadas se pueden programar en algún lenguaje agradable para una búsqueda eficiente, o se pueden tratar de manera abstracta nuevamente, asignando bits individuales a la vez, observando las contradicciones. ¡Solo necesita ver algunos bits de la salida para saber que no coincide con la entrada!
No se ha roto. Todo lo que han podido hacer es, en un tiempo razonable, producir 2 cadenas que equivalen al mismo hash. Todavía es muy difícil producir una cadena que equivalga a un hash específico.
Kibbee
9
No estoy seguro de cómo encontrar uno comprometería md5, más de lo que comprometería el algoritmo si te dijera MD5 ("El rápido zorro marrón salta sobre el perro perezoso") = 9e107d9d372bb6826bd81d3542a419d6
Kip
5
Un punto fijo probablemente daría algo de influencia en las matemáticas que podría conducir a una infracción más completa de MD5. No estoy convencido de que Glomek realmente pueda justificar "probablemente"; Aceptaría "posiblemente" sin equívocos.
Jonathan Leffler
-9
Hay dos interpretaciones, y si a una se le permite elegir cualquiera, la probabilidad de encontrar un punto fijo aumenta al 81,5%.
Interpretación 1: ¿el MD5 de un MD5 sale en binario? coincide con su entrada?
Interpretación 2: ¿el MD5 de una salida MD5 en hexadecimal coincide con su entrada?
No hay nada en el algoritmo MD5 que implique hexadecimal: opera en bytes y produce bytes, por lo que creo que la última interpretación no es válida.
Nick Johnson
Ya sea que haya o no un punto fijo en la interpretación 1, todavía podría haber (o no) uno en la interpretación 2. Sin embargo, si está interesado en explorar el problema, la interpretación 1 parece un lugar mucho mejor para comenzar porque ganó No tiene que tomar todo tipo de decisiones arbitrarias sobre la codificación de caracteres y mayúsculas y minúsculas. Además de eso, ¡el caso binario tiene menos bits!
rndmcnlly
4
Estás malinterpretando lo que realmente es el maleficio. Puede representar binario en hexadecimal, al igual que puede representarlo en decimal, octal o base 3. Es un número y tiene diferentes representaciones. Entonces, la interpretación 1 y 2 son lo mismo. En lo que está pensando es en la representación de la cadena de caracteres, que no es el mismo hexadecimal en absoluto, pero es un valor binario completamente diferente. De hecho, podría tener muchas cadenas hexadecimales diferentes en diferentes conjuntos de caracteres. El valor hash de 128 bits se puede representar como una cadena "hexadecimal", pero no es igual a la cadena. La cadena no es la misma información binaria.
define el
Dustin, la interpretación 2 realmente significa el MD5 de la cadena de visualización.
Joshua
4
Sin embargo, existe un gran problema con esa idea, ya que depende directamente de la codificación de los caracteres. Un esquema de codificación diferente dará como resultado conjuntos de resultados completamente diferentes. Incluso hay un proyecto completo y un artículo que lo desacredita basándose en este malentendido de cómo funciona MD5 acodingfool.typepad.com/blog/2009/05/the-kembler-identity.html
define el
-23
Estrictamente hablando, dado que la entrada de MD5 tiene 512 bits de longitud y la salida es de 128 bits, diría que eso es imposible por definición.
La entrada puede ser de cualquier tamaño. Si la entrada tiene menos de 512 bytes, se rellena, pero las entradas pequeñas siguen siendo aceptables. De Wikipedia: "MD5 procesa un mensaje de longitud variable en una salida de longitud fija de 128 bits. El mensaje de entrada se divide en fragmentos de bloques de 512 bits (dieciséis enteros little endian de 32 bits); el mensaje se rellena para que su longitud es divisible por 512 ".
Naaff
Entonces, ¿está asumiendo que, digamos, 0000000001 = 1? Diría entonces que la pregunta está mal especificada, en el mejor de los casos.
Ori Pessach
11
La entrada a MD5 puede ser de 128 bits. Si MD5 quiere rellenar esa entrada, bueno, francamente, eso es asunto de MD5. La entrada aún está bien definida. Asimismo, la salida es de 128 bits bien definidos. Si la entrada (bien definida) y la salida (bien definida) son iguales, entonces MD5 (x) = x.
Naaff
2
@Joshua, el MD5 de una cadena vacía (es decir, 0 bytes) incluso existe
md5(x) == x, porquemd5(x)tiene una longitud de 128 bits. Por lo tanto, hay un punto fijo en md5 para una entrada de tamaño arbitrario si y solo si hay un punto fijo en md5 en el dominio de 128 bits.1-(1/e)*(1/e) ≈ 86.47%Respuestas:
Dado que una suma MD5 tiene una longitud de 128 bits, cualquier punto fijo también tendría que tener una longitud de 128 bits. Suponiendo que la suma MD5 de cualquier cadena se distribuye de manera uniforme sobre todas las sumas posibles, entonces la probabilidad de que cualquier cadena de 128 bits dado es un punto fijo es 1 / 2 128 .
Por lo tanto, la probabilidad de que ninguna cadena de 128 bits es un punto fijo es (1 - 1 / 2 128 ) 2 128 , por lo que la probabilidad de que hay un punto fijo es 1 - (1 - 1 / 2 128 ) 2 128 .
Dado que el límite cuando n llega al infinito de (1 - 1 / n ) n es 1 / e , y 2 128 es sin duda un número muy grande, esta probabilidad es casi exactamente 1 - 1 / e ≈ 63,21%.
Por supuesto, no hay aleatoriedad realmente involucrada, o hay un punto fijo o no lo hay. Pero podemos tener un 63,21% de confianza en 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 MD5 fueran de 32 bits o 1024 bits, la respuesta sería la misma, siempre que sea mayor que 4 o 5 bits).
fuente
Mi intento de fuerza bruta encontró una coincidencia de 12 prefijos y 12 sufijos.
prefijo 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762
sufijo 12: df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78
Publicación de blog: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN
fuente
md5sumcomando linux, obtuve un resultado diferenteDado que el hash es irreversible, sería muy difícil de descifrar. La única forma de resolver esto sería calcular el hash en cada salida posible del hash y ver si se le ocurrió 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 tarda 1 milisegundo en calcular un hash en un valor de 16 bytes, se necesitarían 10790283070806014188970529154,99 años para calcular todos esos hash.
fuente
Si bien no tengo una respuesta de sí / no, mi conjetura es "sí" y, además, tal vez haya 2 ^ 32 de esos puntos fijos (para la interpretación de cadena de bits, no para la interpretación de cadena de caracteres). Estoy trabajando activamente en esto porque parece un rompecabezas increíble y conciso que requerirá mucha creatividad (si no te conformas con la búsqueda de fuerza bruta de inmediato).
Mi enfoque es el siguiente: trátelo como un problema matemático. 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, espero que las ecuaciones se puedan simplificar en gran medida para producir un algoritmo optimizado para el caso de entrada de 128 bits. Estas ecuaciones simplificadas se pueden programar en algún lenguaje agradable para una búsqueda eficiente, o se pueden tratar de manera abstracta nuevamente, asignando bits individuales a la vez, observando las contradicciones. ¡Solo necesita ver algunos bits de la salida para saber que no coincide con la entrada!
fuente
Probablemente, pero encontrarlo tomaría más tiempo del que tenemos o implicaría comprometer MD5.
fuente
Hay dos interpretaciones, y si a una se le permite elegir cualquiera, la probabilidad de encontrar un punto fijo aumenta al 81,5%.
fuente
Estrictamente hablando, dado que la entrada de MD5 tiene 512 bits de longitud y la salida es de 128 bits, diría que eso es imposible por definición.
fuente