pure transit server
rra at stanford.edu
Thu Mar 1 06:48:19 UTC 2001
Kai Henningsen <kaih at khms.westfalen.de> writes:
> rra at stanford.edu (Russ Allbery) wrote:
>> * You need to use a hash of reasonable size; what we're currently doing
>> really isn't large enough. Right now, we're only using 48 bits out of
>> MD5's 128 bits, and I think we're running a non-trivial risk of serious
>> hash collisions.
> I'm extremely doubtful that md5 is a reasonable hash to use for this
> type of stuff. It has nice crypto properties, but crypto properties are
> not really what we're after here. Fast and distributed well is.
My understanding is that one of the side effects of its crypto properties
is that it's distributed well; being a cryptographic one-way hash is
actually a *stronger* property than well-distributed. A hash that isn't
well-distributed doesn't sound usable for crypto either; it would seem to
make it too easy to find multiple plain texts that hash to the same thing.
The only problem with MD5 is that it's fairly slow; apart from that, I
think it's pretty much ideal.
Admittedly, I'm not a cryptographer and haven't researched it extensively.
> I've just written a test program for checking my favourite hash against my
> local history. Let's see how many collisions I get there.
> ... ok, results are in.
> On 1,215,927 message ids, I find exactly one 64-bit hash collision.
If that rate holds (hard to tell with that particular statistic), that
means eight hash collisions on my current history file. Even a large news
server should get *no* hash collisions if we use a good hash.
Russ Allbery (rra at stanford.edu) <http://www.eyrie.org/~eagle/>
More information about the inn-workers