Hash Collision

¿Qué es Hash Collision?

Hash Collision ocurre cuando dos entradas diferentes producen exactamente la misma salida de hash. Imagínate dos llaves distintas que, de algún modo, abren la misma cerradura digital. Es raro, pero si sucede con un algoritmo débil, puede causar problemas.

Cómo funciona Hash Collision

Piensa en un hash como una etiqueta pequeña para datos grandes. Aquí tienes un breve recorrido desde la entrada hasta el problema.

1. Entrada: Comienzas con cualquier mensaje, archivo o transacción.
2. Hash: Una función de la familia de funciones hash criptográficas convierte esa entrada en una cadena de longitud fija.
3. Colisión: Como las salidas son limitadas pero las entradas infinitas, dos entradas distintas pueden corresponder al mismo resultado.
4. Ataque: Una amenaza grave es cuando alguien puede crear a propósito dos entradas distintas que colisionen y luego sustituir una por la otra.
5. Defensa: Los buenos algoritmos hacen que esa búsqueda sea astronómicamente costosa, de modo que intentar adivinar al azar consume tiempo y dinero.

Sí, esa es la idea.

Por qué importa Hash Collision

¿Por qué deberías interesarte en este rincón discreto de matemáticas y código?

• Beneficio: Una fuerte resistencia mantiene únicas las etiquetas de tus datos, lo que deja menos margen para trucos engañosos.
• Perspectiva: Las colisiones amenazan la integridad de tecnologías como tecnología blockchain, las actualizaciones de software y la verificación de archivos.
• Relevancia: Lo encontrarás en billeteras, exchanges, pruebas y herramientas de auditoría que confían en la igualdad de hashes.

Características clave de Hash Collision

Qué hace que este fenómeno sea especial y digno de mención:

• Inevitable: Con salidas finitas y entradas ilimitadas, alguna pareja colisionará por el principio del palomar.
• Difícil: Para los hashes modernos, encontrar una colisión a propósito está diseñado para ser computacionalmente brutal.
• Firmas: Muchas firmas digitales firman un hash, por lo que la resistencia a colisiones protege a los firmantes de mensajes de intercambio fraudulento.

¿Cómo se calcula Hash Collision?

Puedes estimar el esfuerzo con la idea del cumpleaños. Para un hash de k bits, el número de intentos aleatorios necesarios para una probabilidad aproximada del cincuenta por ciento de cualquier colisión es aproximadamente la raíz cuadrada de 2 elevado a k, multiplicada por aproximadamente 1.1774.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

Ejemplo: con k igual a 256, los intentos requeridos son inimaginablemente grandes, por eso forzar una colisión por fuerza bruta no es un proyecto de fin de semana.

Variaciones

Aparecen distintas variantes en investigaciones y ataques:

• Colisión: Cualquier dos entradas distintas comparten el mismo hash.
• Segunda preimagen: Dada una entrada, encontrar otra que coincida en su hash.
• Preimagen: Dado un hash, encontrar cualquier entrada que lo produzca.
• Prefijo: Una colisión de prefijo elegido crea dos mensajes con comienzos distintos elegidos que terminan con el mismo hash.

Ejemplo

Si un atacante pudiera crear dos transacciones distintas con el mismo txid, podría intentar un truco de Double Spending al cambiar una por la otra después de que firmes.

Dato curioso

Hace décadas se demostraron colisiones en MD5, y el proyecto SHAttered produjo una colisión pública de SHA 1 con dos PDFs diferentes, un golpe que impulsó a la industria a retirarlo.

Resumen

En pocas palabras, Hash Collision es el caso raro de dos entradas distintas que comparten la misma huella digital, y la criptografía moderna trabaja duro para que eso sea solo una curiosidad.