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 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]
Las colisiones hash pueden ocurrir por casualidad y pueden crearse intencionalmente para muchos algoritmos hash. Por lo tanto, la probabilidad de una colisión hash depende del tamaño del algoritmo, la distribución de los valores hash y de si es matemáticamente conocido y computacionalmente factible crear colisiones específicas.
Tenga en cuenta los siguientes algoritmos hash: CRC-32, MD5 y SHA-1. Estos son algoritmos hash comunes con distintos niveles de riesgo de colisión. [10]
CRC-32 plantea el mayor riesgo de colisiones de hash. Por lo general, no se recomienda el uso de esta función hash. Si un centro contuviera 77.163 valores hash, la probabilidad de que se produjera una colisión hash es del 50 %, lo cual es extremadamente alto en comparación con otros métodos. [11]
MD5 es la más utilizada y, en comparación con las otras dos funciones hash, representa el término medio en términos de riesgo de colisión de hash. Para obtener un 50% de posibilidades de que ocurra una colisión de hash, tendría que haber más de 5,060 millones de registros en el centro. [11]
SHA-1 ofrece el riesgo más bajo de colisiones de hash. Para que una función SHA-1 tenga un 50 % de posibilidades de que se produzca una colisión hash, tendría que haber 1,42 × 10 24 registros en el centro. Tenga en cuenta que la cantidad de registros mencionados en estos ejemplos tendría que estar en el mismo centro. [11]
Tener un centro con una cantidad menor de registros podría disminuir la probabilidad de una colisión hash en todas estas funciones hash, aunque siempre habrá un riesgo menor presente, que es inevitable, a menos que se utilicen técnicas de resolución de colisiones.
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 sondeo lineal , hash doble y sondeo cuadrático . [12] El direccionamiento abierto también se conoce como hash cerrado. [13]
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 de 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. [12] El encadenamiento separado también se conoce como hash abierto. [14]
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. [15] 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. [12]
Mucho más que algoritmos de cifrado, las funciones hash unidireccionales son los caballos de batalla de la criptografía moderna.