A collision is when two different inputs to the same cryptographic hash function yield the same output. Cryptographic hash or “checksum” functions take an input such as a sequence of strings, or perhaps a binary application, and produce a fixed-size string of unqiue characters as output.
Similar to how we uniquely identify human beings by fingerprint, DNA, or handwriting signature, the output to a hash function is known as the input data's “signature” which should be unique for any given input value. Just as no two humans should share the same fingerprint, no two varying inputs to the same hash function should yield the same output. While this is optimal in theory, is not always the case in reality. Cryptographic hash functions often experience collisions-- that is, two different inputs which yield the same output signature.
Mathematically, collisions occur roughly at a rate of (1.25 * √S) where 'S' represents the number of outputs in a given set. For example, if your set has 25 outputs, then the likelihood of finding a collision in a set of 25 occurs after (1.25 * √25) times, or after about 6 iterations.
|
|
Last Updated on Saturday, 21 November 2009 09:37 |
Feed Entries 
Tech Encyclopedia 
