A bit of a weird longshot, but does anyone have any resources on reducing the viable search space of inputs to a polynomial rolling hash where the multiplier is known, and the modulus is just over a 4-byte word?

[mrl314@peoplemaking.games]

A bit of a weird longshot, but does anyone have any resources on reducing the viable search space of inputs to a polynomial rolling hash where the multiplier is known, and the modulus is just over a 4-byte word?

I’ve given a couple of thoughts to cracking this but I keep hitting hard dead-ends to my knowledge.

Also I must state this isn’t for any actual security breaching, (you shouldn’t be using this kind of hash for anything remotely secure), this is mostly a pet project with a minor application in reverse engineering a few hashed strings in an older game with no reference in the code to the original strings

[mrl314@peoplemaking.games]

For those more curious, the rolling part of the hash is:

h_i = s_i + h_i-1 * 31
over an int32

My current approach was to try to find a lattice basis for
KNOWN_HASH = sum(0<=k<n, s_i * 31^(n-1 - k)) mod 2^32 where n = length of string s
and then run some brutes over that search space since it’ll likely be significantly smaller than just regular bruting

However I’m both very interested in the math, and I don’t want to chug my computer on the problem more than I need to

[clarfonthey@toot.cat]

@MrL314 I think you're kinda stuck since this seems to just be a standard discrete logarithm problem

that said even with a pretty meagre GPU you could probably just brute-force the entire space in a few minutes