[Cryptography] Amongst the requirements for digests...

[Jerry Leichter]

> 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.
> 
> Pre-image resistance
> Given a hash value h it should be difficult to find any message m such that h = hash(m).
> 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.
> 
> So I have been designing deranged hash functions that have the correct work factor but are wrong, wrongety wrong.
> 
> So SHA2-Yuk is defined as 
> 
> H(x) = (SHA2(x OR 1) OR 1) XOR (x AND 1)
> 
> Where the boolean operators only act on the last bit in the input.
> 
> 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.
There are simpler "deranged" hash functions.  For example, you could take:

H_Leaky(x) =  First k bits of x || SHA2(x)

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.

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.

                                                        -- Jerry



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20181228/a8464a5e/attachment.html>