Practicidad de una determinada función hash

Question

Considere la siguiente función hash:

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

$A, B,$ y $C$ son números primos grandes. $V$ es el valor del hash y se garantiza que contiene al menos tantos bits como el número primo más grande.

Aparentemente, esto debería proporcionar un excelente nivel de resistencia a colisiones.

Ahora, asumiendo que los números primos en cuestión son lo suficientemente grandes, calcular el reverso debería ser inviable. ¿Correcto?

Answer 1

La debilidad obvia cuando uno ve un cuadrado es

$$(a)^{2} = (-a)^{2},$$Esto no es un problema en el Criptosistema Rabin ya que requiere un mecanismo adicional para resolver el mensaje de 4 posibles candidatos. Aquí, sin embargo, esto puede causar una colisión directa.

Además, como señaló fgrieu, el cálculo de la raíz cuadrada no es difícil en el caso principal de los Tonelli-Shanks . Este algoritmo funciona para prime$p$y generalizado para$p^k$, también.

Ahora, asumiendo que los números primos en cuestión son lo suficientemente grandes, calcular el reverso debería ser inviable. ¿Correcto?

Tomar $$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ Entonces no hay razón para $A$ y $B$ser un primo. Dado que no es un hash con clave, debemos conocer todos los valores, como$A,B,C$ entonces

$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ esto tiene dos soluciones en la gama $[0,C{-1}]$ e infinitas soluciones en el $\mathbf{Z}$. Podemos encontrar estos dos primeros con los Tonelli-Shanks y el resto con aritmética modular.

Por lo tanto, se pueden encontrar preimágenes, preimágenes secundarias y colisiones con mucha facilidad. Recuerde que en el ataque de preimagen no necesitamos encontrar el valor real$V$y cualquier valor $V'$ que produce el valor hash dado $h$ será suficiente para que este ataque tenga éxito.

Ni siquiera cerca de ser una función hash segura.