openwall / openwall/john

Rules engine performance

Open
#3,468 17 comments 0 reactions 1 assignee View on GitHub

@magnumripper is already working on this.

Since Nov 22, 2018.

enhancement RFC / discussion
Dominant language
C
Stars
13.6k
Forks
2.6k
PR merge metrics
No merged PRs in 30d

Description

The rules engine is a bottleneck. Can we make it faster?

  • Profile with valgrind using NT format.
  • We have * for max_length (and related +/-). Could we benefit from having similar variables for min_length? I'm thinking rule rejection, for a start.
  • Try to improve dupe rejection, perhaps by "unifying" rules a little (unified rule would only be used internally to the dupe rejection stuff).
  • Note to self: The --rules:NT case-toggler (especially when used with max length less than 14) can be 50-60% faster if we add ->N and >N to it, eg.
-c T8QT[z0]T[z1]T[z2]T[z3]T[z4]T[z5]T[z6]T[z7]

could be

-c ->9 >8 T8QT[z0]T[z1]T[z2]T[z3]T[z4]T[z5]T[z6]T[z7]
  • Enhance the rules optimizer - and perhaps add a unifier step: If changing things like $1$2$3 to Az"123" we not only gain performance but also help the dupe-rule suppression.
  • Also the optimizer: Is it possible to sometimes do implicit rule rejection for rules that use TN, DN, xNM, iNX, oNX, XNMI and so on, when max-len is < N (or max-len < I for XNMI)? Would there be side effects? Theoretically we might change something beyond max length and then truncate the beginning of the word. We could however add a mnemonic that either enables or disables (depending on that we'd use as default) such optimizations per line. Or the optimizer (rejector) could possibly be clever enough to make some safe decisions.
  • ...add here

See also #3467

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.