Consider a hash function that outputs 50 bit long hash values. What is the avera

Question

Consider a hash function that outputs 50 bit long hash values. What is the average workload needed for finding a second-preimage? Similarly what is the average workload needed for finding any collision?

UPDATE: I figured out the second question. The equation for probability of finding a collision is 1-e^(k(k-1)/2N) where N=2^50 in my case. So having a 50% probability means 0.5=1-e^(k(k-1)/(2*2^50)) so then k=39,507,326. My first guess (2^25) was off by about about 8% 2^25=33,554,432. I think 2^25 can be used as a loose estimate. (I'm pretty sure the answer to the first question is 2^49, for any future person asking this.)

Explanation / Answer

I think you are right

Average workload needed for finding a second-preimage --> 2^(number of bits -1) = 2^49

Average workload needed for finding any collision --> 2^((number of bits)/2)=2^25

Hope you understand. Feel free to ask any doubts. Have a nice day. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.