gocrack

CPU hash cracker in Go with hand-written 8-way AVX2 multi-buffer kernels for MD5 and SHA-1. Single binary, no dependencies, no GPU.

Hashes 8 candidates per instruction -- an AVX2 register is eight 32-bit lanes, one per candidate. Keeps the candidate generator inside the buffer it hashes, so advancing the search copies nothing. Compares against the target in registers, so a block that does not match writes no digest to memory at all.

go build -o gocrack ./cmd/gocrack

Both kernels run at 88-90% of the measured ceiling of this machine, so there is little left to win inside them. See "How much is left" below for how that was established, including which optimisations were tried and failed.

Commands

gocrack bench
gocrack brute    -H <hash> [-a auto|md5|sha1] [-c ?l?d?s] [-m 1] [-M 8] [-t 0] [-max-time 0]
gocrack wordlist -H <hash> [-a auto|md5|sha1] -w <file> [-t 0]
gocrack verify   -H <hash> [-a auto|md5|sha1] -p '<candidate>'

Supported algorithms: md5, sha1. Both cover candidates up to 55 bytes, i.e. anything that still fits a single padded block.

-a defaults to auto, which infers the algorithm from the width of the digest: 32 hex chars are 16 bytes (md5), 40 hex chars are 20 bytes (sha1). That is the whole of what a hash value can tell you. It is not a hash identifier -- md5, md4 and ntlm all produce 16 bytes, and sha1 and ripemd-160 both produce 20 -- so a 16-byte hash from an unknown source is still a guess until it cracks, and ntlm is the obvious thing to add next. An unsupported width is reported with the widths that are supported rather than guessed at.

-max-time bounds a brute-force run by wall clock; without it the search runs until the space is exhausted, which for a 62-symbol charset at length 8 is 2.2e14 candidates -- about 81 days on this machine. The progress line reports the live count, rate and ETA precisely so a hopeless request is obvious rather than looking like a hang.

Charset flags: ?l lower, ?u upper, ?d digits, ?s special, ?a all printable. Literal characters may be mixed in.

For authorised testing and recovery of credentials you own.

Measured throughput

Intel Core i5-7360U (Skylake, 2 physical cores, AVX2, no AVX-512, no SHA-NI), Go 1.26 darwin/amd64. MH/s all is a projection; the 4-thread figures below are measured end to end.

workload	1 core	4 threads
MD5 brute force, whole pipeline	38 MH/s	151 MH/s
MD5 wordlist, 8 at a time	30 MH/s	121 MH/s
md5x8 kernel alone	48 MH/s	-
crypto/md5 (stdlib)	5.7 MH/s	-
SHA-1 brute force, pipeline	22 MH/s	89 MH/s
SHA-1 wordlist, 8 at a time	20 MH/s	79 MH/s
sha1x8 compare path, kernel	22 MH/s	-
crypto/sha1 (stdlib)	4.1 MH/s	-

Measured scaling of the brute-force path: 31.9 MH/s on 1 thread, 59.6 on 2 (1.87x, close to the 2 physical cores), 76.6 on 4 including SMT.

The MD5 kernel is at the hardware limit, not a software limit: it uses 10 AVX2 integer ops per step, i.e. 5 cycles per step on two ALU ports, which is 20.8 ns/hash. Removing one of those operations entirely only buys 1.4% more, so there is nothing left to win in the kernel without changing the algorithm. For comparison, hashcat's GPU backend does ~60 GH/s for MD5; without CUDA there is no realistic GPU path here, so this is a CPU-mode tool.

SHA-1 lands at about 57% of MD5's rate, which is what the opcode counts predict: 80 rounds instead of 64, a six-opaque message schedule in 64 of those rounds, and a longer critical path.

How much is left

Both kernels are within about 10% of what this machine can actually do, and the way to see it is to measure the machine rather than the spec sheet. A loop of twelve independent 256-bit VPXORs, no dependency chain to slow it down, retires in 2.74 ns: 4.4 ALU ops per nanosecond. That is half of what three AVX2 ALU ports at 3 GHz would give, so a spec-sheet estimate would have pointed at a 2x gap that does not exist.

Against that ceiling:

kernel	ALU ops/block	ops/ns	share of ceiling
md5x8	640	3.8	88%
sha1x8	1404	3.9	90%

Deleting the pieces one at a time confirms where the time goes: the four register moves per round cost 1.2% (Skylake eliminates vector-to-vector moves at rename, so rotating the state registers instead would buy nothing), while the message schedule costs ~11-33%. The schedule is irreducible for SHA-1: W[i] = ROTL(W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16], 1) needs three XORs and, for the rotate, a shift plus a shift plus an OR. Storing the words pre-rotated does not help, because rotation is XOR-linear and the round's adder needs the unrotated value, so the rotate just moves rather than disappears.

The one structural change that did not pay off: unrolling all 80 rounds costs 12.2 KB of straight-line code, and 16 bytes/cycle of legacy decode would be 766 cycles against a ~510-cycle ALU bound, so the code looked fetch-bound. A 16-round loop over a 512-byte window cut the code to 6.4 KB and came out 45% slower (358 -> 521 ns/block), because the per-round phase dispatch costs more in branches than the decode saved. Code size was never the constraint.

Design

Message layout

The kernel works in the classic multi-buffer layout: 8 candidates are held side by side, one per 256-bit lane, so a single VMOVDQU at msg[w*32 + l*4] yields word w for all 8 candidates at once.

type Buffer [512]byte // word w of lane l at w*32 + l*4

internal/cand generates brute-force candidates directly into this layout, one 32-bit store per word per lane. There is no transposition pass in the kernel and no per-candidate allocation. internal/md5x8.BuildTransposed is the reference implementation of the layout, used for wordlists and tests.

MD5 round functions as bitwise identities

The kernel needs the four MD5 round functions on full 256-bit lanes, one dword per candidate. They are rewritten as pure bitwise identities so no byte-level shuffling is needed:

F(b,c,d) = d ^ (b & (c ^ d))
G(b,c,d) = c ^ (d & (b ^ c))     // (d&b)|(^d&c), matching Go's crypto/md5
H(b,c,d) = b ^ c ^ d
I(b,c,d) = c ^ ~(~b & d)         // c ^ (b | ~d)

I needs a real NOT, so Y15 holds all-ones for the whole kernel.

Each step is 11 instructions: 1 message load, 1 constant broadcast, 3 for the round function, 3 adds, 3 for the rotate, 1 accumulate.

STEP: a = b + ROTL(a + fn(b,c,d) + X[w] + T[k], s)

The result goes back into a, and the caller rotates the roles (a,b,c,d) -> (d,a,b,c), so no register is overwritten before it is read. With 16 steps per round the roles return to their starting point, which is why the register assignment can be static across all 64 steps:

Y0=A  Y4=D  Y5=B  Y9=C     Y6=msg  Y7=fn  Y8=acc  Y13,Y14=rotate  Y15=ones

Comparison happens in the kernel

md5x8msg takes the target digest pre-broadcast into 32 dwords and finishes with VPCMPEQD + VPMOVMSKB, returning a lane bitmask. A block that misses therefore costs no digest stores and no Go-side scan of 32 dwords — the Go driver only inspects the mask.

Candidate generation

The message buffer is the odometer. Each lane's plaintext bytes sit in the transposed block already holding the characters themselves, so a carry step is a byte read, a table lookup and a byte write — no digit array, no charset indirection, no repacking of unchanged words. A block covers counters Lanes apart, so every lane advances by Lanes; the carry is resolved through a precomputed (carry, character) table rather than a division, and it propagates from position plen-1 (least significant) downwards.

This took the generator from 28.3 ns/hash to 4.97 ns/hash, which mattered far more than any kernel work: the pipeline went from 15.6 to 36 MH/s.

Two bugs here were worth the tests they got:

• Fill advances the odometer in the same buffer the kernel then reads, so the driver must hash first and advance second. Filling first silently skipped the first 8 candidates of every range, and BlockStart was off by 8, so a found password could be reported as the wrong candidate. TestFirstBlockIsSearched and TestLastCandidateIsReachable pin this down.
• The plaintext byte offset is (i/4)*32 + lane*4 + (i%4), not i*8 + lane*4. The second looks right and is wrong for every i%4 != 0.

Wordlist path

WordBuilder applies the same idea: only plaintext bytes are ever written, and the 0x80 terminator, padding and bit length are a per-length template stamped once. All eight lanes of a block must share a length, because the bit length is a single field in the padded block; the wordlist command pads the unused lanes from one preallocated string. Rebuilding the eight full 64-byte blocks per line (the obvious implementation) costs more than the hashing.

Why the step looks the way it does

Two chains run through an MD5 step: one through a, and one through fn(b,c,d), which also depends on the previous step because b is a. Two optimisations were tried and both are wrong:

• Pre-rotating the round constant. Tempting, because it moves an add off the chain, but bit rotation is linear over XOR, not over addition with carries, so ROTL(u+v) != ROTL(u) + ROTL(v). Measured wrong digests, not wrong timings.
• Reassociating to (X + T + F) + a. This shortens the a path from three adds to one, but pushes the fn path from and,xor,add,shift,or,add (6) to and,xor,add,add,shift,or,add (7). It measured 12% slower (24.67 vs 21.65 ns/hash).

Both were caught by a same-process A/B harness that interleaves the variants and keeps the minimum, because this machine's clock drifts enough between runs to invert a 12% result. See TestStepFormComparison.

Go assembler traps hit while building this

These cost most of the debugging time and are worth writing down.

X0-X7 are the low 128 bits of Y0-Y7, not separate registers. MOVL $-1, R9; VMOVD R9, X4 silently zeroes the upper half of a live Y4. Any register used as a broadcast source must not be one whose Y counterpart holds state. Only Y1,Y2,Y3,Y10,Y11,Y12 are free here.

VPBROADCASTD with a redefined XMM source. Reusing the same Xn across several broadcasts, with Xn rewritten in between, mis-encodes: the first destination ends up holding a later constant. Give every broadcast its own source register.

VPANDN A, B, C assembles as C = ~B & A (not ~A & B). Reading the Intel intrinsic order backwards silently produces wrong digests in round 4 only, which is why the first three rounds still matched.

CMPL $imm, reg does not exist. Use ANDL + TESTL + Jcc instead.

VPBROADCASTD with a GPR source encodes as EVEX (AVX-512) and SIGILLs on AVX2-only hardware. Broadcast from memory or from an XMM register instead.

VINSERTI128 with four operands is rejected; VMOVDQU from a pre-broadcast table is simpler anyway.

VPSHUFB indexes into the whole 16-byte half, not into a dword. A mask of 0x00010203, which reads like a per-dword byte reverse, actually computes dst[4..7] = src[3..0], so all four lanes of a 128-bit half come out holding lane 0's value. The mask has to carry each dword's own offset: 3,2,1,0 / 7,6,5,4 / 11,10,9,8 / 15,14,13,12, repeated for the upper half. This one produced correct digests for lane 0 and for every all-zero input, which is exactly why it survived a quick eyeball test.

VPMOVMSKB is 128-bit only. Handed a YMM it reads just the low half, so lanes 4-7 can never be reported. Extract the upper half with VEXTRACTI128 $1, Y.., X.. and fold its 16 bits in above the lower half's.

An unrolled block silently drops its tail. A 16-slot INIT macro written with offsets 0,32,...,448 covers only 15 slots: the last message word, at offset 480, is never loaded, and the round code then reads whatever was on the stack. The only symptom is a wrong length field, so it looks like a padding bug rather than a truncated unroll.

SHA-1's schedule has no inner rotations. W[i] = ROTL(W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16], 1). Writing ROTL(...,15) and ROTL(...,7) into the first two terms is a natural mistake and gives a schedule that is wrong from round 16 on. Dropping them also makes the schedule six ops instead of twelve, which is worth about 8% of the kernel.

Verification

Every kernel is checked against crypto/md5:

• TestKernelMatchesStdlib — 400 random 8-candidate batches
• TestKernelBoundaryLengths — every length 0..55
• TestSingleStepAsm — one step, isolating the step macro
• TestMicroOps — F, shift and OR in isolation
• scalar_ref_test.go — an independent scalar reference, so a wrong round structure is distinguishable from a wrong encoding

TestStoreForwarding checks one thing that looked suspicious and turned out not to be: the kernel's 32-byte VMOVDQU load overlaps the generator's eight 4-byte stores. Measured penalty: 0.00 ns/hash. No padding or reordering needed.

The generator is checked separately in internal/cand:

• TestGeneratorCoversSpaceExactly — every candidate produced once, layout compared against an independent implementation
• TestGeneratorSplitCoversSpace — the parallel split loses and duplicates nothing
• TestOdometerMatchesArithmetic — odometer digits vs. the closed-form decomposition of the counter
• TestGeneratorHashesCorrectly — a generated candidate compresses to the same MD5 as the string itself
• TestFirstBlockIsSearched, TestLastCandidateIsReachable — block boundaries and the first/last candidate
• TestWordBuilderMatchesReference, TestWordBuilderLengthChange — the wordlist assembler against a from-scratch layout, across length changes

Not implemented yet

MD5 and SHA-1 are done. SHA-256 and NTLM/MD4 follow the same structure (the round tables and the STEP macro change; the layout and the compare-in-kernel tail are reusable) -- MD4/NTLM is the easy one, since it is MD5 with three rounds, one lane of constant data, little-endian length and an MD4 byte-reverse in the load. SHA-256 needs a 16-word schedule with three different round constants per round and its Sigma functions, so its kernel will cost roughly twice MD5's per block rather than 80/64 of it.

Candidates longer than 55 bytes need multi-block handling, which none of the kernels do yet; a message that long is rejected rather than silently truncated.

Keyed hashes (bcrypt/scrypt/PBKDF2) are out of scope for a multi-buffer design -- they have no compressible midstate.