Calculadora de Probabilidad de Colisión de Hash
Datos de entrada
| Tamaño del hash | 128 |
|---|---|
| Número de elementos | 1.000.000 |
Calculadora de Probabilidad de Colisión de Hash
Estima la probabilidad de una colisión por cumpleaños entre un conjunto de valores hash y calcula cuántos elementos son necesarios para alcanzar un 50 % de probabilidad de colisión según el tamaño del hash.
Datos de entrada
Parámetros del hash
Resultados
Introduce un valor para ver los resultados.
Probabilidad de colisión
Probabilidad de colisión de hash
Una función hash transforma una entrada de longitud arbitraria en una salida de longitud fija denominada resumen o digest. En condiciones ideales, ningún par de entradas distintas produce el mismo resumen, propiedad conocida como resistencia a colisiones. En la práctica, como el espacio de salida es finito, las colisiones deben existir; la cuestión es cuántas entradas hay que procesar antes de que una sea probable. Esta calculadora cuantifica esa probabilidad mediante la aproximación del cumpleaños, que recibe su nombre de la paradoja del cumpleaños.
La paradoja del cumpleaños
En un grupo de 23 personas elegidas al azar entre los 365 días del año, ya existe una probabilidad superior al 50 % de que dos compartan cumpleaños. La probabilidad es mucho mayor de lo que la intuición sugiere porque cuenta cualquier par dentro del grupo, no una coincidencia con un objetivo concreto. La misma asimetría rige las colisiones de hash: encontrar dos entradas con el mismo hash (una colisión) es mucho más fácil que encontrar una entrada que produzca un hash objetivo específico (una preimagen).
Fórmula
Para una función hash con bits de salida, el espacio de búsqueda tiene valores igualmente probables. Dados elementos procesados de forma aleatoria, la probabilidad exacta de colisión es el complemento de la probabilidad de que los resúmenes sean todos distintos:
p=1−k=0∏n−1(1−2bk)Para grande y moderado, la aproximación del cumpleaños proporciona una forma cerrada más sencilla:
p≈1−e−n2/(2⋅2b)Despejando el número de elementos al que la probabilidad alcanza el 50 %:
n50%=2⋅2b⋅ln2Ejemplo resuelto
Para un hash de 32 bits (como el CRC32 utilizado en sumas de verificación):
n50%=2×232×ln2=2×4294967296×0,6931≈5954124768≈77163Con tan solo 77.163 ficheros en un repositorio, existe aproximadamente un 50 % de probabilidad de que dos compartan el mismo CRC de 32 bits. La confirmación con la fórmula de aproximación:
p=1−e−771632/(2×232)≈1−e−0,693≈0,50Por eso CRC32 no es adecuado como identificador único en colecciones grandes, aunque sí es un excelente código de detección de errores en flujos de datos pequeños.
Implicaciones de seguridad
El límite del cumpleaños establece que una función hash de bits proporciona solo bits de resistencia a colisiones. Un atacante necesita aproximadamente evaluaciones de hash para encontrar una colisión, no . Por eso las funciones hash criptográficas se diseñan con más bits de salida que el nivel de seguridad objetivo:
| Función hash | Salida | Resistencia a colisiones |
|---|---|---|
| MD5 | 128 bits | ~ (comprometida en la práctica) |
| SHA-1 | 160 bits | ~ (comprometida en la práctica) |
| SHA-256 | 256 bits | ~ (estándar actual) |
| SHA-3-512 | 512 bits | ~ (alta seguridad) |
MD5 y SHA-1 se consideran «comprometidas» no solo por el límite del cumpleaños, sino porque investigadores encontraron debilidades algorítmicas que producen colisiones con mucha más rapidez que operaciones. Las colisiones de MD5 pueden calcularse en hardware convencional en cuestión de minutos usando técnicas publicadas.
Para un análisis relacionado sobre los espacios de búsqueda de contraseñas, véase Calculadora de Entropía de Contraseñas.
Preguntas frecuentes (FAQ)
¿Qué es la paradoja del cumpleaños en criptografía?
La paradoja del cumpleaños es el resultado contraintuitivo de que en un grupo de tan solo 23 personas existe ya más de un 50 % de probabilidad de que dos compartan cumpleaños, a pesar de que hay 365 fechas posibles.
La misma matemática se aplica a las funciones hash: un atacante solo necesita aproximadamente √(2^b) = 2^(b/2) elementos procesados para alcanzar un 50 % de probabilidad de encontrar dos con la misma salida. Esto se conoce como ataque de cumpleaños. Para un hash de 128 bits como MD5, ese umbral es aproximadamente 2^64 ≈ 1,8 × 10¹⁹ elementos, muy por debajo de las 2^128 combinaciones que requeriría un ataque de preimagen.
¿Por qué un ataque de cumpleaños requiere solo la mitad de los bits para comprometer la función?
Un ataque de preimagen debe encontrar una salida de hash específica y, por tanto, tiene que explorar el espacio completo de 2^b valores. Un ataque de cumpleaños solo necesita que dos entradas cualesquiera colisionen, y por el límite del cumpleaños la probabilidad de encontrar dicho par supera el 50 % tras aproximadamente 2^(b/2) muestras.
Por eso las funciones hash criptográficas se diseñan con el doble de bits de salida que el nivel de seguridad deseado: un hash de 256 bits ofrece 128 bits de resistencia a colisiones.
¿Por qué se consideran inseguros MD5 y SHA-1?
MD5 (128 bits) y SHA-1 (160 bits) han sido comprometidos mediante ataques de colisión prácticos; no solo ataques probabilísticos por el límite del cumpleaños, sino debilidades algorítmicas que permiten encontrar colisiones con mucha más eficiencia de la que predice ese límite. En 2004, investigadores demostraron colisiones en MD5; en 2017, el proyecto SHAttered de Google produjo la primera colisión conocida públicamente en SHA-1.
Estas funciones siguen siendo seguras para usos no criptográficos como sumas de verificación o direccionamiento de contenido, pero no deben emplearse donde la resistencia a colisiones sea relevante, como en firmas digitales o autoridades de certificación.
¿Qué diferencia hay entre una colisión y una preimagen?
Una colisión consiste en encontrar dos entradas distintas x e y tales que hash(x) = hash(y). Una preimagen consiste en encontrar una entrada x que produzca un valor objetivo h concreto, lo que es más difícil porque no se pueden elegir libremente ambas entradas. Una segunda preimagen consiste en encontrar una entrada y diferente que tenga el mismo hash que una x conocida.
Estas propiedades se ordenan de menor a mayor dificultad: la resistencia a colisiones es la más débil y la resistencia a segunda preimagen es la más fuerte. Las funciones hash usadas en firmas digitales deben resistir ataques de segunda preimagen; las usadas en tablas hash o filtros de Bloom solo necesitan una resistencia débil a colisiones.