Date: Mon, 27 Sep 2004 09:04:16 -0600 From: "David G. Andersen" <danderse@cs.utah.edu> To: Giorgos Keramidas <keramida@freebsd.org> Cc: Colin Percival <cperciva@wadham.ox.ac.uk> Subject: Re: compare-by-hash (was Re: sharing /etc/passwd) Message-ID: <20040927090416.B16227@cs.utah.edu> In-Reply-To: <20040927084511.E75411@cs.utah.edu>; from danderse@cs.utah.edu on Mon, Sep 27, 2004 at 08:45:11AM -0600 References: <Pine.LNX.4.33.0111071900280.24824-100000@moroni.pp.asu.edu> <20011107211316.A7830@nomad.lets.net> <20040925140242.GB78219@gothmog.gr> <41575DFC.9020206@wadham.ox.ac.uk> <20040927091710.GC914@orion.daedalusnetworks.priv> <20040927084511.E75411@cs.utah.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
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@lcs.mit.edu me: dga@pobox.com
MIT Laboratory for Computer Science http://www.angio.net/
I do not accept unsolicited commercial email. Do not spam me.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040927090416.B16227>