Incomputer science, afingerprinting algorithm is a procedure that maps an arbitrarily large data item (such as a computer file) to a much shorter bit string, itsfingerprint, that uniquely identifies the original data for all practical purposes just as human fingerprints uniquely identify people for practical purposes. This fingerprint may be used for data deduplication purposes. This is also referred to asfile fingerprinting,data fingerprinting, orstructured data fingerprinting.
Fingerprints are typically used to avoid the comparison and transmission of bulky data. For instance, a web browser or proxy server can efficiently check whether a remote file has been modified by fetching only its fingerprint and comparing it with that of the previously fetched copy.
Fingerprint functions may be seen as high-performancehash functions used to uniquely identify substantial blocks of data wherecryptographic hash functions may be unnecessary.
Special algorithms exist for audio and video fingerprinting.
To serve its intended purposes, a fingerprinting algorithm must be able to capture the identity of a file with virtual certainty. In other words, the probability of acollision — two files yielding the same fingerprint — must be negligible, compared to the probability of other unavoidable causes of fatal errors (such as the system being destroyed bywar or by ameteorite): say, 10−20 or less.
This requirement is somewhat similar to that of achecksum function, but is much more stringent. To detect accidental data corruption or transmission errors, it is sufficient that the checksums of the original file and any corrupted version will differ with near certainty, given some statistical model for the errors. In typical situations, this goal is easily achieved with 16- or 32-bit checksums. In contrast, file fingerprints need to be at least64-bit long to guarantee virtual uniqueness in large file systems (seebirthday attack).
When proving the above requirement, one must take into account that files are generated by highly non-random processes that create complicated dependencies among files. For instance, in a typical business network, one usually finds many pairs or clusters of documents that differ only by minor edits or other slight modifications. A good fingerprinting algorithm must ensure that such "natural" processes generate distinct fingerprints, with the desired level of certainty.
Computer files are often combined in various ways, such asconcatenation (as inarchive files) or symbolic inclusion (as with theC preprocessor's#include directive). Some fingerprinting algorithms allow the fingerprint of a composite file to be computed from the fingerprints of its constituent parts. This "compounding" property may be useful in some applications, such as detecting when a program needs to be recompiled.
Rabin's fingerprinting algorithm is the prototype of the class.[1] It is fast and easy to implement, allows compounding, and comes with a mathematically precise analysis of the probability of collision. Namely, the probability of two stringsr ands yielding the samew-bit fingerprint does not exceed max(|r|,|s|)/2w-1, where |r| denotes the length ofr in bits. The algorithm requires the previous choice of aw-bit internal "key", and this guarantee holds as long as the stringsr ands are chosen without knowledge of the key.
Rabin's method is not secure against malicious attacks. An adversarial agent can easily discover the key and use it to modify files without changing their fingerprint.
Mainstreamcryptographic grade hash functions generally can serve as high-quality fingerprint functions, are subject to intense scrutiny fromcryptanalysts, and have the advantage that they are believed to be safe against malicious attacks.
A drawback of cryptographic hash algorithms such asMD5 andSHA is that they take considerably longer to execute than Rabin's fingerprint algorithm. They also lack proven guarantees on the collision probability. Some of these algorithms, notablyMD5, are no longer recommended for secure fingerprinting. They are still useful for error checking, where purposeful data tampering is not a primary concern.
Perceptual hashing is the use of a fingerprinting algorithm that produces a snippet,hash, or fingerprint of various forms ofmultimedia.[2][3] A perceptual hash is a type oflocality-sensitive hash, which is analogous iffeatures of the multimedia are similar. This is in contrast tocryptographic hashing, which relies on theavalanche effect of a small change in input value creating a drastic change in output value. Perceptual hash functions are widely used in finding cases of onlinecopyright infringement as well as indigital forensics because of the ability to have a correlation between hashes so similar data can be found (for instance with a differingwatermark).
NIST distributes a software reference library, the AmericanNational Software Reference Library, that uses cryptographic hash functions to fingerprint files and map them to software products. TheHashKeeper database, maintained by theNational Drug Intelligence Center, is a repository of fingerprints of "known to be good" and "known to be bad" computer files, for use in law enforcement applications (e.g. analyzing the contents of seized disk drives).
Fingerprinting is currently the most widely applied approach to content similarity detection. This method forms representative digests of documents by selecting a set of multiple substrings (n-grams) from them. The sets represent the fingerprints and their elements are called minutiae.[4][5]A suspicious document is checked for plagiarism by computing its fingerprint and querying minutiae with a precomputed index of fingerprints for all documents of a reference collection. Minutiae matching with those of other documents indicate shared text segments and suggest potential plagiarism if they exceed a chosen similarity threshold.[6] Computational resources and time are limiting factors to fingerprinting, which is why this method typically only compares a subset of minutiae to speed up the computation and allow for checks in very large collection, such as the Internet.[4]
Keyless Signatures Infrastructure (KSI) is a globally distributed system for providing time-stamping and server-supported digital signature services. Global per-second hash trees are created and their root hash values published. We discuss some service quality issues that arise in practical implementation of the service and present solutions for avoiding single points of failure and guaranteeing a service with reasonable and stable delay. Guardtime AS has been operating a KSI Infrastructure for 5 years. We summarize how the KSI Infrastructure is built, and the lessons learned during the operational period of the service.
pHash is an open source software library released under the GPLv3 license that implements several perceptual hashing algorithms, and provides a C-like API to use those functions in your own programs. pHash itself is written in C++.