There's a lot of work finding "partial collisions" in hashes, and "Parallel Collision Search with Cryptanalytic Applications" seems to be the go-to paper for this work. I'm trying to understand why finding partial collisions, particularly by brute force, is such a topic of interest. As an example, let's say we have a 256-bit hash, and the last 4 bytes are the same for two message.

Is the interest in this work just because it's a useful segue to understand how to make collision? Is there a condition where one would truncate a longer hash that would cause a partial collision to be a problem?

  • $\begingroup$ If we think about the hash function $h:\{0,1\}^* \rightarrow \{0,1\}^n$ as $n$ boolean functions, $f_i:\{0,1\}^* \rightarrow \{0,1\}$, then finding a collision method for some output bits is a kind of divide and conquer attack. $\endgroup$ – kelalaka Dec 14 '18 at 16:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.