Colisión de hash

John Smith y Sandra Dee comparte el mismo valor hash de 02, causando una colisión precipitada.

En informática, una colisión de hash o colisión de hash se produce cuando dos datos de 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.

Aunque los algoritmos hash se han creado con la intención de ser resistentes a colisiones, aún pueden asignar diferentes datos al mismo hash (en virtud del principio del casillero). Los usuarios maliciosos pueden aprovechar esto para imitar, acceder o alterar datos.

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.

Antecedentes

Las colisiones hash pueden ser inevitables según la cantidad de objetos en un conjunto y si la cadena de bits a la que están asignados es lo suficientemente larga o no. 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 ocurra.

Otra razón por la que las colisiones hash son probables en algún momento se deriva 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 número de personas. Esta idea ha llevado a lo que se ha llamado el ataque de cumpleaños. La premisa de este ataque es que es difícil encontrar un cumpleaños que coincida específicamente con su cumpleaños o un cumpleaños específico, pero la probabilidad de encontrar un conjunto de cualquier dos personas con cumpleaños coincidentes aumenta la probabilidad en gran medida. Los malos actores pueden usar 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.

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 hashing sensible a la localidad. 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. Los casos en los que los malhechores intentan crear o encontrar colisiones de hash se conocen como ataques de colisión.

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 se puedan usar en cualquier lugar y lo suficientemente seguros como para que sea extremadamente difícil encontrar colisiones..

Probabilidad de ocurrencia

Las colisiones de hash pueden ocurrir por casualidad y pueden crearse intencionalmente para muchos algoritmos de hash. Por lo tanto, la probabilidad de una colisión de hash depende del tamaño del algoritmo, la distribución de los valores de hash y si es o no 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 diferentes niveles de riesgo de colisión.

CRC-32

CRC-32 presenta el mayor riesgo de colisiones de hash. Por lo general, no se recomienda el uso de esta función hash. Si un concentrador tuviera 77 163 valores hash, la posibilidad de que se produzca una colisión de hash es del 50 %, lo que es extremadamente alto en comparación con otros métodos.

MD5

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 tener un 50 % de posibilidades de que se produzca una colisión de hash, tendría que haber más de 5060 millones de registros en el hub.

SHA-1

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 de hash, debería haber 1,42 × 10²⁴ registros en el concentrador. Tenga en cuenta que la cantidad de registros mencionados en estos ejemplos tendría que estar en el mismo concentrador.

Tener un concentrador con un número menor de registros podría disminuir la probabilidad de una colisión de hash en todas estas funciones de hash, aunque siempre habrá presente un riesgo menor, que es inevitable, a menos que se utilicen técnicas de resolución de colisiones.

Resolución de colisiones

Dado que las colisiones hash son inevitables, las tablas hash tienen mecanismos para manejarlas, conocidas 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 de la memoria caché es otra estrategia que se ha discutido en el pasado para las tablas hash de cadenas.

John Smith y Sandra Los dee están siendo dirigidos a la misma celda. El abordaje abierto causará la tabla de hash para redirigir Sandra Dee a otra célula.

Direccionamiento abierto

A las celdas de la tabla hash se les asigna uno de los tres estados en este método: ocupada, vacía o eliminada. Si se produce una colisión hash, se sondeará la tabla para mover el registro a una celda alternativa que se indica como vacía. Hay diferentes tipos de sondeo que tienen lugar cuando ocurre una colisión hash y se implementa este método. Algunos tipos de sondeo son el sondeo lineal, el hash doble y el sondeo cuadrático. El direccionamiento abierto también se conoce como hashing cerrado.

Encadenamiento separado

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án a esa celda como una lista enlazada. Esto evita de forma eficaz 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 esté utilizando se vuelva muy lenta. El encadenamiento separado también se conoce como hashing abierto.

Resolución de colisiones consciente de la memoria caché

Aunque mucho menos utilizado que los dos anteriores, Askitis & Zobel (2005) propuso el método de resolución de colisiones consciente de caché en 2005. Es una idea similar a los métodos de encadenamiento separados, 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 el uso de valores numéricos.