collision and pre-image difference

Question

I'm doing an online free course about cryptography and there's a very confusing question:

Can anyone explain the answer please?

Question for hashing algorithms:
Select one or more than one.

a. It is impossible to break its resistance to collision and preimage
b. It is more difficult to break its resistance to collision than to the preimage
c. It's just as easy to break your resistance to collision than to preimage
d. It is easier to break its resistance to collision than to preimage

Answer 1

I will omit the exact complexities as it is not directly asked, however let me know if you would like me to elaborate on them more.

There are three levels of security for a cryptographic hash function $H$:

1. Preimage resistance: it is infeasible for an attacker presented with $x$ to find $m$ so that $H(m) = x$.
2. Second-preimage resistance: it is infeasible for an attacker presented with $m_1$ to find $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.
3. Collision resistance: it is infeasible for an attacker to find any $m_1$ and $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.

Now to the alternative answers in your quiz:

a. It is impossible to break its resistance to collision and preimage

No, it can not be impossible in theory since an attacker with unlimited resources could brute-force over all possible inputs. The key here is the concept of computational infeasibility.

b. It is more difficult to break its resistance to collision than to the preimage

c. It's just as easy to break your resistance to collision than to preimage

d. It is easier to break its resistance to collision than to preimage

(d.) is the correct answer. Here's why:

For successfully 'breaking' preimage resistance, you get some output hash $x$ and need to find the corresponding input $m$ to that specific $x$. Unless there is a structural flaw in the hash algorithm, the quasi-randomising effect of the hash function dictates that the only way is to brute-force over a lot of different inputs until you find your target input $m$. This is extremely expensive, and intentionally so.

For collisions, you need to find any two distinct inputs $m_1,m_2$ that result in the same output hash. Now again you could choose a brute-force approach and try different inputs until you find a match. However you are not constrained by the fact that your inputs must result in a specific hash, like in both preimage cases. This makes it significantly easier to 'break' collision resistance.