# collision and pre-image difference

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

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


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.

• Note that a. is also wrong because - if I remember correctly - there is no way of proving that a hash function is secure. Without such proof it is impossible to say that it is impossible to break a hash function wrt to collision resistance or pre-image attacks. – Maarten Bodewes Feb 26 '18 at 1:35
• good point, IMO it's generally inappropriate to speak of impossibilities in cryptography, strictly speaking. (edit): I mean, there is 'provable secure' collision resistance but that's only a way of saying 'infeasible to attack'. – indiscreteLogarithm Feb 26 '18 at 6:56