¿Existe alguna medida de tasa de colisión para los algoritmos de hashing populares (md5, crc32, sha- *)?
Si eso depende solo del tamaño de la salida, es bastante trivial de medir, pero supongo que también depende de la distribución y los elementos internos del algoritmo (y exige algún tipo de prueba formal, creo).
Si intento crear colisiones para MD5, puedo crear una cada 14 segundos (en promedio) en mi PC, usando un solo núcleo (Core2, 2.4 GHz). Esto explota las debilidades en la estructura interna de MD5. Si solo intento datos aleatorios y espero a que aparezcan colisiones, bueno, esperaré bastante tiempo: se espera la primera colisión después de aproximadamente 2 mensajes de hash 64 (dame un millar de PC, y debería lograr una colisión en aproximadamente 20 años de cómputo a tiempo completo).
Para las funciones de hash criptográficas ininterrumpidas actualmente, no se conoce ninguna debilidad interna (eso es lo que significa "intacto"), por lo que intentar mensajes aleatorios es el método más conocido para crear colisiones. Las posibilidades de obtener una colisión de esta manera son muy pequeñas hasta que usted tenga al menos 2 mensajes n / 2 , para una función hash con una salida de n bits. Esto significa que con cualquier función hash adecuada con una salida de 256 bits o más, la tasa de colisión es, en condiciones prácticas, cero (no obtendrá ninguna y ese es el final de la historia).
Wikipedia tiene algunos consejos sobre el tema. Consulte también el capítulo 9 del Manual de criptografía aplicada (página 369).
Lea otras preguntas en las etiquetas attacks hash cryptography