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

[David G. Andersen]

David G. Andersen just mooed:
> 
> 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

  (btw, I wasn't really being fair to compare-by-hash in this
example.  Assuming you're synchronizing a "moderate" file with
rsync, it's going to split it into, say, S/1k chunks.  So
let's be nasty and say that it's a 1Tb file.  The chances
of any one block colliding with any of the other blocks in the
file is (again, because our probabilities are really small)
2^30 / 2^160 =~ 1/2^130.  In the example above, I used a very
conservative value of 1/2^80.  So the actual worsening is
probably from

 0.0000005  to
 0.000000500000000000000000000000000000001

I'll take those odds any day.  Even if you send each data packet
3x with a non-hashed rcp, your chances of death per-packet are
still 0.000000000000000000125 or thereabouts...

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