Fingerprint (computing)
Encyclopedia
In computer science
, a fingerprinting algorithm is a procedure that maps an arbitrarily large data
item (such as a computer file) to a much shorter bit string, its fingerprint, that uniquely identifies the original data for all practical purposes just as human fingerprint
s uniquely identify people for practical purposes. This fingerprint may be used for data deduplication
purposes.
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-performance hash function
s used to uniquely identify substantial blocks of data where cryptographic hash function
s may be unnecessary. Audio fingerprint algorithms should not be confused with this type of fingerprint function.
or by a meteorite
): say, 10−20 or less.
This requirement is somewhat similar to that of a checksum 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 least 64-bit long to guarantee virtual uniqueness in large file systems (see birthday 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.
s) or symbolic inclusion (as with the C 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.
is the prototype of the class. 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 strings r and s yielding the same w-bit fingerprint does not exceed max(|r|,|s|)/2w-1, where |r| denotes the length of r in bits. The algorithm requires the previous choice of a w-bit internal "key", and this guarantee holds as long as the strings r and s 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.
A drawback of cryptographic hash algorithms such as MD5
and SHA
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, notably MD5
, are no longer recommended for secure fingerprinting. They are still useful for error checking, where purposeful data tampering isn't a primary concern.
for relational databases emerged as candidate solutions to provide copyright protection, tamper detection, traitor tracing, maintaining integrity of relational data. Many techniques have been proposed in the literature to address these purposes. A survey of the current state-of-the-art and a classification of the different approaches according to their intent, the way they express the fingerprint/watermark, the cover type, the granularity level, and their verifiability, can be found in
.
, that uses cryptographic hash functions to fingerprint files and map them to software products. The HashKeeper
database, maintained by the National 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).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a fingerprinting algorithm is a procedure that maps an arbitrarily large data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
item (such as a computer file) to a much shorter bit string, its fingerprint, that uniquely identifies the original data for all practical purposes just as human fingerprint
Fingerprint
A fingerprint in its narrow sense is an impression left by the friction ridges of a human finger. In a wider use of the term, fingerprints are the traces of an impression from the friction ridges of any part of a human hand. A print from the foot can also leave an impression of friction ridges...
s uniquely identify people for practical purposes. This fingerprint may be used for data deduplication
Data deduplication
In computing, data deduplication is a specialized data compression technique for eliminating coarse-grained redundant data. The technique is used to improve storage utilization and can also be applied to network data transfers to reduce the number of bytes that must be sent across a link...
purposes.
Fingerprints are typically used to avoid the comparison and transmission of bulky data. For instance, a web browser
Web browser
A web browser is a software application for retrieving, presenting, and traversing information resources on the World Wide Web. An information resource is identified by a Uniform Resource Identifier and may be a web page, image, video, or other piece of content...
or proxy server
Proxy server
In computer networks, a proxy server is a server that acts as an intermediary for requests from clients seeking resources from other servers. A client connects to the proxy server, requesting some service, such as a file, connection, web page, or other resource available from a different 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-performance hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
s used to uniquely identify substantial blocks of data where cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s may be unnecessary. Audio fingerprint algorithms should not be confused with this type of fingerprint function.
Virtual uniqueness
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 a collision --- 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 by warWar
War is a state of organized, armed, and often prolonged conflict carried on between states, nations, or other parties typified by extreme aggression, social disruption, and usually high mortality. War should be understood as an actual, intentional and widespread armed conflict between political...
or by a meteorite
Meteorite
A meteorite is a natural object originating in outer space that survives impact with the Earth's surface. Meteorites can be big or small. Most meteorites derive from small astronomical objects called meteoroids, but they are also sometimes produced by impacts of asteroids...
): say, 10−20 or less.
This requirement is somewhat similar to that of a checksum 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 least 64-bit long to guarantee virtual uniqueness in large file systems (see birthday attack
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
).
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.
Compounding
Computer files are often combined in various ways, such as concatenation (as in archive fileArchive file
An archive file is a file that is composed of one or more files along with metadata that can include source volume and medium information, file directory structure, error detection and recovery information, file comments, and usually employs some form of lossless compression. Archive files may be...
s) or symbolic inclusion (as with the C preprocessor
C preprocessor
The C preprocessor is the preprocessor for the C and C++ computer programming languages. The preprocessor handles directives for source file inclusion , macro definitions , and conditional inclusion ....
'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 algorithm
Rabin's fingerprinting algorithmRabin fingerprint
The Rabin fingerprinting scheme is a method for implementing public key fingerprints using polynomials over a finite field.-Scheme:Given an n-bit message m0,...,mn-1, we view it as a polynomial of degree n-1 over the finite field GF....
is the prototype of the class. 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 strings r and s yielding the same w-bit fingerprint does not exceed max(|r|,|s|)/2w-1, where |r| denotes the length of r in bits. The algorithm requires the previous choice of a w-bit internal "key", and this guarantee holds as long as the strings r and s 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.
Cryptographic hash functions
Mainstream cryptographic grade hash functions generally can serve as high-quality fingerprint functions, are subject to intense scrutiny from cryptanalysts, and have the advantage that they are believed to be safe against malicious attacks.A drawback of cryptographic hash algorithms such as MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
and SHA
Sha
For other uses, see Sha .Sha is a letter of the Cyrillic alphabet. It commonly represents the voiceless postalveolar fricative , like the pronunciation of ⟨sh⟩ in "sheep", or the somewhat similar voiceless retroflex fricative . It is used in every variation of the Cyrillic alphabet, for Slavic and...
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, notably MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
, are no longer recommended for secure fingerprinting. They are still useful for error checking, where purposeful data tampering isn't a primary concern.
Fingerprinting and Watermarking for Relational Databases
Fingerprinting and Digital watermarkingDigital watermarking
Digital watermarking is the process of embedding information into a digital signal which may be used to verify its authenticity or the identity of its owners, in the same manner as paper bearing a watermark for visible identification. In digital watermarking, the signal may be audio, pictures, or...
for relational databases emerged as candidate solutions to provide copyright protection, tamper detection, traitor tracing, maintaining integrity of relational data. Many techniques have been proposed in the literature to address these purposes. A survey of the current state-of-the-art and a classification of the different approaches according to their intent, the way they express the fingerprint/watermark, the cover type, the granularity level, and their verifiability, can be found in
.
Application examples
NIST distributes a software reference library, the American National Software Reference LibraryNational Software Reference Library
The National Software Reference Library , a project of the National Institute of Standards and Technology, is supported by the United States Department of Justice's National Institute of Justice, federal, state, and local law enforcement, and the National Institute of Standards and Technology...
, that uses cryptographic hash functions to fingerprint files and map them to software products. The HashKeeper
HashKeeper
HashKeeper is a database application of value primarily to those conducting forensic examinations of computers on a somewhat regular basis.- Overview :...
database, maintained by the National Drug Intelligence Center
National Drug Intelligence Center
The U.S. National Drug Intelligence Center , established in 1993, is a component of the U.S. Department of Justice and a member of the Intelligence Community...
, 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).