¿Un hash tiene más de un mensaje original posible? [duplicar]

Question

¿Un hash tiene más de un mensaje original posible? [duplicar]

#1 de CodeExpress (2 votos)

2

Muchos algoritmos de hash parecen tener un resumen de mensajes de longitud fija como salida.

Si calculo el hash md5 de dos cadenas:

>>> hashlib.md5("This is a really really long text string to make a hash out of").hexdigest()
'2916991b5ebba69ab38a84a0a72b4176'

>>> hashlib.md5("Short").hexdigest()
'30bb747c98bccdd11b3f89e644c4d0ad'

Obtengo una salida de 32 caracteres para cada una, aunque hay una diferencia significativa en la longitud de las entradas. ¿Es teóricamente posible que pueda encontrar dos (o más) entradas completamente diferentes que generen la misma salida, ya que hay infinitas posibilidades para una entrada y solo un número finito de caracteres para la salida?

En caso afirmativo, ¿cuál es la probabilidad de encontrar otra entrada que genere la misma salida?

cryptography

pregunta jdickson 03.07.2012 - 00:19

fuente

1 respuesta

Lea otras preguntas en las etiquetas cryptography

¿Cómo uso OpenSSL con Java Keytool? Forzar la exploración AV de la unidad USB en comparación con la exploración de acceso a archivos

score 2 · Accepted Answer

¿Es teóricamente posible que pueda encontrar dos (o más) entradas completamente diferentes que generen la misma salida, ya que hay infinitas posibilidades para una entrada y solo un número finito de caracteres para la salida?

Sí, es teóricamente posible. Pero las funciones hash están diseñadas para hacerlo prácticamente difícil. Cuando digo que es prácticamente difícil, quiero decir que se necesitarán ciclos de cálculo inmensos (que se traducen en dinero y tiempo) para calcular una colisión.

En caso afirmativo, ¿cuál es la probabilidad de encontrar otra entrada que genere la misma salida?

Esto depende de las funciones hash. La propiedad se llama Resistencia a la colisión

Para representar a través de un ejemplo, construyamos una función de hash que hace un hash de números en un espacio de dirección más pequeño resultante [0, 9]. Nuestra función hash simple es hash(X) = X mod 10 . Por lo tanto

hash(10)   = 0
hash(1864) = 4

Esta es una función hash válida pero tiene una resistencia de colisión muy pobre. Por ejemplo, hash de 24 y 1284 es el mismo. Si confía en el hash (4 en este caso) para la integridad del mensaje, un atacante puede reemplazar de forma segura el mensaje 24 a 1284 que tiene el mismo valor. Este ataque en particular se denomina Ataque de preimagen La resistencia de colisión de preimagen es una propiedad principal de cualquier función hash.