7
$\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?

Improve this question
$\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
    Commented Dec 14, 2018 at 16:52

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ this answer adds nothing new to the other answer I am afraid $\endgroup$
    – kodlu
    Commented Mar 13, 2021 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
    Commented Mar 15, 2021 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
    Commented Mar 16, 2021 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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