On 07/11/2012 10:06 PM, Bill Sommerfeld wrote:
> On 07/11/12 02:10, Sašo Kiselkov wrote:
>> Oh jeez, I can't remember how many times this flame war has been going
>> on on this list. Here's the gist: SHA-256 (or any good hash) produces a
>> near uniform random distribution of output. Thus, the chances of getting
>> a random hash collision are around 2^-256 or around 10^-77.
> I think you're correct that most users don't need to worry about this --
> sha-256 dedup without verification is not going to cause trouble for them.
> But your analysis is off. You're citing the chance that two blocks picked at
> random will have the same hash. But that's not what dedup does; it compares
> the hash of a new block to a possibly-large population of other hashes, and
> that gets you into the realm of "birthday problem" or "birthday paradox".
> See http://en.wikipedia.org/wiki/Birthday_problem for formulas.
> So, maybe somewhere between 10^-50 and 10^-55 for there being at least one
> collision in really large collections of data - still not likely enough to
> worry about.
Yeah, I know, I did this as a quick first-degree approximation. However,
the provided range is still very far above the chances of getting a
random bit-rot error that even Fletcher won't catch.
> Of course, that assumption goes out the window if you're concerned that an
> adversary may develop practical ways to find collisions in sha-256 within the
> deployment lifetime of a system. sha-256 is, more or less, a scaled-up sha-1,
> and sha-1 is known to be weaker than the ideal 2^80 strength you'd expect from
> 2^160 bits of hash; the best credible attack is somewhere around 2^57.5 (see
Of course, this is theoretically possible, however, I do not expect such
an attack to be practical within any reasonable time frame of the
deployment. In any case, should a realistic need to solve this arise, we
can always simply switch hashes (I'm also planning to implement
Skein-512/256) and do a recv/send to rewrite everything on disk. PITA?
Yes. Serious problem? Don't think so.
> on a somewhat less serious note, perhaps zfs dedup should contain "chinese
> lottery" code (see http://tools.ietf.org/html/rfc3607 for one explanation)
> which asks the sysadmin to report a detected sha-256 collision to
> eprint.iacr.org or the like...
How about we ask them to report to me instead, like so:
1) Detect collision
2) Report to me
zfs-discuss mailing list