Pat to Pass
This months BruCON 5x5 project came from an idea sent to me by a friend after I released Passpat. Passpat takes passwords and tries to find keyboard patters in them, Pat to Pass is almost the opposite, it takes observed key presses and tries to convert them to potential passwords. The project in its current state is more a proof of concept and sample code which hopefully can be taken forward to be turned into something practical by someone who has better skills at handling very large lists of data.
The scenario, you see someone typing a password, you get that it is right hand, left hand, left, left, left, right, left, left then a left hand number. What could the password be?[1] Well, if you feed that sequence into Pat to Pass it will generate you a list of all potential options. It will be a very long list, 11*15*15*15*15*11*15*15*6 = 8,269,593,750, but at least it is a starting point.
An easier password, just six characters with an equal split of left and right hands, creates a more manageable word list of approximately 4.5 million entries.
These lists may be practical for use with offline brute force attacks, especially against the weaker hashing algorithms, but if you want to try an online brute force, or even a manual attack, then you need to narrow things down a lot further, this is where the Levenshtein distance comes in.
The Levenshtein distance is the number of single character changes you need to make to word one to get to word two, for example "abc" to "abd" has a distance of 1, "abc" to "def" has a distance of 3. This is useful here as most people tend to chose passwords that are close to dictionary words therefore, by comparing the seemingly random words generated by the main algorithm with real words and filtering out those outside a given tolerance, the final list produced will be a lot smaller and so a lot more useful. In tests I generated the potential words based on the key presses for the word password and just by looking at the output it was easy to spot that password was the original word.
Due to the speed of processing the huge amount of data quite a bit of optimisation would be required to this script to make it completely practical but I'm releasing it as I think it is interesting and hopefully someone else will take up the challenge of making it into a practical tool.
Install / Usage
The app has been written and tested in Ruby 1.9.x and 2.0.x.
A single extra gem is required, levenshtein-ffi. This can be installed with:
gem install levenshtein-ffi
Once installed the script can be ran to get full instructions:
./pat_to_pass.rb --help
Pat to Pass 1.0 Robin Wood (robin@digininja.org) (www.digininja.org)
Usage: pat_to_pass [OPTION] ... PATTERN
--help, -h: show help
--disp-keys: display the pattern options
--output, -o : output to file
--dictionary, -d : The dictionary to use for the Levenshtein tests
--lev-distance: Tollerance for Levenshtein distance, default 3
--recursive: Use a recursive algorithm rather than basic looping
PATTERN: The pattern to generate words from
Example Patterns:
l,r = left hand followed by right hand
mr,tl = middle right followed by top left
#q,tr,l,l,#1 = the character q followed by top right then left,
left and the character 1
use --disp-keys to see a full list of pattern options.
WARNING - long patterns will take a long time to run, start small
As it says, using a long pattern will take a long time to run, potentially years so start small (4-5 chars) and work up.
Patterns are passed as quoted strings with the position on the keyboard defined by one of the following characters:
- l = qwertasdfgzxcvb
- tl = qwert
- ml = asdfg
- bl = zxcvb
- r = yuiophjklnm
- tr = yuiop
- mr = hjkl
- br = nm
- nl = 123456
- nr = 7890
Where l is left and r is right and t, m and b are top, middle and bottom.
For example, the word "love" could be either "r,r,l,l" or, more specifically, "mr,tr,bl,tl". The more specific you are, the quicker the script will run through as there are less words to generate.
If you spot exact characters you can specify those by using the # symbol, for example, if you spotted the last character of the password "god1" you could enter "l,r,l,#1". Again, the more specific you are, the better.
If you want to use a non-UK keyboard lay out then you will need to edit the script. The mapping is at the top of the file and should be fairly simple to change to your local layout.
If you want to provide a dictionary for a Levenshtein check then that is passed in with the --dictionary parameter and the tolerance for the displayed matches is set with --lev-distance. Here you need to consider that every word produced by the app will be tested against every word in the dictionary, I therefore suggest a very small dictionary, just four or five words ideally. Do your recon and pick words which best match your target.
Output is sent to screen by default but can be directed to a file by using the --output parameter.
A final option is whether to use basic looping or recursion, this defines the internal algorithm used to generate the words. In my tests both ran about the same speed and had the same failure point so, unless you have a good reason for changing, leave it at the default. I wrote the two different ways in an attempt to improve performance but even though neither appear to be better I figured it is worth including them both in case one is easier for someone else to pick up and improve.
Download
Download Pat to Pass version 1.0
You can also find the source on GitHub if you want to submit patches.
Feedback/Todo
Please feel free to submit patches to improve performance, I've a few ideas but don't have much time to work on them so if you are interested get in touch, I'm happy to discuss things.
Thanks BruCON
Pat to Pass is one of the tools sponsored by the BruCON 5x5 project.
[1] That particular sequence is one of the worlds most popular passwords, password1.
