[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with c
From: |
Paul Eggert |
Subject: |
Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils) |
Date: |
Thu, 05 Aug 2010 16:29:37 -0700 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.11) Gecko/20100713 Thunderbird/3.0.6 |
On 08/04/10 19:58, Paolo Bonzini wrote:
> MD5 is used simply as a kind of "random key generator", so it doesn't
> matter.
That depends on what one is using "sort -R" for. If one uses it to
choose data that are relevant for cryptographic purposes, it might
matter. (Admittedly this is unlikely.)
I'm not that familiar with cracking MD5, but I would guess that the
cracking methods are rendered ineffective by the 128-bit salt that
"sort -R" uses. If so, then there's no real problem.
If the fact that MD5 is crackable is a problem, it'd be trivial to
substitute (say) SHA256. However, this would slow down 'sort -R'
considerably: switching to SHA256 would slow down 'sort -R' by a factor of
2.5 on the little million-line benchmark that I just tried it on ("seq
1000000", x86-64, Xeon E5620, gcc 4.5.1).
> 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).
> 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.
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?
- propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/03
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Bruno Haible, 2010/08/03
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/04
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Simon Josefsson, 2010/08/04
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paolo Bonzini, 2010/08/04
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils),
Paul Eggert <=
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paolo Bonzini, 2010/08/06
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/06
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Simon Josefsson, 2010/08/08
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/08
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Bruno Haible, 2010/08/08
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/09
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Bruno Haible, 2010/08/10
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Paul Eggert, 2010/08/10
- new module 'astrxfrm', Bruno Haible, 2010/08/14
- Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils), Bruno Haible, 2010/08/14