En informática , una colisión de hash o choque de hash [1] es cuando dos datos distintos en una tabla hash comparten el mismo valor hash. El valor hash en este caso 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 todavía pueden asignar diferentes datos al mismo hash (en virtud del principio del casillero ). Los usuarios malintencionados pueden aprovechar esto para imitar, acceder o alterar 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, funciones hash criptográficas ), la prevención de colisiones se ha convertido en un tema importante en la seguridad informática.
Las colisiones 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 tiene o no la longitud suficiente. 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 hash es 1, lo que significa que está garantizado que ocurrirá. [4]
Otra razón por la que las colisiones de hash son probables en algún momento proviene de 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 entre n personas. [5] Esta idea ha dado lugar a lo que se ha denominado el ataque de cumpleaños . La premisa de este ataque es que es difícil encontrar un cumpleaños que coincida específicamente con el suyo o con un cumpleaños específico, pero la probabilidad de encontrar un conjunto de dos personas con cumpleaños coincidentes aumenta enormemente la probabilidad. Los malos actores 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 verificació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] Los casos en los que los malos actores intentan crear o encontrar colisiones de 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 poder 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 hash son inevitables, las tablas hash tienen mecanismos para abordarlas, conocidos como resoluciones de colisión. Dos de las estrategias más comunes son el direccionamiento abierto y el encadenamiento separado . La resolución de colisiones consciente del 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 ocurre una colisión de hash y se implementa este método. Algunos tipos de sondeo son el sondeo lineal , el sondeo 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 dos registros se dirigen a la misma celda, ambos irán a esa celda como una lista vinculada. Esto evita eficazmente 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. Hacer un seguimiento de tantas listas es difícil y puede hacer que cualquier herramienta que se utilice se vuelva muy lenta. [10] El encadenamiento separado también se conoce como hash abierto. [12]
Aunque mucho menos utilizado que los dos anteriores, Askitis y Zobel (2005) propusieron el método de resolución de colisiones consciente de caché en 2005. [13] Es una idea similar a los métodos de encadenamiento separado, aunque técnicamente no involucra 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 tablas hash de cadenas y aún se desconoce su uso para valores numéricos. [10]
Mucho más que algoritmos de cifrado, las funciones hash unidireccionales son los caballos de batalla de la criptografía moderna.