Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

Question

I came upon the following hash function (pseudo-code):

function customHash(integer:user_input)
{
    user_input = user_input modulo 2654435789
    user_input = user_input * 2654435789
    ret_to_user = user_input >> 32
    return ret_to_user
}

The goal of the problem I am trying to solve is:

• Find two inputs [i,j] that can only be lowercase characters, uppercase characters, digits or a compination of them (a-zA-Z0-9) where the customHash(j) == customHash(i)^2. The input to the function is the integer representation of the input (meaning we take the whole input, convert it to integer and then pass this integer to the function). Also, there is no restriction to the length of the input that is passed to customHash function.

For example:

• customHash(i) = 5
• customHash(j) = 25

I tried using code to brute force inputs until I got a solve to this problem but the code was running forever. Also, even if it did find a match, It might not be a solution that is in (a-zA-Z0-9).

I got one suggestion that this can be done with lattices, but I am not sure how, so if anyone is proficient with lattices (and it indeed is solvable with lattice approach) or has some other approach to this problem, I would really like an explanation to it.

Answer 1

$i=j=0$, both representing the empty string and hashing to the integer $0$, is a trivial answer to the question for most of the plausible readings of “convert it to integer”. In the following I add to the statement that we restrict to non-empty input, and that conversion to integer is from ASCII strings either big-endian or little-endian, as per int.from_bytes in modern Python.

---

We remark that if $p=2654435789=\mathtt{9E3779CD_h}$, the output of the hash function $H$ is an integer in $\left[0,m\right)$ with $m=\left\lfloor p\,(p-1)/2^{32}\right\rfloor+1=1640531550=\mathtt{61C8865E_h}$, and approximately equidistributed on that range for large random input. I first outline a method that uses only this characteristic.

The desired $(i,j)$ are such that $H(i)^2=H(j)$. We thus are interested only in inputs

1. $i$ such that $H(i)\in\left[0,r\right)$ with $r=\left\lfloor\sqrt{m-1}\right\rfloor+1=40504$
2. $j$ such that $H(j)$ is a square in $\left[0,m\right)$, of which there are $r$.

When we pick a random valid input, there is probability about $1/r$ that it falls into category 1., same for category 2. Thus if we try $r^{3/2}$ random inputs, that is $<9$ millions, which is quite feasible, we'll have roughly $r^{1/2}\approx200$ in each category, and there is sizable chance that we have a collision between an $H(i)^2$ with $i$ in category 1, and $H(j)$ with $j$ in category 2, hence a solution. We only need to keep track of about $400$ input/output pairs, thus memory is not an issue. Each time we double the hashing effort and memory, the probability of not reaching a collision is divided by about four, and that quickly becomes negligible.

Advantages of that solution are that it works without diving into the details of customHash, and it's easy to restrict to meaningful inputs, or/and palindromes so that our solution will be accepted by both a little-endian and big-endian homework checker. However it's not optimal in term of computation.

---

It's easy to break preimage resistance of customHash. That is, given a desired output value $y\in\left[0,m\right)$, find an $x$ (with the restriction to ASCII in digits and letters for each of it's bytes) such that $H(x)=y$. This allows to find a solution. We only need to break preimage resistance

• once for either $y=0$ or $y=1$, which are their own squares, and will give us a single input $x$ with $H(x)^2=H(x)$
• or twice, for some $y_j\in\left[2,r\right)$ and for the matching $y_i={y_j}^2$.

To break preimage resistance, we use that the last 3 our of 4 steps of customHash implement multiplication by $p/2^{32}$ rounding down, which is trivially inverted (sometime with two possible inputs for a given output) yielding one (at least) $z\in[0,p)$ for any given $y$. Now it remains to find a valid $x$ such that $x\bmod p=z$. Using big-endian, we can pick any prefix bytestring $x_0$ consisting of digits and letters, compute $x_1=(z-x_0\,2^{32})\bmod p$, and check if $x_1$ has all it's 4 bytes digits or letters, which will happens for about one out of $p/62^4\approx180$ random prefixes $x_0$ that we try (optionally: if it does not and $x_1<2^{32}-p$, we can replace $x_1$ by $x_1+p$ and have a second chance at little cost). Then $x_0\mathbin\|x_1=x_0\,2^{32}+x_1$ is the desired valid preimage $x$. For little-endian, we just need to reverse $x$ obtained for big-endian.

Breaking preimage resistance restricting to palindromes is also feasible, and left as an exercise to the reader.