Mid-Square Hash Quality

From "mid-square random number generation", let me simply define the "128-hash" as the middle bits of the square of a 128-bit number.

Does this hash have any known collisions?

Are there any known impossible hashes? In other words, is there a known "128-hash" which would never occur even if all starting 128-bit numbers were tried?

• I'm not sure this question is really on-topic here, given that AFAIK nobody has ever seriously suggested using the middle-square RNG for any cryptographic purpose. It might be better suited for Computer Science or Mathematics. Jan 12 '17 at 16:12

Does this hash have any known collisions?

Of course; any value with 96 leading zeros (that is, between $0$ and $2^{32}-1$) will middle square to 0, hence that gives a $2^{32}$-wide collision right there.

• Ok, but what about my second part? Jan 12 '17 at 8:10

The existence of collisions, as demonstrated in poncho's answer, implies by a counting argument that there are impossible hashes. That however does not explicitly exhibit any.

Experiment with small even $k$-bit hash show that values very close to the high end of the interval are much more likely to be impossible hashes than others (e.g. at the low end). Here are highest impossible hashes for various $k$

k (dec)       Six highest impossible hashes (hex)
4            F            D            B            7            5            3
6           3F           3B           39           36           35           31
8           FD           FC           FB           F7           F5           F3
10          3FB          3F9          3F7          3F6          3F3          3F1
12          FFF          FF8          FF7          FF3          FF2          FEF
14         3FFF         3FFD         3FFB         3FFA         3FF9         3FF6
16         FFFF         FFFD         FFFC         FFF5         FFF4         FFF1
18        3FFFF        3FFFC        3FFFA        3FFF8        3FFF7        3FFF3
20        FFFFD        FFFF9        FFFF8        FFFF6        FFFF5        FFFF1
22       3FFFF9       3FFFF7       3FFFF6       3FFFF3       3FFFEF       3FFFED
24       FFFFFD       FFFFFB       FFFFF7       FFFFF6       FFFFF4       FFFFF2
26      3FFFFEF      3FFFFEE      3FFFFED      3FFFFE8      3FFFFE5      3FFFFE3
28      FFFFFFD      FFFFFFB      FFFFFF5      FFFFFF4      FFFFFEF      FFFFFEA
30     3FFFFFFF     3FFFFFFD     3FFFFFFA     3FFFFFF6     3FFFFFF4     3FFFFFF1
32     FFFFFFFD     FFFFFFFC     FFFFFFFA     FFFFFFF9     FFFFFFF8     FFFFFFF7
34    3FFFFFFFD    3FFFFFFF8    3FFFFFFF7    3FFFFFFEF    3FFFFFFED    3FFFFFFEC
36    FFFFFFFFF    FFFFFFFFB    FFFFFFFFA    FFFFFFFF7    FFFFFFFF4    FFFFFFFEC

This strongly suggests that if we had a feasible way to test that a $k$-bit value is an impossible hash, it would only be a few times harder to exhibit one, by testing $2^k-j$ for increasing $j\ge1$.

I wish I could analyze this analytically. Perhaps that would allow a simple proof that some value is an impossible hash (despite the discouraging anomaly for $k=26$). Lacking this, an automated method that perhaps could work for $k=128$ is to express the test of a $k$-bit impossible hash as a SAT problem with unknowns the $k$ bits of the preimage, use a state of the art solver, and conclude that the hash tested is indeed impossible if the problem is unsatisfiable.

• That is helpful research. So, I'd say the answer is that there is no known impossible hash, but if I paid you to work on it full-time for a year, you have a 50% chance of finding one. Jan 13 '17 at 20:31
• That related question on math.SE has almost died, but has a sibling on Mathoverflow.
– fgrieu
May 6 '20 at 9:42