Passpat, Password Pattern Identifier
It is generally accepted that most passwords in common use are based on dictionary words however, some people decide to use keyboard patterns instead and to try to spot these I've created Passpat. Passpat uses data files containing the layouts of common keyboards (please submit more) to walk each word through the keyboard and score the word based on how close it is to being a pattern. For now I'm taking pattern to mean keys which are next to each other, while qpalzm is a pattern picking something like that up is currently out of the scope of this project.
The way it works is fairly simple, start on the first letter and check the next character, if it is on the same key (a to A or 2 to ") score 0 as we haven't moved anywhere. If we move one character away (1 to 2 or a to S) then score 1. Repeat this for 2 characters away, 3 characters etc as far as the mappings go. I don't think there is much value going beyond a single step but the app can handle any distance of steps. If the character isn't found then add on the maximum distance (usually just one character) plus one. This gives you a total score for how far you had to move around the keyboard to type the word. Finally divide the score by number of steps (number of characters - 1) to get an average score for the word.
A score of 0 shows the password never moved off a single key, for example aAaaaAAAaaaaaA would score 0. A score of 1 means each character is a single step away from the previous, asdFDsw"34rfGh. A score of the maximum value shows that each key is more than a single step away, aDgp4ma9r.
Worked Example
As normal, I prefer examples so here is one. Lets take the password Ade3#4%U on a Mac keyboard[1]. Looks fairly random, its 8 characters and mixed character sets but lets work through it checking to see if it is a pattern. I'll be using the Mac keyboard for this with mappings for just single steps which means we score 0 for same key, 1 for key next door and 2 for any other key.
| Last Key | Current Key | Score | Description | Running Total |
|---|---|---|---|---|
| A | d | 2 | More than the single key away so score 2 | 2 |
| d | e | 1 | Single key away so score 1 | 3 |
| e | 3 | 1 | Single key away so score 1 | 4 |
| 3 | # | 0 | 3 and # are the same key so score 0 | 4 |
| # | 4 | 1 | Single key away so score 1 | 5 |
| 4 | % | 2 | Single key away so score 1 | 6 |
| % | U | 2 | More than the single key away so score 2 | 8 |
After 7 steps the running total is 8 so average this - 8/7 - gives a pattern score of 1.14285714286. This shows a password that looks fairly random, Ade3#4%U, is actually pretty much a keyboard pattern.
Hopefully that makes sense, basically the app works out the average distance of movement between keys while typing.
Install / Usage
The app has been written and tested in Ruby 1.9, it probably won't work in 1.8.x but should work in 2.x.
No extra gems are required so it should run on a vanilla Ruby install.
Use --help to get full usage instructions:
./passpat.rb --help
passpat 1.0 Robin Wood (robin@digininja.org) (www.digininja.org)
Usage: passpat.rb [OPTIONS] ... PASSWORD_FILE
--layout x, -l x: use the layout file specified. No default is set so this
must be specified
--list-layouts: show the available layout files
--help, -h: show help
--verbose, -v: verbose messages
PASSWORD_FILE: the list of passwords to check
Running it is simple, give it a layout file to use and a list of passwords to analyse:
./passpat.rb --layout uk pattern_sample.txt
Password: asdfghjkl
Total score = 8
Number of moves = 8
Pattern score = 1.0 out of 2
Password: apeofmsk
Total score = 14
Number of moves = 7
Pattern score = 2.0 out of 2
Password: aqwsxcdef
Total score = 8
Number of moves = 8
Pattern score = 1.0 out of 2
Total passwords processed: 3
Overall pattern score 1.3333333333333333 out of 2
Total length zeros found: 0
Total length ones found: 2
Download
Passpat is released as part of the Pipal github repo.
If you aren't sure what you are doing with github just click the ZIP button on the approximately middle left and that will give you a zip file which you can decompress and use as you would the versions below.
Analysis
I'm planning to run this against some of the password lists I've ran Pipal against to find average scores and I'll be posting up the results as they are generated. Something I think I might spot is dumps that have been taken from sites or apps which are primarily used through mobile devices. As mobile devices are not the easiest things to type on I think people will naturally chose patterns just to make entering easy.
Once I get a few more layouts then running different ones against the same dumps may also reveal interesting results.
All these have been analysed with a UK keyboard.
- phpBB
Total passwords processed: 184344
Overall pattern score 1.7017217768424548 out of 2
Total length zeros found: 285
Total length ones found: 3083 - Hotmail
Total passwords processed: 8930
Overall pattern score 1.7343977280864893 out of 2
Total length zeros found: 30
Total length ones found: 103 - LinkedIn
Total passwords processed: 2950516
Overall pattern score 1.720141081248872 out of 2
Total length zeros found: 303
Total length ones found: 27680
We Need More Layouts
The more keyboard layouts Passpat has the better it will work, please submit more. The ones I'd like to see are:
- US
- Dvorak
- Australian
- Any non-western keyboard, Thai, Japanese etc.
If you are interested then have a look at the UK keyboard file in layouts/uk.rb, this is fully documented and a good place to start. If you need any help just let me know.
Feedback/Todo
As with Pipal, the initial release is unoptimized. I'd like to get a working tool first and find out what features people like, dislike or would like to see added. If you would like to contribute speed improvements or new features feel free to submit pull requests to the github repo.
Something else I'd like to add is the ability to sort the results based on their scores. The problem with this is that I would have to cache all the results in memory before sorting then displaying. With large dumps this could take a lot of memory which is something I'd like to avoid. I'll have a think about it.
A CSV export may be useful as well, that would allow import into a spreadsheet so you can sort and analyse the results yourself.
Credits
To everyone who has supported Pipal and who has helped me put this together.
Thanks BruCON
This is the second of my tools sponsored by the BruCON 5x5 award.
[1] Using this as I found a nice image of one to illustrate with.
