Hashing, Birthday and Passwords
What is a Hash function?
It’s an algorithm that maps an input of arbitrary length to a unique output of fixed length, this value is known as HASH, FINGERPRINT or DIGEST.
It is usually used to verify the integrity of data, in fact, digital signature algorithms are applied to the DIGEST and not to the entire document.
What are collisions?
Every input of HASH functions supposed to be mapped to a different output (DIGEST) but this is not always true, it’s possible to find two messages that may produce the same result, in this case, we have found a collision. That’s not all because for each message there are infinite collisions.
So what?
Security of HASH functions is based on the fact it’s very hard to find collisions knowing the hashed message. This is fundamental, let’s suppose we have digitally signed a document, someone knowing it may compute a variant disadvantageous for us, that collides that is to say it produces the same DIGEST.
So when using a HASH function we have to be sure it’s computationally impossible to find a collision, this safety is based on the birthday paradox.
