stringtranslate.com

Colisión de hash

John Smith y Sandra Dee comparten el mismo valor hash de 02, lo que provoca una colisión hash.

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.

Fondo

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]

Resolución de colisiones

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.

A John Smith y Sandra Dee se les está dirigiendo a la misma celda. El direccionamiento abierto hará que la tabla hash redirija a Sandra Dee a otra celda.

Direccionamiento abierto

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]

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í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]

Resolución de colisiones consciente de la memoria caché

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 por separado, 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]

Véase también

Referencias

  1. ^ Thomas, Cormen (2009), Introducción a los algoritmos , MIT Press, p. 253, ISBN 978-0-262-03384-8
  2. ^ Stapko, Timothy (2008), "Seguridad integrada", Practical Embedded Security , Elsevier, págs. 83-114, doi :10.1016/b978-075068215-2.50006-9, ISBN 9780750682152, consultado el 8 de diciembre de 2021
  3. ^ Schneier, Bruce . "Criptoanálisis de MD5 y SHA: tiempo para un nuevo estándar". Computerworld . Archivado desde el original el 16 de marzo de 2016. Consultado el 20 de abril de 2016. Mucho más que los algoritmos de cifrado, las funciones hash unidireccionales son los caballos de batalla de la criptografía moderna.
  4. ^ Ciberseguridad y Matemáticas Aplicadas. 2016. doi :10.1016/c2015-0-01807-x. ISBN 9780128044520.
  5. ^ Soltanian, Mohammad Reza Khalifeh (10 de noviembre de 2015). Métodos teóricos y experimentales para la defensa contra ataques DDoS. ISBN 978-0-12-805399-7.OCLC 1162249290  .
  6. ^ Conrad, Eric; Misenar, Seth; Feldman, Joshua (2016), "Dominio 3: Ingeniería de seguridad (Ingeniería y gestión de la seguridad)", Guía de estudio CISSP , Elsevier, págs. 103-217, doi :10.1016/b978-0-12-802437-9.00004-7, ISBN 9780128024379, consultado el 8 de diciembre de 2021
  7. ^ Rajaraman, A.; Ullman, J. (2010). "Extracción de conjuntos de datos masivos, cap. 3".
  8. ^ ab Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). Funciones hash criptográficas: tendencias de diseño recientes y nociones de seguridad. Inscrypt '10.
  9. ^ Schema, Mike (2012). Hackear aplicaciones web .
  10. ^ abc Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (20 de agosto de 2014). "Una estrategia eficiente para la resolución de colisiones en tablas hash". Revista internacional de aplicaciones informáticas . 99 (10): 35–41. Bibcode :2014IJCA...99j..35N. doi : 10.5120/17411-7990 . ISSN  0975-8887.
  11. ^ Kline, Robert. "Closed Hashing". CSC241 Estructuras de datos y algoritmos . Universidad de West Chester . Consultado el 6 de abril de 2022 .
  12. ^ "Hash abierto o encadenamiento separado". Registro 2 2 .
  13. ^ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (eds.). Resolución de colisiones consciente de la memoria caché en tablas hash de cadenas . Simposio internacional sobre procesamiento de cadenas y recuperación de información. Procesamiento de cadenas y recuperación de información SPIRE 2005. Lecture Notes in Computer Science. Vol. 3772. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 91–102. doi :10.1007/11575832_11. ISBN. 978-3-540-29740-6.

Enlaces externos