Hashing difuso

Técnica algorítmica que utiliza hash

El hash difuso , también conocido como hash de similitud, ^[1] es una técnica para detectar datos que son similares , pero no exactamente iguales, a otros datos. Esto contrasta con las funciones hash criptográficas , que están diseñadas para tener hashes significativamente diferentes incluso para diferencias menores. El hash difuso se ha utilizado para identificar malware ^{[2] [3]} y tiene potencial para otras aplicaciones, como la prevención de pérdida de datos y la detección de múltiples versiones de código. ^{[4] [5]}

Fondo

Una función hash es un algoritmo matemático que asigna datos de tamaño arbitrario a una salida de tamaño fijo. Muchas soluciones utilizan funciones hash criptográficas como SHA-256 para detectar duplicados o comprobar si hay archivos conocidos dentro de una gran colección de archivos. ^[4] Sin embargo, las funciones hash criptográficas no se pueden utilizar para determinar si un archivo es similar a un archivo conocido, porque uno de los requisitos de una función hash criptográfica es que un pequeño cambio en la entrada debe cambiar el valor hash de manera tan extensa que el nuevo valor hash parezca no estar correlacionado con el valor hash anterior ( efecto avalancha ) ^[6]

El algoritmo de hash difuso existe para resolver este problema de detección de datos que son similares, pero no exactamente iguales, a otros datos. Los algoritmos de hash difuso utilizan específicamente algoritmos en los que dos entradas similares generarán dos valores de hash similares. Esta propiedad es exactamente lo opuesto al efecto de avalancha deseado en las funciones de hash criptográficas.

El hash difuso también se puede utilizar para detectar cuándo un objeto está contenido dentro de otro. ^[1]

Enfoques para el hash difuso

Existen algunos enfoques utilizados para construir algoritmos hash difusos: ^{[7] [5]}

• Hashing por partes activado por contexto (CTPH), que construye un hash dividiendo la entrada en varias partes, calculando hashes tradicionales para cada parte y luego combinando esos hashes tradicionales en una sola cadena. ^[8]
• El hash sensible a la localidad coloca elementos de entrada similares en los mismos "depósitos", que se pueden usar para agrupar datos y realizar búsquedas de vecinos más cercanos.

Herramientas y algoritmos de hash difuso notables

• Spamsum es una herramienta escrita por Andrew Tridgell que utiliza un algoritmo hash difuso para determinar si un correo electrónico es similar a un correo no deseado conocido. Funciona generando un algoritmo hash difuso para un correo electrónico que compara con los algoritmos hash difusos de correos electrónicos no deseados conocidos para generar un resultado de coincidencia entre 0 (discordancia total) y 100 (coincidencia perfecta). Si el resultado de la coincidencia es lo suficientemente alto, el correo electrónico se clasifica como correo no deseado. ^{[9] [10]}
• Nilsimsa Hash es un algoritmo hash sensible a la localidad y centrado en la lucha contra el spam .
• ssdeep es una herramienta de hash difuso basada en hash activado por fragmentos de contexto para comparar archivos. ^[4]
• sdhash es una herramienta de hash difuso basada en el uso de filtros Bloom para determinar si un archivo está contenido dentro de otro o qué tan similares son dos archivos entre sí. ^[11]
• TLSH es un esquema de hash sensible a la localidad para comparar si los archivos son similares entre sí y se ha utilizado para la agrupación de malware. ^[12]

Véase también

• Hash de Nilsimsa
• Hashing sensible a la localidad
• Suma de comprobación#Fuzzy_checksum

Referencias

1. Breitinger, Frank (mayo de 2014). "Publicación especial NIST 800-168" (PDF) . Publicaciones del NIST . doi :10.6028/NIST.SP.800-168 . Consultado el 11 de enero de 2023 .
2. Pagani, Fabio; Dell'Amico, Matteo; Balzarotti, Davide (13 de marzo de 2018). "Más allá de la precisión y la recuperación" (PDF) . Actas de la octava conferencia de la ACM sobre seguridad y privacidad de datos y aplicaciones . Nueva York, NY, EE. UU.: ACM. págs. 354–365. doi :10.1145/3176258.3176306. ISBN 9781450356329. Recuperado el 12 de diciembre de 2022 .
3. Sarantinos, Nikolaos; Benzaïd, Chafika; Arabiat, Omar (2016). "Análisis forense de malware: el valor de los algoritmos de hash difusos para identificar similitudes". 2016 IEEE Trustcom/BigDataSE/ISPA (PDF) . págs. 1782–1787. doi :10.1109/TrustCom.2016.0274. ISBN. 978-1-5090-3205-1.S2CID 32568938.10.1109  /TrustCom.2016.0274.
4. Kornblum, Jesse (2006). "Identificación de archivos casi idénticos mediante hash por partes activado por contexto". Digital Investigation . 3, Suplemento (septiembre de 2006): 91–97. doi : 10.1016/j.diin.2006.06.015 . Consultado el 30 de junio de 2022 .
5. Oliver, Jonathan; Cheng, Chun; Chen, Yanggui (2013). "TLSH: un hash sensible a la localidad" (PDF) . Cuarto taller sobre ciberdelincuencia y computación confiable de 2013. IEEE. págs. 7–13. doi :10.1109/ctc.2013.9. ISBN. 978-1-4799-3076-0. Recuperado el 12 de diciembre de 2022 .
6. Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). "Funciones hash criptográficas: tendencias de diseño recientes y nociones de seguridad". Archivo de criptografía electrónica . Informe 2011/565.
7. Oliver, Jonathan; Hagen, Josiah (2021). "Diseño de los elementos de un esquema de hash difuso" (PDF) . 2021 IEEE 19th International Conference on Embedded and Ubiquitous Computing (EUC) . IEEE. págs. 1–6. doi :10.1109/euc53437.2021.00028. ISBN . 978-1-6654-0036-7Archivado desde el original (PDF) el 14 de abril de 2021 . Consultado el 14 de abril de 2021 .
8. "Open Source Similarity Digests DFRWS August 2016" (PDF) . tlsh.org . Consultado el 11 de diciembre de 2022 .
9. "spamsum README". samba.org . Consultado el 11 de diciembre de 2022 .
10. "spamsum.c". samba.org . Consultado el 11 de diciembre de 2022 .
11. Roussev, Vassil (2010). "Huellas dactilares de datos con compendios de similitud". Avances en la ciencia forense digital VI . IFIP Avances en la tecnología de la información y la comunicación. Vol. 337. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 207–226. doi :10.1007/978-3-642-15506-2_15. ISBN 978-3-642-15505-5. ISSN  1868-4238.
12. "Agrupamiento rápido de datos de alta dimensión: agrupamiento del conjunto de datos de Malware Bazaar" (PDF) . tlsh.org . Consultado el 11 de diciembre de 2022 .