compare-by-hash (was Re: sharing /etc/passwd)

[David G. Andersen]

Giorgos Keramidas just mooed:
> 
> What I pointed out was that when a non-zero possibility of two data
> blocks comparing as equal (even though they are no) exists, the method
> in question should not be used for password data or other sensitive bits
> of information.  A larger hash key will never yield a possibility of
> zero, so it doesn't mean that you can sleep untroubled at night while
> the rsync server overwrites /etc/*pwd.db files periodically.

  P(hash collision) << p(gamma ray memory bit-flip)
      also          << p(disk block error)
      also          << p(undetected network error w/TCP)

You're worried about the wrong thing.  Unless you're talking about malicious
hash collision generation with a broken hash function, the random hash
collision probability, particularly with something like sha-1,
really is small enough as to be insignificant.  The section in the
paper dealing with this is pure bunk.  _everything_ is a probability --
it's just a matter of how much you're willing to spend (bandwidth,
computation, storage) to drive that probability low.  Illustrative
example from the paper:

   "The empirically observed rate of undetected errors in TCP
    packets is about 0.0000005% ... or we could slightly worsen
    that rate by sending only the hash"

What's the error rate when sending only the hash?  Since the
probabilities are small, we can effectively add them.

P(undetected TCP error) =  0.000000005
P(hash collision)       =  1/1208925819614629174706176
                        =~ 0.00000000000000000000001

"Worsening"             =  0.00000000500000000000001

Now, if I were a smart programmer, I'd look at that and say,
"If I'm worried about reliability, then TCP is my enemy.  Hashes
are my friend -- because I can send _two_ different hashes
of the same data for _way_ less then the cost of sending the
data, and that way I can protect myself against undetected
TCP errors!"

  -dave

-- 
work: dga at lcs.mit.edu                          me:  dga at pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/
      I do not accept unsolicited commercial email.  Do not spam me.