pure transit server

[Russ Allbery]

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