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

22 Views Asked by At

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. Also, there is no restriction to the length of the input that is passed to customHash function.

For example:

  • customHash(i) = 5
  • customHash(i) = 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.

(P.s. I also asked this question in crypto exchange forum in case you prefer to answer there)