<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div><blockquote type="cite" class=""><span style="font-size: small;" class="">I was just looking through some articles on cryptographic digests setting out the criteria for acceptance and it occurs to me that as specified they are necessary but not sufficient.</span><br class=""><div class=""><div dir="ltr" class=""><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small"><i style="font-family:sans-serif;font-size:14px" class="">Pre-image resistance</i><span style="font-family:sans-serif;font-size:14px" class=""></span><dl style="margin-top:0.2em;margin-bottom:0.5em;font-family:sans-serif;font-size:14px" class=""><dd style="margin-left:1.6em;margin-bottom:0.1em;margin-right:0px" class="">Given a hash value <i class="">h</i> it should be difficult to find any message <i class="">m</i> such that <i class="">h</i> = hash(<i class="">m</i>).</dd></dl></div><div class="gmail_default" style="font-size:small">That is necessary but I would want h to effectively disclose no useful information whatsoever about m. Not the number of bits, not the parity, nothing.</div><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small">So I have been designing deranged hash functions that have the correct work factor but are wrong, wrongety wrong.</div><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small">So SHA2-Yuk is defined as </div><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small">H(x) = (SHA2(x OR 1) OR 1) XOR (x AND 1)</div><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small">Where the boolean operators only act on the last bit in the input.</div><div class="gmail_default" style="font-size:small"><br class=""></div><div class="gmail_default" style="font-size:small">The intent here is to ensure that the hash values of adjacent inputs are paired such that H(x) XOR H(x XOR 1) = 1.</div></div></div></blockquote>There are simpler "deranged" hash functions. For example, you could take:</div><div><br class=""></div><div>H_Leaky(x) = First k bits of x || SHA2(x)</div><div><br class=""></div><div>You can modify this to pre-pend any fixed-length boolean function of x instead. (Granted, this has "the wrong work factor" as it's only as hard as SHA2, while it "should be" 2^k times harder. But the requirement of minimality - i.e., that an n-bit hash output should have difficulty 2^n for pre-image resistance (2^(n/2) for second) isn't in the explicit requirements anywhere - and in fact we accept cryptographic functions that are "a few bits shy" of the theoretical maximum.</div><div><br class=""></div><div>The conditions of first and second pre-image resistance relate to the *cryptographically strong* part of the notion of *cryptographically strong hash function*. Historically we don't write down a definition for the "hash function" part - which is where SHA2-Yuk and H_Leaky fail. I'd guess there's a good definition out there, but it's not obvious. People often try "changing any one bit, on average, changes half the bits of the output", but I don't think that works, though a counterexample isn't clear to me.</div><div><br class=""></div><div><div> -- Jerry</div><div class=""><br class=""></div></div><div><br class=""></div><div><br class=""></div></body></html>