Feature Request: Runtime Estimates

[galiagante]

It might be useful to include an estimate on how long a generate run will take (given the initial training data) and approximately how many passwords could be generated.

[lakiw]

Thanks for the interest in the tool and for the feature request!

The short reply is that given a non-trivial training set the PCFG cracker will never generate all of the possible guesses in a timeframe compatible with the heat death of the universe. Therefore providing a key-space estimate won't provide much value.

Longer answer. The main constraint for a PCFG based attack using the current version of the tool is that it starts out slow generating guesses and gets progressively slower as time goes on. At the same time, the memory resources it uses increase as the cracking session continues. This is because it is essentially doing a breadth first search of a custom parse tree. There's some back-end memory saving things in the pcfg code that I've done to limit this by reducing the size of the parse-tree which also reduces the size of the grammar, but that's unlikely to cause a cracking session to actually end due to key exhaustion.

One of the features I'd eventually like to add is to allow user tweaking of that back-end memory management. In that case having a run-time estimate like you requested would be very useful. Unfortunately, adding that feature is pretty low on my to-do list so I don't expect to get around to that anytime soon. Aka it's not a change that I could feel comfortable rolling out in a couple of days of development.

From an academic standpoint, it might be interesting to calculate the total keyspace during training. I might add something like this as part of the trainer re-write that I'm currently working on, but since maybe only one or two other people would be interested in this feature, it's also low on my to-do list. (Aka I'd like to get the new trainer working first).

Now turning your question around a bit, I do think it'd be interested to give better status updates on how many guesses are expected to be generated in a given period of time, along with the expected success rate. That would be really helpful to people wondering if they should continue a cracking session or kill it off and try other attacks.

I'll leave this feature request open for now as it'll provide a kick in the butt for me to look into these features, but I don't expect to make any progress on this for the foreseeable future. Thanks again for posting it, and using the tool. I hope it is helpful for you. Also for anyone reading this response, I accept pull requests if you want to look into it!

[galiagante]

Thanks for the speedy response!

Admittedly, I do not have quite enough spare time to wait for the universe to reach thermal equilibrium. As a stop-gap measure, I think I might implement some control by wrapping this script and watching output (e.g. terminate after so many passwords are generated) and/or resource utilization (e.g. terminate if memory consumption exceeds some threshold value).

If it's not too much of a kludge, I might post it via PR.

Thanks again for the awesome tool!

[lakiw]

Checking back in as I'm working on overhauling the back-end password guess generator right now. This is more a notes to myself and to give anyone else a chance to chime in.

One idea I was considering was keeping track of how much of the 'probability space' the cracker has currently covered. I know that's a horrible kludge of a term so I'm trying to think of something better. Basically though, consider it makes the following 4 guesses with associated probabilities:

Guesses/prob: 'pass':0.1 'monkey':0.05 'princess':0.03 'qwerty':0.02

Then the current probability coverage would be 0.1 + 0.05 + 0.03 + 0.02 = 0.2 or 20%

Now as a cracking session progresses, the speed that this probability coverage increases will drastically slow down. This is because it is making smaller and smaller probable guesses so each guess covers less of it. This 'probability coverage' will also not tell you how much longer the cracker will run, but it will give you an idea of how much progress and your likely chance of succeeding will be if you let it continue.

Downsides of this approach: 1) It can be really misleading since it's not a keyspace calculation 2) It can also be misleading since this is the probability if the target passwords match up exactly with the training set, which doesn't happen in real life. Based on tests so far the PCFG cracker will only crack around 80% of passwords even if you let it essentially run forever. 3) This adds computational overhead. It shouldn't add a lot of overhead, but the pcfg guesser is already slow.

I'd appreciate any ideas or comments!

[galiagante]

I have to admit, this is a tricky problem. I agree that it would be entirely too easy to provide misleading or non-useful information during a run, but I have no alternate ideas to offer at present. I will be giving this issue more thought. I hope I can find something useful to contribute.

In related news: I have stumbled across an attempt to recreate the pcfg_manager in Go, but it previously had some unresolved issues. See: https://github.com/Dasio/pcfg-manager . It's been updated recently, and I was going to give it another spin Sometime Very Soon (tm).

In terms of run-time limiting, I wrote a simple shell script that monitors a given run and halts it after a target number of password is reached. It lacks grace and refinement (not an elegant solution at all), but it's a start.

[lakiw]

Oh wow, thanks for sharing a link to the Go version. I wasn't aware of it before. That's really cool! As to the kill script, it'd be nice to be able to include a feedback loop from the actual password cracker and the pcfg guess generator. If I ever finish a C version that might be a possibility as Atom mentioned that this would be a good candidate for a slow guess generator in Hashcat.

[lakiw]

Below is an example of the current status report format. I'm open to ideas on how to improve this.

Status Report: Total Guesses (Approximate): 60981949 Number of Pre-Terminals (Rules) Processed: 2285954 Probability Coverage: 0.6669411624181398 Current Probabilty of Guesses: 7.533528623574639e-10 Current Pre-Terminal (Rule): [('A3', 17), ('C3', 2), ('Y1', 37)] Example Guess From Rule: Ana1973

Press [ENTER] to display an updated status output Press 'q' [ENTER] to exit

[galiagante]

So far, all I might suggest is that for persons who aren't well-acquainted with the terminology used in the status report sample, some additional explanation in the documentation would be prudent-- possibly throwing in some supporting theory, if you feel such a thing would be useful.

[lakiw]

Updated documentation is one of the hard requirements I put out for myself for the 4.0 release. I'm curious though, what level of documentation do you think would be helpful to include in the status reports themselves? I don't want to have a wall of text, but I also don't expect everyone to read the full readme.

[galiagante]

it is, indeed, a tricky balance to achieve. Good documentation is like oxygen, one never knows how much you need it unless it's missing....

In general, "experts" aren't going to need much supporting theory and "novices" won't understand it beyond a certain point. It's been my experience that focusing on only explaining terminology and elements that relates directly to the actual operations of a given feature is a good benchmark. Using no more than two or three sentences is expected, but less is (usually) more. If you can boil thing down to simple check-lists, one-liners, etc., so much the better.

Adding anything extra will likely be ignored by your target audience. Anyone wanting more depth or details can raise their hands and ask the teacher, if they wish.

[lakiw]

Ok, added a 'h' option to the status report that will print out a help screen to explain the status reports. That way it won't clutter it up for everyone, but someone can quickly get some explanations without having to dig up the documents.

`Status Report: Total Guesses (Approximate): 964,011 Number of Pre-Terminals (Rules) Processed: 107,035 Probability Coverage: 0.4652337401049547 Current Probability of Guesses: 5.9012063588716535e-08 Current Pre-Terminal (Rule): [('A4', 163), ('C4', 0), ('D2', 31)] Example Guess: rico33

Status Report Help

Fields: Total Guesses: Overview: Approximate number of guesses generated so far Misc: Not 100% accurate as this is updated periodically

Number of Pre-Terminals:
    Overview: Can be viewed as the number of rules that have
              have been processed so far
    Misc: Mostly for debugging. Do not expect to exhaust
          all the rules as there are likely billions+

Probability Coverage:
    Overview: Expected chance that a password would be
              guessed at this point
    Misc: This is a fuzzy metric since it assumes that the
          target password follows the same probability
          distribution as the training set and that the grammar
          is perfect.
          Narrator: "The grammar was not perfect"

          Can be useful to determine if this PCFG run is
          worth continuing or not.

          Much like Zeno's paradox, this percentage will increase
          slower and slower as a guessing session continues as
          each guess has a lower probability than the previous.

Current Probability of Guesses:
    Overview: According to the PCFG, the probability of the
              current guess being a password

Current Pre-Terminal:
    Overview: The current rule being processed
              -Rules are processed left to right
              -Pairs of rule type and index into the rule
              -Index starts at 0 with lower being more probable

    Rule Type Key:
          "M": OMEN (Ordered Markov ENumerator). Basically smart bruteforce
          "An": (A)lpha string (Letter) of length "n"
          "Cn": (C)apitalization mangling for length "n"
          "Dn": (D)igit string (number) of length "n"
          "Y1": (Y)ear, four digits, (eg. 2019)
          "Kn": (K)eyboard walk of length "n"
          "X1": Conte(x)t sensitive replacement, (eg. "<3")
          "On": (O)ther replacement. Special characters, (eg. !@#$)

Example Guess:
    Overview: This is the first guess that will be generated for
              the current rule.
    Misc: Will not display for OMEN guess generation

          An error message may display instead if the guess can
          not be printed to terminal due to character encoding issues.

Various OMEN Status Outputs:
    Overview: As a guessing session goes on, the keyspace for
              each Omen guess generation grows, so it is helpful
              to know how long it will be until other rule based
              guessing will resume.

              Other OMEN status outputs can be useful for debugging
              and research purposes.`

[lakiw]

With the release of v4.0 with the above features I'm going to close this issue for now. If there is a desire for more advanced runtime estimates feel free to re-open this or create a new issue.

[galiagante]

Many thanks!