1
$\begingroup$

It is often suggested that hashing of long character columns can be used for indexing in databases, but the possibility of collisions is an issue for Unique indexes. Whilst I know that both MD5 and SHA-256 can (rarely) produce collisions, I was wondering what the possibility of them both clashing at the same point with the same input? In other words, if I produce a Unique key by running both MD5 and SHA-2 against the same character field and combining them to make the Unique key, is this collision free.

$\endgroup$
5
  • 2
    $\begingroup$ If you find a collision for SHA256 you will be famous. The collision probability is $2^{128}$ with 50%. If you fear just use a 512 bit hash like SHA-512. And note that there question and anwers for this in this site. $\endgroup$ – kelalaka Sep 3 '20 at 16:11
  • 1
    $\begingroup$ Perhaps you meant SHA-1 instead of SHA-256? If so, see crypto.stackexchange.com/questions/36988/… which asks about the effort needed to find a simultaneous collision... $\endgroup$ – poncho Sep 3 '20 at 18:07
  • 1
    $\begingroup$ related crypto.stackexchange.com/questions/270/… $\endgroup$ – Richie Frame Sep 3 '20 at 20:24
  • 1
    $\begingroup$ @kelalaka to be pedantic, the probability of a collision after $2^{128}$ (uniformly random) hashes is approximately $e^{-k^2 / 2n}$ (with $k = 2^{128}, n = 2^{256}$), which is slightly over $60\%$. Of course, your heuristic is close enough for practical purposes. $\endgroup$ – Daniel Lubarov Sep 4 '20 at 6:58
  • $\begingroup$ @DanielLubarov Yes, If we provide better approaches. It was a mobile comment, anyway, I should use $\approx$ $\endgroup$ – kelalaka Sep 4 '20 at 8:27
3
$\begingroup$

Currently no collisions are known for SHA-256 and it can be used safely to hash long texts and you can be confident you won't happen to get a collision by chance.

Generally speaking if we have two different hash functions and $f$ and $g$ and you hash some input $x$ with both and use the concatenation $f(x)||g(x)$ the collision resistance of this will be better than either function individually and in some cases much better. If the functions are unrelated and you are only worried about chance collision the likelihood of a collision will be the product of the likelihood of collision in each function individually. However this last statement will not hold in face of an attacker exploiting weakness in these function. It's still harder that either individually but may not be noticeably harder to find a collision than finding a collision in just one of the two.

Other techniques of combining the functions such as $f(g(x))$ are ill advised and won't add security, since any collision of $g$ is also a collision in the composition.

$\endgroup$
6
  • $\begingroup$ If you need more speed than SHA256 with even more negligible collision risk consider Blake3 with 512-bit output. $\endgroup$ – SAI Peregrinus Sep 3 '20 at 17:30
  • $\begingroup$ @kelalaka A collision in $g$ directly implies a collision in $f\circ g$ $\endgroup$ – Mark Sep 4 '20 at 2:35
  • 1
    $\begingroup$ I have accepted this answer, thank you. Your last paragraph is self evident and the main body of your argument largely what I had thought may be the case. I am getting the impression that, for my use case, just using SHA-256 would be sufficient. $\endgroup$ – user3621075 Sep 4 '20 at 8:49
  • 1
    $\begingroup$ @user3621075 forger MD5, run away from it!. $\endgroup$ – kelalaka Sep 4 '20 at 9:10
  • 2
    $\begingroup$ @SAI Peregrinus: Note that BLAKE3 carries 256 bits of state between blocks, regardless of the output length. So using a 512 bit output doesn't generally mean you'll get more collision resistance. $\endgroup$ – Jack O'Connor Sep 5 '20 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.