Suppose given fix values $a,b$, how difficult to find a pair of sha256 pre-images $x_1,x_2$ such that $H(x_2)=aH(x_1)+b$? How difficult to find 4 hash pre-images $x_1,x_2,x_3,x_4$ such that $\dfrac{H(x_2)-a}{H(x_1)+b}=\dfrac{H(x_3)-a}{H(x_4)+b}$?


Case 1: Assuming $\mathbb{F}_2^n.$ The only scalar constants you can have in characteristic $2$ to are $0$ or $1$? So, you need to define multiplication for quantities in $\mathbb{F}_2^n$ for this to be non trivial.

Let $n=256.$ For any vectors $b\in \mathbb{F}_2^n,$ your first equation with scalar $a$ is equivalent to

  • $H(x_2)=b$ if $a=0,$ which takes $O(2^n)$ work (preimage problem).
  • $H(x_1)\oplus H(x_2)=b,$ which takes $O(2^{n/2})$ work (collision problem).

As for your second equation, it reduces to a quadratic relation which doesn't look meaningful in this context since the multiplication has to be defined for it to make sense.

One can use $\mathbb{F}_{2^n}$ as a representation for $\mathbb{F}_2^n,$ under some canonical basis, maybe a self dual basis, but more cryptographic justification for what you seem to be attempting needs to be provided for such an operation, given that solving quadratics is no easier than solving linear equations.

Case 2: (Thanks to @kelalaka) If you mean to take $\mathbb{Z}_{2^{256}},$ then one might guess that if the hash function is strong, the $a-$multiple $a H(x_1):=H_a(x_1)$ can itself be modeled as a random function and you are now solving a generalized collision problem between two random functions $$ H(x_2)-H_a(x_1)=b $$ which again should have complexity $O(2^{n/2}).$

For the second question things are trickier. Firstly there are zero divisors in the ring $\mathbb{Z}_{2^{256}},$ and you should not divide but cross multiply and consider $$ (H(x_2)-a)(H(x_4)+b)=(H(x_1)-a)(H(x_3)+b) $$ Let $u_i$ be the largest exponent of $2$ which divides the value $H(x_i)- c_i$ modulo $2^{256}$ where $c_1=c_3=a$ and $c_2=c_4=-b$. If $u_1+u_3\geq 256,$ then we need to have either $H(x_2)=a,$ or $H(x_4)=-b,$ (either happen with probability $2^{-256}$ or $u_2+u_4\geq 256,$ for this equation to have a solution.

Again, modeling these translated hashes as pseudorandom functions $Pr[u_i\geq k]=2^{-k},$ for $0\leq k\leq 255.$ For example, $Pr[u_i\geq 1]=1/2,$ which happens if the LSB of the hash output is 0.

Using this, one can derive actual probabilities for these equations to hold, based on the argument in italics.

  • $\begingroup$ aha, that might be. Let's see if he clarifies. $\endgroup$
    – kodlu
    Jun 8 '20 at 10:53
  • 1
    $\begingroup$ have a look at what I wrote, don't have much time to do more right now. $\endgroup$
    – kodlu
    Jun 8 '20 at 11:16

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.