pcfg_cracker: perform research into how humans generate passwords

by do son ·

generate passwords

pcfg_cracker

This project uses machine learning to identify password creation habits of users. A PCFG model is generated by training on a list of disclosed plaintext/cracked passwords. In the context of this project, the model is referred to as a ruleset and contains many different parts of the passwords identified during training, along with their associated probabilities. This stemming can be useful for other cracking tools such as PRINCE, and/or parts of the ruleset can be directly incorporated into more traditional dictionary-based attacks. This project also includes a PCFG guess generator that makes use of this ruleset to generate password guesses in probability order. This is much more powerful than standard dictionary attacks, and in testing has proven to be able to crack passwords on average with significantly fewer guesses than other publicly available methods. The downside is that generating guesses in probability order is slow, meaning it is creating on average 50-100k guesses a second, where GPU based algorithms can create millions to billions (and up), of guesses a second against fast hashing algorithms. Therefore, the PCFG guesser is best used against large numbers of salted hashes, or other slow hashing algorithms, where the performance cost of the algorithm is made up for with the accuracy of the guesses.

Training

The default ruleset included in this repo was created by training on a 1 million password subset of the RockYou dataset. Better performance can be achieved by training on the full 32 million passwords set for RockYou, but that was excluded to keep the download size small. You can use the default ruleset to start generating passwords without having to train on a new list, but it is recommended to train on a target set of passwords that may be closer to what you are trying to target. If you do create your own ruleset, here is a quick guide:

  1. Identify a set of plaintext passwords to train on.
  • This passwords set should include duplicate passwords. That way the trainer can identify common passwords like 123456 are common.
  • The passwords should be in plaintext with hashes and associated info like usernames removed from them. Don’t try to use raw .pot files as your training set as the hashes will be considered part of the password by the training program.
  • The passwords should be encoded the same way you want to generate password guesses as. So, if you want to create UTF-8 password guesses, the training set should also be encoded as UTF-8. Long term, the ability to modify this when generating guesses is on the development plan, but that feature is currently not supported.
  • The training password list should be between 100k and 50 million. Testing is still being done on how the size of the training password list affects guess generation, and there has been good success even with password lists as small as 10k, but an ideal size is likely around 1 million, with diminishing returns after that.
  • For the purposes of this tutorial the input password list will be referred to as INPUT_PASSWORD_LIST
  1. Choose a name for your generated ruleset. For the purposes of this tutorial it will be NEW_RULESET
  2. Run the trainer on the input password list
  • python3 -t INPUT_PASSWORD_LIST -r NEW_RULESET
  • Common optional flags: a. coverage: How much you trust the training set to match the target passwords. A higher coverage means to use less intelligent brute force generation using Markov modeling, (currently using the OMEN algorithm). If you set coverage to 1, no brute force will be performed. If you set coverage to 0, it will only generate guesses using Markov attacks. This value is a float, with the default being 0.6 which means it expects a 60% chance the target password’s base words can be found in the training set. Example: python3 -t INPUT_PASSWORD_LIST -r NEW_RULESET -c 0.6 b. –save_sensitive: If this is specified, sensitive data such as e-mail addresses and full websites which are discovered during training will be saved in the ruleset. While the PCFG guess generator does not currently make use of this data, it is very valuable during a real password cracking attack. This by default is off to make this tool easier to use in an academic setting. Note, even when this is off, there will almost certainly still be PII data saved inside a ruleset, so protect generated rulesets appropriately. Example: python3 -t INPUT_PASSWORD_LIST -r NEW_RULESET --save_sensitive c. –comments: Adds a comment to your ruleset config file. This is useful so you know why and how you generated your ruleset when looking back at it later. Include the comment you want to add in quotes.

Guess Generation

This generates guesses to stdout using a previously training PCFG ruleset. These guesses can then be piped into any program that you want to make use of them. If no ruleset is specified, the default ruleset DEFAULT will be used. For the purposes of this guide, it will assume the ruleset being used is NEW_RULESET.

  1. Note: the guess generation program is case sensitive when specifying the ruleset name.
  • A session name is not required, (it will by default create a session called default_run), but it is helpful to make restarting a paused/stopped session easier. These examples will use the session name SESSION_NAME. Note, there is no built in sanity check if you run multiple sessions with the same name at the same time, but it is recommended to avoid that.
  1. To start a new guessing session run:
  • python3 pcfg_guesser.py -r NEW_RULESET -s SESSION_NAME
  1. To restart a previous guessing session run:
  • python3 pcfg_guesser.py -s SESSION_NAME --load

Password Strength Scoring

There are many cases where you may want to estimate the probability of a password being generated by a previously trained ruleset. For example, this could be part of a password strength metric or used for other research purposes. A sample program has been included to perform this.

  • INPUT_LIST represents the list of passwords to score. These passwords should be plaintext, and separated by newlines, with one password per line.
  1. To run a scoring session: python3 password_scorer -r NEW_RULESET -i INPUT_LIST
  2. By default. it will output the results to stdout, with each password scored per line
  • The first value is the raw password
  • The second value will represent if the input value was scored a ‘password’, ‘website’, ‘e-mail address’, or ‘other’. This determination of password or other is dependent on the limits you set for both OMEN guess limit, as well as probability associated with the PCFG.
  • The third value is the probability of the password according to the Ruleset. If it is assigned a value of 0.0, that means that the password will not be generated by the ruleset, though it may be generated by a Markov based attack
  • The fourth value is the OMEN level that will generate the password. A value of -1 means the password will not be generated by OMEN.

Install