Huella dactilar (informática)
Identificador digital derivado de los datos mediante un algoritmo

En informática , un algoritmo de huellas dactilares es un procedimiento que asigna un elemento de datos arbitrariamente grande (como un archivo de computadora) a una cadena de bits mucho más corta , su huella digital , que identifica de forma única los datos originales para todos los fines prácticos, al igual que las huellas dactilares humanas identifican de forma única a las personas para fines prácticos. [1] Esta huella dactilar se puede utilizar para fines de deduplicación de datos . Esto también se conoce como huella dactilar de archivos , huella dactilar de datos o huella dactilar de datos estructurados .

Las huellas digitales se utilizan normalmente para evitar la comparación y transmisión de datos voluminosos. Por ejemplo, un navegador web o un servidor proxy pueden comprobar de forma eficaz si se ha modificado un archivo remoto, obteniendo únicamente su huella digital y comparándola con la de la copia obtenida anteriormente. [2] [3] [4] [5] [6]

Las funciones de huellas dactilares pueden considerarse funciones hash de alto rendimiento utilizadas para identificar de forma única bloques sustanciales de datos donde las funciones hash criptográficas pueden ser innecesarias.

Existen algoritmos especiales para la toma de huellas digitales de audio y de vídeo .

Una función hash en funcionamiento

Propiedades

Unicidad virtual

Para cumplir con sus propósitos, un algoritmo de identificación de huellas digitales debe ser capaz de capturar la identidad de un archivo con una certeza virtual. En otras palabras, la probabilidad de una colisión (que dos archivos den la misma huella digital) debe ser insignificante, comparada con la probabilidad de otras causas inevitables de errores fatales (como que el sistema sea destruido por una guerra o por un meteorito ): digamos, 10 −20 o menos.

Este requisito es similar al de una función de suma de comprobación , pero es mucho más estricto. Para detectar errores de transmisión o corrupción de datos accidentales, es suficiente que las sumas de comprobación del archivo original y cualquier versión dañada difieran con casi total certeza, dado algún modelo estadístico para los errores. En situaciones típicas, este objetivo se logra fácilmente con sumas de comprobación de 16 o 32 bits. Por el contrario, las huellas digitales de archivos deben tener al menos 64 bits de longitud para garantizar la unicidad virtual en sistemas de archivos grandes (consulte el ataque de cumpleaños ).

Al probar el requisito anterior, se debe tener en cuenta que los archivos se generan mediante procesos altamente no aleatorios que crean dependencias complicadas entre los archivos. Por ejemplo, en una red empresarial típica, normalmente se encuentran muchos pares o grupos de documentos que difieren solo por ediciones menores u otras modificaciones leves. Un buen algoritmo de identificación de huellas digitales debe garantizar que dichos procesos "naturales" generen huellas digitales distintas, con el nivel deseado de certeza.

Composición

Los archivos de computadora suelen combinarse de varias maneras, como por ejemplo mediante concatenación (como en los archivos de almacenamiento ) o inclusión simbólica (como con la directiva #include del preprocesador de C ). Algunos algoritmos de identificación permiten calcular la huella de un archivo compuesto a partir de las huellas de sus partes constituyentes. Esta propiedad de "combinación" puede ser útil en algunas aplicaciones, como por ejemplo para detectar cuándo es necesario volver a compilar un programa.

Algoritmos

El algoritmo de Rabin

El algoritmo de huellas dactilares de Rabin es el prototipo de la clase. [7] Es rápido y fácil de implementar, permite la composición y viene con un análisis matemáticamente preciso de la probabilidad de colisión. Es decir, la probabilidad de que dos cadenas r y s produzcan la misma huella dactilar de w bits no excede max(| r |,| s |)/2 w -1 , donde | r | denota la longitud de r en bits. El algoritmo requiere la elección previa de una "clave" interna de w bits, y esta garantía se mantiene siempre que las cadenas r y s se elijan sin conocimiento de la clave.

El método de Rabin no es seguro contra ataques maliciosos. Un agente adversario puede descubrir fácilmente la clave y usarla para modificar archivos sin cambiar su huella digital.

Funciones hash criptográficas

Las funciones hash de grado criptográfico convencionales generalmente pueden servir como funciones de huellas dactilares de alta calidad, están sujetas a un escrutinio intenso por parte de los criptoanalistas y tienen la ventaja de que se cree que son seguras contra ataques maliciosos.

Una desventaja de los algoritmos de hash criptográficos como MD5 y SHA es que tardan considerablemente más en ejecutarse que el algoritmo de huellas dactilares de Rabin. También carecen de garantías probadas sobre la probabilidad de colisión. Algunos de estos algoritmos, en particular MD5 , ya no se recomiendan para la toma de huellas dactilares seguras. Siguen siendo útiles para la comprobación de errores, donde la manipulación intencionada de datos no es una preocupación principal.

Hashing perceptivo

El hash perceptual es el uso de un algoritmo de huellas digitales que produce un fragmento, hash o huella digital de varias formas de multimedia . [8] [9] Un hash perceptual es un tipo de hash sensible a la localidad , que es análogo si las características del multimedia son similares. Esto contrasta con el hash criptográfico , que se basa en el efecto de avalancha de un pequeño cambio en el valor de entrada que crea un cambio drástico en el valor de salida. Las funciones hash perceptuales se utilizan ampliamente para encontrar casos de infracción de derechos de autor en línea , así como en la investigación forense digital debido a la capacidad de tener una correlación entre hashes para que se puedan encontrar datos similares (por ejemplo, con una marca de agua diferente ).

Ejemplos de aplicación

El NIST distribuye una biblioteca de referencia de software, la Biblioteca Nacional de Referencia de Software de Estados Unidos , que utiliza funciones criptográficas hash para identificar archivos y asignarlos a productos de software. La base de datos HashKeeper , mantenida por el Centro Nacional de Inteligencia sobre Drogas , es un repositorio de huellas digitales de archivos informáticos "conocidos como buenos" y "conocidos como malos", para su uso en aplicaciones de aplicación de la ley (por ejemplo, analizar el contenido de unidades de disco incautadas).

Detección de similitud de contenido

La toma de huellas dactilares es actualmente el método más utilizado para la detección de similitud de contenido. Este método forma resúmenes representativos de documentos seleccionando un conjunto de múltiples subcadenas ( n-gramas ) de ellos. Los conjuntos representan las huellas dactilares y sus elementos se denominan minucias. [10] [11]

Un documento sospechoso se comprueba en busca de plagio calculando su huella digital y consultando los detalles minuciosos con un índice de huellas digitales precalculado para todos los documentos de una colección de referencia. Los detalles minuciosos que coinciden con los de otros documentos indican segmentos de texto compartidos y sugieren plagio potencial si superan un umbral de similitud elegido. [12] Los recursos computacionales y el tiempo son factores limitantes para la identificación de huellas digitales, por lo que este método normalmente solo compara un subconjunto de detalles minuciosos para acelerar el cálculo y permitir verificaciones en colecciones muy grandes, como Internet. [10]

Véase también

Referencias

  1. ^ Broder, AZ (1993). "Algunas aplicaciones del método de huellas dactilares de Rabin". Secuencias II: métodos en comunicaciones, seguridad y ciencias de la computación . Springer. págs. 143–152. ISBN. 0-387-97940-9.
  2. ^ Detección de archivos duplicados y casi duplicados. Patente de EE. UU. 6658423 Publicada el 2 de diciembre de 2003
  3. ^ AZ Broder (1998). "Sobre la semejanza y la contención de los documentos". Actas. Compresión y complejidad de secuencias 1997 (Cat. No.97TB100171) . IEEE Computer Society. pp. 21–27. CiteSeerX 10.1.1.24.779 . doi :10.1109/SEQUEN.1997.666900. ISBN .  978-0-8186-8132-5. Número de identificación del sujeto  11748509.
  4. ^ Brin, S. y Davis, J. y Garcia-Molina, H. (1995) Mecanismos de detección de copias para documentos digitales Archivado el 18 de agosto de 2016 en Wayback Machine . En: ACM International Conference on Management of Data (SIGMOD 1995), 22-25 de mayo de 1995, San José, California, de stanford.edu. 18/08/2016. Consultado el 11/01/2019.
  5. ^ Fan, L.; Cao, P.; Almeida, J.; Broder, A. (2000). "Caché de resumen: un protocolo escalable de uso compartido de caché web de área amplia". Transacciones IEEE/ACM sobre redes . 8 (3): 281–293. doi :10.1109/90.851975.
  6. ^ Manber, U. (1994). "Cómo encontrar archivos similares en un sistema de archivos grande". Actas de la conferencia técnica de invierno de USENIX .
  7. ^ Rabin, MO (1981). "Huellas dactilares mediante polinomios aleatorios". Centro de Investigación en Tecnología Informática, Universidad de Harvard, Informe TR-15-81 .
  8. ^ Buldas, Ahto; Kroonmaa, Andrés; Laanoja, Risto (2013). "Infraestructura de firmas sin llave: cómo construir árboles hash distribuidos globalmente". En Riis, Nielson H.; Gollmann, D. (eds.). Sistemas TI seguros. NordSec 2013 . Apuntes de conferencias sobre informática. vol. 8208. Berlín, Heidelberg: Springer. doi :10.1007/978-3-642-41488-6_21. ISBN 978-3-642-41487-9. ISSN  0302-9743. La Infraestructura de Firmas Sin Clave (KSI) es un sistema distribuido globalmente para proporcionar servicios de sellado de tiempo y firma digital con soporte de servidor. Se crean árboles hash globales por segundo y se publican sus valores hash raíz. Analizamos algunos problemas de calidad del servicio que surgen en la implementación práctica del servicio y presentamos soluciones para evitar puntos únicos de falla y garantizar un servicio con un retraso razonable y estable. Guardtime AS ha estado operando una Infraestructura de KSI durante 5 años. Resumimos cómo se construye la Infraestructura de KSI y las lecciones aprendidas durante el período operativo del servicio.
  9. ^ Klinger, Evan; Starkweather, David. "pHash.org: Home of pHash, the open source perceptual hash library" (pHash.org: hogar de pHash, la biblioteca de hash perceptual de código abierto). pHash.org . Consultado el 5 de julio de 2018. pHash es una biblioteca de software de código abierto publicada bajo la licencia GPLv3 que implementa varios algoritmos de hash perceptual y proporciona una API similar a C para usar esas funciones en sus propios programas. pHash está escrito en C++.
  10. ^ ab Hoad, Timothy; Zobel, Justin (2003), "Métodos para identificar documentos plagiados y versionados" (PDF) , Journal of the American Society for Information Science and Technology , 54 (3): 203–215, CiteSeerX 10.1.1.18.2680 , doi :10.1002/asi.10170, archivado desde el original (PDF) el 30 de abril de 2015 , consultado el 14 de octubre de 2014 
  11. ^ Stein, Benno (julio de 2005), "Fuzzy-Fingerprints for Text-Based Information Retrieval", Actas de la I-KNOW '05, 5.ª Conferencia internacional sobre gestión del conocimiento, Graz, Austria (PDF) , Springer, Know-Center, págs. 572-579, archivado desde el original (PDF) el 2 de abril de 2012 , consultado el 7 de octubre de 2011
  12. ^ Brin, Sergey; Davis, James; Garcia-Molina, Hector (1995), "Mecanismos de detección de copias para documentos digitales", Actas de la Conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos (PDF) , ACM, págs. 398–409, CiteSeerX 10.1.1.49.1567 , doi :10.1145/223784.223855, ISBN  978-1-59593-060-6, S2CID  8652205, archivado desde el original (PDF) el 18 de agosto de 2016 , consultado el 7 de octubre de 2011
Obtenido de "https://es.wikipedia.org/w/index.php?title=Huella_digital_(informática)&oldid=1247329284"