Hash Collision - what are the chances? [closed]

I have some code on my PHP powered site that creates a random hash (using sha1()) and I use it to match records in the database.

What are the chances of a collision? Should I generate the hash, then check first if it's in the database (I'd rather avoid an extra query) or automatically insert it, based on the probability that it probably won't collide with another.

If you assume that SHA-1 does a good job, you can conclude that there's a 1 in 2^160 chance that two given messages have the same hash (since SHA-1 produces a 160-bit hash).

2^160 is a ridiculously large number. It's roughly 10^48. Even if you have a million entries in your database, that's still a 1 in 10^42 chance that a new entry will share the same hash.

SHA-1 has proved to be fairly good, so I don't think you need to worry about collisions at all.

As a side note, use PHP's raw_output feature when you use SHA-1 as this will lead to a shorter string and hence will make your database operations a bit faster.

EDIT: To address the birthday paradox, a database with 10^18 (a million million million) entries has a chance of about 1 in 0.0000000000003 of a collision. Really not worth worrying about.

Use a symmetric encryption scheme and a private server key to encrypt the ID (and other values) when you send them to the client and decrypt again on reception. Take care that your cryptographic function provides both confidentiality and integrity checks.

This allows you to use sensible values when talking to the DB without any collision, great security when talking to the client and reduces your probability to land on thedailyWTF by approximatly 2^160.

See also Pounding A Nail: Old Shoe or Glass Bottle?!

why not do something which guarantees there'll be no collisions, as well as makes sure that no one can change a GET parameter to view something they shouldn't: using a salt, combine the id and its hash.

$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5

even if you do accidentally stumble upon two numbers which have the exact same sha1 hash (with your salt), then the $key will still be different and you'll avoid all collisions.