En informática , una colisión de hash o choque de hash [1] se produce cuando dos datos distintos de una tabla hash comparten el mismo valor hash. En este caso, el valor hash se deriva de una función hash que toma una entrada de datos y devuelve una longitud fija de bits. [2]
Aunque los algoritmos hash, especialmente los algoritmos hash criptográficos, se han creado con la intención de ser resistentes a las colisiones , a veces aún pueden asignar diferentes datos al mismo hash (en virtud del principio de pigeonhole ). Los usuarios malintencionados pueden aprovechar esto para imitar, acceder o alterar los datos. [3]
Debido a las posibles aplicaciones negativas de las colisiones hash en la gestión de datos y la seguridad informática (en particular, las funciones hash criptográficas ), la prevención de colisiones se ha convertido en un tema importante en la seguridad informática.
Las colisiones de hash pueden ser inevitables dependiendo de la cantidad de objetos en un conjunto y de si la cadena de bits a la que están asignados es lo suficientemente larga. Cuando hay un conjunto de n objetos, si n es mayor que | R |, que en este caso R es el rango del valor hash, la probabilidad de que haya una colisión de hash es 1, lo que significa que está garantizado que ocurrirá. [4]
Otra razón por la que es probable que se produzcan colisiones de hash en algún momento se debe a la idea de la paradoja del cumpleaños en matemáticas. Este problema analiza la probabilidad de que un conjunto de dos personas elegidas al azar tengan el mismo cumpleaños de entre n personas. [5] Esta idea ha dado lugar a lo que se ha denominado el ataque del cumpleaños . La premisa de este ataque es que es difícil encontrar un cumpleaños que coincida específicamente con el tuyo o con un cumpleaños específico, pero la probabilidad de encontrar un conjunto de dos personas cualesquiera con cumpleaños coincidentes aumenta enormemente la probabilidad. Los actores maliciosos pueden utilizar este enfoque para que les resulte más sencillo encontrar valores hash que colisionen con cualquier otro valor hash, en lugar de buscar un valor específico. [6]
El impacto de las colisiones depende de la aplicación. Cuando se utilizan funciones hash y huellas dactilares para identificar datos similares, como secuencias de ADN homólogas o archivos de audio similares, las funciones están diseñadas para maximizar la probabilidad de colisión entre datos distintos pero similares, utilizando técnicas como el hash sensible a la localidad . [7] Las sumas de comprobación , por otro lado, están diseñadas para minimizar la probabilidad de colisiones entre entradas similares, sin tener en cuenta las colisiones entre entradas muy diferentes. [8] Las instancias en las que los actores maliciosos intentan crear o encontrar colisiones hash se conocen como ataques de colisión. [9]
En la práctica, las aplicaciones relacionadas con la seguridad utilizan algoritmos hash criptográficos, que están diseñados para ser lo suficientemente largos como para que las coincidencias aleatorias sean poco probables, lo suficientemente rápidos como para que puedan usarse en cualquier lugar y lo suficientemente seguros como para que sea extremadamente difícil encontrar colisiones. [8]
En las tablas hash, dado que las colisiones de hash son inevitables, las tablas hash tienen mecanismos para lidiar con ellas, conocidos como resoluciones de colisiones. Dos de las estrategias más comunes son el direccionamiento abierto y el encadenamiento separado . La resolución de colisiones consciente de la memoria caché es otra estrategia que se ha discutido en el pasado para las tablas hash de cadenas.
En este método, a las celdas de la tabla hash se les asigna uno de tres estados: ocupada, vacía o eliminada. Si se produce una colisión de hash, se sondeará la tabla para mover el registro a una celda alternativa que se indique como vacía. Existen diferentes tipos de sondeo que tienen lugar cuando se produce una colisión de hash y se implementa este método. Algunos tipos de sondeo son el sondeo lineal , el hash doble y el sondeo cuadrático . [10] El direccionamiento abierto también se conoce como hash cerrado. [11]
Esta estrategia permite "encadenar" más de un registro a las celdas de una tabla hash. Si se dirigen dos registros a la misma celda, ambos irían a esa celda como una lista enlazada. Esto evita de manera eficiente que se produzca una colisión de hash, ya que los registros con los mismos valores hash pueden ir a la misma celda, pero tiene sus desventajas. Mantener un registro de tantas listas es difícil y puede hacer que cualquier herramienta que se esté utilizando se vuelva muy lenta. [10] El encadenamiento por separado también se conoce como hash abierto. [12]
Aunque mucho menos utilizado que los dos anteriores, Askitis y Zobel (2005) propusieron en 2005 el método de resolución de colisiones consciente de la memoria caché . [13] Es una idea similar a los métodos de encadenamiento independiente, aunque técnicamente no implica las listas encadenadas. En este caso, en lugar de listas encadenadas, los valores hash se representan en una lista contigua de elementos. Esto es más adecuado para las tablas hash de cadenas y aún se desconoce su uso para valores numéricos. [10]
más que los algoritmos de cifrado, las funciones hash unidireccionales son los caballos de batalla de la criptografía moderna.