Estoy desarrollando un algoritmo hash largo de 16 caracteres. Tengo un segundo algoritmo que genera cadenas de caracteres de 1024 aleatorias. Este algoritmo realiza un bucle y detecta si hay una colisión entre el hash recién generado y cualquier otro anterior.
¿Cuántas iteraciones sin colisión necesito antes de poder afirmar que mi algoritmo hash es "casi seguro"?
Tengo un segundo algoritmo que genera cadenas de caracteres de 1024 aleatorias. Este algoritmo realiza un bucle y detecta si hay una colisión entre el hash recién generado y cualquier otro anterior. ¿Cuántas iteraciones sin colisión necesito [...]?
Con una función hash desea una distribución uniforme. Entonces, si hash datos aleatorios un montón de veces, querrás que los resultados contengan cada resultado el mismo número de veces.
Esta propiedad de distribución uniforme es difícil de traducir a su pregunta. Quieres saber el número de resultados sin colisión. Sin embargo, esto es difícil de medir porque cada iteración tiene una posibilidad de colisión. Esta posibilidad aumenta con el número de iteraciones. Pero debido a que es una probabilidad, si obtienes una colisión después de 10,000 iteraciones, no sabes si tu función hash es defectuosa o si tienes mala suerte.
Probablemente, una mejor manera sería generar muchos valores hash y luego observar la distribución de 0 y 1 de cada bit. En una distribución uniforme, se esperaría que cada bit tuviera un 50% de probabilidad de ser 0 y un 50% de probabilidad de ser 1.
En cuanto al cálculo de la probabilidad, este artículo puede ayudar a calcular la probabilidad de una colisión.
Este artículo proporciona información sobre la uniformidad de las funciones hash utilizadas comúnmente.
¿Cuántas iteraciones sin colisión necesito antes de poder afirmar que mi algoritmo hash es "casi seguro"?
Nunca. No puedes afirmar que tu algoritmo hash es seguro. Debe ser cuidadosamente auditado por criptógrafos / matemáticos talentosos que saben exactamente lo que están haciendo.
No puede esperar tener suficiente poder de cómputo / dinero para ejercer la fuerza bruta durante el tiempo suficiente, especialmente si está solo. Google necesitó más de un año y más de $ 1 millón para encontrar esa famosa colisión SHA-1 . ¿Crees que tienes suficiente tiempo / dinero?
Además, la fuerza bruta por sí sola no es la mejor manera de descifrar una función hash. La función puede tener defectos importantes que podrían ser muy difíciles de encontrar a través de la fuerza bruta. Es por eso que necesita personas con talento para auditar el algoritmo.
A menos que se haya realizado todo ese trabajo, realmente debería usar funciones hash estándar que se consideran seguras en la actualidad.
Lea otras preguntas en las etiquetas hash