0

In my web application I have to store hashed values (using BCrypt) as ID for a database table.
The input for each hash value is a unique string.
I am concerned about possible collisions.
1) What is a chance to have collision (which will cause DB exception, while inserting new row with generated collided id)?
2) What are the means to prevent it?

Please do not advise, that hashed values can't be used as IDs.
However I'm not stick to BCrypt solely (alternative is ok).
The main task is to have unique secure hash values.

4
  • Can you describe what problem you're actually trying to solve with this scheme? And why do you need to use these values as the primary key on this table? Commented Jun 24, 2017 at 18:31
  • 1
    As far as the stated questions, you're essentially asking how to create a hash table. That's an introductory computer science topic, so there is plenty of material on it. Commented Jun 24, 2017 at 18:33
  • There is no hash algorithm that does not produce duplicates. So when you detect a collision just append a letter or somethint. It's not like these IDs are usable anyway
    – BlueWizard
    Commented Jun 25, 2017 at 21:57
  • You didn't name the database tdchnology at work here. Some DBs allow multiple Collums as ID so you could have the hash as ID as well as a number which you incremend for every collision. Alternatively you could just assign a different salt when the current hash would be a duplicate
    – BlueWizard
    Commented Jun 25, 2017 at 21:59

1 Answer 1

0

If you're using bcrypt, then in addition to the plaintext/password you're hashing, bcrypt requires a salt and a work factor. I'm assuming you're keeping the work factor constant, but you didn't say about the salt.

Generally, the collision probability of a good hash function depends on the size of the hash's output. The birthday paradox makes collisions much more frequent than your intuition allows for; a (very rough) approximation is to take the square root of the number of possible outputs (call the result n) and assume that you'll see a collision after hashing n inputs.

So, if you kept the salt constant, you'd get 184 bits of output space, translating to about 1 collision in 292 hashed inputs. If you used a random salt on every input, you'd have an additional 128 bits of output space, further improving collision resistance.

Note that these are probabilities, not guarantees. So you might produce your first collision much earlier than expected, even though it's unlikely. Still, you should probably plan for collisions. If you actually produced a collision, you could change the salt and try again until you went collision-free; that's simple enough to not complicate your code much.

This article gives you the math behind calculating hash collision probabilities.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .