in reply to Re^5: 64-bit digest algorithms
in thread 64-bit digest algorithms

Once I made the leap from 'digest' to 'hash', my searching has been more effective, and I finally turned up (one of) the references I read previously that leads to my concerns regarding the truncation of a larger digest algorithm.

In particular, see the section headed "Funneling" and the paragraph that reads "For example, consider XORhash and 30-byte keys. All 30 lowest-order key bits funnel into only the lowest-order bit of the internal state. Every set of a billion (2^30) keys, which differ only in the lowest order key bits, maps into just 2 hash values, even though 101 hash values are available."

Another reference that I haven't yet tracked down, but may be linked indirectly from the above, suggested that testing had shown that truncation (of any form) of MD5 resulted in poor distribution. I don't have the knowledge to either challenge or verify that assertion.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^7: 64-bit digest algorithms
by GrandFather (Saint) on Nov 13, 2008 at 09:23 UTC

    If I understand your intent correctly you have some message text that you wish to hash to 64 bits. The funnelling weakness is a potential issue for the hash algorithm, but is not a concern for the one off (per message) mixing of, say, a 128 bit MD5 digest down to 64 bits. By using an xor mix of the two 64 bit fields you are retaining the entropy and distribution characteristics present in the individual fields so long as there isn't a problem with coupling between bits (and for MD5 that seems unlikely).

    The sort of code I had in mind would be something like:

    use strict;
use warnings;
use Digest::MD5;

my $msg = 'The quick brown fox jumps over the lazy dog.';
my $digest = Digest::MD5::md5_hex ($msg);

$digest = substr ($digest, 0, 8) ^ substr ($digest, 8, 8);
print unpack ('H16', $digest), "\n";

    [download]
    Perl reduces RSI - it saves typing
[reply]
[d/l]
[reply]

In Section Seekers of Perl Wisdom