text: #!/usr/bin/env python3
  # Rulegen.py - Advanced automated password rule and wordlist generator for the
  #              Hashcat password cracker using the Levenshtein Reverse Path
  #              algorithm and Enchant spell checking library.
  #
  # This tool is part of PACK (Password Analysis and Cracking Kit)
  #
  # VERSION 0.0.4
  #
  # Copyright (C) 2013 Peter Kacherginsky
  # All rights reserved.
  #
  # Please see the attached LICENSE file for additional licensing information.
  
  import re
  import sys
  import time
  
  import enchant
  import multiprocessing
  import subprocess
  
  from collections import Counter
  from optparse import OptionParser, OptionGroup
  from tqdm import tqdm
  
  
  VERSION = "0.0.5"
  
  # Testing rules with hashcat --stdout
  HASHCAT_PATH = "hashcat/"
  
  # Newline constant for use in f-strings
  NEWLINE = "\r\n"
  
  # Rule Generator class responsible for the complete cycle of rule generation
  
  
  class RuleGen:
      # Initialize Rule Generator class
      def __init__(
          self,
          language,
          providers="aspell,myspell",
          basename="analysis",
          threads=multiprocessing.cpu_count(),
      ):
  
          self.threads = threads
  
          self.enchant_broker = enchant.Broker()
          self.enchant_broker.set_ordering("*", providers)
  
          self.enchant = enchant.Dict(language, self.enchant_broker)
  
          # Output options
          self.basename = basename
  
          # Finetuning word generation
          self.max_word_dist = 10
          self.max_words = 10
          self.more_words = False
          self.simple_words = False
  
          # Finetuning rule generation
          self.max_rule_len = 10
          self.max_rules = 10
          self.more_rules = False
          self.simple_rules = False
          self.brute_rules = False
  
          # Debugging options
          self.verbose = False
          self.debug = False
          self.word = None  # Custom word to use.
          self.quiet = False
  
          #######################################################################
          # Word and Rule Statistics
          self.numeric_stats_total = 0
          self.special_stats_total = 0
          self.foreign_stats_total = 0
  
          #######################################################################
          # Preanalysis Password Patterns
          self.password_pattern = dict()
          self.password_pattern["insertion"] = re.compile(
              "^[^a-z]*(?P<password>.+?)[^a-z]*$", re.IGNORECASE
          )
          self.password_pattern["email"] = re.compile(
              r"^(?P<password>.+?)@[A-Z0-9.-]+\.[A-Z]{2,4}", re.IGNORECASE
          )
          self.password_pattern["alldigits"] = re.compile(r"^(\d+)$", re.IGNORECASE)
          self.password_pattern["allspecial"] = re.compile(
              "^([^a-z0-9]+)$", re.IGNORECASE
          )
  
          #######################################################################
          # Hashcat Rules Engine
          self.hashcat_rule = dict()
  
          ######################
          # Dummy rule         #
          ######################
  
          # Do nothing
          self.hashcat_rule[":"] = lambda x: x
  
          ######################
          # Case rules         #
          ######################
  
          # Lowercase all letters
          self.hashcat_rule["l"] = lambda x: x.lower()
          # Capitalize all letters
          self.hashcat_rule["u"] = lambda x: x.upper()
          # Capitalize the first letter
          self.hashcat_rule["c"] = lambda x: x.capitalize()
          # Lowercase the first found character, uppercase the rest
          self.hashcat_rule["C"] = lambda x: x[0].lower() + x[1:].upper()
          # Toggle the case of all characters in word
          self.hashcat_rule["t"] = lambda x: x.swapcase()
          # Toggle the case of characters at position N
          self.hashcat_rule["T"] = lambda x, y: x[:y] + x[y].swapcase() + x[y + 1 :]
          # Upper case the first letter and every letter after a space
          self.hashcat_rule["E"] = lambda x: " ".join(
              [i[0].upper() + i[1:] for i in x.split(" ")]
          )
  
          ######################
          # Rotation rules     #
          ######################
  
          # Reverse the entire word
          self.hashcat_rule["r"] = lambda x: x[::-1]
          # Rotate the word left
          self.hashcat_rule["{"] = lambda x: x[1:] + x[0]
          # Rotate the word right
          self.hashcat_rule["}"] = lambda x: x[-1] + x[:-1]
  
          ######################
          # Duplication rules  #
          ######################
  
          # Duplicate entire word
          self.hashcat_rule["d"] = lambda x: x + x
          # Duplicate entire word N times
          self.hashcat_rule["p"] = lambda x, y: x * y
          # Duplicate word reversed
          self.hashcat_rule["f"] = lambda x: x + x[::-1]
          # Duplicate first character N times
          self.hashcat_rule["z"] = lambda x, y: x[0] * y + x
          # Duplicate last character N times
          self.hashcat_rule["Z"] = lambda x, y: x + x[-1] * y
          # Duplicate every character
          self.hashcat_rule["q"] = lambda x: "".join([i + i for i in x])
          # Duplicate first N characters
          self.hashcat_rule["y"] = lambda x, y: x[:y] + x
          # Duplicate last N characters
          self.hashcat_rule["Y"] = lambda x, y: x + x[-y:]
  
          ######################
          # Cutting rules      #
          ######################
  
          # Delete first character
          self.hashcat_rule["["] = lambda x: x[1:]
          # Delete last character
          self.hashcat_rule["]"] = lambda x: x[:-1]
          # Deletes character at position N
          self.hashcat_rule["D"] = lambda x, y: x[:y] + x[y + 1 :]
          # Truncate word at position N
          self.hashcat_rule["'"] = lambda x, y: x[:y]
          # Delete M characters, starting at position N
          self.hashcat_rule["O"] = lambda x, y, z: x[:y] + x[y + z :]
          # Extracts M characters, starting at position N
          self.hashcat_rule["'"] = lambda x, y, z: x[y : y + z]
          # Purge all instances of X
          self.hashcat_rule["@"] = lambda x, y: x.replace(y, "")
  
          ######################
          # Insertion rules    #
          ######################
  
          # Append character to end
          self.hashcat_rule["$"] = lambda x, y: x + y
          # Prepend character to front
          self.hashcat_rule["^"] = lambda x, y: y + x
          # Insert character X at position N
          self.hashcat_rule["i"] = lambda x, y, z: x[:y] + z + x[y:]
  
          ######################
          # Replacement rules  #
          ######################
  
          # Overwrite character at position N with X
          self.hashcat_rule["o"] = lambda x, y, z: x[:y] + z + x[y + 1 :]
          # Replace all instances of X with Y
          self.hashcat_rule["s"] = lambda x, y, z: x.replace(y, z)
          # Bitwise shift left character @ N
          self.hashcat_rule["L"] = lambda x, y: x[:y] + chr(ord(x[y]) << 1) + x[y + 1 :]
          # Bitwise shift right character @ N
          self.hashcat_rule["R"] = lambda x, y: x[:y] + chr(ord(x[y]) >> 1) + x[y + 1 :]
          # Increment character @ N by 1 ascii value
          self.hashcat_rule["+"] = lambda x, y: x[:y] + chr(ord(x[y]) + 1) + x[y + 1 :]
          # Decrement character @ N by 1 ascii value
          self.hashcat_rule["-"] = lambda x, y: x[:y] + chr(ord(x[y]) - 1) + x[y + 1 :]
          # Replace character @ N with value at @ N plus 1
          self.hashcat_rule["."] = lambda x, y: x[:y] + x[y + 1] + x[y + 1 :]
          # Replace character @ N with value at @ N minus 1
          self.hashcat_rule[","] = lambda x, y: x[:y] + x[y - 1] + x[y + 1 :]
  
          ######################
          # Swapping rules     #
          ######################
  
          # Swap first two characters
          self.hashcat_rule["k"] = lambda x: x[1] + x[0] + x[2:]
          # Swap last two characters
          self.hashcat_rule["K"] = lambda x: x[:-2] + x[-1] + x[-2]
          # Swap character X with Y
          self.hashcat_rule["*"] = (
              lambda x, y, z: x[:y] + x[z] + x[y + 1 : z] + x[y] + x[z + 1 :]
              if z > y
              else x[:z] + x[y] + x[z + 1 : y] + x[z] + x[y + 1 :]
          )
  
          #######################################################################
          # Common numeric and special character substitutions (1337 5p34k)
          self.leet = dict()
          self.leet["1"] = "i"
          self.leet["2"] = "z"
          self.leet["3"] = "e"
          self.leet["4"] = "a"
          self.leet["5"] = "s"
          self.leet["6"] = "b"
          self.leet["7"] = "t"
          self.leet["8"] = "b"
          self.leet["9"] = "g"
          self.leet["0"] = "o"
          self.leet["!"] = "i"
          self.leet["|"] = "i"
          self.leet["@"] = "a"
          self.leet["$"] = "s"
          self.leet["+"] = "t"
  
          #######################################################################
          # Preanalysis rules to bruteforce for each word
          self.preanalysis_rules = []
          self.preanalysis_rules.append(([], self.hashcat_rule[":"]))  # Blank rule
          self.preanalysis_rules.append((["r"], self.hashcat_rule["r"]))  # Reverse rule
          # self.preanalysis_rules.append((['{'],self.hashcat_rule['}'])) # Rotate left
          # self.preanalysis_rules.append((['}'],self.hashcat_rule['{'])) #
          # Rotate right
  
      ##########################################################################
      # Calculate Levenshtein edit path matrix
      @staticmethod
      def levenshtein(word, password):
          matrix = []
  
          # Generate and populate the initial matrix
          for i in range(len(password) + 1):
              matrix.append([])
              for j in range(len(word) + 1):
                  if i == 0:
                      matrix[i].append(j)
                  elif j == 0:
                      matrix[i].append(i)
                  else:
                      matrix[i].append(0)
  
          # Calculate edit distance for each substring
          for i in range(1, len(password) + 1):
              for j in range(1, len(word) + 1):
                  if password[i - 1] == word[j - 1]:
                      matrix[i][j] = matrix[i - 1][j - 1]
                  else:
                      insertion = matrix[i - 1][j] + 1
                      deletion = matrix[i][j - 1] + 1
                      substitution = matrix[i - 1][j - 1] + 1
                      matrix[i][j] = min(insertion, deletion, substitution)
  
          return matrix
  
      def levenshtein_distance(self, s1, s2):
          """Calculate the Levenshtein distance between two strings.
  
          This is straight from Wikipedia.
          """
          if len(s1) < len(s2):
              return self.levenshtein_distance(s2, s1)
          if not s1:
              return len(s2)
  
          previous_row = range(len(s2) + 1)
          for i, c1 in enumerate(s1):
              current_row = [i + 1]
              for j, c2 in enumerate(s2):
                  insertions = previous_row[j + 1] + 1
                  deletions = current_row[j] + 1
                  substitutions = previous_row[j] + (c1 != c2)
                  current_row.append(min(insertions, deletions, substitutions))
              previous_row = current_row
  
          return previous_row[-1]
  
      @staticmethod
      def levenshtein_print(matrix, word, password):
          """ Print word X password matrix """
          print(f"      {'  '.join(list(word))}")
          for i, row in enumerate(matrix):
              if i == 0:
                  print(" ", end=" ")
              else:
                  print(password[i - 1], end=" ")
              print(" ".join(f"{col for col in row}"))
  
      def generate_levenshtein_rules(self, word, password):
          """ Generates levenshtein rules. Returns a list of lists of levenshtein rules. """
  
          # 1) Generate Levenshtein matrix
          matrix = self.levenshtein(word, password)
  
          # 2) Trace reverse paths through the matrix.
          paths = self.levenshtein_reverse_recursive(
              matrix, len(matrix) - 1, len(matrix[0]) - 1, 0
          )
  
          # 3) Return a collection of reverse paths.
          return [path for path in paths if len(path) <= matrix[-1][-1]]
  
      def levenshtein_reverse_recursive(self, matrix, i, j, path_len):
          """Calculate reverse Levenshtein paths.
          Recursive, Depth First, Short-circuited algorithm by Peter Kacherginsky
          Generates a list of edit operations necessary to transform a source word
          into a password. Edit operations are recorded in the form:
          (operation, password_offset, word_offset)
          Where an operation can be either insertion, deletion or replacement.
          """
  
          if i == 0 and j == 0 or path_len > matrix[-1][-1]:
              return [[]]
          else:
              paths = list()
  
              cost = matrix[i][j]
  
              # Calculate minimum cost of each operation
              cost_delete = cost_insert = cost_equal_or_replace = sys.maxsize
              if i > 0:
                  cost_insert = matrix[i - 1][j]
              if j > 0:
                  cost_delete = matrix[i][j - 1]
              if i > 0 and j > 0:
                  cost_equal_or_replace = matrix[i - 1][j - 1]
              cost_min = min(cost_delete, cost_insert, cost_equal_or_replace)
  
              # Recurse through reverse path for each operation
              if cost_insert == cost_min:
                  insert_paths = self.levenshtein_reverse_recursive(
                      matrix, i - 1, j, path_len + 1
                  )
                  for insert_path in insert_paths:
                      paths.append(insert_path + [("insert", i - 1, j)])
  
              if cost_delete == cost_min:
                  delete_paths = self.levenshtein_reverse_recursive(
                      matrix, i, j - 1, path_len + 1
                  )
                  for delete_path in delete_paths:
                      paths.append(delete_path + [("delete", i, j - 1)])
  
              if cost_equal_or_replace == cost_min:
                  if cost_equal_or_replace == cost:
                      equal_paths = self.levenshtein_reverse_recursive(
                          matrix, i - 1, j - 1, path_len
                      )
                      for equal_path in equal_paths:
                          paths.append(equal_path)
                  else:
                      replace_paths = self.levenshtein_reverse_recursive(
                          matrix, i - 1, j - 1, path_len + 1
                      )
                      for replace_path in replace_paths:
                          paths.append(replace_path + [("replace", i - 1, j - 1)])
  
              return paths
  
      def load_custom_wordlist(self, wordlist_file):
          self.enchant = enchant.request_pwl_dict(wordlist_file)
  
      def generate_words(self, password):
          """ Generate source word candidates."""
  
          if self.debug:
              print(f"[*] Generating source words for {password}")
  
          words = list()
          words_collection = list()
  
          # Let's collect best edit distance as soon as possible to prevent
          # less efficient pre_rules like reversal and rotation from slowing
          # us down with garbage
          best_found_distance = 9999
  
          #######################################################################
          # Generate words for each preanalysis rule
          if not self.brute_rules:
              self.preanalysis_rules = self.preanalysis_rules[:1]
  
          for pre_rule, pre_rule_lambda in self.preanalysis_rules:
  
              pre_password = pre_rule_lambda(password)
  
              # Generate word suggestions
              if self.word:
                  suggestions = [self.word]
              elif self.simple_words:
                  suggestions = self.generate_simple_words(pre_password)
              else:
                  suggestions = self.generate_advanced_words(pre_password)
  
              # HACK: Perform some additional expansion on multi-word suggestions
              # TODO: May be I should split these two and see if I can generate
              # rules for each of the suggestions
              for suggestion in suggestions[: self.max_words]:
                  suggestion = suggestion.replace(" ", "")
                  suggestion = suggestion.replace("-", "")
                  if suggestion not in suggestions:
                      suggestions.append(suggestion)
  
              if len(suggestions) != len(set(suggestions)):
                  print(sorted(suggestions))
                  print(sorted(set(suggestions)))
  
              for suggestion in suggestions:
                  distance = self.levenshtein_distance(suggestion, pre_password)
  
                  word = dict()
                  word["suggestion"] = suggestion
                  word["distance"] = distance
                  word["password"] = pre_password
                  word["pre_rule"] = pre_rule
                  word["best_rule_length"] = 9999
  
                  words.append(word)
  
          #######################################################################
          # Perform Optimization
          for word in sorted(words, key=lambda w: w["distance"], reverse=False):
  
              # Optimize for best distance
              if not self.more_words:
                  if word["distance"] < best_found_distance:
                      best_found_distance = word["distance"]
  
                  elif word["distance"] > best_found_distance:
                      if self.verbose:
                          print(
                              f"[-] {word['suggestion']} => {{edit distance suboptimal: "
                              f"{word['distance']} ({best_found_distance})}} => {word['password']}"
                          )
                      break
  
                      # Filter words with too big edit distance
              if word["distance"] <= self.max_word_dist:
                  if self.debug:
                      print(
                          f"[+] {word['suggestion']} => {{edit distance: "
                          f"{word['distance']} ({best_found_distance})}} = > {word['password']}"
                      )
  
                  words_collection.append(word)
  
              else:
                  if self.verbose:
                      print(
                          f"[-] {word['suggestion']} => {{max distance exceeded: "
                          "{word['distance']} ({self.max_word_dist})}} => {word['password']}"
                      )
  
          if self.max_words:
              words_collection = words_collection[: self.max_words]
  
          return words_collection
  
      def generate_simple_words(self, password):
          """ Generate simple words. A simple spellcheck."""
  
          return self.enchant.suggest(password)
  
      def generate_advanced_words(self, password):
          """Generate advanced words.
          Perform some additional non-destructive cleaning to help spell-checkers:
          1) Remove non-alpha prefixes and appendixes.
          2) Perform common pattern matches (e.g. email).
          3) Replace non-alpha character substitutions (1337 5p34k)
          """
  
          # Remove non-alpha prefix and/or appendix
          insertion_matches = self.password_pattern["insertion"].match(password)
          if insertion_matches:
              password = insertion_matches.group("password")
  
          # Pattern matches
          email_matches = self.password_pattern["email"].match(password)
          if email_matches:
              password = email_matches.group("password")
  
          # Replace common special character replacements (1337 5p34k)
          preanalysis_password = ""
          for c in password:
              if c in self.leet:
                  preanalysis_password += self.leet[c]
              else:
                  preanalysis_password += c
          password = preanalysis_password
  
          if self.debug:
              f"[*] Preanalysis Password: {password}"
  
          return self.enchant.suggest(password)
  
      ##########################################################################
      # Hashcat specific offset definition 0-9,A-Z
      @staticmethod
      def int_to_hashcat(n):
          if n < 10:
              return n
          else:
              return chr(65 + n - 10)
  
      @staticmethod
      def hashcat_to_int(n):
          if n.isdigit():
              return int(n)
          else:
              return ord(n) - 65 + 10
  
      def generate_hashcat_rules(self, suggestion, password):
          """ Generate hashcat rules. Returns a length sorted list of lists of hashcat rules."""
  
          # 2) Generate Levenshtein Rules
          lev_rules = self.generate_levenshtein_rules(suggestion, password)
  
          # 3) Generate Hashcat Rules
          hashcat_rules = []
          hashcat_rules_collection = []
  
          #######################################################################
          # Generate hashcat rule for each levenshtein rule
          for lev_rule in lev_rules:
  
              if self.simple_rules:
                  hashcat_rule = self.generate_simple_hashcat_rules(
                      suggestion, lev_rule, password
                  )
              else:
                  hashcat_rule = self.generate_advanced_hashcat_rules(
                      suggestion, lev_rule, password
                  )
  
              if hashcat_rule is None:
                  print(f"[!] Processing FAILED: {suggestion} => ;( => {password}")
                  print("    Sorry about that, please report this failure to")
                  print("    the developer: iphelix [at] thesprawl.org")
  
              else:
                  hashcat_rules.append(hashcat_rule)
  
          best_found_rule_length = 9999
  
          #######################################################################
          # Perform Optimization
          for hashcat_rule in sorted(hashcat_rules, key=lambda rule: len(rule)):
  
              rule_length = len(hashcat_rule)
  
              if not self.more_rules:
                  if rule_length < best_found_rule_length:
                      best_found_rule_length = rule_length
  
                  elif rule_length > best_found_rule_length:
                      if self.verbose:
                          print(
                              f"[-] {suggestion} => {{best rule length exceeded: "
                              f"{rule_length} ({best_found_rule_length})}} => {password}"
                          )
                      break
  
              if rule_length <= self.max_rule_len:
                  hashcat_rules_collection.append(hashcat_rule)
  
          return hashcat_rules_collection
  
      def generate_simple_hashcat_rules(self, word, rules, password):
          """ Generate basic hashcat rules using only basic insert,delete,replace rules. """
          hashcat_rules = []
  
          if self.debug:
              print(f"[*] Simple Processing {word} => {password}")
  
          # Dynamically apply rules to the source word
          # NOTE: Special case were word == password this would work as well.
          word_rules = word
  
          for (op, p, _w) in rules:
  
              if self.debug:
                  print(
                      f"\t[*] Simple Processing Started: "
                      f"{word_rules} - {' '.join(hashcat_rules)}"
                  )
  
              if op == "insert":
                  hashcat_rules.append(f"i{self.int_to_hashcat(p)}{password[p]}")
                  word_rules = self.hashcat_rule["i"](word_rules, p, password[p])
  
              elif op == "delete":
                  hashcat_rules.append(f"D{self.int_to_hashcat(p)}")
                  word_rules = self.hashcat_rule["D"](word_rules, p)
  
              elif op == "replace":
                  hashcat_rules.append(f"o{self.int_to_hashcat(p)}{password[p]}")
                  word_rules = self.hashcat_rule["o"](word_rules, p, password[p])
  
          if self.debug:
              print(
                  f"\t[*] Simple Processing Ended: "
                  f"{word_rules} => {' '.join(hashcat_rules)} => {password}"
              )
  
          # Check if rules result in the correct password
          if word_rules == password:
              return hashcat_rules
          else:
              if self.debug:
                  print(
                      f"[!] Simple Processing FAILED: "
                      f"{word} => {' '.join(hashcat_rules)} => {password} ({word_rules})"
                  )
              return None
  
      def generate_advanced_hashcat_rules(self, word, rules, password):
          """ Generate advanced hashcat rules using full range of available rules. """
          hashcat_rules = []
  
          if self.debug:
              print(f"[*] Advanced Processing {word} => {password}")
  
          # Dynamically apply and store rules in word_rules variable.
          # NOTE: Special case where word == password this would work as well.
          word_rules = word
  
          # Generate case statistics
          password_lower = len([c for c in password if c.islower()])
          password_upper = len([c for c in password if c.isupper()])
  
          for i, (op, p, w) in enumerate(rules):
  
              if self.debug:
                  print(
                      f"\t[*] Advanced Processing Started: "
                      f"{word_rules} - {' '.join(hashcat_rules)}"
                  )
  
              if op == "insert":
                  hashcat_rules.append(f"i{self.int_to_hashcat(p)}{password[p]}")
                  word_rules = self.hashcat_rule["i"](word_rules, p, password[p])
  
              elif op == "delete":
                  hashcat_rules.append(f"D{self.int_to_hashcat(p)}")
                  word_rules = self.hashcat_rule["D"](word_rules, p)
  
              elif op == "replace":
  
                  # Detecting global replacement such as sXY, l, u, C, c is a non
                  # trivial problem because different characters may be added or
                  # removed from the word by other rules. A reliable way to solve
                  # this problem is to apply all of the rules the source word
                  # and keep track of its state at any given time. At the same
                  # time, global replacement rules can be tested by completing
                  # the rest of the rules using a simplified engine.
  
                  # The sequence of if statements determines the priority of
                  # rules
  
                  # This rule was made obsolete by a prior global replacement
                  if word_rules[p] == password[p]:
                      if self.debug:
                          print(
                              f"\t[*] Advanced Processing Obsolete Rule: "
                              f"{word_rules} - {' '.join(hashcat_rules)}"
                          )
  
                  # Swapping rules
                  elif (
                      p < len(password) - 1
                      and p < len(word_rules) - 1
                      and word_rules[p] == password[p + 1]
                      and word_rules[p + 1] == password[p]
                  ):
                      # Swap first two characters
                      if p == 0 and self.generate_simple_hashcat_rules(
                          self.hashcat_rule["k"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("k")
                          word_rules = self.hashcat_rule["k"](word_rules)
                      # Swap last two characters
                      elif p == len(
                          word_rules
                      ) - 2 and self.generate_simple_hashcat_rules(
                          self.hashcat_rule["K"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("K")
                          word_rules = self.hashcat_rule["K"](word_rules)
                      # Swap any two characters (only adjacent swapping is
                      # supported)
                      elif self.generate_simple_hashcat_rules(
                          self.hashcat_rule["*"](word_rules, p, p + 1),
                          rules[i + 1 :],
                          password,
                      ):
                          hashcat_rules.append(
                              f"*{self.int_to_hashcat(p)}{self.int_to_hashcat(p + 1)}"
                          )
                          word_rules = self.hashcat_rule["*"](word_rules, p, p + 1)
                      else:
                          hashcat_rules.append(f"o{self.int_to_hashcat(p)}{password[p]}")
                          word_rules = self.hashcat_rule["o"](word_rules, p, password[p])
  
                  # Case Toggle: Uppercased a letter
                  elif word_rules[p].islower() and word_rules[p].upper() == password[p]:
  
                      # Toggle the case of all characters in word (mixed cases)
                      if (
                          password_upper
                          and password_lower
                          and self.generate_simple_hashcat_rules(
                              self.hashcat_rule["t"](word_rules), rules[i + 1 :], password
                          )
                      ):
                          hashcat_rules.append("t")
                          word_rules = self.hashcat_rule["t"](word_rules)
  
                      # Capitalize all letters
                      elif self.generate_simple_hashcat_rules(
                          self.hashcat_rule["u"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("u")
                          word_rules = self.hashcat_rule["u"](word_rules)
  
                      # Capitalize the first letter
                      elif p == 0 and self.generate_simple_hashcat_rules(
                          self.hashcat_rule["c"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("c")
                          word_rules = self.hashcat_rule["c"](word_rules)
  
                      # Toggle the case of characters at position N
                      else:
                          hashcat_rules.append(f"T{self.int_to_hashcat(p)}")
                          word_rules = self.hashcat_rule["T"](word_rules, p)
  
                  # Case Toggle: Lowercased a letter
                  elif word_rules[p].isupper() and word_rules[p].lower() == password[p]:
  
                      # Toggle the case of all characters in word (mixed cases)
                      if (
                          password_upper
                          and password_lower
                          and self.generate_simple_hashcat_rules(
                              self.hashcat_rule["t"](word_rules), rules[i + 1 :], password
                          )
                      ):
                          hashcat_rules.append("t")
                          word_rules = self.hashcat_rule["t"](word_rules)
  
                      # Lowercase all letters
                      elif self.generate_simple_hashcat_rules(
                          self.hashcat_rule["l"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("l")
                          word_rules = self.hashcat_rule["l"](word_rules)
  
                      # Lowercase the first found character, uppercase the rest
                      elif p == 0 and self.generate_simple_hashcat_rules(
                          self.hashcat_rule["C"](word_rules), rules[i + 1 :], password
                      ):
                          hashcat_rules.append("C")
                          word_rules = self.hashcat_rule["C"](word_rules)
  
                      # Toggle the case of characters at position N
                      else:
                          hashcat_rules.append(f"T{self.int_to_hashcat(p)}")
                          word_rules = self.hashcat_rule["T"](word_rules, p)
  
                  # Special case substitution of 'all' instances (1337 $p34k)
                  elif (
                      word_rules[p].isalpha()
                      and not password[p].isalpha()
                      and self.generate_simple_hashcat_rules(
                          self.hashcat_rule["s"](word_rules, word_rules[p], password[p]),
                          rules[i + 1 :],
                          password,
                      )
                  ):
  
                      # If we have already detected this rule, then skip it thus
                      # reducing total rule count.
                      # BUG: Elisabeth => sE3 sl1 u o3Z sE3 => 31IZAB3TH
                      # if not "s%s%s" % (word_rules[p],password[p]) in
                      # hashcat_rules:
                      hashcat_rules.append(f"s{word_rules[p]}{password[p]}")
                      word_rules = self.hashcat_rule["s"](
                          word_rules, word_rules[p], password[p]
                      )
  
                  # Replace next character with current
                  elif (
                      p < len(password) - 1
                      and p < len(word_rules) - 1
                      and password[p] == password[p + 1]
                      and password[p] == word_rules[p + 1]
                  ):
                      hashcat_rules.append(f".{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule["."](word_rules, p)
  
                  # Replace previous character with current
                  elif (
                      p > 0
                      and w > 0
                      and password[p] == password[p - 1]
                      and password[p] == word_rules[p - 1]
                  ):
                      hashcat_rules.append(f",{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule[","](word_rules, p)
  
                  # ASCII increment
                  elif ord(word_rules[p]) + 1 == ord(password[p]):
                      hashcat_rules.append(f"+{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule["+"](word_rules, p)
  
                  # ASCII decrement
                  elif ord(word_rules[p]) - 1 == ord(password[p]):
                      hashcat_rules.append(f"-{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule["-"](word_rules, p)
  
                  # SHIFT left
                  elif ord(word_rules[p]) << 1 == ord(password[p]):
                      hashcat_rules.append(f"L{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule["L"](word_rules, p)
  
                  # SHIFT right
                  elif ord(word_rules[p]) >> 1 == ord(password[p]):
                      hashcat_rules.append(f"R{self.int_to_hashcat(p)}")
                      word_rules = self.hashcat_rule["R"](word_rules, p)
  
                      # Position based replacements.
                  else:
                      hashcat_rules.append(f"o{self.int_to_hashcat(p)}{password[p]}")
                      word_rules = self.hashcat_rule["o"](word_rules, p, password[p])
  
          if self.debug:
              print(
                  f"\t[*] Advanced Processing Ended: "
                  f"{word_rules} {' '.join(hashcat_rules)}"
              )
  
          #######################################################################
          # Prefix rules
          last_prefix = 0
          prefix_rules = list()
          for hashcat_rule in hashcat_rules:
              if (
                  hashcat_rule[0] == "i"
                  and self.hashcat_to_int(hashcat_rule[1]) == last_prefix
              ):
                  prefix_rules.append(f"^{hashcat_rule[2]}")
                  last_prefix += 1
              elif len(prefix_rules):
                  hashcat_rules = prefix_rules[::-1] + hashcat_rules[len(prefix_rules) :]
                  break
              else:
                  break
          else:
              hashcat_rules = prefix_rules[::-1] + hashcat_rules[len(prefix_rules) :]
  
          ####################################################################
          # Appendix rules
          last_appendix = len(password) - 1
          appendix_rules = list()
          for hashcat_rule in hashcat_rules[::-1]:
              if (
                  hashcat_rule[0] == "i"
                  and self.hashcat_to_int(hashcat_rule[1]) == last_appendix
              ):
                  appendix_rules.append(f"${hashcat_rule[2]}")
                  last_appendix -= 1
              elif len(appendix_rules):
                  hashcat_rules = (
                      hashcat_rules[: -len(appendix_rules)] + appendix_rules[::-1]
                  )
                  break
              else:
                  break
          else:
              hashcat_rules = hashcat_rules[: -len(appendix_rules)] + appendix_rules[::-1]
  
          ####################################################################
          # Truncate left rules
          last_precut = 0
          precut_rules = list()
          for hashcat_rule in hashcat_rules:
              if (
                  hashcat_rule[0] == "D"
                  and self.hashcat_to_int(hashcat_rule[1]) == last_precut
              ):
                  precut_rules.append("[")
              elif len(precut_rules):
                  hashcat_rules = precut_rules[::-1] + hashcat_rules[len(precut_rules) :]
                  break
              else:
                  break
          else:
              hashcat_rules = precut_rules[::-1] + hashcat_rules[len(precut_rules) :]
  
          ####################################################################
          # Truncate right rules
          last_postcut = len(password)
          postcut_rules = list()
          for hashcat_rule in hashcat_rules[::-1]:
  
              if (
                  hashcat_rule[0] == "D"
                  and self.hashcat_to_int(hashcat_rule[1]) >= last_postcut
              ):
                  postcut_rules.append("]")
              elif len(postcut_rules):
                  hashcat_rules = (
                      hashcat_rules[: -len(postcut_rules)] + postcut_rules[::-1]
                  )
                  break
              else:
                  break
          else:
              hashcat_rules = hashcat_rules[: -len(postcut_rules)] + postcut_rules[::-1]
  
          # Check if rules result in the correct password
          if word_rules == password:
              return hashcat_rules
          else:
              if self.debug:
                  print(
                      f"[!] Advanced Processing FAILED: "
                      f"{word} => {' '.join(hashcat_rules)} => {password} ({word_rules})"
                  )
              return None
  
      def check_reversible_password(self, password):
          """ Check whether the password is likely to be reversed successfuly. """
  
          # Skip all numeric passwords
          if password.isdigit():
              if self.verbose and not self.quiet:
                  print(f"[!] {password} => {{skipping numeric}} => {password}")
              self.numeric_stats_total += 1
              return False
  
          # Skip passwords with less than 25% of alpha character
          # TODO: Make random word detection more reliable based on word entropy.
          elif len([c for c in password if c.isalpha()]) < len(password) // 4:
              if self.verbose and not self.quiet:
                  print(
                      f"[!] {password} => {{skipping alpha less than 25%}} => {password}"
                  )
              self.special_stats_total += 1
              return False
  
          # Only check english ascii passwords for now
          # TODO: Add support for more languages.
          elif [c for c in password if ord(c) < 32 or ord(c) > 126]:
              if self.verbose and not self.quiet:
                  print(f"[!] {password} => {{skipping non ascii english}} => {password}")
              self.foreign_stats_total += 1
              return False
  
          else:
              return True
  
      def analyze_password(
          self,
          password,
          rules_queue=multiprocessing.Queue(),
          words_queue=multiprocessing.Queue(),
      ):
          """ Analyze a single password. """
  
          if self.verbose:
              print(f"[*] Analyzing password: {password}")
  
          words = []
  
          # Short-cut words in the dictionary
          if self.enchant.check(password) and not self.word:
  
              word = dict()
              word["password"] = password
              word["suggestion"] = password
              word["hashcat_rules"] = [[]]
              word["pre_rule"] = []
              word["best_rule_length"] = 9999
  
              words.append(word)
  
          # Generate rules for words not in the dictionary
          else:
  
              # Generate source words list
              words = self.generate_words(password)
  
              # Generate levenshtein reverse paths for each suggestion
              for word in words:
                  # Generate a collection of hashcat_rules lists
                  word["hashcat_rules"] = self.generate_hashcat_rules(
                      word["suggestion"], word["password"]
                  )
  
          self.print_hashcat_rules(words, password, rules_queue, words_queue)
  
      def print_hashcat_rules(self, words, password, rules_queue, words_queue):
  
          best_found_rule_length = 9999
  
          # Sorted list based on rule length
          for word in sorted(words, key=lambda w: len(w["hashcat_rules"][0])):
  
              words_queue.put(word["suggestion"])
  
              for hashcat_rule in word["hashcat_rules"]:
  
                  rule_length = len(hashcat_rule)
  
                  if not self.more_rules:
                      if rule_length < best_found_rule_length:
                          best_found_rule_length = rule_length
  
                      elif rule_length > best_found_rule_length:
                          if self.verbose:
                              print(
                                  f"[-] {word['suggestion']} => "
                                  f"{{best rule length exceeded: {rule_length} "
                                  f"({best_found_rule_length})}} => {password}"
                              )
                          break
  
                  if rule_length <= self.max_rule_len:
                      hashcat_rule_str = " ".join(
                          hashcat_rule + word["pre_rule"] or [":"]
                      )
                      if self.verbose:
                          print(
                              f"[+] {word['suggestion']} => {hashcat_rule_str} => {password}"
                          )
  
                      rules_queue.put(hashcat_rule_str)
  
      def password_worker(self, i, passwords_queue, rules_queue, words_queue):
          if self.debug:
              print(f"[*] Password analysis worker [{int(i)}] started.")
          try:
              while True:
                  password = passwords_queue.get()
  
                  # Interrupted by a Death Pill
                  if password is None:
                      break
  
                  self.analyze_password(password, rules_queue, words_queue)
          except (KeyboardInterrupt, SystemExit):
              if self.debug:
                  print(f"[*] Password analysis worker [{int(i)}] terminated.")
  
          if self.debug:
              print(f"[*] Password analysis worker [{int(i)}] stopped.")
  
      def rule_worker(self, rules_queue, output_rules_filename):
          """ Worker to store generated rules. """
          print(f"[*] Saving rules to {output_rules_filename}")
  
          f = open(output_rules_filename, "w")
          if self.debug:
              print("[*] Rule worker started.")
          try:
              while True:
                  rule = rules_queue.get()
  
                  # Interrupted by a Death Pill
                  if rule is None:
                      break
  
                  f.write(f"{rule}\n")
                  f.flush()
  
          except (KeyboardInterrupt, SystemExit):
              if self.debug:
                  print("[*] Rule worker terminated.")
  
          f.close()
          if self.debug:
              print("[*] Rule worker stopped.")
  
      def word_worker(self, words_queue, output_words_filename):
          """ Worker to store generated rules. """
          print(f"[*] Saving words to {output_words_filename}")
  
          f = open(output_words_filename, "w")
          if self.debug:
              print("[*] Word worker started.")
          try:
              while True:
                  word = words_queue.get()
  
                  # Interrupted by a Death Pill
                  if word is None:
                      break
  
                  f.write(f"{word}\n")
                  f.flush()
  
          except (KeyboardInterrupt, SystemExit):
              if self.debug:
                  print("[*] Word worker terminated.")
  
          f.close()
          if self.debug:
              print("[*] Word worker stopped.")
  
      # Analyze passwords file
      def analyze_passwords_file(self, passwords_file):
          """ Analyze provided passwords file. """
  
          print(f"[*] Analyzing passwords file: {passwords_file} ...")
          print("[*] Press Ctrl-C to end execution and generate statistical analysis.")
  
          # Setup queues
          passwords_queue = multiprocessing.Queue(self.threads)
          rules_queue = multiprocessing.Queue()
          words_queue = multiprocessing.Queue()
  
          # Start workers
          for i in range(self.threads):
              multiprocessing.Process(
                  target=self.password_worker,
                  args=(i, passwords_queue, rules_queue, words_queue),
              ).start()
          multiprocessing.Process(
              target=self.rule_worker, args=(rules_queue, f"{self.basename}.rule")
          ).start()
          multiprocessing.Process(
              target=self.word_worker, args=(words_queue, f"{self.basename}.word")
          ).start()
  
          # Continue with the main thread
  
          f = open(passwords_file, "r", encoding="latin-1", errors="ignore")
  
          password_count = 0
          analysis_start = time.time()
          try:
              for password in tqdm(f):
                  if self.verbose is True:
                      tqdm.disable = True
                  password = password.rstrip("\r\n")
                  if len(password) > 0:
  
                      # Provide analysis time feedback to the user
                      if (
                          not self.quiet
                          and password_count != 0
                          and password_count % 5000 == 0
                      ):
                          print(
                              f"[-] Skipped {password_count} all numeric passwords "
                              f"({float(self.numeric_stats_total) * 100.0 / float(password_count):.2f}%) "
                          )
  
                      password_count += 1
  
                      # Perform preliminary checks and add password to the queue
                      if self.check_reversible_password(password):
                          passwords_queue.put(password)
  
          except (KeyboardInterrupt, SystemExit):
              print("\n[!] Rulegen was interrupted.")
  
          else:
              # Signal workers to stop.
              for _ in range(self.threads):
                  passwords_queue.put(None)
  
                  # Wait for all of the queued passwords to finish.
              while not passwords_queue.empty():
                  time.sleep(1)
  
              # Signal writers to stop.
              rules_queue.put(None)
              words_queue.put(None)
  
          f.close()
  
          analysis_time = time.time() - analysis_start
          print(
              f"[*] Finished processing {int(password_count)} passwords in "
              f"{analysis_time:.2f} seconds at the rate of "
              f"{(float(password_count) / analysis_time):.2f} p/sec"
          )
  
          print(f"[*] Generating statistics for [{self.basename}] rules and words.")
          print(
              f"[-] Skipped {self.numeric_stats_total} all numeric passwords "
              f"(({float(self.numeric_stats_total) * 100.0 / float(password_count)}):.2f%)"
          )
          print(
              f"[-] Skipped {self.special_stats_total} passwords with less than 25%"
              f" alpha characters ({float(self.special_stats_total) * 100.0 / float(password_count)}:.2f%)"
          )
          print(
              f"[-] Skipped {self.foreign_stats_total} passwords with non ascii "
              f"characters ({float(self.foreign_stats_total) * 100.0 / float(password_count)}:.2f%)"
          )
  
          # TODO: Counter breaks on large files. uniq -c | sort -rn is still the most
          #       optimal way.
          rules_file = open(f"{self.basename}.rule", "r")
          rules_sorted_file = open(f"{self.basename}-sorted.rule", "w")
          rules_counter = Counter(rules_file)
          rule_counter_total = sum(rules_counter.values())
  
          print("\n[*] Top 10 rules")
          rules_i = 0
          for (rule, count) in rules_counter.most_common():
              rules_sorted_file.write(rule)
              if rules_i < 10:
                  print(
                      f"[+] {rule.rstrip(NEWLINE)} - {count} "
                      f"({count * 100 / rule_counter_total}:.2f%)"
                  )
              rules_i += 1
  
          rules_file.close()
          rules_sorted_file.close()
  
          words_file = open(f"{self.basename}.word", "r")
          words_sorted_file = open(f"{self.basename}-sorted.word", "w")
          words_counter = Counter(words_file)
          word_counter_total = sum(rules_counter.values())
  
          print("\n[*] Top 10 words")
          words_i = 0
          for (word, count) in words_counter.most_common():
              words_sorted_file.write(word)
              if words_i < 10:
                  print(
                      f"[+] {word.rstrip(NEWLINE)} - "
                      f"{count} ({count * 100 / word_counter_total}:.2f%)"
                  )
              words_i += 1
  
          words_file.close()
          words_sorted_file.close()
  
      ##########################################################################
      def verify_hashcat_rules(self, word, rules, password):
  
          f = open(f"{HASHCAT_PATH}/test.rule", "w")
          f.write(" ".join(rules))
          f.close()
  
          f = open(f"{HASHCAT_PATH}/test.word", "w")
          f.write(word)
          f.close()
  
          p = subprocess.Popen(
              [
                  f"{HASHCAT_PATH}/hashcat-cli64.bin",
                  "-r",
                  f"{HASHCAT_PATH}/test.rule",
                  "--stdout",
                  f"{HASHCAT_PATH}/test.word",
              ],
              stdout=subprocess.PIPE,
          )
          out, err = p.communicate()
          out = out.strip()
  
          if out == password:
              hashcat_rules_str = " ".join(rules or [":"])
              if self.verbose:
                  print(f"[+] {word} => {hashcat_rules_str} => {password}")
  
          else:
              print(
                  f"[!] Hashcat Verification FAILED: {word} => "
                  f"{' '.join(rules or [':'])} => {password} ({out})"
              )
  
  
  if __name__ == "__main__":
  
      header = "                       _ \n"
      header += f"     RuleGen {VERSION}    | |\n"
      header += "      _ __   __ _  ___| | _\n"
      header += r"     | '_ \ / _` |/ __| |/ /\n"
      header += "     | |_) | (_| | (__|   < \n"
      header += r"     | .__/ \__,_|\___|_|\_\\\n"
      header += "     | |                    \n"
      header += "     |_| iphelix@thesprawl.org\n"
      header += "\n"
  
      parser = OptionParser("%prog [options] passwords.txt", version=f"%prog {VERSION}")
  
      parser.add_option(
          "-b",
          "--basename",
          help="Output base name. The following files will be generated: "
          + "basename.words, basename.rules and basename.stats",
          default="analysis",
          metavar="rockyou",
      )
      parser.add_option(
          "-w",
          "--wordlist",
          help="Use a custom wordlist for rule analysis.",
          metavar="wiki.dict",
      )
      parser.add_option(
          "-q",
          "--quiet",
          action="store_true",
          dest="quiet",
          default=False,
          help="Don't show headers.",
      )
      parser.add_option(
          "--threads",
          type="int",
          default=multiprocessing.cpu_count(),
          help="Parallel threads to use for processing.",
      )
  
      wordtune = OptionGroup(parser, "Fine tune source word generation:")
      wordtune.add_option(
          "--maxworddist",
          help="Maximum word edit distance (Levenshtein)",
          type="int",
          default=10,
          metavar="10",
      )
      wordtune.add_option(
          "--maxwords",
          help="Maximum number of source word candidates to consider",
          type="int",
          default=5,
          metavar="5",
      )
      wordtune.add_option(
          "--morewords",
          help="Consider suboptimal source word candidates",
          action="store_true",
          default=False,
      )
      wordtune.add_option(
          "--simplewords",
          help="Generate simple source words for given passwords",
          action="store_true",
          default=False,
      )
      parser.add_option_group(wordtune)
  
      ruletune = OptionGroup(parser, "Fine tune rule generation:")
      ruletune.add_option(
          "--maxrulelen",
          help="Maximum number of operations in a single rule",
          type="int",
          default=10,
          metavar="10",
      )
      ruletune.add_option(
          "--maxrules",
          help="Maximum number of rules to consider",
          type="int",
          default=5,
          metavar="5",
      )
      ruletune.add_option(
          "--morerules",
          help="Generate suboptimal rules",
          action="store_true",
          default=False,
      )
      ruletune.add_option(
          "--simplerules",
          help="Generate simple rules insert,delete,replace",
          action="store_true",
          default=False,
      )
      ruletune.add_option(
          "--bruterules",
          help="Bruteforce reversal and rotation rules (slow)",
          action="store_true",
          default=False,
      )
      parser.add_option_group(ruletune)
  
      spelltune = OptionGroup(parser, "Fine tune spell checker engine:")
      spelltune.add_option(
          "--providers",
          help="Comma-separated list of provider engines",
          default="aspell,myspell",
          metavar="aspell,myspell",
      )
      spelltune.add_option(
          "--language",
          help="Language for spellchecker to use",
          default="en",
          metavar="en",
      )
      parser.add_option_group(spelltune)
  
      debug = OptionGroup(parser, "Debuggin options:")
      debug.add_option(
          "-v",
          "--verbose",
          help="Show verbose information.",
          action="store_true",
          default=False,
      )
      debug.add_option(
          "-d", "--debug", help="Debug rules.", action="store_true", default=False
      )
      debug.add_option(
          "--password",
          help="Process the last argument as a password not a file.",
          action="store_true",
          default=False,
      )
      debug.add_option(
          "--word", help="Use a custom word for rule analysis", metavar="Password"
      )
      debug.add_option(
          "--hashcat",
          help="Test generated rules with hashcat-cli",
          action="store_true",
          default=False,
      )
      parser.add_option_group(debug)
  
      (options, args) = parser.parse_args()
  
      # Print program header
      if not options.quiet:
          print(header)
  
      if len(args) < 1:
          parser.error("no passwords file specified")
          exit(1)
  
      try:
          rulegen = RuleGen(
              language=options.language,
              providers=options.providers,
              basename=options.basename,
              threads=options.threads,
          )
      except enchant.errors.DictNotFoundError:
          print(
              "[-] Cannot find a dictionary for specified language. "
              "Please install it and try again."
          )
          print(
              "[*] Hint: Usually this dictionary resides within an "
              "aspell / myspell package."
          )
          exit(-1)
  
      # Finetuning word generation
      rulegen.max_word_dist = options.maxworddist
      rulegen.max_words = options.maxwords
      rulegen.more_words = options.morewords
      rulegen.simple_words = options.simplewords
  
      # Finetuning rule generation
      rulegen.max_rule_len = options.maxrulelen
      rulegen.max_rules = options.maxrules
      rulegen.more_rules = options.morerules
      rulegen.simple_rules = options.simplerules
      rulegen.brute_rules = options.bruterules
      if rulegen.brute_rules:
          print("[!] Bruteforcing reversal and rotation rules. (slower)")
  
      # Debugging options
      rulegen.word = options.word
      rulegen.verbose = options.verbose
      rulegen.debug = options.debug
      rulegen.hashcat = options.hashcat
      rulegen.quiet = options.quiet
  
      # Make multiprocessing use fork method instead of spawn
      multiprocessing.set_start_method("fork", force=True)
  
      # Custom language
      print(f"[*] Using language: '{rulegen.enchant.tag}'")
  
      # Custom wordlist
      if not options.word:
          if options.wordlist:
              print(f"[*] Loading wordlist: {options.wordlist} ...")
              rulegen.load_custom_wordlist(options.wordlist)
          print(
              f"[*] Using Enchant {rulegen.enchant.provider.name} module. "
              "For best results please install"
          )
          print(f"    '{rulegen.enchant.provider.name}' module language dictionaries.")
  
      # Analyze a single password or several passwords in a file
      if options.password:
          rulegen.analyze_password(args[0])
      else:
          rulegen.analyze_passwords_file(args[0])
  