Break the broken hash Some time ago, I found this unused hash function (written in Java) in our codebase:

long hashPassword(String password)
{
    password = password.toUpperCase();
    long hash = 0;
    int multiplier = 13;
    for (int i = 0; i &lt; password.length(); i++)
    {
        hash += hash * multiplier + (short)password.charAt(i);
        multiplier++;
    }
    hash = Math.abs(hash);
    hash &lt;&lt;= hash % 11;
    hash = Math.abs(hash);
    return hash;
}


I am very happy that it was unused, because it is beyond broken. Not only is this hash function very weak with an ouput of only 8 bytes, but it is also reversible, and it collides very easily: there are many similar inputs that will generate the same hash. A friend and I worked on the problem, and we managed to create a C# program that does just that: take a hash, and show the reasonable inputs that could have generated this hash.

Now is your turn. Write a program, in any language, that accepts a numeric hash as its sole parameter, and yields all possible inputs (made of 5+ characters with only printable ASCII characters) that would produce the given hash if passed to the function above, each on a new line. You don't need to handle any specific kind of error, as long as it works for any given numeric hash.

On your post, please include the hash of a word of your choice, and five possible inputs that have this hash (though your program must not be limited to finding only five).

Most elegant solution wins, and elegance is defined as algorithmic elegance (in other words, brute-force won't win). I'll accept an answer on March 13.

Example input and output (UNIX shell optional):

$ ./hashbreaker 224443104
ZNEAK
Y^4Q]
\2'!'
ZMUB9
Y_%AK
[and many, many, many more results...]
I got more than enough answers without reversing both abs calls, so I skipped that.  They'd be trivial to add back if really needed.  I'm not even taking long overflow into account, but that'd let you insert most any word you like in the greater hashes.  As if that was needed to get collisions.

import Data.Char
import Data.Bits
import Control.Monad

printables = [32..95]

reverseModShift11 x = do
  let zeros = head $ filter (testBit x) [0..]
  b &lt;- [0 .. zeros]
  let h = x `shiftR` b
  guard $ (h `mod` 11) == (fromIntegral b)
  return h

reverseBase p m n | m &lt; 13    = []
                  | n &lt;  0    = []
                  | n == 0 &amp;&amp; m == 13 = return p
                  | otherwise = do
  let r = n `mod` m
  c &lt;- filter (\x -&gt; x `mod` m == r) printables
  reverseBase (chr c:p) (m-1) ((n-c) `div` m)

reverseBases = join . ap (map (reverseBase "") [14..29]) . return

breakHash = reverseModShift11 &gt;=&gt; reverseBases


Sample use:

*Main&gt; breakHash 224443104
["]#'!'","\\2'!'","[A'!'","ZP'!'","Y_'!'",
  (...)
"[?EAK","ZNEAK","Y]EAK",
  (...)
"] TQ]","\\/TQ]","[&gt;TQ]","ZMTQ]","Y\\TQ]"]