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!

Improve this question
$\endgroup$
4
  • $\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$ Commented Sep 25, 2020 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$ Commented Sep 25, 2020 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$ Commented Sep 26, 2020 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$ Commented Sep 26, 2020 at 23:50

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Sep 25, 2020 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$ Commented Sep 25, 2020 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$ Commented Sep 25, 2020 at 23:50
  • $\begingroup$ All right, I think (and hope :P) I understood. Thanks again. :) $\endgroup$ Commented Sep 26, 2020 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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented Sep 25, 2020 at 23:01
  • $\begingroup$ Collision resistance implies preimage resistance for strongly compressing hash functions, but is strictly broader. $\endgroup$ Commented Sep 26, 2020 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$ Commented Sep 26, 2020 at 22:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.