How the rulest pipeline turns a huge pool of candidate rules into a small ruleset that actually maximizes distinct password recovery — instead of just summing individual rule scores — and why this consistently beats plain frequency ranking at every budget size.
Sorting candidate rules by raw GPU frequency and taking the top-N is the obvious first
approach, but it optimizes the wrong quantity. Two high-frequency rules can crack almost
the same subset of the target list — keeping both wastes budget that a lower-frequency,
but orthogonal, rule would have spent far better. What actually matters for a
ruleset of size k is not the sum of individual scores, but the size of the
union of everything those k rules recover.
That's a classic set-cover problem: each rule r defines a set
C(r) of the distinct target words it actually cracks, and the goal is to choose
a budget-sized collection of rules whose combined C(r) sets cover as much of
the target universe as possible. Set cover is NP-hard to solve exactly, but the coverage
function is submodular — each additional rule can only add as much or less
than it would have earlier, never more — which is exactly the property that makes a
simple greedy strategy provably close to optimal (within a factor of
1 − 1/e, roughly 63%, of the true best selection).
Every candidate rule is dispatched to the GPU against the full base wordlist using a
fast bloom-filter kernel. This cheaply flags which (rule, base_word)
pairs are probably a hit, without paying the cost of exact string
verification on the entire candidate pool up front.
Bloom filters admit false positives, and a set-cover objective is only meaningful if its universe is the thing actually being maximized. So every bloom-positive pair is re-run through an exact verification kernel, and only outputs that literally match a real target-wordlist entry are kept. This removes bloom false positives before they can distort the optimization.
Each verified hit is mapped to an integer ID in the deduplicated target-word universe, so a rule's coverage is "which distinct target words does this rule actually recover" — not "which base words happened to trigger a bloom hit." This is the same distinction that separates a meaningful cover objective from a proxy that can be gamed.
Each GPU batch's coverage rows are written straight to a coverage store and dropped
from memory immediately after — the full {rule: hits} matrix is never
assembled at once. Below a size threshold this store is a plain in-memory dict (zero
overhead); above it, it's disk-backed, so candidate pools that don't fit in RAM at all
remain usable instead of forcing a smaller run.
The textbook greedy algorithm repeatedly scans every remaining candidate, recomputes
its marginal gain against the current covered set, and picks the best one — then
repeats from scratch. That's O(rules × budget) evaluations, which is
fine at a few thousand candidates but becomes the bottleneck well before 100k, let
alone the 1.7M-candidate pools this pipeline routinely evaluates.
The Cost-Effective Lazy Forward selection algorithm exploits submodularity directly: since a rule's marginal gain can only shrink (never grow) as more of the target universe gets covered, a rule whose gain was already computed doesn't need to be rescanned — it only needs to be re-checked if it reaches the top of a priority queue. Each step pops the current best candidate off a heap, recomputes its gain against the up-to-date covered set, and either accepts it immediately (if it's still the best) or re-inserts it at its corrected priority and pops again.
The covered set is tracked as a single numpy boolean array over the target-word
universe, updated in place with fancy indexing, rather than as Python
set() unions. At 150k–1.7M candidates this avoids repeated hashing and
boxed-integer churn, keeping each marginal-gain check a cheap array operation instead
of an object-heavy one.
Selection continues until either the requested rule budget is reached, or no
remaining candidate adds any new coverage at all (saturation). An optional cost term
(gain / depth^α) can bias the search toward shorter, cheaper rule chains
among candidates with similar marginal gain — pure marginal-coverage greedy is the
α = 0 default.
After greedy selection, an optional local-search pass tries swapping each selected rule for a promising unselected one, accepting the swap only if it strictly increases total recovery. This nudges the result slightly past greedy's own local optimum at very low extra cost, since only a residual candidate pool — not the full candidate set — needs to be re-scored.
Frequency ranking asks "how many hits does this rule get on its own?" Greedy CELF asks
"how many new passwords does this rule recover that nothing already selected
recovers?" Those are different questions, and at every budget size the second one is the
one that actually determines how many unique passwords a ruleset of size k
will crack. The practical result is a ruleset that reaches a given coverage percentage with
dramatically fewer rules — or reaches a much higher coverage percentage at the same rule
count — than a frequency-sorted list ever can, because frequency ranking has no mechanism
to notice or penalize redundancy between rules.
Single-run results on base = hashmob.mini, target = hashmob.medium.
Each pair below holds ruleset size fixed and compares greedy CELF selection against plain
frequency ranking.
| Ruleset | Cover | Size | Efficiency |
|---|---|---|---|
| rulest.greedy.150000.rule | 36.12% | 150,000 | 0.2408 |
| rulest.freq.150000.rule | 28.02% | 150,000 | 0.1868 |
| rulest.greedy.50000.rule | 29.78% | 50,000 | 0.5956 |
| rulest.freq.50000.rule | 20.25% | 50,000 | 0.4050 |
| rulest.greedy.25000.rule | 24.91% | 25,000 | 0.9964 |
| rulest.freq.25000.rule | 15.99% | 25,000 | 0.6396 |
| rulest.greedy.10000.rule | 19.71% | 10,000 | 1.971 |
| rulest.freq.10000.rule | 11.44% | 10,000 | 1.144 |
| rulest.greedy.1500.rule | 10.45% | 1,500 | 6.9667 |
| rulest.freq.1500.rule | 4.61% | 1,500 | 3.0733 |
| rulest.greedy.250.rule | 5.06% | 250 | 20.24 |
| rulest.freq.250.rule | 1.73% | 250 | 6.92 |
| rulest.greedy.64.rule | 2.10% | 64 | 32.8125 |
| rulest.freq.64.rule | 0.88% | 64 | 13.75 |
Below the candidate-count threshold, coverage is kept in a plain dict — zero overhead. Above it, a SQLite-backed store takes over so pools far larger than available RAM stay usable; point lookups cost roughly one order of magnitude more, negligible next to the GPU-bound evaluation phase it follows.
A fixed budget stops selection at exactly k rules. Leaving it unset runs to
saturation — every rule that can still add coverage gets added, useful for finding the
practical ceiling of a candidate pool before picking a production budget.
Raising cost_alpha above 0 divides marginal gain by chain depth raised to
that power, nudging ties toward shorter, cheaper rules — useful when hashcat runtime per
candidate matters as much as raw coverage.
Raw GPU frequency is accepted as a tie-breaker input but has no effect on final ordering — the heap's own tuple comparison already decides ties deterministically by rule string, independent of any pre-sort.