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
ExpPreImageRes_{A,\Pi,y}(n)
-------------------------------
s <- Gen
x <- A(1^n, s, y)
return H(s, x) == yH 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:
https://news.ycombinator.com/item?id=16782085
(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).