Break the broken hash
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 <- [0 .. zeros]
let h = x `shiftR` b
guard $ (h `mod` 11) == (fromIntegral b)
return h
reverseBase p m n | m < 13 = []
| n < 0 = []
| n == 0 && m == 13 = return p
| otherwise = do
let r = n `mod` m
c <- filter (\x -> 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 >=> reverseBases
Sample use:
*Main> breakHash 224443104
["]#'!'","\\2'!'","[A'!'","ZP'!'","Y_'!'",
(...)
"[?EAK","ZNEAK","Y]EAK",
(...)
"] TQ]","\\/TQ]","[>TQ]","ZMTQ]","Y\\TQ]"]
Another partial answer:
using System;
using System.Collections.Generic;
namespace Sandbox {
class Launcher {
public static int Main(string[] args) {
long h4;
if (args.Length != 1 || !long.TryParse(args[0], out h4)) {
Console.Error.WriteLine("Usage: Sandbox.exe <hash>");
return -1;
}
// TODO Handle 15-char or longer solutions. 15 chars is the point at which simple mod breaks because the multipliers wrap.
for (int len = 5; len < 15; len++)
foreach (long h3 in invAbs(h4))
foreach (long h2 in h3Toh2(h3))
foreach (long h1 in invAbs(h2))
foreach (string soln in solveH1Inner(h1, new char[len], len - 1, 1, 13 + len))
Console.WriteLine(soln);
return 0;
}
private static IEnumerable<string> solveH1Inner(long rem, char[] chs, int off, long mul, long mod) {
if (off < 0) {
if (rem == 0) yield return new string(chs);
yield break;
}
long mask = (mul & -mul) - 1;
if ((rem & mask) != 0) yield break;
foreach (char ch in " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_{|}~") {
if ((ch * mul) % mod == rem % mod) {
chs[off] = ch;
foreach (string soln in solveH1Inner(rem - mul * ch, chs, off - 1, mul * mod, mod - 1))
yield return soln;
}
}
yield break;
}
private static IEnumerable<long> invAbs(long h4) {
if (h4 < 0 && h4 != long.MinValue) throw new ArgumentException();
yield return h4;
if (h4 != long.MinValue) yield return -h4;
}
private static IEnumerable<long> h3Toh2(long h3) {
// h3 = h2 << (h2 % 11)
// where h2 is either long.MinValue or non-negative.
// long.MinValue << (long.MinValue % 11) = 0
if (h3 == 0) yield return long.MinValue;
for (int shift = 0; shift < 11; shift++) {
if (shift == 0 && h3 < 0) continue;
long mask = (1L << shift) - 1;
if ((h3 & mask) != 0) break;
long inc = shift == 0 ? 0 : 1L << (64 - shift);
long maskBottom = inc - 1;
long bottom = (h3 >> shift) & maskBottom;
long top = 0;
do {
if ((top + bottom) % 11 == shift) yield return (top + bottom);
top += inc;
} while (top > 0);
}
}
}
}
There are some minor optimisations which could be done, but I think it's more legible like this. (Arguably I should eliminate the enumerators and push the WriteLine in too, but hey).
Example of collisions for 199681664
PETER OTTER R(DER Q6SVR R*&$@
JavaScript 224 LOC
This function will calculate all results of a given length, optionally limited to results starting with a given string, that is if it's done within the 1 second that I have allotted. If no results exist it is done virtually instantly. The function rely heavily on a very slow custom built 64 bit integer library, an equivalent C function would probably be 100 to 1000 times faster. I might set up a nice web interface.
<html>
<head>
<title>Break Hash</title>
</head>
<body>
<pre id="out"></pre>
<script>
function to64(inp){
var res=[]
res[0]=inp%(256*256*256)
inp=Math.floor(inp/(256*256*256))
res[1]=inp%(256*256*256)
inp=Math.floor(inp/(256*256*256))
res[2]=inp%(256*256)
return res
}
function add64(inp1,inp2){
var res=[]
res[0]=inp1[0]+inp2[0]
res[1]=inp1[1]+inp2[1]+Math.floor(res[0]/(256*256*256))
res[2]=(inp1[2]+inp2[2]+Math.floor(res[1]/(256*256*256)))&(256*256-1)
res[0]&=(256*256*256-1)
res[1]&=(256*256*256-1)
return res
}
function neg64(inp){
var res=[]
res[0]=inp[0]^(256*256*256-1)
res[1]=inp[1]^(256*256*256-1)
res[2]=inp[2]^(256*256-1)
return add64(res,[1,0,0])
}
function abs64(inp){
if(inp[2]>=(256*128)){
return neg64(inp)
}
return inp
}
function mul64(inp1,inp2){
var res=[]
res[0]=inp1[0]*inp2[0]
res[1]=inp1[1]*inp2[0]+inp1[0]*inp2[1]+Math.floor(res[0]/(256*256*256))
res[2]=inp1[2]*inp2[0]+inp1[1]*inp2[1]+inp1[0]*inp2[2]+Math.floor(res[1]/(256*256*256))
overflow=(res[2]>=(256*256)) //Global shortcut
res[2]&=(256*256-1)
res[0]&=(256*256*256-1)
res[1]&=(256*256*256-1)
return res
}
function mod64(inp1,inp2){ //64,float -> float
var res=inp1[2]%inp2
res=(res*(256*256*256)+inp1[1])%inp2
return (res*(256*256*256)+inp1[0])%inp2
}
function div64(inp1,inp2){ //64,float -> 64
var res=[]
res[2]=Math.floor(inp1[2]/inp2)
var mem1=inp1[1]+(inp1[2]%inp2)*(256*256*256)
res[1]=Math.floor(mem1/inp2)
res[0]=Math.floor((inp1[0]+(mem1%inp2)*(256*256*256))/inp2)
return add64(res,[0,0,0])
}
function cmp64(inp1,inp2){
for(var a=2;a>=0;a--){
if(inp1[a]>inp2[a]){
return 1
}
if(inp1[a]<inp2[a]){
return -1
}
}
return 0
}
function string64(inp){
var res=""
while(cmp64(inp,[0,0,0])){
res=mod64(inp,10)+res
inp=div64(inp,10)
}
return res||"0"
}
function hashPassword(password){
var i
password=stringtoarray(password)
var hash = to64(0);
var multiplier = to64(13);
for (i = 0; i < password.length; i++){
multiplier = add64(multiplier,[1,0,0])
hash = add64(mul64(hash,multiplier),to64(password[i]));
}
hash = abs64(hash);
hash = mul64(hash,to64(Math.pow(2,mod64(hash,11))));
hash = abs64(hash);
return string64(hash)
}
function stringtoarray(password){
var i
if((typeof password)=="string"){
var password2 = password.toUpperCase();
password=[]
for(i=0;i<password2.length;i++){
password[i]=password2.charCodeAt(i)
}
}
return password
}
function reverse(hash,start,len){
var maxtime=(+new Date())+1000
var m1=neg64(to64(1))
start=stringtoarray(start)
var multipliers=[]
var multipliersum=[]
var max=[]
var min=[]
var firstlimit=0
multipliers[len-1]=[1,0,0]
multipliersum[len-1]=[1,0,0]
max[len-1]=[126,0,0]
min[len-1]=[32,0,0]
for(var a=len-2;a>=0;a--){
multipliers[a]=mul64(multipliers[a+1],to64(15+a))
multipliersum[a]=add64(multipliers[a],multipliersum[a+1])
min[a]=mul64(multipliersum[a],[32,0,0])
max[a]=mul64(multipliersum[a],[126,0,0])
if(overflow && !firstlimit){
firstlimit=a+1
}
}
var startvalue=[0,0,0]
for(var a=0;a<start.length;a++){
startvalue=add64(startvalue,mul64(to64(start[a]),multipliers[a]))
}
startvalue=neg64(startvalue)
allowed=[]
for(a=0;a<32;a++){
allowed[a]=false
}
for(a=32;a<97;a++){
allowed[a]=true
}
for(a=97;a<123;a++){
allowed[a]=false
}
for(a=123;a<127;a++){
allowed[a]=true
}
for(a=127;a<256;a++){
allowed[a]=false
}
var results=[]
function arrtostring(arr){
str=""
for(var a=0;a<arr.length;a++){
//str+=String.fromCharCode(arr[a])
str+="&#"+arr[a]+";"
}
return str
}
function makepwd(ihash){ //This is where clock cycles go to die
ihash=add64(ihash,startvalue)
stringarr=[]
for(var a=0;a<start.length;a++){
stringarr[a]=start[a]
}
function addrest(ihash,startfrom){
if(maxtime<(+new Date())){
return
}
var a
var jhash
if(startfrom==len){
if(cmp64(ihash,[0,0,0])==0){
results[results.length]=arrtostring(stringarr)
}
}
else if(startfrom<firstlimit || ((cmp64(ihash,min[startfrom])!=-1) && (cmp64(ihash,max[startfrom])!=1))){
for(a=32;a<127;a++){
if(allowed[a]){
jhash=add64(ihash,neg64(mul64(to64(a),multipliers[startfrom])))
stringarr[startfrom]=a
addrest(jhash,startfrom+1)
}
}
}
}
addrest(ihash,start.length)
}
function reversemod(ihash){
if(ihash[2]<(128*256)){
if(mod64(ihash,11)==0){
makepwd(ihash)
makepwd(neg64(ihash))
}
}
var modresult=1
var a
var addlim
var jhash
while(mod64(ihash,2)==0){
ihash=div64(ihash,2)
addlim=Math.pow(2,modresult-1)
for(a=0;a<addlim;a++){
jhash=add64(to64(a*Math.pow(2,64-modresult)),ihash)
if(mod64(jhash,11)==modresult){
makepwd(jhash)
makepwd(neg64(jhash))
}
}
modresult++
}
}
reversemod(hash)
reversemod(neg64(hash))
return results
}
document.getElementById("out").innerHTML=reverse(to64(224443104),"ebusiness",22).join("<br>")
//document.getElementById("out").innerHTML=hashPassword("EBUSINESS\"XUWL]NHHHF{I")
</script>
</body>
</html>
Some collisions for 224443104
EBUSINESS"XUWL]NHHHF{I
EBUSINESS"XUWL]NHHHF|&
EBUSINESS"XUWL]NHHHGYI
EBUSINESS"XUWL]NHHHGZ&
EBUSINESS"XUWL]NHHHH7I