Consider the following hash function:

$$(V\cdot A + V\cdot B)^2 \bmod C$$

$A, B,$ and $C$ are large primes. $V$ is the value to be hashed and is guaranteed to contain at least as many bits as the largest prime.

Ostensibly, this should provide an excellent level of collision resistance.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

  • 2
    $\begingroup$ Plus, computing square root modulo a large prime is feasible by Tonneli-Shanks. $\endgroup$ – fgrieu Nov 14 '20 at 8:50
  • $\begingroup$ @fgrieu Thanks! $\endgroup$ – Sir Galahad Nov 14 '20 at 9:35
  • $\begingroup$ Uhm, $VA+VB$ is just $V(A+B)$ and believing Goldbach's conjecture, $A+B$ can essentially be any large even integer?! $\endgroup$ – Hagen von Eitzen Nov 14 '20 at 22:06

The obvious weakness when one sees a square is

$$(a)^{2} = (-a)^{2},$$ This is not a problem in the Rabin Cryptosystem since it requires an additional mechanism to resolve the message from possible 4 candidates. Here, however, this is can cause a direct collision.

Also, as noted by fgrieu, the calculation of the square root is not hard in the prime case by the Tonelli-Shanks. This algorithm work for prime $p$ and generalized for $p^k$, too.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

Take $$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ So there is no reason for $A$ and $B$ to be a prime. Since it is not a keyed hash, we should know all values, like $A,B,C$ then

$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ this has two solutions in the range $[0,C{-1}]$ and infinitely many solutions in the $\mathbf{Z}$. We can find these first two with the Tonelli-Shanks and the rest with modular arithmetic.

Therefore, one-can find pre-images, secondary pre-images, and collisions very easily. Remember in the pre-image attack we don't need to find the actual value $V$, and any value $V'$ that produces the given hash value $h$ will be enough for this attack to be successful.

Not even close to being a secure hash function at all.

  • $\begingroup$ Thank you, excellent explanation. So short of using a randomized RSA-style modulus, there's not much that could be done to make anything useful of that then I gather? $\endgroup$ – Sir Galahad Nov 14 '20 at 9:42
  • 1
    $\begingroup$ It is not RSA modulus, RSA modulus is the product of two primes and the power is not two. Rabin Cryptosystem uses 2. If you wonder about Hash with RSA here a previously asked question What is wrong in the following algorithm for computing a hash function using RSA? $\endgroup$ – kelalaka Nov 14 '20 at 9:59
  • 1
    $\begingroup$ Surely you mean two solutions in the range [0..C-1], right? V and -V mod C? $\endgroup$ – Vaelus Nov 14 '20 at 15:24
  • $\begingroup$ @Vaelus thanks. corrected. $\endgroup$ – kelalaka Nov 14 '20 at 15:28

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.