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

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?

Any input would be GREATLY appreciated!

• The question implicitly considers that the input set of the hash is (possibly, a subset of) $\{0,1,2,\ldots,n-2,n-1\}$ or similar. Otherwise, there is no second-preimage resistance, and (thus) no collision resistance.
– fgrieu
Sep 25 '20 at 6:30
• @fgrieu, are you sure? I ask because the part of the solution that says "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)." seems to imply to me that it's not limited to non-negative integers which are less than n. Did I misunderstand something? Sep 25 '20 at 23:05
• @Kaminsky: My mistake. I wish I wrote "The question implicitly considers that the input set is (possibly, a subset of) $\{0,1,2,\ldots,(n-1)/2\}$ or similar", in order to avoid a small variant of the attack you state, where $m$ and $n-m$ obviously collide.
– fgrieu
Sep 26 '20 at 8:55
• Actually, m = m^1 and n - m colliding is not obvious to me. :( The closest thing I can think of is m^2 and m^2 - n (or m^2 +/- any multiple of n) yielding the same output value. Also, that's not what I was saying; what I was saying was that -m ∉ {0,1,...,n-2,n-1} (so it's also the case that -m ∉ {0,1,...,(n-1)/2}) (and the solution considers -m to be valid input). In fact, it seems to me that any integer input is acceptable. I think considering {0,1,...,(n-1)/2} is just for a cryptanalyst to find p or q in O(√n), rather than in O(n). As usual, please let me know if I'm misunderstanding. :) Sep 26 '20 at 23:50

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.

• Thanks a lot! About the (Z/qZ)× notation, is it the case that Z means all integers, gZ == Z_g means all integers from q onwards and that the × is for specifying that the output is an ordered pair? Sep 25 '20 at 23:07
• @AlfredKaminski Unfortunately no. $\mathbb{Z}/n\mathbb{Z}$ denotes "arithmetic mod $n$". Essentially you can define new operations $+'$ and $\times'$ where $a+'b = a+b\bmod n$ and $a\times' b = a\times b\bmod n$, so for example in $\mathbb{Z}/7\mathbb{Z}$ $3+'5 = 8\equiv 1\bmod 7$. $(\mathbb{Z}/n\mathbb{Z})^\times$ means only looking at the multiplication operation. You want everything to have an inverse (an element $b$ such that $a\times' b = 1$), so have to exclude some elements (always 0, if not working in $(\mathbb{Z}/q\mathbb{Z})^\times$ for $q$ prime then more as well).
– Mark
Sep 25 '20 at 23:48
• @AlfredKaminski For a concrete example of $m_q^{-1}\bmod q$ though, let $q = 5$, and assume that $m_q = 3$. Then $3\times' 2 = 6\bmod 5\equiv 1\bmod 5$, so $3^{-1}\bmod 5 = 2$. This is different than the $1/3$ you would expect from working in $\mathbb{R}$, but it is what I intend in the above.
– Mark
Sep 25 '20 at 23:50
• All right, I think (and hope :P) I understood. Thanks again. :) Sep 26 '20 at 23:57

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.

• According to this ( code.i-harness.com/en/q/820cfd ), "the weak collision resistance property is sometimes also referred to as second preimage resistance", so what you quoted does not seem to be incorrect. Am I missing something? Sep 25 '20 at 23:01
• Collision resistance implies preimage resistance for strongly compressing hash functions, but is strictly broader. Sep 26 '20 at 14:03
• Re-reading the solution after having read what you said and other sources too, it seems to me that m is just a placeholder variable that can in fact be any message (instead of being a specific message (because the solution says "for any m", and not something like "for some m = m_0")), so then the solution seems correct after all, doesn't it? Sep 26 '20 at 22:45