Hispanopedia Wiki
Articulo de referencia

Colisión de hash

John Smith y Sandra Dee comparten el mismo valor hash, 02, lo que provoca una colisión de hash. En informática , una colisión de hash o choque de hash [ 1 ] ocurre cuando dos da...

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

En informática , una colisión de hash o choque de hash [ 1 ] ocurre cuando dos datos distintos en 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 ]

El hash se utiliza típicamente como una función de muchos a uno , donde el número de entradas potenciales (tamaño del dominio de entrada ) es mucho mayor que el número de valores de salida potenciales ("rango"), lo que hace inevitables las colisiones (" principio del palomar "). Para las funciones hash criptográficas (CHF), la salida es una representación compacta de un valor de entrada particular que los algoritmos de integridad de datos utilizan para operar de manera eficiente, empleando esta representación en lugar de los datos de entrada mucho más grandes. [ 3 ] Una colisión viola los supuestos de los algoritmos de integridad, por lo que las CHF están diseñadas para que encontrar una colisión práctica sea computacionalmente inviable (la llamada resistencia a colisiones ). [ 3 ]

Los usos típicos de las funciones hash no criptográficas (FHCN), como los filtros Bloom , las tablas hash y los esquemas de conteo , son menos sensibles a las colisiones, por lo que las FHCN solo requieren la distribución uniforme y las propiedades de avalancha . [ 4 ] Aun así, la resistencia a las colisiones es una característica adicional que resulta útil contra los ataques de inundación de hash ; las FHCN simples, como la verificación de redundancia cíclica (CRC), prácticamente no tienen resistencia a las colisiones [ 5 ] y, por lo tanto, no pueden utilizarse con una entrada susceptible de manipulación por parte de un atacante. Las aplicaciones no criptográficas emplean múltiples formas de gestionar las colisiones de hash cuando se producen.

Fondo

Las colisiones de hash pueden ser inevitables dependiendo del número de objetos en un conjunto y de si la cadena de bits a la que se asignan es lo suficientemente larga. Cuando hay un conjunto denorte{\displaystyle n}objetos, sinorte{\displaystyle n}es mayor que|R|{\displaystyle |R|}, que en este casoR{\displaystyle R}es el conjunto de los valores hash, se garantiza que ocurrirá una colisión de hash. [ 6 ]

Otra razón por la que es probable que se produzcan colisiones de hash 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 de entre un conjunto denorte{\displaystyle n}número de personas. [ 7 ] 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 tuyo o con un cumpleaños específico, pero la probabilidad de encontrar un conjunto de dos personas cualesquiera con cumpleaños coincidentes aumenta considerablemente. Los ciberdelincuentes pueden utilizar este enfoque para simplificar la búsqueda de valores hash que colisionan con cualquier otro valor hash, en lugar de buscar un valor específico. [ 8 ]

El impacto de las colisiones depende de la aplicación. Cuando se utilizan funciones hash y huellas digitales para identificar datos similares, como secuencias de ADN homólogas o archivos de audio similares, las funciones se diseñan para maximizar la probabilidad de colisión entre datos distintos pero similares, utilizando técnicas como el hashing sensible a la localidad . [ 9 ] Por otro lado, las sumas de verificación se diseñan para minimizar la probabilidad de colisiones entre entradas similares, sin tener en cuenta las colisiones entre entradas muy diferentes. [ 10 ] Los casos en los que actores malintencionados intentan crear o encontrar colisiones de hash se conocen como ataques de colisión. [ 11 ]

En la práctica, las aplicaciones relacionadas con la seguridad utilizan algoritmos hash criptográficos, diseñados para ser lo suficientemente largos como para que las coincidencias aleatorias sean improbables, lo suficientemente rápidos como para poder usarse en cualquier lugar y lo suficientemente seguros como para que sea extremadamente difícil encontrar colisiones. [ 10 ]

Resolución de colisiones

En las tablas hash, dado que las colisiones de hash son inevitables, existen mecanismos para gestionarlas, conocidos como resolución de colisiones. Dos de las estrategias más comunes son el direccionamiento abierto y el encadenamiento separado . La resolución de colisiones con optimización de caché es otra estrategia que se ha analizado anteriormente para tablas hash de cadenas.

Tanto John Smith como Sandra Dee están siendo dirigidos a la misma celda. El direccionamiento abierto provocará que la tabla hash redirija a Sandra Dee a otra celda.

Dirección abierta

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 esté marcada 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 doble hash y el sondeo cuadrático . [ 12 ] El direccionamiento abierto también se conoce como hash cerrado. [ 13 ]

encadenamiento separado

Esta estrategia permite que más de un registro se "encadene" a las celdas de una tabla hash. Si dos registros se dirigen a la misma celda, ambos se insertarán en ella como una lista enlazada. Esto evita eficazmente las colisiones de hash, ya que los registros con el mismo valor hash pueden insertarse en la misma celda, pero tiene sus desventajas. Gestionar tantas listas es difícil y puede ralentizar considerablemente la herramienta utilizada. [ 12 ] El encadenamiento separado también se conoce como hash abierto. [ 14 ]

Resolución de colisiones con conciencia de la caché

Aunque mucho menos utilizado que los dos anteriores, Askitis y Zobel (2005) propusieron el método de resolución de colisiones consciente de la caché en 2005. [ 15 ] Es una idea similar a los métodos de encadenamiento separados, aunque técnicamente no involucra 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 su uso para valores numéricos aún se desconoce. [ 12 ]

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, pp. 83–114 , doi : 10.1016/b978-075068215-2.50006-9 , ISBN  9780750682152, consultado el 8 de diciembre de 2021
  3. ^ Menezes , van Oorschot y Vanstone 1997 , pág. 321.
  4. ^ Sateesan y col. 2023 , pág. 2.
  5. ↑ Sello 2011 .
  6. ↑ Ciberseguridad y Matemáticas Aplicadas . 2016. doi : 10.1016/c2015-0-01807-x . ISBN 9780128044520.
  7. ↑ 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-7OCLC 1162249290​​ 
  8. ↑ 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
  9. ↑ Rajaraman, A.; Ullman, J. (2010). "Minería de conjuntos de datos masivos, Cap. 3" .
  10. 1 2 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.
  11. ↑ Schema, Mike (2012). Hacking Web Apps .
  12. 1 2 3 Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (2014-08-20). "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 . 
  13. ↑ Kline, Robert. "Closed Hashing" . CSC241 Estructuras de datos y algoritmos . Universidad de West Chester . Consultado el 6 de abril de 2022 .
  14. ↑ "Hashing abierto o encadenamiento separado" . Log 2 2 .
  15. ↑ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (eds.). Resolución de colisiones con optimización de 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. Notas de clase en informática. Vol. 3772. Berlín, Heidelberg: Springer Berlin Heidelberg. pp. 91–102 . doi : 10.1007/11575832_11 . ISBN   978-3-540-29740-6.

Fuentes

  • Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). Manual de criptografía aplicada . Matemáticas discretas y sus aplicaciones. Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8523-0.{{cite book}}: CS1 mantenimiento: referencia duplica el valor predeterminado ( enlace )
  • Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (abril de 2023). "Algoritmos y arquitecturas optimizadas para funciones hash rápidas no criptográficas en hardware" (PDF) . Microprocessors and Microsystems . 98 104782. doi : 10.1016/j.micpro.2023.104782 . ISSN 0141-9331 . 
  • Stamp, Mark (8 de noviembre de 2011). «Hashes no criptográficos» . Seguridad de la información: principios y práctica (2.ª  ed.). John Wiley & Sons. ISBN 978-1-118-02796-7OCLC 1039294381​​