Questions regarding the one-wayness and collision-resistance of a hash function based on RSA-like problem

Question

Problem statement:

"Bob is a paranoid cryptographer who does not trust dedicated hash functions such as SHA1 and SHA-2. Bob decided to build his own hash function based on some ideas from number theory. More precisely, Bob decided to use the following hash function: $H(m)= m^2\bmod n, n= p\times q$, where $p$ and $q$ are two large distinct primes. Does this hash function satisfy the one-wayness property? What about collision resistance? Explain."

Official solution:

"Since p and q are secret, then finding the square root mod n is a hard problem. Thus this hash function satisfies the one-wayness property. On the other hand, H does not satisfy the weak/strong collision resistance property because for any m, -m would also have the same hash value, i.e., H(m)=H(-m)."

My confusion:

For the one-wayness property part of this cryptographic hash function problem, the solution says that finding the square root mod n is a hard problem since p and q are secret. If, for example, this were the asymmetric RSA encryption algorithm, then that would make sense to me because having p and q could allow you to get the decryption key, but for this hash problem, I don't see how knowing p and/or q would make it easier for an attacker to reverse that modular operation even if p and q were known.

Also, about the collision resistance property part of this cryptographic hash problem, can a file that's being tested for not being tampered with provide a negative value as an input to a cryptographic hash function?

Could someone please help me understand what I'm unclear about?

Any input would be GREATLY appreciated!

Answer 1

Knowing either $p$ or $q$ is sufficient to recover both of them (as $q = n/p$). So imagine we know all of $p, q$, and $n$.

The chinese remainder theorem can be phrased many different ways. In general, it states that when working mod $n$ (where $n$ is a product of distinct primes [1]), you can instead work mod each prime separately. In this particular setting, this means that instead of looking at the equation:

$$H(m) = m^2\bmod pq$$ We can look at the pair of equations: $$H(m_q, m_p) = (m_q^2\bmod q, m_p^2\bmod p)$$ If we can "solve" one of the sets of equations ($\bmod n$ vs $(\bmod q,\bmod p)$), we can efficiently convert the solution into a solution of the other equation. The second equation will be easier to solve, so will be how we can perform a preimage attack.

In more detail, say you're given a "target" point $c = H(m)$ for some unknown $m$. Then, we can apply the chinese remainder theorem to convert this into two points $(c_q, c_p)$ for the bottom equation (in particular, $c_q = c\bmod q, c_p= c\bmod p$).

How can we find $m_q$ such that $c_q = m_q^2\bmod q$? There are known algorithms to do it (see Cipolla's algorithm) which do so efficiently (it looks like it is $O(\log q)$). So, we can find $m_q, m_p$ that solve the bottom equation efficiently.

Then, we just convert $m_q, m_p$ back into $m$. This can be computed efficiently, in particular by writing: $$m = m_q(m_q^{-1}\bmod q) p + m_p(m_p^{-1}\bmod p)q$$ Where $m_q^{-1}\bmod q$ is the inverse of $m_q$ within $(\mathbb{Z}/q\mathbb{Z})^{\times}$, meaning is the modular multiplicative inverse.

So essentially, if we know $n$'s factorization, we can apply the chinese remainder theorem to reduce everything to the case of $\mod p$ where $p$ is prime. Arithmetic behaves much better in this case, so we can efficiently solve the equation.

---

[1] One can even apply this to distinct prime powers, meaning an equation $\bmod p^2 q^3$ can be broken into two equations $\bmod p^2$ and $\bmod q^3$. It cannot be broken into 5 equations $(\bmod p, \bmod p, \bmod q, \bmod q,\bmod q)$ though.

Answer 2

Also, about the collision resistance property part of this cryptographic hash problem, can a file that's being tested for not being tampered with provide a negative value as an input to a cryptographic hash function?

That would be more akin to breaking second preimage resistance (given a message $m$ and hash $H(m)$, find another message $m'\neq m$ such that $H(m')=H(m)$). Collisions just mean finding any two distinct messages that have the same hash.