Murmur3 Hash Inverse
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

Complete the hashInverse function such that the main function will run without throwing an exception

public class Murmur3Bounty {
    protected static long rotl64(long v, int n) {
        return ((v << n) | (v >>> (64 - n)));
    }

    protected static long fmix(long k) {
        k ^= k >>> 33;
        k *= 0xff51afd7ed558ccdL;
        k ^= k >>> 33;
        k *= 0xc4ceb9fe1a85ec53L;
        k ^= k >>> 33;
        return k;
    }

    public static long hash(long num) {
        long c1 = 0x87c37b91114253d5L;
        long c2 = 0x4cf5ad432745937fL;
        long k1 = Long.reverseBytes(num);
        k1 *= c1;
        k1  = rotl64(k1, 31);
        k1 *= c2;
        long h1 = k1 ^ 8;
        long h2 = 8;

        h1 += h2;
        h2 += h1;

        h1 = fmix(h1);
        h2 = fmix(h2);

        h1 += h2;
        return h1;
    }

    protected static long reverseRotl64(long v, int n) {
        return ((v >>> n) | (v << (64 - n)));
    }

    protected static long reverseRightShiftXor(long value, int shift) {
        long output = 0;
        long i = 0;
        while (i * shift < 64)
        {
            long compartment = (0xffffffffffffffffL << (64 - shift)) >>> (shift * i);
            long partOutput = value & compartment;
            value ^= partOutput >>> shift;
            output |= partOutput;
            i += 1;
        }
        return output;
    }

    protected static long reverseFmix(long k) {
        k = reverseRightShiftXor(k, 33);
        k *= -7154897129451604005L; // Multiplicative inverse of 0xc4ceb9fe1a85ec53L
        k = reverseRightShiftXor(k, 33);
        k *= 5725274745694666757L; // Multiplicative inverse of 0xff51afd7ed558ccdL
        k = reverseRightShiftXor(k, 33);
        return k;
    }

    public static long testHash(long num) {
        long c1 = 0x87c37b91114253d5L;
        long c2 = 0x4cf5ad432745937fL;
        long k1 = Long.reverseBytes(num);
        k1 *= c1;
        k1  = rotl64(k1, 31);
        k1 *= c2;
        long h1 = k1 ^ 8;
        long h2 = 8;
        h1 += h2;
        //h2 += h1;
        h1 = fmix(h1);
        //h2 = fmix(h2);
        //h1 += h2;
        return h1;
    }

    public static long testHashInverse(long hash) {
        long c1inv = -6231845090142302851L;
        long c2inv = -6332601014241317761L;
        long h1 = hash;
        //long h2 = ??
        //h1 -= h2
        h1 = reverseFmix(h1);
        h1 -= 8;
        long k1 = h1 ^ 8;
        k1 *= c2inv;
        k1 = reverseRotl64(k1, 31);
        k1 *= c1inv;
        k1 = Long.reverseBytes(k1);
        return k1;
    }

    public static long hashInverse(long num) {
        //TODO Complete this function
        return 0;
    }

    public static void main(String[] args) {
        for (long hash = Long.MIN_VALUE; hash < Long.MAX_VALUE; hash++) {
            long num = hashInverse(hash);
            long actual = hash(num);
            if (hash != actual) {
                throw new RuntimeException("incorrect inverse " + num + " for " + hash + " got " + actual);
            }
        }
    }
}
What is hashinverse supposed to accomplish? You can’t really invert a hash function
BrianSantoso 3 months ago
@BrianSantoso cause its a non-crypto hash you can. See http://bitsquid.blogspot.com/2011/08/code-snippet-murmur-hash-inverse-pre.html . I think its better called a pre-image function. See testHash and testHashInverse to see example that is close to the hash function that is for the bounty. The objective is generate an input value that will generate that hash value that was put into it.
grom358 3 months ago
Ahh, gotcha!
BrianSantoso 3 months ago
Tags
java

Crowdsource coding tasks.

1 Solution


Unfortunately, I believe it's impossible to find the inverse of this particular hash function

We can rewrite the hash function such that each variable does not get reassigned (for the sake of simplicity):

public static long myHash(long num){

    long c1 = 0x87c37b91114253d5L;
    long c2 = 0x4cf5ad432745937fL;
    long k1 = Long.reverseBytes(num);
    long k2 = k1 * c1;
    long k3 = rotl64(k2, 31);
    long k4 = k3 * c2;

    long h1 = k4 ^ 8;
    long h2 = 8;

    long h_1 = h1 + h2;
    long h_2 = h2 + h_1;

    long h_3 = fmix(h_1);
    long h_4 = fmix(h_2);

    long h_5 = h_3 + h_4;
    return h_5;

}

Working backwards, we could try something like the following to find num, however we run into a problem.

public static long myHashInverse(long h_5){

    long c1 = 0x87c37b91114253d5L;
    long c2 = 0x4cf5ad432745937fL;
    long h2 = 8;


    // Cannot find h3
    long h_3 = h_5 - h_4;
    long h_4 = h_5 - h_3;


    long h_4 = h_5 - h_3;
    long h_2 = inv_fmix(h_4);
    long h_1 = h_2 - h2;


    long h1 = h_1 - h2;
    long k4 = h1 ^ 8;
    long k3 = k4 / c2;
    long k2 = inv_rotl64(k3, 31);
    long k1 = k2 / c1;
    long num = Long.reverseBytes(k1);


    return num;
}

We cannot find h_3 nor h_4 given only h_5 and the constants, as the last line operation of myHash takes the form of C = A + B and there simply is not enough information to derive A and B, given just C.