42
$\begingroup$

I would like to maintain a list of unique data blocks (up to 1MiB in size), using the SHA-256 hash of the block as the key in the index. Obviously there is a chance of hash collisions, so what is the best way of reducing that risk? If I also calculate the (e.g.) MD-5 hash of the block, and use the combination (SHA-256, MD-5) as the key, is the chance of a collision about the same as some 384-bit hash function, or is it a little bit better because I'm using different hash functions?

Thanks for the info!

Edit: My blocks come from normal user data on hard drives, but it will be many petabytes in total.

Edit2: As a follow-up (just tell me if this should be moved to a different question): Since the blocks can vary in size but can be up to some preconfigured limit (e.g. 1MiB), how will collision resistance be affected if I make the (64-bit) size of the block part of the key? That way you can only have collisions of blocks with the same size...

Improve this question
$\endgroup$
2
  • $\begingroup$ On Edit2, adding the size as part of the key will, at best, add a few extra bits of security (but in the grand scheme of things it won't really matter since the hash function is so secure already). At worst, it will add nothing. I can't think of a way, however, that it takes away from the security of the system. $\endgroup$
    – mikeazo
    Nov 14, 2011 at 12:26
  • 1
    $\begingroup$ Cont'd on Edit2, be careful in your implementation, however, as error messages could create information leaks (i.e., the length of the file could potentially be leaked). $\endgroup$
    – mikeazo
    Nov 14, 2011 at 12:28

4 Answers 4

Reset to default
89
$\begingroup$

The risk of collision is only theoretical; it will not happen in practice. Time spent worrying about such a risk of collision is time wasted. Consider that even if you have $2^{90}$ 1MB blocks (that's a billion of billions of billions of blocks -- stored on 1TB hard disks, the disks would make a pile as large of the USA and several kilometers high), risks of having a collision are lower than $2^{-76}$. On the other hand, the risks of being mauled by a gorilla escaped from a zoo are at least $2^{-60}$ per day, i.e. 65000 times more probable than the SHA-256 collision over way more blocks than possibly makes sense. Stated otherwise, before hitting a single collision, you can expect the visit from 65000 successive murderous gorillas. So if you know what's good for you, drop that MD5 and go buy a shotgun.

SHA-256 collisions are not scary; gorillas are.

Now for the suggestion of concatenating the outputs of two distinct hash functions, say SHA-256 and MD5. It turns out that this does not enhance security as much as one could believe. The total size of 384 bits would certainly not provide more security against collisions that what a 384-bit hash function would give; but it actually is much weaker than that: it would not be really much stronger than SHA-256 alone. See this previous question, and this research article for the gory details. This can be summed up as follows: when using several hash functions in parallel and concatenating the outputs, the total is not stronger against collisions than the strongest of the individual functions.

And, of course, MD5 itself is weak against collisions and as such should not be envisioned for newer designs.

Improve this answer
$\endgroup$
10
  • 11
    $\begingroup$ While this is certainly amusingly written, it does miss one point: if the probability of being mauled by a runaway Gorilla is $2^{-60}$, then the probability of being mauled by two runaway Gorillas is not $0.5 \times 2^{-60}$, but $(2^{-60})^2 = 2^{-120}$. Hence, you can't really expect to be mauled by 250000 successive gorillas before you find a collision; however, you are still far more likely to be mauled by one than find a collision. $\endgroup$
    – poncho
    Nov 11, 2011 at 21:49
  • 7
    $\begingroup$ @poncho: $2^{-60}$ per day. So $2^{-120}$ is the probability of encountering two gorillas the same day. You can view it with a time frame: on average, you will meet a gorilla every $2^{60}$ days. You will get a SHA-256 collision every $2^{76}$ days (there was a mistake in my estimate, so 65000 gorillas, not 250000)(assuming you regenerate the $2^{90}$ 1MB blocks every day). So you really get $2^{16}$ gorillas for every collision -- but not in one go, as a massive gorilla army attack ! (that would be spooky) $\endgroup$
    – Thomas Pornin
    Nov 11, 2011 at 22:00
  • 3
    $\begingroup$ Ah, I missed that point. On the other hand, I was going through the probability that you really will be attacked by a Gorilla that escaped from the zoo: a quick Google shows at least three people who have actually been attacked by Gorilla's escaping from a zoo in the last decade (none severely). That bounds the probability of such an event to about $3/(7000000000 \times 365 \times 10) \approx 2^{-43}$. Hence, finding a collision isn't that much more likely than being attacked by two separate Gorillas in the same day (!) $\endgroup$
    – poncho
    Nov 12, 2011 at 14:39
  • 2
    $\begingroup$ @Ricky: if we knew how to handcraft data blocks specifically to trigger a SHA-256 collision, with better success than with random blocks, then this would be advertised as a break on SHA-256. No such break is currently known on SHA-256. Current methods for attacking MD5 and SHA-1 appear unlikely to apply to SHA-256 (this has been tried). $\endgroup$
    – Thomas Pornin
    Nov 13, 2011 at 14:48
  • 7
    $\begingroup$ Just remember that gorilla escapes are not necessarily independent events. :-) $\endgroup$
    – Tim has moved to Codidact
    Dec 22, 2012 at 20:03
13
$\begingroup$

The risk of collision is only theoretical; it will not happen in practice.

Except in one particular instance. The description given implies that this system is going to be some form of de-duplicating filesystem or backup system. For most users, the collision risk is tiny.

But, for one particular class of users, there is a much larger risk. Those users are cryptographic hash researchers for whom one could presume that hash collisions within their HD's data content are more likely than the average joe, simply because they are attempting to manufacture such collisions.

Therefore, if this is to be a de-duplicating filesystem or backup system, and a cryptographic hash researcher makes use of it, the risk of two different data blocks having a colliding hash is larger than for the average joe.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ As explained in another comment, any success in increasing the likelihood of collision is breaking the hash. So you're speculating about the odds that a researcher can break the hash, not about the odds of collision. crypto.stackexchange.com/questions/1170/… $\endgroup$
    – Brent
    Dec 25, 2020 at 21:26
7
$\begingroup$

To have approximately a 50% chance of a collision, you'd need $2^{128}$ data blocks. This comes from the birthday problem. Are you anticipating your list to be that large? I would doubt it as that would be an astronomical amount of data (much, much more than a petabyte).

That said, it is very, very unlikely that a collision for MD5 would also be a collision for SHA-256, so you would probably be fine doing the dual hash thing, but why not just use SHA-384 (or SHA-512) if you are that worried about a collision.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for the response. I guess my question is: is SHA-384 a better option than SHA-256 and MD-5 combined? And yes, I do anticipate a very large number of data blocks. Let's say there are $2^{64}$ blocks, does that mean there's a 25% chance of a collision? $\endgroup$
    – Theodor Kleynhans
    Nov 11, 2011 at 15:10
  • 2
    $\begingroup$ No, with $2^{64}$ blocks, there is about a $(2^{64})^2 / 2^{256} = 2^{-128} \approx 3 * 10^{-39}$ probability of a collision using just SHA-256 as a hash. In my opinion, that probability is sufficiently low that it's not worth bothering to do anything more. $\endgroup$
    – poncho
    Nov 11, 2011 at 15:19
  • $\begingroup$ @TheodorKleynhans, It's looking like SHA-384 is better than SHA-256+MD5 as pointed out in the gorilla answer. :) And, $2^{64}$ is approximately an Exbibyte. Do you even anticipate that much storage? $\endgroup$
    – mikeazo
    Nov 11, 2011 at 17:16
  • 2
    $\begingroup$ @Theodor: For a random collision, a simple look at the combined output size $n$ (in bits) is enough: You need about $2^{n/2}$ blocks to have a good chance. As $256 + 128 = 384$, the probabilities are quite the same. If you fear malicious collisions by attackers, avoid MD5 as its collision resistance is broken, and avoid concatenations of different hash functions, as in the answer by Thomas. $\endgroup$
    – Paŭlo Ebermann
    Nov 12, 2011 at 2:36
  • 1
    $\begingroup$ SHA-384 is a much better choice than SHA-256 and MD-5 combined. First, it's even faster than SHA-256 alone (on modern hardware, assuming most hashes are on objects over 32 bytes). Second, its security properties are probably better than SHA-256 and MD5 combined because each SHA-512 bit is stronger than each MD5 bit due to weaknesses in MD5. You're proposing trading SHA bits for MD5 bits, that's an obvious losing proposition. (Not that this matters. It's like whether the Sun will burn out in 10 billion years or 15 billion years.) $\endgroup$
    – David Schwartz
    Nov 13, 2011 at 4:24
6
$\begingroup$

The risk of collision in practically non-existent, but as a good software developer write your code to handle it:

If hashes are equal then compare block lenghts, if they are equal then compare blocks byte by byte, and if they differ or if lengths are different then 1) increase an integer counter concatenated at the end of the hash ID (it should be 0 everywhere else), 2) LOG THE COLLISION LOUDLY, 3) profit.

The CPU-intensive part is the comparison but don't worry, it shall happen only in the case of duplicates, and even then comparing bytes should be lightweight. Test the code by choosing CRC32 as the hash function.

EDIT: Don't underestimate cryptology research, nobody can guarantee that in 5 years it won't be feasible to find a collision, so protect yourself against malicious users as well as against gorillas.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ In case of malicious collisions, this can lead to a denial of service attack by building a really slow hash map by creating hash collisions. $\endgroup$
    – Paŭlo Ebermann
    Dec 26, 2012 at 0:44
  • 2
    $\begingroup$ @PaŭloEbermann: True, but the alternative proposed hear would mess-up backed up data, which is much worse! $\endgroup$
    – jimis
    Dec 26, 2012 at 19:05
  • 1
    $\begingroup$ I think the DoS concern is largely unimportant; It'd require someone to find many many SHA-256 collisions (there are currently none known), and even then, the DoSing is highly rate-limited by the speed the user can upload blocks with. Even if, at some point in the future, many SHA-256 collisions become known, you give yourself plenty of time to react to it -- those collisions won't be all become available at once, and even then, the upload speed limit will give you time to react. Just run a check every once in a while for collision count in your database, and you'll probably be fine. $\endgroup$
    – Jonathan Ringstad
    Jul 26, 2014 at 14:56
  • $\begingroup$ @Amadiro SHA-256 is vulnerable to the length extension attack. Once you find 1 collision, you can generate infinite collisions by using it as a prefix. The DoS risk is real! $\endgroup$
    – Navin
    Mar 13, 2017 at 11:10
  • $\begingroup$ @Navin Would that mean that after comparing the length (and it being equal) it'd be more efficient to do the byte-by-byte-comparison starting with the last byte $\endgroup$
    – nitzel
    Jan 2, 2020 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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