Pat to Pass - Convert observed key presses to potential password lists
Ruby
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.txt
pat_to_pass.rb

README.txt

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
<http://en.wikipedia.org/wiki/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

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 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
in case one is easier for someone else to pick up and improve.


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
<http://www.digininja.org/blog/brucon_5x5.php> project.

[1] That particular sequence is one of the worlds most popular passwords, password1.