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 .
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 la corrupción accidental de datos o errores de transmisión, 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.
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.
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.
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.
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).
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]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.
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++.