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

On the face of it the xor of two random bits should have the same distribution as the original bits unless the bits are related in some fashion. I guess the trick is determining whether there is any coupling between the pairs of bits that would be xor'd together.

Perl reduces RSI - it saves typing

Replies are listed 'Best First'.
Re^4: 64-bit digest algorithms
by BrowserUk (Patriarch) on Nov 13, 2008 at 06:48 UTC
    determining whether there is any coupling between the pairs of bits that would be xor'd together

    I read in that same text that in a good digest function, each bit of the input should affect approximately half of the bits of the output. (I think) the implication was that if this ideal is achieved, and the distribution of the affected bits for each bit of input is sufficiently unpredictable, then the digest is 'secure' meaning unpredictable. But the problem with many of the digests that have been shown to be weak, is that the ideal is not achieved, making certain patterns of outputs for given inputs discernable.

    I read that to mean that there is coupling between the upper and lower halves of any digest. Good or bad?

    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.
[reply]

      Coupling between halves is of less concern than if there is coupling between the bits that are xored together. My understanding of the MD5 algorithm suggests that coupling would be low and that xoring the top and bottom halves of an MD5 should retain the distribution characteristics of the non-combined digest (scaled to the smaller range of course). What's the application?

      Perl reduces RSI - it saves typing
[reply]

        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.
[reply]

In Section Seekers of Perl Wisdom