So, the ”The Best64 Challenge” just ended. I only discovered it a couple of days ago (on IRC), but decided to take a shot. If you are not familiar with the challenge, you should click the link for more information before you read further.
In the challenge you were provided with a dictionary and a list of hashes to crack (the famous phpbb password leak). The challenge was to come up with 64 rules that would crack the largest number of hashes from this list.
Note that this is very different than the more useful challenge of “come up with the best 64 rules in general”. (However, I think it would be difficult to set up such a challenge.)
I thought of the challenge as three separate tasks:
- Generate (good) rules
- Measure how good the rules are
- Pick 64 rules that combined will match the largest possible number of hashes
I decided to collect all the rules I wanted to measure, in a database1).
First I looked at the hashcat wiki and “manually” added the simplest forms of all the available functions to my database. I thought simple rules had a potential to be very effective by themselves, but I would also need them for a later scheme to combine rules with themselves.
I added ”:”, “l”, “c” and so on. For functions that require parameters I added several simple rules per function, e.g. “x12”, “x23”, “x34” and “x45”. In addition, I used a PHP script2) to more easily add rules like @a, @b, …, @A, @B, …, @0, @1, …, @., @!, for functions like @. I used a Passpal analysis of the cracked phpbb hashes to figure out which symbols where most frequently used, which password lengths, cases, etc I should focus on. (Note that the Passpal analysis is for a dump of non-unique cracked passwords - so it's not a perfect source.)
The Passpal analysis also prompted me to make rules adding and mangling the base word “phpbb” since this was a frequent password in the dump, but not in the dictionary.
Secondly I added all of the rules that are packed with hashcat (in the rules folder). Someone took the effort to put them there, so I might as well measure them!
Thirdly I generated millions of random rules with hashcat, using the –generate-rules, –debug-mode and –debug-file switches. I then wrote a script3) to filter the results, so that when hashcat was done many hours later generating and executing millions of rules, I could add the ~500 best rules to my database.
After measuring all the rules I had gathered in my database I took the top 100 rules and combined them with themselves to get 10000 new rules. After this, I did the same thing for the best 400 rules (except for the rules I had already covered). I did this in two separate exercises because I was concerned I wouldn't get through measuring more than 100000 rules before the challenge would end.
This was a pretty straightforward step. I wrote a PHP script4) that would, one by one, take an unmeasured rule from the database, run it on hashcat, and record (in the database) which hashes where matched by that particular rule. This script was running continuously up to when the challenge ended.
I wrote another script5) that would search the database and find the rule that had matched the greatest number of hashes. I would then delete (in a temporary fashion) that rule, and the hashes it had found to avoid getting rules that overlap. I would repeat this until I had the 64 “best” rules.
This may, however, not be the best way of doing it. When I pick out a rule that matched 4000 hashes and then delete that rule and the corresponding hashes, I lose the opportunity to find a combination of two other rules that together might have found a lot more if I had not picked that first rule. (This may be a poor and confusing explanation. TL;DR: There might be a better way of doing this step.)
Running this script right before the challenge ended got me 64 rules that cracked 22670 passwords which was good enough for 1st place in the challenge.
The scripts I've posted are a mess and were never intended to be published, nor viewed by others. I have not cleaned up or checked the scripts prior to publishing them. Viewer discretion is advised!
I've continued to work a little bit on the challenge even after it ended. I took the 20000 best of my previously generated rules and added all the rules other people had submitted. My latest 64 best rules recovers 22774 or 12.01% of the passwords, which so far is good enough for 1st place in the post-challenge challenge.
Here is my calculation of the best 80 rules, which recovers 24176 passwords.
This chart shows the individual progression for all competitors. Based on submissions data given to me by superjames.