3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank for your reply. let's focus on my example. let's say that the primary calculated hash is unchangeable. for this problem we just want to make sure that this app or file is not modified. under what scenarios we need collision resistance property. if it is an operating system app? or it same for all? $\endgroup$ – John M. Dec 16 '20 at 20:19
  • 1
    $\begingroup$ @John I've added the definition of the collision, too. As you can see, in the collision attack, the attackers can choose any hash value as they want to collide. If they cannot control the output, but they need to find one that matches, then they need to execute the secondary image attack on the hash function. If you use SHA256 then you will be fine since you will get 256-bit security. For your case, a don't see a reason for the collision resistance since the hash is fixed. $\endgroup$ – kelalaka Dec 16 '20 at 20:51
  • $\begingroup$ Thank you so much $\endgroup$ – John M. Dec 16 '20 at 22:13
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hmm, I think I overread the trusted here. Yes, this is the classic attack that one accepts files/programs from the 3rd parties then this executes well. $\endgroup$ – kelalaka Dec 16 '20 at 22:59

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.