4 ms·
Does anyone have real-world data for the likelihood of SHA256 hash collisions for actual user data (music, movies, documents, source code, etc)? In my toy back
by m_eiman 17y ago
Does anyone have real-world data for the likelihood of SHA256 hash collisions for actual user data (music, movies, documents, source code, etc)?
In my toy backup app I'm doing pretty much what they're doing - I assume that each block with 1MB of data will have a unique hash. I haven't tested it on serious amounts of data though, and so I'm very curious to know how likely this scheme is to survive an encounter with the real world.
- viraptor 17y agoI don't like the way they present the result of how unlikely hash collisions are... The number (2-256) gives much more comfort than saying: If you hash 4KiB-long blocks, then every possible block will share the hash value with (on average) 128 different 4KiB blocks. And on a standard 200GiB disk you can fit (more or less) 52,400,000 blocks. This explanation is a bit less reassuring. Now consider the fact that your data is never random and you hit the same patterns all the time (loads of zeros / ascii letters / x86 code)
- bensummers 17y agoThe same patterns thing is mitigated by the property that changing one bit in the input is (supposed to) change on average half of the bits in the hash. You can also be reassured that there's lots of research going on about how likely these collisions are and how to find them. People are actively trying to break these hash algorithms, so it's not just in theory.
- gcv 17y agoI once read that anyone who actually finds a SHA256 collision should publish it in a paper. SHA256 collisions are supposed to be the just shy of impossible to find (you know, the whole old trope of millions of machines millions of times faster than the ones we have now working for millions of years will find a collision at some point). Some confirmation of this would be welcome.
- bensummers 17y agoHappily, they have a 'verify' mode which checks the data on disc instead of making the assumption that SHA256 works as promised.
- m_eiman 17y agoThey do, but what I'm interested in is if it's something that actually occurs in real data (with SHA256, in the article he says that it's of more use with "worse but faster" hashing algorithms). My initial remedy is to add another hash method and name the data based on the results of both; that way problematic data would need to trigger a collision in two different algorithms at the same time, which "should" be next to impossible. Currently my file fragments are named "{SHA256}.dat", in v2 I could instead name them "{SHA256}{SOME_OTHER_HASH}.dat".
- jcsiracusa 17y agoRegarding the "should" part: http://stackoverflow.com/questions/1323013 http://stackoverflow.com/questions/1323013
- m_eiman 17y agoGood stuff! Perhaps it's safe to remove the "" qualifier from my assumption.
- zmoney 17y agoNetApp and Data Domain are both enterprise-level dedupe vendors who use similar hash functions to find unique strings of bits. Check out their whitepapers. Short answer: not in a million years (and there are further checks in case the hash alg somehow failed.)