rulest_v3
Coverage Evaluation and Greedy Selection
These two post-processing steps were introduced and original single-file rulest_v2 engine was split into a proper modular package.
They solve a long-standing problem: frequency-sorted rulesets waste a large part of their budget on overlapping rules that crack almost the same passwords.
By first measuring the exact target coverage of every candidate and then selecting rules with a lazy greedy (CELF) algorithm, the final ruleset maximises unique recovery instead of raw hit count.
The result is higher real-world efficiency for any given size budget, produced in a single short run instead of multi-hour extraction and manual debugging cycles.
1. Coverage Evaluation
Instead of just counting how many times a rule hits something on the GPU (raw frequency), the system now checks exactly which real target passwords each rule can recover.
- It uses the fast GPU bloom filter as a first filter.
- Every possible hit is then double-checked with an exact verification step.
- The result is a clean map: for every rule → the list of unique target passwords it actually cracks.
This removes false positives and makes the data truthful. We no longer care about “how many hits”, we care about “which real passwords does this rule unlock”.
2. Greedy Selection (CELF - Cost-Effective Lazy Forward)
Once we know the exact coverage of every rule, we select the best subset of rules for a given budget (e.g. 10k, 25k, 50k rules).
The algorithm works like this:
- Start with an empty ruleset.
- Pick the rule that recovers the most new target passwords (the biggest marginal gain).
- Add it to the ruleset and mark those passwords as already covered.
- Repeat: always pick the rule that still gives the biggest new coverage given what we already have.
- Stop when we reach the desired number of rules or when no rule can add anything new.
This is called lazy greedy / CELF. It is much faster than a naive version and is designed for situations with hundreds of thousands of candidate rules.
In short: the rules become more diverse and more efficient. You get higher real recovery for the same size of ruleset, which is exactly what matters when you later run them in hashcat.
Benchmark comparison (same corpus)
Single-run results on base = hashmob.mini, target = hashmob.medium
(time-to-result comparison of obtaining similar rule counts: hcrt.pages.dev/debug_rules_efficiency
Full benchmark table: Google Sheet)
| Ruleset | Cover | Size | Eff. |
|---|---|---|---|
| rulest.greedy.150000.rule | 36.12% | 150000 | 0.2408 |
| rulest.freq.150000.rule | 28.02% | 150000 | 0.1868 |
| rulest.greedy.50000.rule | 29.78% | 50000 | 0.5956 |
| rulest.freq.50000.rule | 20.25% | 50000 | 0.4050 |
| rulest.greedy.25000.rule | 24.91% | 25000 | 0.9964 |
| rulest.freq.25000.rule | 15.99% | 25000 | 0.6396 |
| rulest.greedy.10000.rule | 19.71% | 10000 | 1.971 |
| rulest.freq.10000.rule | 11.44% | 10000 | 1.144 |
| rulest.greedy.1500.rule | 10.45% | 1500 | 6.9667 |
| rulest.freq.1500.rule | 4.61% | 1500 | 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 |
Takeaway
On the same base/target pair, pure frequency ranking consistently underperforms.
Greedy marginal-coverage selection recovers ~30–50 % more unique passwords at every budget size.
The gap is especially large on small rulesets (64–1.5k), where avoiding overlap matters most.
This almost two-hour(rulest+benchmarking) run on an RTX 3060 Ti matches the older, multi-hour rulest.r1/rulest.r2 sets (obtained via extraction and debugging) and most older, more extensive rulest sets.
150k well-chosen rules already provide ~81% coverage of what the 1.74M-rule strip_1p7m have.