1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 12 '17 at 16:12
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ok, but what about my second part? $\endgroup$
    – bobuhito
    Jan 12 '17 at 8:10
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bobuhito
    Jan 13 '17 at 20:31
  • $\begingroup$ That related question on math.SE has almost died, but has a sibling on Mathoverflow. $\endgroup$
    – fgrieu
    May 6 '20 at 9:42

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.