Skip to content

Instantly share code, notes, and snippets.

@orlp

orlp/murmur3break.cpp Secret

Created May 22, 2023 22:21
Download ZIP

Revisions

  1. orlp created this gist May 22, 2023.
    117 changes: 117 additions & 0 deletions murmur3break.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,117 @@
    #include <cstdint>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>

    template<class T>
    T loadword(const void* p) {
    T r;
    std::memcpy(&r, p, sizeof(r));
    return r;
    }

    uint32_t rotl32(uint32_t x, int r) {
    return (x << r) | (x >> (32 - r));
    }

    uint32_t murmurhash3_x86_32(const char* s, int len, uint32_t seed) {
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    const uint32_t c3 = 0x85ebca6b;
    const uint32_t c4 = 0xc2b2ae35;

    uint32_t h = seed;
    for (const char* p = s; p != s + len; p += 4) {
    uint32_t k = loadword<uint32_t>(p);
    k *= c1;
    k = rotl32(k, 15);
    k *= c2;

    h ^= k;
    h = rotl32(h, 13);
    h = h * 5 + 0xe6546b64;
    }

    h ^= len;
    h ^= h >> 16;
    h *= c3;
    h ^= h >> 13;
    h *= c4;
    h ^= h >> 16;
    return h;
    }

    void murmurhash_x86_32_preimage32(uint32_t hash, char* s, uint32_t seed) {
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    const uint32_t c3 = 0x85ebca6b;
    const uint32_t c4 = 0xc2b2ae35;
    const uint32_t c1inv = 0xdee13bb1;
    const uint32_t c2inv = 0x56ed309b;
    const uint32_t c3inv = 0xa5cb9243;
    const uint32_t c4inv = 0x7ed1b41d;
    const uint32_t fiveinv = 0xcccccccd;

    // Invert target hash transformation.
    uint32_t h = hash;
    h ^= h >> 16;
    h *= c4inv;
    h ^= h >> 13;
    h ^= h >> 26;
    h *= c3inv;
    h ^= h >> 16;
    h ^= 32;

    // Compute the hash state for the first 24 bytes as normal.
    uint32_t state = seed;
    for (const char* p = s; p != s + 28; p += 4) {
    uint32_t k = loadword<uint32_t>(p);
    k *= c1;
    k = rotl32(k, 15);
    k *= c2;

    state ^= k;
    state = rotl32(state, 13);
    state = state * 5 + 0xe6546b64;
    }

    // Invert last iteration for last 4 bytes.
    h -= 0xe6546b64;
    h *= fiveinv;
    h = rotl32(h, 19);
    h ^= state;

    h *= c2inv;
    h = rotl32(h, 17);
    h *= c1inv;
    std::memcpy(s + 28, &h, 4);
    }


    int main(int argc, char** argv) {
    char input[33] = {0};
    std::strcpy(input, "orlp-murmurhash3_x86_32---------");

    for (uint64_t seed = 0; true; ++seed) {
    uint64_t s = seed;
    for (int i = 0; i < 4; ++i) {
    input[24 + i] = 'a' + (s % 26);
    s /= 26;
    }
    if (s > 0) break;

    murmurhash_x86_32_preimage32(1337, input, 0);

    bool all_printable = true;
    for (int i = 0; i < 4; ++i) {
    all_printable &= input[28 + i] >= 32;
    all_printable &= input[28 + i] <= 126;
    }

    if (all_printable) {
    std::cout << input << " " << murmurhash3_x86_32(input, 32, 0) << "\n";
    }
    }

    return 0;
    }