Hash Collisions & The Birthday Paradox - Computerphile

¿Qué es el Paradoja del Cumpleaños y su relación con las colisiones de hash?

Introducción a la Paradoja del Cumpleaños

• El presentador introduce el tema de la paradoja del cumpleaños, que trata sobre las colisiones de hash.

• Se menciona que la probabilidad de que dos personas en una habitación compartan el mismo cumpleaños es sorprendentemente alta, lo cual se relaciona con la criptografía y funciones hash.

Funciones Hash

• Se explica brevemente qué es una función hash: toma un mensaje de longitud variable y produce un resumen de longitud fija (ej. 128 o 256 bits).

• Las funciones hash generan resultados que parecen aleatorios pero son determinísticos; el mismo mensaje siempre produce el mismo hash.

Ejemplos Prácticos

• Un uso común de las funciones hash es almacenar contraseñas: se almacena el hash en lugar de la contraseña original para mayor seguridad.

• Otro ejemplo es en firmas digitales, donde se firma un hash del documento debido a su longitud.

Colisiones de Hash

• Se define una colisión como cuando dos mensajes diferentes producen el mismo hash; esto puede ser problemático en criptografía.

• A pesar del gran número posible de hashes (2^256), hay más mensajes posibles que hashes, lo que lleva inevitablemente a colisiones.

Principio del Casillero (Pigeonhole Principle)

• Se introduce el principio del casillero para explicar por qué ocurren las colisiones: si hay más elementos (mensajes) que espacios disponibles (hashes), debe haber al menos una colisión.

• El presentador ilustra este principio usando dibujos humorísticos sobre palomas y agujeros, enfatizando cómo eventualmente todas las "casillas" estarán llenas.

¿Por qué el Paradoja del Cumpleaños es Importante?

Introducción a la Paradoja del Cumpleaños

• La paradoja del cumpleaños ilustra que en un grupo de personas, la probabilidad de que al menos dos compartan un cumpleaños es mayor de lo que se podría suponer inicialmente.

• La intuición común sugiere que con 36 personas hay una baja probabilidad (1 en 10), pero esto no considera las comparaciones entre todos los pares posibles.

Comparación y Colisiones

• No se trata solo de comparar un cumpleaños específico, sino cualquier coincidencia entre los cumpleaños de los presentes.

• A medida que más personas ocupan "espacios" (cumpleaños), aumenta significativamente la probabilidad de colisiones; con 40 o 50 personas, la posibilidad puede llegar hasta el 90%.

Experimento Práctico

• Se realizó un experimento donde aproximadamente 40 personas compartieron sus fechas de nacimiento para verificar la teoría.

• El objetivo era identificar colisiones en las fechas ingresadas; se encontraron múltiples coincidencias, confirmando así la alta probabilidad.

Implicaciones para Funciones Hash

• Este fenómeno tiene relevancia en funciones hash: al seleccionar hashes aleatoriamente, las colisiones son más comunes de lo esperado.

• Con funciones hash grandes (2^256 opciones), la probabilidad real de colisión es considerablemente mayor debido a cómo se distribuyen las combinaciones.

Riesgos Asociados a Colisiones

• Si una función hash tiene un tamaño pequeño, como 128 bits, el espacio para encontrar colisiones se vuelve práctico y accesible para atacantes potenciales.

• Un ejemplo ilustrativo muestra cómo manipular documentos digitales puede llevar a falsificaciones si se encuentran colisiones en los hashes. Esto pone en riesgo la confianza en firmas digitales y comunicaciones seguras.

¿Cuáles son las debilidades de las funciones hash?

Tamaño de salida y colisiones

• Las funciones hash tienen debilidades inherentes, como un tamaño de salida limitado. Por ejemplo, SHA-1 tiene un tamaño de salida de 160 bits, lo que implica un espacio de búsqueda considerablemente grande (2^80) para encontrar una colisión.

• Al diseñar funciones hash, es crucial que la salida sea suficientemente larga y parezca aleatoria para evitar búsquedas exhaustivas. Actualmente, se utilizan funciones hash con al menos 256 bits.

Prevención y ocurrencia de colisiones

• No se puede prevenir completamente la ocurrencia de colisiones en funciones hash; hay más mensajes que hashes posibles. Sin embargo, las probabilidades son tan pequeñas que no suelen ser motivo de preocupación.

• Un caso notable ocurrió cuando Google generó dos archivos PDF con el mismo hash SHA-1, lo que causó problemas en GitHub debido a su sistema de versionado basado en hashes.

Implicaciones prácticas

• La posibilidad teórica de colisiones resalta la importancia del diseño robusto en sistemas informáticos. Si dos archivos con el mismo hash se encuentran sin haber sido comparados antes, los sistemas pueden fallar.

Oportunidades educativas ofrecidas por Jane Street

Programas gratuitos para estudiantes

• Jane Street es una firma global de comercio que utiliza aprendizaje automático y sistemas distribuidos. Ofrecen programas gratuitos para introducir a personas interesadas en su mundo profesional.

• Uno de los programas destacados es Wise, dirigido a mujeres autodefinidas y personas transgénero o expansivas en género que están comenzando su primer año universitario. Este programa se lleva a cabo en varias ciudades importantes.

Acceso y beneficios del programa

• No se requiere experiencia previa en finanzas para aplicar; solo se necesita curiosidad. Los participantes aprenderán sobre Jane Street y tendrán la oportunidad de conocer a personas afines sin costo alguno, ya que todos los gastos están cubiertos.