Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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...

share|improve this question
    
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. –  mikeazo Nov 14 '11 at 12:26
1  
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). –  mikeazo Nov 14 '11 at 12:28

4 Answers 4

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.

share|improve this answer
    
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? –  Theodor Kleynhans Nov 11 '11 at 15:10
2  
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. –  poncho Nov 11 '11 at 15:19
    
@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? –  mikeazo Nov 11 '11 at 17:16
2  
@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. –  Paŭlo Ebermann Nov 12 '11 at 2:36
1  
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.) –  David Schwartz Nov 13 '11 at 4:24

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.

share|improve this answer
2  
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. –  poncho Nov 11 '11 at 21:49
5  
@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) –  Thomas Pornin Nov 11 '11 at 22:00
2  
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 (!) –  poncho Nov 12 '11 at 14:39
1  
@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). –  Thomas Pornin Nov 13 '11 at 14:48
2  
Just remember that gorilla escapes are not necessarily independent events. :-) –  phyzome Dec 22 '12 at 20:03

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.

share|improve this answer
2  
Upvoting because malicious users must be part of your risk analysis. If someone can put up a block specially crafted to match another, they can potentially steal data or alter other users'. –  Mark Dec 22 '12 at 10:01

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.

share|improve this answer
1  
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. –  Paŭlo Ebermann Dec 26 '12 at 0:44
    
@PaŭloEbermann: True, but the alternative proposed hear would mess-up backed up data, which is much worse! –  jimis Dec 26 '12 at 19:05
    
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. –  Amadiro Jul 26 at 14:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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