Example of non-preimage-resistant, but collision-resistant function

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Example of non-preimage-resistant, but collision-resistant function
For Ex7-1 I seek a hash function \Pi = (Gen, H) with H: {0,1}^n x {0,1}^* → {0,1}^n such that

a) it is collision-resistant as in the lecture,

b) and it is non-preimage-resistant defined as follows:

// Note this probably heavily deviates from literature

s <- Gen
x <- A(1^n, s, y)

return H(s, x) == y

H is called non-preimage-resistant iff. there is a ppt-adversary A such that for all y in {0,1}^n: Pr[ExpPreImageRes_{A,\Pi,y}(n) = 1] is a non-negligible function in n.

Note that the experiment is parametric in y, e.g. in contrast to ExpInvert for OWFs, which means I can use the adversary to query preimage values for arbitrarily-distributed image values.

Does anyone have an example?

First: I think that although this is indeed very interesting, you may solve 7.1 without such a construction, as far as I can see it in the “official” solution.

I expected that such a thing exists (I even said that in the exercise session), but it does not seem so:


(I highly recommend to read through the links mentioned there).

My intuition was not entirely wrong, as c.r. implies pre-image safety to another exponential (depending on the parameters = negligible) bound that is smaller than the c.r. bound.
=> So to break the c.r. of H(m0||m1) = m0 || H’(m1) the brute force algorithm is negl.
But using this to store your password on a server means half your password is now leaked and brute forcing your whole password is faster (but still exponential).