6
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\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
5
$\begingroup$

This seems to boil down to whether or not anyone would have a reason to truncate a hash. The answer is yes, absolutely. For example, someone who needs a 256-bit digest may want to use SHA-512/256 instead of SHA-256 on a 64-bit processor for improved performance (the former uses 64-bit operations whereas the latter uses 32-bit operations). SHA-512/256 is nothing more than regular SHA-512 with a distinct IV, truncated to a 256-bit value. Likewise if someone wants a hash with 280 collision resistance, they would want to truncate a stronger hash like SHA-256 to 160 bits instead of using SHA-1 which has cryptographic weaknesses that allow collisions to be found faster than predicted by the birthday bound.

Another reason someone might want to truncate a Merkle–Damgård hash function is to resist length extension attacks. SHA-256 is vulnerable to them, whereas SHA-512/256 is not, despite being of the same size. An efficient collision against such a truncated hash could then be considered problematic.

$\endgroup$
0
$\begingroup$

Some people, when checking a hash manually, will only look at the first few digits—this is mathematically equivalent to truncating the hash to that length. An attack against that equivalent truncated hash will fool the person doing the check.

$\endgroup$
3
  • $\begingroup$ this answer adds nothing new to the other answer I am afraid $\endgroup$ – kodlu Mar 13 at 5:07
  • $\begingroup$ @kodlu this particular reason for truncating a hash (much more common, in my experience, than the ones mentioned) isn't mentioned in the other answer—should I leave it as a comment on the other answer, instead of as an answer of my own? $\endgroup$ – iridia Mar 15 at 23:22
  • $\begingroup$ Thanks for giving the context, you can live it as is. maybe mention that this reason for truncation is a bad reason, in contrast to the other answer, especially if it is only a few bytes people look at. $\endgroup$ – kodlu Mar 16 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.