THE

SPRAWL


The purpose of this research is to help advance the field of password cracking by developing password rule analysis techniques and deliver tools to help enhance rule-based password cracking attacks. The contributions of this research are techniques for source word reversal, the introduction of the Reverse Levenshtein Path algorithm for password rule reversal and a tool, PACK (Password Analaysis and Cracking Kit) that will produce valid rules and wordlists for use with the Hashcat password cracker. Through this work I have stumbled into an exciting new field of password analysis offering plenty of possibilities. I hope by reading this work you will also be inspired to start working and contributing to the art of password cracking.

This work is designed to be as practical as possible with many code snippets along the way. In fact, I highly encourage you to experiment with the sample code in order to get a better feel for the content and hopefully make improvements.

Introduction

The field of password cracking has evolved by leaps and bounds over the last decade with the introduction of new cracking techniques, more advanced software and significantly faster hardware. These innovations were developed not only in response to improvements in cryptographic algorithms, but a gradual improvement of password quality by users as well. While the use of dictionary words for passwords is still a strong trend, many users have developed a set of word mangling rules to come up with passwords which are harder to crack and/or compliant with their organization's or website's password policy. For example, a rule to replace all letters 'a' with a number '4' could be used to mangle a source word 'password' to produce a password candidate 'p4ssword'. As a result, many passwords crackers such as Hashcat and John the Ripper have implemented rule engines that apply common word mangling rules to source wordlists in order to crack these more complex passwords.

The analysis of password rules can be very effective in cracking large number of passwords that were generated using shared rules or words. For example, if a user's password (p4ssword) was compromised on site A, then an attacker can recover same user's password on site B if it was generated with the same rules but a different source word (e.g. dr4gon) or the same source word but different rules (password1). This work can also be used successfully for password cracking competitions such as Defcon's Crack Me If You Can where continuous rule and word recycling are essential to winning.

Below is a series of experiments and observations to address the challenges of source word reversal, password rule generation and practical application through the use of modern password cracking tools.

Reversing source words used in passwords

Let's take a step back for a moment and observe that word mangling is not always intentional. In fact, unintentional word mangling is simply called a spelling error. Let's consider for a moment that a dictionary-based mangled password is a special case of intentionally misspelling a word. Using this assumption, we could utilize a large body of spell-checking algorithms such as the classic Levenshtein Distance and a number of open-source spell-checking libraries such as Aspell, Hunspell and many others.

Let's run a few experiments to determine their usability and limitations for restoring source words from mangled passwords.

Using spell-checking libraries

For this experiment, I have chosen Enchant - a spell-checking wrapper library with an ability to interface and dynamically choose many different spell-checking libraries (Aspell, Myspell, Hunspell, etc.). Let's observe how Enchant interprets the example above using a Python script with the PyEnchant library:

#!/usr/bin/env python
import enchant
import sys

if len(sys.argv) < 1:
    print "Usage: rulegen.py p4ssw0rd"
    sys.exit(1)

d = enchant.Dict("en_US")
password = sys.argv[1]
print "%s: %s" % (password,", ".join(d.suggest(sys.argv[1])))

Now let's analyze a sample password 'p4ssword1':

$ python rulegen1.py p4ssword1
p4ssword1: password, swordplay, crossword

In the list of source word candidates, the source word 'password' was correctly identified as well as a few unexpected candidates. These additional results may not be applicable in this case, but will become crucial in others. For example, consider this example:

$ ./rulegen1.py wordpass
wordpass: word pass, word-pass, passwords, password, wordless, swordplay, wordplay, waitperson

The first candidate guessed that the source of password 'wordpass' was combining two words 'word' and 'pass'; however, we have also identified the word 'password' as a possible candidate. In fact the word 'password' can be transformed into the password 'wordpass' by rotating the source word.

Things get complicated quickly as users come up with more complex rules. For example consider a small variation on the password 'wordpass' above:

$ ./rulegen1.py w0rdp4ss
w0rdp4ss: wardress, redeposit, bandpass

At this point the spell checking library got completely confused by our input and did not return the source word 'password' as any of the candidates. This failure contains an important observation: even though password mangling may appear to be very similar to misspellings for the majority of simple cases, passwords are still unique from simple spelling errors and thus special care must be taken when using spell-checking algorithms or applications for the purposes of rule reversal.

Pre-analysis engine

Let's adjust the previous application with a simple password pre-analysis engine designed to detect known numeric substitutions to prepare passwords to be processed by the spell-checker:

#!/usr/bin/env python
import enchant
import sys

if len(sys.argv) < 1:
    print "Usage: rulegen.py p4ssw0rd"
    sys.exit(1)

leet = dict()
leet['4'] = 'a'
leet['0'] = 'o'

def preanalysis(password):
    preanalysis_password = ''
    for c in password:
        if c in leet: preanalysis_password += leet[c]
        else: preanalysis_password += c
    return preanalysis_password

d = enchant.Dict("en_US")
password = preanalysis(sys.argv[1])

print "%s: %s" % (password,", ".join(d.suggest(password)))

Now let's observe the same example above and observe the difference:

$ ./rulegen2.py w0rdp4ss
wordpass: word pass, word-pass, passwords, password, wordless, swordplay, wordplay, waitperson

Using this primitive preanalysis engine we were able to get the correct source dictionary word 'password' as one of the candidates within top 3 results.

There are several other tasks the preanalysis engine may take care of in order to take specifics of the password creation and present spell checkers with better candidates.

  • Rotation Rules Just like we found a rotation of the word password to wordpass, candidates such as dpasswor, asswordp, etc. are sometimes used by users and are supported by many password crackers.

  • Insertion, prefix and appendix rules Some great prefix and appendix candidates could be detected by observing non-alpha characters on each side of the an alpha word.

  • Duplication rules Duplicating first/last character or substrings (e.g. pppassword, passworddd, papassword, passwordpassword, passworddrowssap, etc.)

  • Combination rules Combining one or more words (e.g. super!man)

  • Password patterns Frequently used password patterns such as email addresses can be detected and processed (e.g. password@aol.com)

By combining existing spell-checking algorithms with the pre-analysis engine which takes into account the specifics of password generation it may be possible to recover much more complex rules.

Custom wordlists

I have intentionally avoided the use of the phrase source "dictionary word" and used "source word" instead. For the purposes of password rule analysis, we must often consider source words not normally considered by standard spell-checking dictionary-based wordlists.

First let's modify the original source code to include the possibility of custom dictionaries:

#!/usr/bin/env python
# iphelix [at] thesprawl.org
import enchant
import sys

if len(sys.argv) < 1:
    print "Usage: rulegen.py p4ssw0rd [wordlist.txt]"
    sys.exit(1)

if len(sys.argv) == 3:
    d = enchant.request_pwl_dict(sys.argv[2])
else:
    d = enchant.Dict("en_US")

print d.suggest(sys.argv[1])

Consider we are trying to reverse the password 'iloveu123'. If we try to use the standard spell-checking dictionary we get the following result:

$ ./rulegen3.py iloveu123
['spillover', 'allover', 'alleviate']

However, imagine that we have already cracked a password 'iloveu'. If we add this already cracked password to a custom wordlist and use it to generate more rules, then we can produce a much better result:

$ ./rulegen3.py iloveu123 wordlist.txt 
['iloveu']

By constantly enhancing the source word list with already cracked passwords it may be possible to correctly reverse passwords generated using highly complex rules impossible to detect otherwise. As a result the number and quality of reversed rules will be highly dependent on the source word list.

Reducing results

The potential for improvement is so large when trying to intelligently produce source words that even getting a couple (or a dozen) of incorrect candidates will still produce a significant improvement in password cracking in the long run and as a result every possible candidate must be considered and recorded.

However, there may be cases where the results list is too large for a particularly slow algorithm. We must be able to determine best word candidates and ignore the rest. A common way to evaluate source word candidates is by calculating their Levenshtein edit distance. Let's modify the original sample program to accept a maximum edit distance parameter and filter results accordingly:

#!/usr/bin/env python
import enchant
import sys

if len(sys.argv) < 2:
    print "Usage: rulegen.py p4ssw0rd 5"
    sys.exit(1)

password = sys.argv[1]
max_edit_distance = sys.argv[2]

# Levenshtein distance algorithm
# Source: https://en.wikipedia.org/wiki/Levenshtein_distance
def levenshtein(s, t):
    if len(s) == 0:
        return len(t)
    elif len(t) == 0:
        return len(s)
    else:
        cost = 0
        if s[0] != t[0]:
            cost = 1

        return min( levenshtein(s[1:], t) + 1,\
                    levenshtein(s, t[1:]) + 1,\
                    levenshtein(s[1:], t[1:]) + cost)

d = enchant.Dict("en_US")
for word in d.suggest(password):
    edit_distance = levenshtein(word,password)
    if edit_distance <= max_edit_distance:
       print "[%s] %s" % (edit_distance,word)

Now let's try determining source words for the password 'p4ssw0rd':

$ ./rulegen4.py p4ssw0rd 5
[2] password
[5] Pissaro
[5] assured

The first candidate 'password' has an edit distance 2 (shown in square brackets), corresponding to the two replacement operations. 'Pissaro' and 'assured' both require 5 edit operations in order to be mangled into 'p4ssw0rd'. Let's filter source word candidates to only include those with edit distance 2 or less:

$ ./rulegen4.py p4ssw0rd 2
[2] password

Please review Levenshtein distance Wikipedia article for details about how the algorithm works.

Future Work

As was illustrated in several examples above, the existing spell-checking libraries and algorithms can be taken only so far when trying to reverse source words. There is plenty of room for improvement of algorithms targeting the specifics of password generation as well as the initial wordlists used for the comparison.

Reversing Word Mangling Rules

Now that we have one or more good source word candidates, let's tackle the second challenge of discovering word mangling rules used to transform source words into passwords.

Levenshtein Edit Distance Algorithm

In order to absorb further research, let's get an intuitive feel for the way Levenshtein distance algorithm works by visually observing the matrix used to generate the edit distance.

Below is a sample dynamic implementation of the Levenshtein distance algorithm which is great for learning since it preserves the matrix as it is calculated.

#!/usr/bin/env python
# iphelix [at] thesprawl.org
import sys

def matrixprint(matrix,source,target):
    print "    %s" % " ".join(list(source))
    for i,row in enumerate(matrix):
        if i == 0: print " ",
        else:      print target[i-1],
        print " ".join(str(col) for col in row)

def levenshtein(source, target):
    # 1) Generate the initial matrix
    matrix = []
    for i in xrange(len(target) + 1):
        matrix.append([])
        for j in xrange(len(source) + 1):
            if i == 0:
                matrix[i].append(j)
            elif j == 0:
                matrix[i].append(i)
            else:
                matrix[i].append(0)

    # 2) Populate the matrix using Levenshtein algorithm
    for i in xrange(1,len(target) + 1):
        for j in xrange(1,len(source) + 1):
            if target[i-1] == source[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

if __name__ == "__main__":
        if len(sys.argv) < 3:
            print "Usage: lev.py word password"
            sys.exit(1)

        word = sys.argv[1]
        password = sys.argv[2]

        matrix = levenshtein(word,password)
        matrixprint(matrix,word,password)

Let's generate a simple example where the source word and the password are the same:

$ python rulegen5.py password password    
    p a s s w o r d
  0 1 2 3 4 5 6 7 8 
p 1 0 1 2 3 4 5 6 7 
a 2 1 0 1 2 3 4 5 6 
s 3 2 1 0 1 2 3 4 5 
s 4 3 2 1 0 1 2 3 4 
w 5 4 3 2 1 0 1 2 3 
o 6 5 4 3 2 1 0 1 2 
r 7 6 5 4 3 2 1 0 1 
d 8 7 6 5 4 3 2 1 0*

The diagonal line of 0s represents edit distance between all possible substrings of equal size (e.g substrings 'pass' == 'pass', 'passwo'=='passwo', etc.). Because we are comparing two identical words, the edit distance between individual letters and substrings for each position is 0 (identical) and as a result the final edit distance (calculated at the bottom right corner) is 0.

Now let's look at an example with a couple of letter replacements:

$ python rulegen5.py password p4ssw0rd
    p a s s w o r d
  0 1 2 3 4 5 6 7 8
p 1 0 1 2 3 4 5 6 7
4 2 1 1 2 3 4 5 6 7
s 3 2 2 1 2 3 4 5 6
s 4 3 3 2 1 2 3 4 5
w 5 4 4 3 2 1 2 3 4
0 6 5 5 4 3 2 2 3 4
r 7 6 6 5 4 3 3 2 3
d 8 7 7 6 5 4 4 3 2*

First observe that the Levenshtein edit distance is "2" which corresponds to the two substitutions occurring at the following substring locations in the matrix:

    p a         p a s s w o
  0 1 2       0 1 2 3 4 5 6
p 1 0 1     p 1 0 1 2 3 4 5
4 2 1 1*    4 2 1 1 2 3 4 5
            s 3 2 2 1 2 3 4
            s 4 3 3 2 1 2 3
            w 5 4 4 3 2 1 2
            0 6 5 5 4 3 2 2*

If you look at the bottom right corners of each sub-matrix then you can see the cells were calculated as a result of this snippet of the algorithm:

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)

In both cases the edit distance corresponding to matrix[i-1][j-1] + 1 was minimal and as a result we have recorded a diagonal increment of 1 corresponding to a substitution operation of 'a' to '4' and 'o' to '0'. Notice how the value propagates toward the bottom right corner accumulating all of the edit counts.

Just to solidify the algorithm let's look at another password with an insertion:

$ python rulegen5.py password p4ssw0rd1
    p a s s w o r d
  0 1 2 3 4 5 6 7 8
p 1 0 1 2 3 4 5 6 7
4 2 1 1 2 3 4 5 6 7
s 3 2 2 1 2 3 4 5 6
s 4 3 3 2 1 2 3 4 5
w 5 4 4 3 2 1 2 3 4
0 6 5 5 4 3 2 2 3 4
r 7 6 6 5 4 3 3 2 3
d 8 7 7 6 5 4 4 3 2
1 9 8 8 7 6 5 5 4 3*

The edit distance for the transformation 'password' to 'p4ssw0rd1' is 3 which corresponds to the two letter substitutions (a=>4 and o=>0) and the insertion operation of '1' at the very end. The bottom-right value was calculated as minimal using matrix[i-1][j] + 1 which corresponds to the insertion operation.

After observing this pattern you will notice that the Levenshtein matrix actually preserves all of the transformations performed on the original string, it can be used to trace back the path from the mangled password to the source word while recording editing operations such as substitutions, deletions and insertions. Now it's getting exciting!

Reverse Levenshtein Path

Using the above observation we can traverse the dynamically generated Levenshtein matrix and attempt to find one or more minimal paths starting from the bottom right corner of the matrix to the top left. Tracing the matrix in reverse (as opposed to start to finish) allows us to traverse only those paths which can result in an optimal edit path. The matrix can be traversed in a recursive function as illustrated by the following pseudocode:

**function** levenshtein reverse paths are:
**input:** matrix, i = matrix_height, j = matrix_width, edit ops counter = 0
**output:** [(edit op), (edit op), ...], [(edit op), (edit op), ...]

    1. if i is 0 and j is 0, return
    2. if edit ops > min edit distance, return
    3. otherwise,

        best path is minimal vertical, horizontal or diagonal cost
            in the reverse direction of the current location in
            the matrix.

        if vertical path is best path,
            edit ops increment 1
            return levenshtein reverse paths(vertical, edit ops) + (insertion)

        if horizontal path is best path, 
            edit ops increment 1
            return levenshtein reverse paths(horizontal, edit ops) + (deletion)

        if diagonal path is best path,
            if diagonal cost is current cost,
                return levenshtein reverse paths(diagonal, edit ops) + (equals)
            otherwise,
                edit ops increment 1
                return levenshtein reverse paths(diagonal, edit ops) + (replacement)

**end** levenshtein reverse paths

The algorithm above is depth-first (will try to traverse a complete path before trying others) and short-circuited (detects paths exceeding minimum edit distance). By combining a dynamically generated matrix and a recursive reversal algorithm above we can create a hybrid algorithm to give us reverse paths as illustrated in the Python implementation below:

#!usr/bin/env python
import sys

############################################################################
# Calculate Levenshtein edit path matrix
def levenshtein(word,password):
    matrix = []

    # Generate and populate the initial matrix
    for i in xrange(len(password) + 1):
        matrix.append([])
        for j in xrange(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 xrange(1,len(password) + 1):
        for j in xrange(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

############################################################################
# Print word X password matrix
def levenshtein_print(matrix,word,password):
    print "      %s" % "  ".join(list(word))
    for i,row in enumerate(matrix):
        if i == 0: print " ",
        else:      print password[i-1],
        print " ".join("%2d" % col for col in row)

############################################################################
# Reverse Levenshtein Path 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.
def levenshtein_reverse_path(matrix,word,password):
    paths = levenshtein_reverse_recursive(matrix,len(matrix)-1,len(matrix[0])-1,0)
    return [path for path in paths if len(path) <= matrix[-1][-1]]

# Calculate reverse Levenshtein paths (recursive, depth first, short-circuited)
def levenshtein_reverse_recursive(matrix,i,j,path_len):

    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.maxint
        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 = 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 = 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 = levenshtein_reverse_recursive(matrix,i-1,j-1,path_len)
                for equal_path in equal_paths: paths.append(equal_path)
            else:
                replace_paths = 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

if __name__ == "__main__":
    if len(sys.argv) < 3:
        print "Usage: rulegen.py word password"
        sys.exit(1)

    word = sys.argv[1]
    password = sys.argv[2]
    matrix = levenshtein(word,password)
    levenshtein_print(matrix,word,password)
    paths = levenshtein_reverse_path(matrix,word,password)

    min_edit_distance = matrix[-1][-1]

    for path in paths:
        if len(path) == min_edit_distance:
            print "[*] Edit path for '%s' to '%s'" % (word,password)
            for op,p,w in path:
                if op == 'insert':
                    print "    [+] Inserted %s" % password[p]
                elif op == 'delete':
                    print "    [+] Deleted %s" % word[w]
                elif op == 'replace':
                    print "    [+] Replaced %s with %s" % (word[w],password[p])

As previously discussed, the above algorithm works by finding all minimal paths to transform 'word' into 'password' by walking the Levenshtein path in reverse while recording edit operations in reverse: diagonal path - replace or equal, horizontal - delete, vertical - insert.

Let's observe some of its output for a transformation from "password" to "p@ssword":

$ python rulegen6.py password p@ssword
      p  a  s  s  w  o  r  d
   0  1  2  3  4  5  6  7  8
p  1  0  1  2  3  4  5  6  7
@  2  1  1  2  3  4  5  6  7
s  3  2  2  1  2  3  4  5  6
s  4  3  3  2  1  2  3  4  5
w  5  4  4  3  2  1  2  3  4
o  6  5  5  4  3  2  1  2  3
r  7  6  6  5  4  3  2  1  2
d  8  7  7  6  5  4  3  2  1
[*] Edit path for 'password' to 'p@ssword'
    [+] Replaced a with @

Using the above Levenshtein matrix, the reverse path algorithm correctly determined the replacement of character 'a' with '@'. Below is a sample graph that illustrates the optimal reverse path and the point where the replacement OP was detected:

      p  a  s  s  w  o  r  d
  #0  1  2  3  4  5  6  7  8
p  1 #0  1  2  3  4  5  6  7
@  2  1 *1  2  3  4  5  6  7
s  3  2  2 *1  2  3  4  5  6
s  4  3  3  2 *1  2  3  4  5
w  5  4  4  3  2 *1  2  3  4
o  6  5  5  4  3  2 *1  2  3
r  7  6  6  5  4  3  2 *1  2
d  8  7  7  6  5  4  3  2 *1

Let's look at a more advanced password:

$ python rulegen6.py password p@sswrd1
      p  a  s  s  w  o  r  d
   0  1  2  3  4  5  6  7  8
p  1  0  1  2  3  4  5  6  7
@  2  1  1  2  3  4  5  6  7
s  3  2  2  1  2  3  4  5  6
s  4  3  3  2  1  2  3  4  5
w  5  4  4  3  2  1  2  3  4
r  6  5  5  4  3  2  2  2  3
d  7  6  6  5  4  3  3  3  2
1  8  7  7  6  5  4  4  4  3
[*] Edit path for 'password' to 'p@sswrd1'
    [+] Replaced a with @
    [+] Deleted o
    [+] Inserted 1

This example involves all three possible operations of insertion, deletion and replacement. The algorithm was able to successfully find all three operations and report all of them.

There are some situations where there may be multiple equally good paths:

$ python rulegen6.py password p4ss0rd
      p  a  s  s  w  o  r  d
   0  1  2  3  4  5  6  7  8
p  1  0  1  2  3  4  5  6  7
4  2  1  1  2  3  4  5  6  7
s  3  2  2  1  2  3  4  5  6
s  4  3  3  2  1  2  3  4  5
0  5  4  4  3  2  2  3  4  5
r  6  5  5  4  3  3  3  3  4
d  7  6  6  5  4  4  4  4  3
[*] Edit path for 'password' to 'p4ss0rd'
    [+] Replaced a with 4
    [+] Replaced w with 0
    [+] Deleted o
[*] Edit path for 'password' to 'p4ss0rd'
    [+] Replaced a with 4
    [+] Deleted w
    [+] Replaced o with 0

The result where we delete 'w' and perform two replacements (a->4 and o->0) is what we would naturally detect through manual review. However, the algorithm was also able to find an alternative sequence which deleted 'o' and simply replaced 'w' with 'o'. Again we can trace these two paths.

      p  a  s  s  w  o  r  d
  *0  1  2  3  4  5  6  7  8
p  1 *0  1  2  3  4  5  6  7
4  2  1 *1  2  3  4  5  6  7
s  3  2  2 *1  2  3  4  5  6
s  4  3  3  2 *1 *2  3  4  5
0  5  4  4  3  2 *2 *3  4  5
r  6  5  5  4  3  3 *3 *3  4
d  7  6  6  5  4  4  4  4 *3

Notice the split that occurred when deciding what to do after '0' and 'o' delete or replace the 'w', this occurred due to deletion (horizontal) and replacement (diagonal) paths having equal costs. It is apparent in this case that deleting 'w' is more appropriate because we are dealing with a dictionary word; however, once we start using other already mangled words as source words this distinction will become less apparent. Thus all results must be collected and carefully observed. A statistical analysis of generated rules performed at a later stage will reveal more prevalent rules which can be prioritized for password cracking.

The reverse Levenshtein path algorithm above has several limitations. The algorithm is designed to try to find paths corresponding to the shortest edit distance; however, there are some situations where the password went through more transformations than determined by the Levenshtein path:

$ python rulegen6.py password passwr1
      p  a  s  s  w  o  r  d
   0  1  2  3  4  5  6  7  8
p  1  0  1  2  3  4  5  6  7
a  2  1  0  1  2  3  4  5  6
s  3  2  1  0  1  2  3  4  5
s  4  3  2  1  0  1  2  3  4
w  5  4  3  2  1  0  1  2  3
r  6  5  4  3  2  1  1  1  2
1  7  6  5  4  3  2  2  2  2
[*] Edit path for 'password' to 'passwr1'
    [+] Deleted o
    [+] Replaced d with 1

In the above example, we have actually performed three operations to the source word password: delete 'o', delete 'd' and insert '1'. However, the algorithm detected the optimal path is in fact replacing 'd' with '1'. This ambiguity is a limitation (or a feature) which can be addressed by introducing additional logic such as operation costs, additional path analysis, etc. However, all additional logic has its own limitations and introduces its own ambiguity issues especially once such logic starts to consider rules specific to dictionary words and not passwords.

Future work

A possible solution to the above is to introduce some preprocessing to help account for the specifics of password generation. For example, if we detect a password which ends with non-alpha characters, then we may elect to remove them (while preserving and later combining insertion rules) and submit the result to the reverse Levenshtein path algorithm for further processing. I am still evaluating whether this approach has sufficient benefit for the challenge of generating reverse word mangling rules.

Generating Hashcat Rules

The last part of the original challenge of generating password rules was to make the research practical by generating rules using syntax understood by a modern password cracker such as Hashcat. You can review the exact syntax at Hashcat - rule_based_attack Wiki page. Insertion, Deletion and Replacement rules can be easily converted as follows:

Levenshtein OPHashcat RuleHashcat Description
(insert,i,j)iNXInserts character X at position N
(delete,i,j)DNDeletes character at position N
(replace,i,j)oNXOverwrites character at postion N with X

Let's generate these simple Hashcat rules using rulegen.py from the Password Analysis and Cracking Kit:

$ python rulegen.py -q --verbose --simplerules --word password --password p4sword1
[*] Analyzing password: p4sword1
[+] password => o14 D3 i71 => p4sword1
[*] Finished analysis in 0.00 seconds

The sequence of rules to obtain the password p4sword1 is o14 D3 i71, corresponding to replacement of letter 'a', deletion of letter 's' and insertion of number '1'.

Advanced Hashcat Rules

Hashcat implements a wide range of rules such as global character replacements, appendix, prefix, capitalization, etc. These advanced rules can much more precisely describe users' actions than the standard insert, delete and replace triad. By implementing additional analysis it is possible to observe that the insertion occurs at the very end, thus it corresponds to the $1 rule (append 1) and the replacement of 'a' to '4', could be converted to a global replacement sa4. Let's rerun the above command without the --simplerules flag:

$ python rulegen.py -q --verbose --word password --password p4sword1
[*] Analyzing password: p4sword1
[+] password => sa4 D3 $1 => p4sword1

Now that's a lot more useful! You can continue on this path to detect more specific Hashcat rules to replace the simple editing triad. Here is just some of the detection logic that you can perform to make Hashcat rules more specific:

Levenshtein OPHashcat RuleHashcat Description
(insert,i,j) where i is at the end of the word.$cAppend character to end.
(insert,i,j) where i is at the beginning of the word.^cPrepend character to end.
(delete,i,j) where i is at the end of the word.]Delete last character.
(delete,i,j) where i is at the beginning of the word.[Delete first character.
(replace,i,j) where i and i+1 were swapped.*XYSwap character X with Y.
(replace,i,j) where i and i+1 were swapped where i at the beginning of the wordkSwap the first two characters.
(replace,i,j) where i and i+1 were swapped where i is at the end of the word*XYSwap the last two characters.
(replace,i,j) where a case changed for the character iTNToggle the case of characters at position N.
(replace,i,j) where all characters at the index location i in the source word were replaced in the passwordsXYReplace all instances of X with Y.
(replace,i,j) where replacement character at i is an ASCII increment+NIncrement character @ N by 1 ascii value.
(replace,i,j) where replacement character at i is an ASCII derement-NDecrement character @ N by 1 ascii value.
(replace,i,j) where replacement character at i is a left bitwise shiftLNBitwise shift left character @ N.
(replace,i,j) where replacement character at i is a right bitwise shiftRNBitwise shift right character @ N.
(replace,i,j) where the next character at i+1 was replaced with current at i.NReplaces character @ N with value at @ N plus 1.
(replace,i,j) where the previous character at i-1 was replaced with current at i,NReplaces character @ N with value at @ N minus 1.

While experimenting with Hashcat rule optimization and global replacements (e.g. sXY), I have ran across an interesting obstacle. Consider this example:

$ python rulegen.py -q --verbose --word password --password pa55words
[*] Analyzing password: pa55words
[+] password => ss5 $s => pa55words

The global replacements such as ss5 are particularly hard to detect if comparing source and target words which include insertions, deletions or other prior substitutions. Because Hashcat rules are applied in a sequential order, the global replacement ss5 actually works in this case, because the last letter 's' was appended after the global replacement of all characters 's'. However in the case below, global replacement would not work as expected:

$ python rulegen10.py -q --verbose --word password --password pa5swords
[*] Analyzing password: pa5swords
[+] password => o25 $s => pa5swords

In order to make global rules such as global letter replacements or case operations reliable it is important to keep the state of the source word as it is modified by preceding rules and not just comparing source word and the resulting password. Word state can be maintained by implementing the complete rule engine and actually applying it to the source word every time a rule is detected. Below is a snippet of a rules engine implemented using Python lambda functions:

# Hashcat Rules Engine
hashcat_rule = dict()

# Dummy rule
hashcat_rule[':'] = lambda x: x

# Case rules
hashcat_rule["l"] = lambda x: x.lower()
hashcat_rule["u"] = lambda x: x.upper()
hashcat_rule["c"] = lambda x: x.capitalize()
hashcat_rule["C"] = lambda x: x[0].lower() + x[1:].upper()
hashcat_rule["t"] = lambda x: x.swapcase()
hashcat_rule["T"] = lambda x,y: x[:y] + x[y].swapcase() + x[y+1:]
hashcat_rule["E"] = lambda x: " ".join([i[0].upper()+i[1:] for i in x.split(" ")])

This engine can be continuously applied to the source word to maintain the state. For example, hashcat_rule["l"](word) will return the original source word with all characters lowered.

There may still be situations when even while preserving the state global rules may produce unexpected results. Consider this example:

 $ python rulegen.py -q --verbose --word password --password ps55words
[*] Analyzing password: ps55words
[+] password => D1 o25 i35 $s => ps55words
[+] password => D1 i25 ,3 $s => ps55words
[+] password => o1s o25 ,3 $s => ps55words

In the example above, the replacement of letter 'a' with 's' made global replacement not applicable. At this point, due to the complexity and variety of possibly generated password rules this becomes akin to The Halting Problem. To solve this issue, I have implemented a simplified version of the rules engine and observe whether a given rule will result in the correct solution: mangled source word is equal to the password. As a result, rules generated by this engine are guaranteed to produce the correct password.

Future work

Another challenge is detection of rules which affect indices of all other operations such as word rotation, reversal and shifting. The challenge here is mixing these rules (after being properly detected) with other rules (e.g. substitutions) that may have occurred after them. Detection of these rules is even more unusual, because it requires actually attempting them and observing whether generated rules are better or worse with and without them. This bruteforce approach increases computational time of the rules and introduces additional complexity when combining bruteforce rules with normally generated ones. It may be that bruteforcing and trying each of these rules in parallel is the best solution; however, this is still an area of research and experimentation.

Results

Below is the source word and password rule analysis for several leaked password lists using tools and techniques introduced in this paper. All of the rules were generated using PACK using Enchant's Aspell provider and a standard English dictionary.

NOTE: Obviously incorrectly guessed words, such as single characters, were removed from final results.

SourceTop Dictionary WordsTop Password Rules
RockYoulove, password, baby, olive, alex, oliver, jim, jam, march and sexy
: - 1079666 (2.22%)
$1 - 238757 (0.49%)
$2 - 76237 (0.16%)
$1 $2 $3 - 56550 (0.12%)
$1 $2 - 52113 (0.11%)
$3 - 50139 (0.10%)
$7 - 45267 (0.09%)
^1 - 42804 (0.09%)
$1 $3 - 40550 (0.08%)
$5 - 39330 (0.08%)
LinkedInlinked, linkedin, password, alex, mike, jim, jfs, jam, jack and job
: - 749269 (3.21%)
$1 - 201449 (0.86%)
$1 $2 $3 - 51743 (0.22%)
$0 $1 - 48108 (0.21%)
$2 - 45760 (0.20%)
$1 $2 - 38274 (0.16%)
$1 $1 - 33420 (0.14%)
$7 - 25973 (0.11%)
$3 - 25788 (0.11%)
^1 - 24744 (0.11%)
MySpacepassword, olive, myspace, love, hearts, baseball, softball, football, cutie and chicken
$1 - 5372 (5.48%)
: - 1613 (1.64%)
$2 - 1121 (1.14%)
$! - 990 (1.01%)
$3 - 715 (0.73%)
$1 $2 $3 - 578 (0.59%)
l $1 - 566 (0.58%)
$7 - 532 (0.54%)
$1 $2 - 530 (0.54%)
$5 - 504 (0.51%)
Stratforskyjack, stratify, jukebox, Kazakh, Uzbek, KGB, password, Bangkok, Reykjavik and Augsburg
: - 33481 (0.37%)
$1 - 7480 (0.08%)
T0 - 6072 (0.07%)
$1 $2 $3 - 1370 (0.02%)
$0 $1 - 1049 (0.01%)
l $1 - 973 (0.01%)
$2 - 968 (0.01%)
$1 $2 - 788 (0.01%)
$1 $! - 711 (0.01%)
$1 $1 - 673 (0.01%)
Singles.orgJesus, love, angel, loveme, faith.
: - 4786 (25.62%)
T0 - 659 (3.53%)
$1 - 390 (2.09%)
] - 100 (0.54%)
$2 - 100 (0.54%)
$7 - 84 (0.45%)
l $1 - 66 (0.35%)
$1 $2 $3 - 55 (0.29%)
$1 $2 - 55 (0.29%)
$4 - 49 (0.26%)
FaithWritersJesus, password, blessed, faith, writer, freedom, grace, mother
: - 3182 (18.06%)
T0 - 374 (2.12%)
$1 - 353 (2.00%)
$2 - 64 (0.36%)
$1 $2 $3 - 62 (0.35%)
l $1 - 62 (0.35%)
$7 - 56 (0.32%)
$3 - 40 (0.23%)
$1 $2 - 37 (0.21%)
^1 - 37 (0.21%)
PHPBBpassword, phoebe, phobia, dragon, forum, alpha, master, Mike, admin, qwerty
: - 43681 (5.94%)
$1 - 4157 (0.57%)
T0 - 2514 (0.34%)
$1 $2 $3 - 1244 (0.17%)
$2 - 1012 (0.14%)
$1 $2 - 708 (0.10%)
$0 $1 - 628 (0.09%)
$9 $9 - 542 (0.07%)
] - 513 (0.07%)
$1 $1 - 509 (0.07%)

With all the time and energy that went into detecting advanced rule sets, I was a bit disappointed at first that a large chunk of passwords could be attacked with simple numeric appendices (even with a few pleasant surprises from Startfor). The results could be explained by users simply choosing highly simplistic appendix rules or a weakness in the rule detection engine (or both). However, when looking at the percentage counts of total rules generated it became clear that the truly juicy rules are the ones that occur less frequently. Here is a list of some of the more unusual rules generated from the above lists which may come in handy at one point:

$@ $a $o $l $. $c $o $m
^8 ^7 ^4 ^1 o6q T7
+1 i2e $2 $1 $0 $7 $2 $0 $0 $7
sW- $- $! $- $- $! $<
^y ^m ^4 o9b oAi $z

The ability to generate these highly complex rule sets and come up with unexpected source word results constitutes the key contribution of this project which allows automatic detection of patterns not normally detectable manually.

Conclusion

Automatic password rule reversal is not only possible, but as was illustrated above it is practical and can be used with great results to profile user passwords. There are several limitations to the above research as was illustrated in the final analysis (need better wordlists, spellchecking, expanded rule detection, etc.); however, I hope the work so far will give you enough interest to start exploring this field more.

Above all, I hope to bring awareness to the inherent weakness of dictionary based pass"words" no matter how many special mangling rules users apply. It is time to switch to pass"phrases" or other forms of authentication.

Acknowledgements

Special thanks goes to atom and Team Hashcat who both inspired and helped encourage me to complete an early version of this research in time for the Crack Me If You Can competition. Go Team Hashcat!

Also thanks to my coworker, Daniel South, for a crucial pointer to explore the area of DNA sequencing algorithms which became very much relevant to this research. Keep on spreading the seed of security!

Related Work

External Links and References

Published on February 13th, 2013 by iphelix

sprawlsimilar

password analysis and cracking kit

Download PACK-0.0.4.tar.gz
Size 68.8 KB
DateAugust 8th, 2013
Version0.0.4

PACK (Password Analysis and Cracking Toolkit) is a collection of utilities developed to aid in analysis of password lists and enhancing cracking of passwords using password pattern detection. It can be used to reverse word mangling rules, generate source words, optimize password masks, craft policy attacks, etc. for the Hashcat family of tools. The toolkit itself is not able to crack passwords, but instead designed to make operation of password crackers more efficient. Read more.

08
aug
2013

Last week I gave a talk during the Password '13 security conference on various password analysis and pattern detection attacks using the Password Analysis and Cracking Kit. You can download slides for the presentation here.

The conference itself was an absolute blast with great organization by Per Thorsheim and Jeremi Gosney. The conference gathered a fascinating crowd which spawned hours of great discussions on password security, cryptography, politics and everything in between. However, I especially enjoyed meeting in real life with many members of Team Hashcat.

Team Hashcat had another great run at the CMIYC during Defcon where we placed 2nd. As always I ended up spending most of the conference in the hotel room or the chill room at Defcon, but that's part of the fun doing contests. Russia-based team Inside-Pro placed first by scoring more points on harder hashes, молодцы ребята!

Today, I have finally finished writing documentation for the many changes and adding the final polish to the next release of PACK 0.0.4. There should be noticeable performance bumps for all of the tools in the toolkit especially Rulegen which is now finally using multiple CPU cores. You should also try out the completely rewritten 'maskgen' which is now capable of generating highly optimized mask collections for use with Hashcat suite of tools (see presentation slides above for more details). Enjoy and most importantly have fun with password cracking! Read more.

26
apr
2011

A product of my research into password cracking methods, PACK (Password Analysis and Cracking Kit) is a collection of several utilities to assist in statistical password analysis and generation of cracking rule sets. Read more.

07
aug
2010

I had an opportunity to participate in the "Crack me if you can" password cracking competition during this year's Defcon. It was a fun and educational experience. Using a couple of video cards, decent processors as well as some research into password generation I was able to place 4th in the contest. In this post you can learn more about hardware, software and strategy used to crack about 25k passwords in two days. Read more.


sprawlcomments

π
///\oo/\\\