GNU bug report logs - #6789
propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils)

Previous Next

Full log

Message #23 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paolo Bonzini <bonzini <at> gnu.org>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: bug-gnulib <at> gnu.org, Bug-coreutils <bug-coreutils <at> gnu.org>
Subject: Re: propose renaming gnulib memxfrm to amemxfrm (naming collision
	with coreutils)
Date: Fri, 06 Aug 2010 10:22:50 +0200

On 08/06/2010 01:29 AM, Paul Eggert wrote:

>> 1) why bother with memxfrm as a tie-breaker? isn't memcmp good enough?
>
> If two keys K1 and K2 compare equal, their random hashes are supposed
> to compare equal too.  So if memcoll(K1,K2)==0, the random hashes must
> be the same.  Hence we can't just do a memcmp on K1 and K2; we need to
> do a memcmp on strxfrm(K1) and strxfrm(K2).

I see.  In practice, this is because "you cannot separate straße and 
strasse".

>> 2) maybe there's something cheaper than md5 that can be used?  For
>> example you could compare a^x and b^x where x is the output of a fast
>> 32-bit random number generator?
>
> That wouldn't be sufficiently random, even for non-cryptographic
> purposes, since keys that are natively nearby would tend to sort near
> to each other after being exclusive-ORed.

You're right, keys that differ only in the leading or trailing bits 
would tend to stay respectively very far and very near, though you 
cannot say anything about the order.

> But I see your point: perhaps there is something faster than MD5 for
> this sort of thing, and which is "secure" enough.  Perhaps the
> ISAAC / ISAAC64 code that is already in GNU coreutils would work
> for that?

ISAAC is a RNG, so wouldn't that have the same problem above?  You 
definitely need to use a hash function, it's just that you do not need a 
cryptographic one.

Paolo

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.