3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fgrieu Sep 25 '20 at 6:30
  • $\begingroup$ @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? $\endgroup$ – Alfred Kaminski Sep 25 '20 at 23:05
  • $\begingroup$ @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. $\endgroup$ – fgrieu Sep 26 '20 at 8:55
  • $\begingroup$ 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. :) $\endgroup$ – Alfred Kaminski Sep 26 '20 at 23:50
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alfred Kaminski Sep 25 '20 at 23:07
  • $\begingroup$ @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). $\endgroup$ – Mark Sep 25 '20 at 23:48
  • $\begingroup$ @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. $\endgroup$ – Mark Sep 25 '20 at 23:50
  • $\begingroup$ All right, I think (and hope :P) I understood. Thanks again. :) $\endgroup$ – Alfred Kaminski Sep 26 '20 at 23:57
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alfred Kaminski Sep 25 '20 at 23:01
  • $\begingroup$ Collision resistance implies preimage resistance for strongly compressing hash functions, but is strictly broader. $\endgroup$ – SAI Peregrinus Sep 26 '20 at 14:03
  • $\begingroup$ 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? $\endgroup$ – Alfred Kaminski Sep 26 '20 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.