Task $4\mathrm{.}2$: Collision$-$Free Property

Collision$-$free property $($also known as strong collision resistant$)$ is that it is computationally infeasible to find any pair $(\backslash (\backslash$mathrm$\{$x$\},\backslash$mathrm$\{$y$\}\backslash ))$ such that $\backslash (\backslash$mathrm$\{$H$\}(\backslash$mathrm$\{$x$\})=\backslash$mathrm$\{$H$\}(\backslash$mathrm$\{$y$\})\backslash ).$ In this task, you will write a program to break the collision$-$free property using brute$-$force method. Please design an experiment to find out the following: How many trials it will take you to break the collision$-$free property using the brute$-$force method?

Hints: You can first randomly generate a string, obtain the corresponding hash value, and store the first $24$ bits of hash value. Then you continue to randomly generate strings and store the first $24$ bits of hash values until you get a $24-$bits value that has already been stored. That is$,$ you find two strings which have same hash values $($the first $24$ bits of hash values are identical$).$ Similarly, you should report the average.

Submissions for Task $4\mathrm{.}2(20$ points$)$

$(1)$ Theoretically, how many attempts on average are needed to brute force collision$-$free property $($you can check the slide $13$ of Module $11\_1$ to find the answer$)?$ Please note that we will reduce the length of the hash value to $24$ bits. $(5$ points$)$

$(2)$ Please explain how you design your program and attach the screenshot of your program. What are two random string that have same first $24$ bits of hash values? $(10$ points$)$

$(3)$ How many trails on average it will take you to break the collision$-$free property using brute$-$force method? $(5$ points$)$

Bonus Points $(10$ points$)$

$(1)$ Based on your observation, which property is easier to break using the brute$-$force method?

$(2)$ Can you explain the difference in your observation mathematically?