En informática , un algoritmo de toma de huellas digitales 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 manera única los datos originales para todos los propósitos prácticos [1] tal como lo hace el ser humano. Las huellas dactilares identifican de forma única a las personas a efectos prácticos. Esta huella digital se puede utilizar con fines de deduplicación de datos . Esto también se conoce como huella digital de archivos , huella digital de datos o huella digital de datos estructurados .
Las huellas dactilares se suelen utilizar para evitar la comparación y transmisión de datos voluminosos. Por ejemplo, un navegador web o un servidor proxy puede verificar de manera eficiente si un archivo remoto ha sido modificado, obteniendo solo su huella digital y comparándola con la de la copia obtenida anteriormente. [2] [3] [4] [5] [6]
Las funciones de huellas dactilares pueden verse como 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 dactilares de audio y de vídeo .
Para cumplir los fines previstos, un algoritmo de toma de huellas digitales debe poder capturar la identidad de un archivo con virtual certeza. En otras palabras, la probabilidad de una colisión (dos archivos que arrojan la misma huella digital) debe ser insignificante, en comparación 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 algo similar al de una función de suma de comprobación , pero es mucho más estricto. Para detectar daños accidentales en los datos o errores de transmisión, es suficiente que las sumas de verificación del archivo original y cualquier versión dañada difieran con casi 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 los 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 demostrar el requisito anterior, se debe tener en cuenta que los archivos se generan mediante procesos altamente no aleatorios que crean dependencias complicadas entre archivos. Por ejemplo, en una red empresarial típica, normalmente se encuentran muchos pares o grupos de documentos que se diferencian sólo por ediciones menores u otras modificaciones leves. Un buen algoritmo de toma de huellas dactilares debe garantizar que dichos procesos "naturales" generen huellas dactilares distintas, con el nivel deseado de certeza.
Los archivos de computadora a menudo se combinan de varias maneras, como la concatenación (como en los archivos de almacenamiento ) o la inclusión simbólica (como con la directiva #include del preprocesador C ). Algunos algoritmos de huellas dactilares permiten calcular la huella digital de un archivo compuesto a partir de las huellas dactilares de sus partes constituyentes. Esta propiedad de "composición" puede resultar útil en algunas aplicaciones, como detectar cuándo es necesario volver a compilar un programa.
El algoritmo de huellas dactilares de Rabin [7] es el prototipo de la clase. Es rápido y fácil de implementar, permite la capitalizació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 digital 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 intenso escrutinio por parte de los criptoanalistas y tienen la ventaja de que se cree que son seguras contra ataques maliciosos.
Una desventaja de los algoritmos hash criptográficos como MD5 y SHA es que tardan mucho 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 segura. Siguen siendo útiles para la verificación de errores, donde la manipulación intencionada de datos no es una preocupación principal.
NIST distribuye una biblioteca de referencia de software, la Biblioteca Nacional Estadounidense de Referencia de Software , que utiliza funciones hash criptográficas para tomar huellas dactilares de archivos y asignarlos a productos de software. La base de datos HashKeeper , mantenida por el Centro Nacional de Inteligencia sobre Drogas , es un depósito de huellas dactilares de archivos informáticos "conocidos como buenos" y "conocidos como malos", para su uso en aplicaciones policiales (por ejemplo, análisis del contenido de unidades de disco incautadas). .
La toma de huellas dactilares es actualmente el enfoque más aplicado para la detección de similitudes 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]
Se comprueba que un documento sospechoso no sea plagio calculando su huella digital y consultando minucias con un índice de huellas dactilares precalculado para todos los documentos de una colección de referencia. Las minucias que coinciden con las de otros documentos indican segmentos de texto compartidos y sugieren un posible plagio si superan un umbral de similitud elegido. [12] Los recursos computacionales y el tiempo son factores limitantes para la toma de huellas dactilares, razón por la cual este método generalmente solo compara un subconjunto de minucias para acelerar el cálculo y permitir controles en colecciones muy grandes, como Internet. [10]{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )Keyless Signatures Infrastructure (KSI) es un sistema distribuido globalmente para proporcionar servicios de firma digital respaldados por servidor y sellado de tiempo. Se crean árboles hash globales por segundo y se publican sus valores hash raíz. Discutimos 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 demoras razonables y estables. Guardtime AS opera una infraestructura KSI desde hace 5 años. Resumimos cómo se construye la infraestructura KSI y las lecciones aprendidas durante el período operativo del servicio.
pHash es una biblioteca de software de código abierto publicada bajo la licencia GPLv3 que implementa varios algoritmos de hash de percepción y proporciona una API similar a C para usar esas funciones en sus propios programas.
El propio pHash está escrito en C++.