Racing the Hash

kernel1 took me way longer than I want to admit, and I got a lot of it wrong on the way — wrong pointer offsets, signed-vs-unsigned mismatches, the usual ways a decompiler dump lies to you if you're tired enough. Near the end of it sits one small, dumb, four-byte hash gate. It's the one part of this box I can actually show my work on without also showing you three hours of me being wrong about a struct layout. The fastest way through it turned out to have nothing to do with how fast anything could hash.

01The gate

Sitting alongside the kernel exploit is a tiny, unassuming checker binary. Compared to everything else in this box, it's almost polite: it reads four bytes from stdin, runs them through a hand-rolled hash, and compares the result against a constant baked into the binary at compile time.

unsigned long hash(char *input) {
    unsigned int hashval = 0;
    for (int i = 0; i < strlen(input); i++) {
        unsigned int tmp = (hashval + input[i]) * 0x401;
        hashval = tmp ^ (tmp >> 6) ^ input[i];
    }
    return hashval;
}

int main(void) {
    read(0, buffer, 4);
    if (hash(buffer) == 0x03319f75)
        puts("Flag");
    else
        puts("Not flag");
}

Four input bytes means a 32-bit search space: 4,294,967,296 candidates. Small enough to brute-force outright. After days of getting the actual kernel exploit wrong in increasingly humbling ways, a problem I could just throw compute at instead of thinking my way through felt like a vacation. So instead of picking whichever method got me the flag fastest and moving on, I made myself actually measure the three ways people reach for when a hash needs cracking.

02Three ways in

Brute force, in C

The obvious move, and the one I trust most precisely because there's so little to get wrong: try every 32-bit value, hash it the same way the checker does, stop when it matches.

for (uint64_t i = 0; i <= 0xffffffff; i++) {
    *(uint32_t*)buf = i;
    if (hash(buf) == 0x03319f75)
        printf("match: %08x\n", (uint32_t)i);
}

Two preimages turn up in the full 2³² space — expected for a birthday-ish spread of a 32-bit hash over 4 billion inputs. Sharding the same loop across the box's 4 threads brings it down further:

Brute force, in Python

Same algorithm, same search order, ported line for line:

def h(buf):
    r = 0
    for c in buf:
        tmp = (r + c) * 0x401 & 0xffffffff
        r = (tmp ^ (tmp >> 6) ^ c) & 0xffffffff
    return r

3,000,000 candidates — about 0.07% of the space — was enough to clock a stable rate. At ~228K hashes/sec, the full sweep would run somewhere north of five hours. I let it run just long enough to be sure of the number, then killed it. Life's too short, and so was my patience by that point in the box.

Symbolic execution, with angr

The third approach is the one I almost skipped, mostly out of stubbornness — I'd already gotten the hash "working" twice by then and didn't love the idea of a tool proving me wrong a third way. It doesn't touch the hash function at all. Instead of asking "what input produces this hash," it asks the binary directly: "what stdin makes you print Flag?"

project = angr.Project("./hash", load_options={'auto_load_libs': False})
flag = claripy.BVS('flag', 32)
state = project.factory.entry_state(stdin=flag)
simulation = project.factory.simgr(state)

simulation.explore(
    find=lambda s: b'Flag' in s.posix.dumps(1),
    avoid=lambda s: b'Not flag' in s.posix.dumps(1))

angr walks the actual instructions the binary executes, turns the byte-by-byte hash loop into a set of constraints over four symbolic bytes, and hands the whole thing to an SMT solver. It doesn't enumerate 4 billion candidates — it reasons about the one path that reaches puts("Flag") and asks Z3 for an input satisfying it. Eight seconds, and it agrees with the brute force.

03The race

† extrapolated from a measured 227,797 hashes/sec over a 3,000,000-candidate sample.

04What actually made the difference

Raw hash-rate explains most of the chart, and none of it is surprising if you've felt it before: C is roughly 150× faster than an interpreted Python loop doing the identical arithmetic, because every +, *, ^, and >> in CPython pays for bytecode dispatch, a dynamic type check, and a heap-allocated int object instead of costing one instruction on real silicon. Threading the C version buys another ~2× — less than the 4× the core count promises, because this hash is small and branchy enough that four threads spend some of their time contending rather than computing.

Why angr wins architecturally, not just numerically

angr isn't a faster hasher — it never hashes at all. Two things about ./hash conspire to make it the wrong problem to brute-force:

That's the actual mechanism, not just a speed difference: brute force is O(2ⁿ) enumeration with zero information reuse between tries. Symbolic execution only wins this decisively because ./hash has no data-dependent branching inside the hash loop itself — the only branch in the whole binary is the final comparison. angr never has to fork on the input, so all of the work lands on Z3, and Z3 treats simple arithmetic like this as a constraint-propagation problem rather than a guessing game. Give the checker real byte-by-byte branching instead of straight-line arithmetic, and angr would start forking on every one of those branches too — at which point the advantage shrinks, and can even reverse.

But the number that actually decided which method I'd reach for next time isn't in that table: it's zero, the number of hash-function bugs angr had to avoid, because it never had one to get right. Both of my brute forces shipped the same signed-char mistake independently, and I'd already gotten a pointer offset wrong once earlier in this exact box. angr doesn't reimplement anything — it reasons about the bytes the CPU actually runs, which is a nice way of saying it doesn't get tired at 2am and mistype a struct offset. For a hash this simple, brute force in C is still the pragmatic choice: fastest wall-clock, trivial to verify, and it enumerates every preimage instead of stopping at the first one a solver happens to find. But the moment the check is more convoluted, obfuscated, or simply not worth re-deriving by hand — and after this box, I'm inclined to assume I'll get it wrong at least once — the fastest path to an answer is the one that never asks you to be right about the algorithm in the first place.