Application of cryptographic hash functions which do not require collision resistance property

Question

I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we open the file and recalculate the hash and compare it to the trusted one, do we need it to be collision resistant?

Answer 1

The two cases for stored files/programs;

1. On your files/programs

   In this case it is the secondary pre-image attack that is given an input $m$ and a hash value $h =Hash(m)$ find another input $\bar m$ such that $m \neq m'$ and $h = Hash(m')$. As long as the hash value $h$ is not under the control of the attackers, they need to find the second input. In this case, we don't need the collision attack that is

   • Collision attack is finding two inputs $a$ and $b$ with $a\neq b$ such that $Hash(a) = Hash(b)$. To have collision resistance, finding such a pair must not be lower than $\mathcal{O}(2^{n/2})$ for hash functions with $n$ bit output size for any probabilistic polynomial-time adversaries. The bound comes from the birthday attack on the hash functions.

   If the attackers can control the hash value, it may be possible to use to their advantage. To prevent this we need to use a keyed hash like HMAC, KMAC.

2. Third-party files/programs

   If you accept the files/programs from the third parties, the classic attack that uses collision of two or more files/programs works as in Luis Casillas's answer and addressed well in Squeamish Ossifrage answer with good, bad, and sneaky versions. Therefore a collision resistance is required. You can mitigate this with HMAC.

Collision resistance is not necessary all the time.

• A good example is the HMAC expanded as either keyed-hash message authentication code or hash-based message authentication code). HMAC is a PRF under the sole assumption that the compression function is a PRF [1] proved by Mihir Bellare in 2006. A PRF doesn't need to have collision resistance. And, usually, we instantiate the HMAC with good hash functions like HMAC-SHA256 or, HMAC-SHA3-256.

• Another example is password hashing, although we don't use standard cryptographic hash functions since they are fast and not memory-hard functions - Scrypt, PBKDF2, or Argon2 is preferred - they are still considered hash functions. In password hashing, the pre-image and secondary pre-image attacks are considered to be important. The collisions are not applicable in password hashing.

Answer 2

You are right that not every application for a cryptographic hash function will need collision resistance. But on the other hand, you need to think of your example more critically in order to rule out the risk of such attack. Think of this scenario:

1. Eve crafts two program executables, $A$ and $B$, such that:
   • $A$ is benign;
   • $B$ is malicious;
   • The two files' hashes collide.
2. Eve gives $A$ to Alice.
3. Alice audits $A$, determines it's benign
4. Alice hashes $A$ and stores the digest securely so that Eve cannot modify it.
5. Alice stores $A$ at path $P$ in a shared volume that Eve can modify.

Alice reasons that even if Eve could modify the file stored at $P$, she can always detect it by checking against her secure copy of the digest for $A$.

But since Eve crafted $A$ and $B$ together she was able to pick them so that they collide. Eve just replaces the contents at $P$ with $B$, and when Alice accesses the path and checks the content against her copy of $A$'s digest, it checks out, runs the malicious executable, and gets pwned.

Turns out Alice would have benefited from collision resistance after all, which stops step #1 of this scenario.

Note that a lot of collision attacks have more or less this flavor, where they hinge on the fact that the bad guys get to craft both the "good" and the "bad" file as a colliding pair. I wager the reason you thought your scenario is secure is because you're implicitly assuming that the "good" file is authored by an honest party, and the bad guys must try to independently craft a file that hashes the same as it.