How to determine if a hash is pre image resistant or collision free

Question

Let $H : \{0,1\}^*\to \{1,\dots, 2^{256}\}$ be a hash function. Let $p > 2^{256}$ be a safe prime, and $\alpha$ a primitive root for $p$. Define: $$H'(m) = H(m || m),\quad H''(m) = \alpha^{H(m)}\bmod p$$ Where $m||m$ is the concatenation of $m$ with itself.

I am confused how when given hash functions like this, how to explain or tell if they are preimage resistant or strongly or weekly collision free? I also am confused on how the hashes, such as $H,H'$, and $H''$ connect to each other in that respect?

Answer 1

Name and exact definition of security properties of hashes vary, depending on level of formalism. Refer to your reference material. However the general idea always is:

1. preimage resistant (or first preimage resistant): given $h$, it's infeasible to come up with $m$ having hash $h$.
2. second preimage resistant (or weakly collision free): given $m$, it's infeasible to come up with $m'\ne m$ such that $m$ and $m'$ have the same hash.
3. collision resistant (or strongly collision free): it's infeasible to come up with $m$ and $m'\ne m$ such that $m$ and $m'$ have the same hash.
4. indistinguishable from a random member of a Pseudo Random Function family (or indistinguishable from a PRF; or secure in the Random Oracle Model) meaning that lacking some fragment of the definition of the hash, it's infeasible to distinguish it from a random function with the same domains.

Some of these properties are stronger than others. Finding implications involving (3) and those involving (4) is easy, and highly recommended to help grasp these properties. With appropriately large input domain of the hash, (2) implies (1), see this.

---

On relation between security properties of different hashes: the general idea is to assume an algorithm that can break one security property of one of the hashes, and use it (as a subprogram) to build a new algorithm that breaks one property (often, the same) for another hash. This proves that the second hash is no stronger than the first (or equivalently that if the first hash is secure, then the second is) w.r.t. the security property/properties considered.

---

For example, take preimage resistance for $H'$. Assume an algorithm $\mathcal A'$ breaking that. It is one which, given $h\in\{1,\dots, 2^{256}\}$ as input, outputs¹^,² $m\in\{0,1\}^*$ with $H'(m)=h$; that is an algorithm¹ such that² $H'(\mathcal A'(h))=h$.

By definition of $H'$, for the $m=\mathcal A'(h)$ that this algorithm produces, it also holds $H(m\mathbin\|m)=h$.

Therefore we can devises an algorithm $\mathcal A$ breaking preimage resistance for $H$, as follows:

• accept input $h\in\{1,\dots, 2^{256}\}$
• compute $m=\mathcal A'(h)$ by invoking the hypothesized algorithm breaking preimage resistance of $H'$
• compute and output $m\mathbin\|m$

We see that² $H(\mathcal A(h))=h$ (and the runtime of $\mathcal A$ is only slightly/linearly higher than that of $\mathcal A'$).

We conclude that if $H$ has preimage resistance, then $H'$ also has.

---

It is possible to make similar demonstrations for other security properties and other pairs of functions in the question.

Hint: In the problem at hand, the function $h\mapsto\alpha^h\bmod p$ is used in the construction of $H''$. Given the stated properties of $p$ and $\alpha$, this function has one demonstrable property and one conjectured property, which can be put to use to derive security properties of $H$ or $H''$, or relations between these properties.

---

¹ With running time polynomial w.r.t. the width of the output of the hash, but that formalism is not in the question, and can be omitted to some degree.

² With non-negligible probability, though that's sometime left implicit.