Sunday, August 21, 2022

More Password Cracking Tips: A Defcon 2022 Crack Me If You Can Roundup

 “We do not learn from experience... we learn from reflecting on experience.” 

-- John Dewey

Introduction:

KoreLogic's Crack Me if You Can (CMIYC) is one of the oldest as most established password cracking competitions. Held every year at Defcon, it serves as a great way to pull together password enthusiasts from all over the world and provides a shared use-case that drives password cracking tool development throughout the rest of the year.

This year I competed as a street team and managed to finish in 12th place:



Now that I've had a week to look back on things, there certainly are strategies where I could have done better. The first is with my cracking setup. I had two systems I used. My primary cracking system was still my laptop running an Ubuntu VM utilizing WSL on a Windows 11 install. My secondary system was the computer I described setting up in this blog post.

Primary Laptop:
CPU: i7-8640U CPU
RAM: 16 GB
Storage: 500GB SSD
 
Desktop Computer:
CPU: Intel i5-7600k, 1 processor; 4 cores
RAM: 16GB
Storage: 500GB SSD
GPU: GeForce GTX 1070

I really didn't do a good job of splitting my work between both these systems and making sure that my limited GPU was always working. For example, I had a bad habit of running JtR sessions on my desktop computer. Long story short, one week later I have a lot of ideas for future projects to improve my cracking skills, and I'm super excited to start working on them, which is the real benefit of competing in contests like this. Rather than go through a blow for blow recount of the contest, I'll instead try to highlight a couple of tips and lessons I learned along the way.

Core Contest Techniques:

Before diving into this write-up, I HIGHLY recommend reading my previous write-up for the CrackTheCon contest which is available here.

I'm going to skip most of the techniques covered there, but I will say they all applied to the KoreLogic contest as well. It really surprised me how much I referred back to that article when I was competing in this contest.

Contest Overview:

At a high level the contest consisted of cracking a variety of encrypted files, each of which would have individual hashes to crack. For the street teams, the password to crack the encrypted files were fairly simple, so the real challenge there was getting your tooling setup properly to handle those files. 

Once the encrypted files were cracked, the unencrypted files could be opened up to reveal a set of very quick to compute hashes. As someone who doesn't have a lot of compute resources to throw at the problem, I really appreciated the fact that the hashes were so fast! Cracking these hashes was all about trying to figure out the base words used to construct them, as well as the mangling rules that were applied. One thing I will say is that the selection of mangling rules Korelogic picked made "loopback" style attacks significantly less effective than the CrackTheCon contest. Don't get me wrong, loopback attacks were still very powerful! But as a player I really needed to analyze the passwords and figure out the underlying mangling rules vs. using loopback as a crutch.

Long story short, I thought that KoreLogic outdid themselves when it came to creating a fun challenge. I thought the contest had a good difficulty scaling to make it approachable to a wide variety of players while still providing areas of growth and frustration to more experienced players.

Tip #1: Make use of John the Ripper *2John utilities to crack encrypted files

Password cracking programs don't need to use the entire encrypted file. Just think about it; Would you really want to try to have you cracking program parse a 100 GiB file every time it makes a guess? What cracking programs really need is a "hash" to make a guess against. To extract that "hash", and to save it in a format that password cracking programs can utilize, John the Ripper comes with a large selection of helper programs in the /john/run/ directory which are identifiable by the '2john' suffix. You can see this below:


The main challenge is to figure out which helper program you want to use. For example, here is me running pdf2john to extract the password hash from the list23-ThisYearsWorst.pdf challenge:


Rather than having it print out to your screen, I'd recommend piping the output of this into a file which you would then load in as the target hash file for your cracking program. One important thing: If you are cracking multiple encrypted files at once, you can store all of these hashes in the same file, just like with any other John the Ripper hash format. Many of these hashes are also supported by Hashcat too, so once you extract them using the 2john helper utilities, don't feel like you have to stick to using John the Ripper to crack the hashes.

Tip #2: Make sure you compile John the Ripper with all the optional libraries to enable cracking encrypted files.

One downside about the flexibility that John the Ripper provides by being able to compile and run it on just about anything, is that it will gladly compile without certain features and cracking modes being enabled if you don't have the correct libraries present when building it. This can be very hard to diagnose after the fact beyond a "For some reason JtR doesn't seem to recognize a particular hash type" style errors.

This happened to me in the previous CrackTheCon contest where I couldn't get John the Ripper to crack an encrypted Zip file. Luckily for this contest I realized what was going on and was able to fix it, but I really need to update my JtR install instructions here with the new information. 

That being said, here are all the additional libraries I needed to have before running './configure' to build John the Ripper (with Ubuntu 18) to enable support for cracking encrypted files used during the CMIYC contest:

sudo apt-get install libz-dev, bzip2, yasm libgmp-dev libpcap-dev libnss3-dev libkrb5-dev pkg-config libbz2-dev zlib1g-dev libcompress-raw-lzma-perl

Most of these libraries were specifically for cracking the 7zip and zip files. The perl library was for being able to successfully run 7zip2john.pl.

What this process really highlighted for me is that I really should create an Ansible Playbook to configure a system to run John the Ripper. Going back through all my write-ups in the past to figure out the different dependencies is no fun, and causes a lot of problems when I accidently miss one of them. Unless I get distracted, watch this space as I'll probably end up posting about that Ansible playbook here, and posting it to github.

Tip #3: Save your John the Ripper rules in an external file

Let's face it, John the Ripper's default config file has grown way too large and unwieldy to effectively edit during a password cracking competition. Instead, I highly recommend including your custom rules in an external file to make it easier to quickly find the rules you want to edit or modify. Another advantage of this approach is if you upgrade your copy of John the Ripper, and the config file changes, your old rules will still be saved.

The first step to do this is to include a link in your john.conf file to your custom .conf file by inserting the line:

.include <FILENAME_OF_YOUR_CONFIG_FILE>

Here is a snapshot of my john.conf file I used for this contest:


 And here is a subset of the rules in my custom "cmiyc.conf" file for targeting challenge 20 hashes:


You'll notice I still have individual rule sets in my custom configuration. This way I can perform quick cracking runs to figure out new rules, (or pipe the output to other John sessions. See Tip #4), and then have longer runs to perform on new dictionary words that I later identify.

Tip #4: Use the --stdout and --pipe options to combine multiple cracking rules

In the screenshot above of my rules for targeting challenge 20, you'll see similar blocks of rules where the only different is the first mangling rule, (either nothing, 'c', or 'u'). 'c' stands for Capitalizing and 'u' stands for UPPERCASE. The proper way to handle this would be to leverage John the Ripper's rule preprocessor to try combinations of different rules. The rule preprocessor is one of those killer features that JtR has but Hashcat doesn't. For example you can try multiple rule types, (such as capitalization and uppercasing), by including them between brackets []. For example:

[cu]

 Here is a screenshot of that in action:


Still, there are times when you have a larger set of rules you quickly want to apply one or more additional mangling rules to. One of the easier ways to to this is to pipe one instance of JtR or Hashcat into another instance of your cracking program of choice.

The format for doing this with both JtR and Hashcat is slightly different. With JtR, the base generating instance will have the '--stdout' flag in place of a hashfile. You can then pipe '|' the results into another JtR instance that has the '--pipe' flag instead of a wordlist. Note: You will want to use the '--pipe' command and not the '--stdin' command so that the rules of the second instance are applied to every word sent to it. For example:


You can also pipe guesses into Hashcat instead of John the Ripper. This is a very powerful technique because you can take advantage of John the Ripper's rule preprocessor, (or features such as its better Incremental Markov mode, or built-in Prince mode), but still have Hashcat take advantage of your GPUs when cracking hashes. All you need to do in Hashcat is not enter in a wordlist file and it will automatically accept guesses from stdin. This tends to work better if you also have a large number of mangling rules in Hashcat to help keep those GPUs of yours busy since you want to limit the amount of time transferring information from your CPU to the GPU. Aka if you can transfer a limited number of base "words" from the CPU and expand them via additional mangling rules in the GPU, you'll achieve a higher guess per second rate. Below is a screenshot of using this approach. Ignore the '--force' option as I took the screenshot on my laptop vs. my desktop which I normally run my Hashcat sessions from.


Tip #5: For password cracking competitions, perform web searches on "interesting" words

This was the piece of advice I wish I could build a time machine and send back to my past self. I really didn't do a good job of this during the contest. This is despite the fact that Saturday night I finally googled some of the words for challenge #20 and found that creating wordlists from articles discussing a high schooler hacking the Homecoming queen prom vote were extremally effective. In fact, I had the biggest jumps in my score thanks to finding those articles.


This is an area ripe for tool development. Admittedly it likely won't have much real world applications. But for contests, having a tool or process to automate the identification of sources of wordlists would be super helpful. In my head, the tool would take the following approach:

  1. Use the PCFG trainer to create an input wordlist of the base words in cracked passwords
  2. Identify words that weren't in the "top 500 English words" or in John the Ripper's "password.lst" wordlist
  3. Perform a google search and identify results that contained [all/most] of the words to identify possible sources of the wordlist
  4. Scrape the sites and build a custom dictionary.
Who knows, maybe I'll get motivated and have this done before next year's CMIYC?

Tip #6: Use Linux's 'alias' command to make your commands shorter

I'll admit I don't always do this, (for example see all of the screenshots above), but rather than type the full path for John the Ripper or Hashcat, you can use Linux's 'alias' command to link to them. For example:

alias john=/mnt/c/github/JohnTheRipper/run/john

alias hashcat=/mnt/c/tools/hashcat/hashcat.bin

With the above, now you can simply type 'john' or 'hashcat' to invoke them. Note: This works better than trying to add the John the Ripper or Hashcat directories to your command path as John the Ripper specifically gets weird when you do that. This probably won't help you crack more passwords, but it is a nice quality of life improvement, especially if you have different directories you are maintaining for contest hash lists and dictionaries.

Tip #7: Modify the PCFG's multiword detector to identify shorter words

Of course I need to make a new tip utilizing the PCFG toolset! The PCFG trainer is a really powerful tool to create input dictionaries from cracked passwords. During this contest, one thing I noticed from the passwords I was cracking was that KoreLogic added a large number of two/three letter prefixes/suffixes to the base word. For example, here is some of the mangling rules I started using.


One problem I had utilizing the PCFG trainer on these passwords was that its multiword detector enforced a minimum length five characters long for detecting base words. This was to reduce false positives. Or to put it another way, if you are parsing 60 million passwords, if you reduced the minimum base-word length to three characters, everything would look like a multiword!

The difference during a competition is that your training list is not 60 million passwords long (unless you are doing really, really well!). Therefore it was helpful for me to modify my code to detect multiwords that were only three characters in length. I eventually plan on releasing a patch to the PCFG toolset to make this a command line option, but until then you can make the changes yourself here in the code:


Conclusion:

As I continue to reflect on this contest, I'll probably keep adding to the list of tips above. Even as I write this conclusion other ideas are popping into my head (such as using the online version of Microsoft OneNote to pass documentation and commands between different computers). But I want to conclude by saying I hope these blog posts are helpful, and that I really wanted to thank the KoreLogic team once again for running an amazing contest.

Tuesday, May 3, 2022

Password Cracking Tips: A CrackTheCon Roundup

“It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something.”― Franklin D. Roosevelt

CrackTheCon, a password cracking contest run by CynoSurePrime, just finished. I competed as a Street team and I was really impressed. This was a well run contest, and I felt was very friendly to new and experienced password crackers alike. At least from a player's perspective, the infrastructure was rock solid, there was a great variety of challenges, and the difficulty level had a good gradient. Thanks to everyone who helped put this contest together!

My computer setup for this challenge was limited. I performed all my cracking on one laptop with no GPU support. You read that right, I was rolling old school with a pure CPU cracking session. Because of that, my primary password cracking program was John the Ripper, which has a ton of features that I prefer when I can't just let HashCat burn through some GPUs. While my operating system was Windows, I used Windows Subsystem for Linux to run John the Ripper and perform analysis on the cracked passwords. You can read about how to configure JtR and WSL here.

Picture of my laptop and my cat

This lead to a modest performance of 9th place:

Score Ranking of the Crack the Con Street Teams (9th Place)

GPUs are nice, and this certainly shows it! If you have some GPUs available I highly recommend using them along with HashCat. As some backstory, I still have my main password cracker set up to run medical security capture the flag events, and I was too lazy to get it reconfigured for this contest.

Computer surrounded by infusion pumps

Therefore you should probably take everything I say with a healthy degree of skepticism. Based on the chat on Discord afterwards though I realized there's a few password cracking tips that might be helpful to share. One important point I want to stress is that anyone can make use of these tips. You don't need a fancy GPU hash-cracking monster to crack passwords. In fact, most of all my attacks were "semi-automated" with very little manual analysis of the cracked passwords. So you can apply all of these techniques yourself regardless of your past level of experience.


Tip #1: Make sure your John the Ripper build is based off Bleeding-Jumbo, and update it regularly!


Even if you normally use Hashcat, JtR is a very powerful password cracking tool that has a lot of nice "research friendly" features. This makes it an extremely useful tool to have in your toolbox. As a general rule of thumb, if I'm cracking passwords with a GPU I use Hashcat. If I'm leveraging my CPU I use JtR. The key to JtR is you need to use the Bleeding-Jumbo version of it. The "main" branch prioritizes compatibility with different architectures, but the Bleeding-Jumbo branch goes all in on features. As an example, over the last couple of months they added "duplication detection" to the early portions of a password cracking session (to help with slow or salted hashes), and performed a complete rework of the included rulesets. What I do is use Git to clone JtR from its github repo at: https://github.com/openwall/john, check out the "bleeding-jumbo" branch, and then periodically pull down updates and rebuild it, (roughly once a month). This makes a huge difference!

Picture of John the Ripper's Github site

As to the deeper question of "Why would you ever crack passwords on a CPU and not GPU", that gets more complicated... At  a high level, I do a lot of password cracking research from a researcher and hobbyist viewpoint, so a CPU based approach makes it easier to tailor attacks. The real reason though is I don't own a massive cracking setup. From a training perspective, this means even if you only have a Raspberry Pi, you can pretty much recreate all of the techniques described here. That being said, sometimes the features of John the Ripper still outweigh the speed that a GPU provides, and at the very least it's a good tool to run on parallel on a VM or research computer while running longer GPU sessions with Hashcat on your main cracking box.


Tip #2: Use the '--loopback' option to leverage previously cracked passwords in your rules


The clickbait title was going to be: "This one simple trick is like a cheat code for password cracking competitions!" That's not much of an exaggeration. Full disclaimer, this technique probably resulted in around 50% of my successful password cracks in the CrackTheCon competition. I'd periodically wander over to my laptop, and feel l33t by hitting the enter key to kick off a new loopback session. So if you only follow one of these tips, this is the one to pay attention to.

As to the actual technique itself, John the Ripper's '--loopback' option tells JtR to use previously cracked passwords as a wordlist in a cracking session. Hashcat also supports loopback attacks as well. There's a million different names for this approach, which by itself should tell you how powerful it can be. You can further optimize this attack by specifying a different .pot file from your main one such as '--loopback=Challenge1.pot'. This can be helpful if you are keeping your .pot files separate for different challenges, (I don't actually do this, but some people might). Once you are using --loopback to generate your base words, you can then apply mangling rules to them like a normal wordlist. Aka by also adding: '--rules=hashcat'. 

What this means was that my typical cracking session would start by running fairly basic attacks to generate an initial set of cracked passwords. For example, I'd run '--incremental' to brute force shorter passwords. I'd run a quick cracking session using the wordlist 'dic-0294' and hashcat + single rules to get slightly more complicated passwords. And I'd run a quick PCFG guessing session as well. After that initial set of passwords were cracked, loopback became one of my main attacks. And as you can see from the results, it was very effective.

Now in the real world, loopback attacks while still powerful, aren't nearly as game braking as it is in a password cracking competition. Real users don't exclusively pick their passwords from a list of fungi names. But even then, loopback can still be useful to help augment your other cracking sessions. 


Tip #3: John the Ripper supports dynamic hash formants on the command line. No need to modify a kernel or look though lots of documentation!


This being a CynoSurePrime cracking competition, there was bound to be weird hashtypes to crack. This problem also pops up time in real life cracking situations where some vendor decides to roll their own password hashing function. This can be a challenge since writing your own Hashcat kernel is not a lot of fun. That's one area where JtR really shines is with their extensive "Dynamic" hash type support. You can see the main formats that JtR supports by specifying '--list=formats' on the command line. That only shows the "mainstream" formats though. If you really want to see all the various formats supported by "Dynamic" mode you can specify '--list=subformats' on the command line.

Lots of dynamic format details


There's a lot of them included, and sometimes even that is a pain to look through and remember. One feature of JtR most people don't know about though is you can specify the hash details directly on the command line. For example, Challenge2 of the CtC contest was five rounds of MD5. To crack this with John the Ripper I simply needed to specify the following command:
./john '--format=dynamic=md5(md5(md5(md5(md5($p)))))'

The single quote around format is important so that your shell command doesn't misinterpret the parenthesis (). Basically though, you can specify the hash type, and how the password ($p) is applied, along with any salt ($s) as well. Dynamic mode supports multiple types of hash primitives, so for example, with Challenge4 which was a sha256 of a md5 hash I was able to use the following command:

./john '--format=dynamic=sha256(md5($p))'

Long story short, if you ever find yourself needing to crack a weird hash type, don't forget about John the Ripper's Dynamic formats. 


Tip #4: Leverage MDXFind to identify unknown hash types


I'll be up-front. I did not follow this tip and I'm really kicking myself over it. To guess the hash types, I relied on trying the suggestions provided by John the Ripper, and when that failed, I manually tried different hashing functions using the command line dynamic mode (Tip #3). Don't be like me. If you are dealing with an unknown hash, the tool you want to use is MDXFind. You can obtain it here: https://www.techsolvency.com/pub/bin/mdxfind/. If I had followed this advice, I probably would have ranked higher as I never figured out that Challenge #5 was:
 --format=dynamic=sha256(sha1($p))

 To get MDXFind running on an Ubuntu image running on Windows Subsystem for Linux (WSL2):

  1. Download mdxfind.1.116.bin
  2. sudo apt-get install libjudy-dev
  3. sudo apt-get install libmhash-dev
  4. sudo apt-get install librhash-dev
Here is an example leveraging MDXFind to identify the hash type for Challenge #5. The passwords look like SHA256, so the command I'd start with would be:
./mdxfind.1.116.bin -h 'SHA256' -f Challenge5.txt wordlist.txt

  • -h 'SHA256': is the base hash type to use
  • -f Challenge5.txt: is the hashlist
  • wordlist.txt: is the wordlist 
And the results...
MDXFind Results

It quickly identified SHA256(SHA1($p)) in 4 seconds... Yeah that would have been nice to use.


Tip #5: John the Ripper supports mangling rules on the command line


In password cracking competitions one of the keys is to try and identify mangling techniques and create rulesets to target them. Now, I'll admit that for this competition, I mostly relied on the included rulesets (Tip #6), and using the PCFG Toolset to autodetect and create rulesets (Tip #7). A hands on approach is more effective though, but it quickly becomes annoying to have to constantly open up your ruleset file to modify it. This may sound like a minor nitpick, but your analysis time is valuable. One hidden feature John the Ripper supports is creating rulesets right on the command line. This is a huge timesaver, and in my opinion one of the killer features of John the Ripper. For example, let's say you want to duplicate a word and then add two digits to the end of it. Your JtR command might look like:
./john --wordlist=somelist.txt '--rules=:d$[0-9]$[0-]' hashlist

Key points:

  • You need to include --rules in single quotes. Aka '--rules...'
  • Your rule needs to start with ':' which is JtR's "no-op"
  • You can include multiple rules separated by a ';'. For example: '--rules=:d$[0-9]$[0-];:$[a-z]' 
This is also very useful to test the output of your rules. To do this you can feed in an single word via stdin, and then you can apply rules to it using JtR's --pipe command. So for example:
echo test | ./john --stdout --pipe '--rules=:d$[0-9]$[0-9]'

Testing JTR Rules Using Cmd Line Switches

It may seem weird, but this is one of those tricks that makes me smile every time I use it.


Tip #6: Making use John the Ripper's mangling rulesets

John the Ripper includes a ton of wordlist mangling rules. Given this contest was run by CynoSurePrime, I figured there would be heavy hashcat users on the hash creation side, so I primarily used the 'hashcat' ruleset. Aka:
./john --wordlist=somelist.txt --rules=hashcat
This runs through some of the main rules included in Hashcat such as:
[List.Rules:hashcat]
.include [List.Rules:best64]
.include [List.Rules:d3ad0ne]
.include [List.Rules:dive]
.include [List.Rules:InsidePro]
.include [List.Rules:T0XlC]
.include [List.Rules:rockyou-30000]
.include [List.Rules:specific]

Other useful rulesets (though not as useful for this particular competition)

  • --rules=phrase: Great for attacking passphrases
  • --rules=l33t: Good for attacking l33tsp33k passwords
  • --rules=ShiftToggle: Good for attacking weird capitalization
  • --rules=by-score: A good set of rules to use for fast hashes
  • --rules=by-rate: A good set of rules to use for slower hashes


Tip #7: Using the Pretty Cool Fuzzy Guesser (PCFG) Toolset


Of course I was going to mention the PCFG toolset! I just recently released version 4.3 and it has a ton of expanded documentation, plus better support for cracking Russian passwords. You can get it here:

The default PCFG ruleset is usually decent, but not great when it comes to password cracking competitions. This is because context passwords don't resemble RockYou passwords which the default ruleset was trained on. The real value is using the PCFG trainer to learn new rules and create new wordlists based on cracked passwords. The trainer does a lot of cool stuff in the backend such as multiword detection, keyboard walk identification, and other mangling rule generation. It can also be fairly effective even if you only have a couple of hundred cracked passwords.

To train a PCFG ruleset:
  1. You first need to create the training list. Adding support for JtR pot files has been on my todo list forever, but currently you need to strip the hash information off of your cracked passwords. For example, if I wanted to create a training list for Challenge #2 which was five rounds of md5 I ran: "cat john.pot | grep 'md5(md5(md5(md5(' | awk -F':' '{print$2$3$4$5$6}' > plains_2.txt" Yes this is a horribly inefficient way to do this, but it printed out all of the hashes, then only printed ones with the correct hashtype, then stripped off the hash, and then saved the results to plains_2.txt.
  2. Run the PCFG trainer on the set. For example: "python3 trainer.py -r Challenge2 -t plains_2.txt
Once you have the training set you can do a couple of things:
  1. You can run a PCFG attack against the challenge using the new ruleset. For this I recommend disabling Markov generation using the --skip_brute option. For example: python3 pcfg_guesser.py --skip_brute -r Challenge2 | ../JohnTheRipper/run/john --stdin '--format=dynamic=md5(md5(md5(md5(md5($p)))))' Challenge2.txt
  2. Another good option is to use princeling to generate a wordlist optimized for PRINCE attacks. You can also use this as a normal wordlist as well. For example, this will create a 50k word dictionary: python3 prince_ling.py -r Challenge2 --size 50000 -o new_wordlist.txt
  3. You can manually go through the generate rules file to identify mangling rules. A good option to open up is: Rules/<RULENAME>/Grammar/grammar.txt
Summing all of this up, 99% of my cracking sessions for this contest were:
  • Identify the correct hashtype
  • Run a default attack against it using the dict0294 wordlist and the hashcat rules
  • At the same time run a JTR bruteforce Incremental attack "./john --incremental=All". That's the nice thing about CPU cracking. I have enough cores I can run around three sessions at the same time on my laptop before things get really slow.
  • Run a couple of loopback attacks using the hashcat rules
  • Train a PCFG ruleset and run a PCFG cracking session until it gets to around 95% coverage. You can see the coverage by hitting enter while running it.
  • Run a couple more loopback attacks
  • Re-Train the PCFG ruleset
  • Create a wordlist using the PCFG prince_ling
  • Run a PRINCE cracking session using the wordlist and JtR
  • Run a normal cracking session using the prince wordlist and the hashcat ruleset
  • Re-Train the PCFG ruleset and run a PCFG cracking session
  • Repeat. Maybe run a longer incremental session, or try another input dictionary.

Following these steps, you too can get 9th place in a password cracking competition!

Thursday, August 1, 2019

Installing John the Ripper on Microsoft's Windows Subsystem for Linux (WSL)

"I see my path, but I don't know where it leads. Not knowing where I'm going is what inspires me to travel it." --Rosalía de Castro

Introduction:

With great regret I finally decided to retire my 10-year-old MacBook Pro as my personal travel laptop. Part of that is I'll be attending Defcon this year to help out #IAmTheCalvary and the #WeHeartHackers initiative by volunteering in the Defcon Biohacking village. Side note, if you are in Vegas, feel free to drop by and we can talk about cyber security in a clinical setting. Doctors and nurses hate passwords too!

Getting back on track, I wanted something a bit more modern to participate in this year's Crack Me If You Can Completion, as well as to play around in the various hacking villages so I bought myself a Microsoft Surface Book. The challenge was while Hashcat has a native Windows build, my experiences getting John the Ripper (JtR) running on Windows in the past have been ... troubled. That's part of why I loved my old MacBook. It just worked (sorry Linux), and JtR ran great on it. Now I could re-image my laptop with Linux or dual boot it but having Excel and Notepad++ makes my life so much better. Plus, I'm really digging the tablet. So before I went ahead and installed VirtualBox and ran JtR in a VM I figured I'd try and install JtR using the new Windows Subsystem on Linux (WSL). Long story short, it worked great and was straightforward to do, so I figured I'd share my experiences.

Other Options for Running John the Ripper on Windows

If you want to skip this guide and instead install a pre-built executable of JtR, you can obtain a relatively up-to-date version here: https://github.com/claudioandre-br/packages/releases/tag/jumbo-dev

Note: I've never run these, so I'm not very familiar with how they perform.

Other options include installing JtR using Cygwin. A guide for doing so is available here: https://openwall.info/wiki/john/tutorials/win64-howto-build

Finally, a very common option that I referenced to above is to simply install VirtualBox, and then run JtR in a VM.

Windows Subsystem for Linux:

If you are wondering what WSL is, you are not alone! At a high level, it lets you run Linux programs on Windows without having to recompile them or run them in CygWin. To steal Microsoft's own words:
The Windows Subsystem for Linux lets developers run a GNU/Linux environment -- including most command-line tools, utilities, and applications -- directly on Windows, unmodified, without the overhead of a virtual machine.
You can:
  1. Choose your favorite GNU/Linux distributions from the Microsoft Store.
  2. Run common command-line free software such as grep, sed, awk, or other ELF-64 binaries.
  3. Run Bash shell scripts and GNU/Linux command-line applications including:
    • Tools: vim, emacs, tmux
    • Languages: Javascript/node.js, Ruby, Python, C/C++, C# & F#, Rust, Go, etc.
    • Services: sshd, MySQL, Apache, lighttpd
  1. Install additional software using own GNU/Linux distribution package manager.
  2. Invoke Windows applications using a Unix-like command-line shell.
  3. Invoke GNU/Linux applications on Windows.
The mechanics of it are complicated with significant differences between WSLv1 and WSLv2. This guide was written with WSLv1, though if I get adventurous before Defcon I may try to upgrade to WSLv2.

Enabling WSLv1 and Install a Linux Distro:

The first thing you need to do is enable WSLv1 as it is disabled by default. As a fair warning, this will require a reboot.
  • There are several ways to enable WSLv1. I opted to use PowerShell. The first step then is to open an Administrative instance of PowerShell. 
  • Run the following command (ref):
    • Enable-WindowsOptionalFeature -Online -FeatureName Microsoft-Windows-Subsytem-Linux
  • Reboot your system when prompted to.
  • Once your computer starts back up, the next step is to pick a Linux distro. Open the Microsoft store and type Linux in the search menu
  • Side note: You'll be happy to know that Kali Linux is rated "E for Everyone"!

  • Important Note: All the Linux distros I looked at in the Windows Store, (including Kali), are barebones and do not include graphical desktops, or many tools or installed libraries. It's not like installing a Kali live boot image.
  • Because Kali doesn't come with any tools preconfigured, I opted to go with a base Ubuntu build. That's also partially because Kali and Hashcat in the past haven't been an ideal match, so I tend to stay away from it on my desktop builds

  • Once you install Ubuntu, you'll still need to initialize it. To do this open PowerShell again, though this time you can run it as a standard user. For Ubuntu, simply type 'ubuntu'

  • You'll be prompted to create a user account. Go ahead and do so.
  • Congratulations, you are now running Linux on Windows!

Installing John the Ripper

  • This guide was written using the bleeding-jumbo version of John the Ripper, which is available here: https://github.com/magnumripper/JohnTheRipper
  • It's beyond the scope of this guide on how to install and use Git on Windows, (I personally like GitKracken). While you can download the source-code as a zip file, I highly recommend downloading it using git to make keeping it up to date much easier. With WSLv1, it's recommended that you install the code somewhere besides your new Linux filesystem. I put it in c:\github\JohnTheRipper\. With WSLv2 that changes, but I'll cross that bridge when I try that out. You could also probably install git into Ubuntu and download it that way, but I didn't try that.
  • The next step is to install all the required libraries in WSLv1 Ubuntu. Run all the following commands in the PowerShell window above after starting Ubuntu. If you ever close your window, you can restart PowerShell and type "ubuntu" to restart Ubuntu.
  • Update your package libraries. If you don't do this, the following installs will not work, (as seen in all the errors above the command in the below screenshot)
    • sudo apt update

  • Install GCC. Select 'Y'es when prompted. The install will take a while.
    • sudo apt install gcc


  • Install Make
    • sudo apt install make
  • Install various libraries required/recommended for JtR Bleeding-Jumbo
    • sudo apt install libssl-dev
    • sudo apt install libgmp-dev
    • sudo apt install libkrb5-dev
  • Navigate to your Windows drive where you installed the John the Ripper source-code. You can access you C:\ Drive under the /mnt/c directory. Run the following command to build JtR
    • ./configure && make

  • The build process will likely take around 10-15 minutes. After it is done you should see the following. If there are any errors, something went wrong so you will likely need to perform additional troubleshooting.

  • Finally navigate to the run directory '../run/' and try to start John the Ripper:
    • .\john

  • Congratulations! You are now running John the Ripper on Windows!

Performance:

If you are curious, here is a short snipped of me benchmarking JtR on my PC. Note, this is only running on a single core. I should have also included the --fork=8, which I'll admit I didn't realize worked with the --test option before writing this guide.

Laptop Specs: 
  • Microsoft Surface Book 13 Inch,
  • Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz
  • 16.0 GB Ram
Test command: ./john --test

Benchmarking: bcrypt ("$2a$05", 32 iterations) [Blowfish 32/64 X3]... (8xOMP) DONE
Speed for cost 1 (iteration count) of 32
Raw:    6344 c/s real, 790 c/s virtual

Benchmarking: Raw-MD5 [MD5 256/256 AVX2 8x3]... DONE
Raw:    61074K c/s real, 61074K c/s virtual

Benchmarking: scrypt (16384, 8, 1) [Salsa20/8 128/128 AVX]... (8xOMP) DONE
Speed for cost 1 (N) of 16384, cost 2 (r) of 8, cost 3 (p) of 1
Raw:    280 c/s real, 35.0 c/s virtual

Benchmarking: LM [DES 256/256 AVX2]... (8xOMP) DONE
Raw:    121470K c/s real, 15241K c/s virtual




Tuesday, September 11, 2018

Configuring a Password Cracking Computer

  • “Be willing to be a beginner every single morning.” —Meister Eckhart
Disclaimer: While the reason I'm writing this is because I was lucky enough to win a new cracking rig from Netmux's Hash Crack Challenge, I want to state for the record that he never asked me to blog about it, and all of the good things I say are 100% of my own choosing and not contingent on me receiving any prize.

2nd Disclaimer: I plan on this being a "living" blog entry as I continue to update and use my new computer. Since install procedures change over time, for the record I started to perform my install on September 7th 2018. I'll try to date my entries as I write them to help anyone trying to follow this so they can estimate how useful these instructions are.

ChangeLog:
  • September 12, 2018, (rearranged sections, added MDXFind, updated installing OpenCL instructions)

September 7, 2018 (Computer Arrives):

Wow, I suddenly and unexpectedly found myself in possession of a dedicated password cracking machine! For more background how that happened, please refer to my post on Netmux's Hash Cracking Challenge here. For the record, Netmux was amazing when it came to promptly shipping my portable cracking rig and keeping me in the loop. I'll admit I was a bit hesitant to hand out my home address to professional pen-tester and password cracker I met on the internet, but I've made a lot worse threat modeling decisions in the past, (There is a story behind the first picture that gets everyone who knows and cares about me legit angry for the stupid trust I've put in absolute strangers before). Long story short, Netmux was professional in shipping the server, kept me in the loop, and when it showed up I was super excited! As some background, while I study password cracking, develop and analyze password cracking tools, and participate in password cracking challenges, I've never been willing to personally invest in a dedicated password cracking rig. Mostly I've made do with a 2010 MacBook Pro, and a Windows machine with a GTX970 that I'll freely admit spends more time running Excel and playing World of Warcraft than cracking hashes. Which is another way of saying please take all my advice with a grain of salt, and the understanding that I'm planning on using this new server for research. I'm not optimizing it as a pure password cracking rig. But also this is a way of saying that I no longer have any excuses in how much I contribute in password cracking challenges in the future! This gift has inspired me to start a few new research projects so I want to give yet another huge thanks to Netmux!!! If you see me post additional blog content in the next few months or update my PCFG cracker, please give credit to him!

A Quick Aside on my New Password Cracking Rig:

Let me first say that it arrived in perfect shape so of course the first thing I did was crack it open and look at the inside...
My new rig from Netmux
Super excited!!!
The wiring was very well done, the whole rig is water cooled, the case certainly adds hacker creds, and little things were taken care of such as having good filters over the air vents which is pretty much a make or break requirement for this cat owner. I'm *very* happy with it, and would recommend it to someone else.

As far as the specs go:
CPU: Intel i5-7600k, 1 processor; 4 cores
RAM: 16GB
Storage: 500GB SSD
GPU: GeForce GTX 1070

Installing the OS:

Netmux's cracking rig came pre-installed with Ubuntu, but I figured I might as well re-install everything from scratch. After consulting with several password cracking experts I'm lucky to know, my end decision was to re-install Ubuntu. The version I used was 18.04.1 LTS. I plan on using this server for research as well so I went with a full graphical desktop. If you are hardcore and want 100% of your machine devoted to cracking then by all means go with a server deployment, but this guide probably won't help you to much since I *love* GUIs. Spoiler alert, I recommend installing a GUI git client like GitKracken, so that's where this guide is taking you.

Building the Boot USB (September 7, 2018):
Like anyone has a DVD anymore... The very first step I took was to create a bootable USB.

Steps:
  1. You can download an Ubunto ISO from here
  2. Since I already was running Ubuntu, I could use Startup Disk Creator  to create a bootable USB drive. You can perform a search, (use the Windows key), for that application if you are running Ubuntu already.
  3. Follow the options to create a bootable USB using the ISO that you previously downloaded
Installing Ubuntu fro USB (September 7, 2018):
  1. Use multiple swear words and reboot several times until you find the BIOS option to change your boot preference to start with your USB drive. In my case it was hitting F2.
  2. Once you boot from the USB, follow the steps in the Ubuntu installer and configure it how you want.
  3. If you are going to configure full hard drive encryption, (this will be a real portable rig that will potentially be unattended in your car when you make a restroom stop, or you are worried about legal issues), this is the time to configure full hard drive encryption. Just saying.

Core OS Drivers and Important Tools for Other Capabilities:

Installing OpenCL drivers (Originally installed September 7, 2018, updated September 12):
Special thanks to WinXP5421. The following section was written by him, though I tested it on my system and made minor edits based on my experiences and formatting it for this blog
  1. Download the appropriate Opencl Drivers for your system. We are specifically looking for “Intel® Xeon™ Processors OR Intel® Core™ Processors OpenCL runtime” drivers.  
  2. Extract the archive:
    • tar -xvzf opencl_runtime*.tgz
  3. The opencl runtime requires `lsb-core` to be installed on the ubuntu machine:
    • sudo apt install lsb-core
  4. Now install the drivers:
    • Go to the intel directory that you extracted in step #2
    • sudo ./install.sh
    • Work your way through the installer answering questions as needed. The install script will complain that your Ubuntu operating system is not supported this is fine continue with the installation anyway.
  5. Let’s verify we have a working Opencl environment by installing and running `clinfo`
    • Note: clinfo was already installed on my machine, but one of the other tools I installed later may have installed it -- Matt
    • sudo apt install clinfo
    • clinfo
    • The output of clinfo should display detailed information about each CPU core you have on your system. Simply put “Lots of output = all good” If OpenCL did not install properly you will see short and specific errors after running clinfo. 
Installing NVidia Drivers (September 7, 2018):
  1. Run: ubuntu-drivers devices
  2. Select the driver from the list you want to install. In my case it was: 
    1. sudo apt-get install nvidia-driver-396
Install basic GIT (September 7, 2018):
I usually only use a command line git when something goes horribly wrong, but having it ready helps a lot when that happens.
  1. Sudo apt-get install git
Install a GUI GIT Client (September 7, 2018):
I've used a lot of git GUIs in the past. The following is purely personal preference, but I would highly recommend using a graphical git GUI if you are doing any development. Having the ability to easily view changes, manage merge requests, fork, etc, I've found to be invaluable in all my work.

My favorite git GUI of all time has been the official github client from several years ago. Unfortunately since then they re-based everything in a web layout, it completely broke my workflow. I've tried to use Atlassian's SourceTree, but after a few horribly failed merges was told to never use it again by several co-workers. I currently use GitKracken, and am very happy with it. GitKracken is not free for commercial use. I've been told to use SmartGit by several people but don't have experience with it. If you are using this tutorial for commercial use and don't have funding to pay for GitKracken please check it out. Otherwise, I've found GitKracken to be great for non-profit and personal use.
  1. Install GitKracken from https://www.gitkraken.com/
  2. Run the following command or gitkracken will never actually start: sudo apt install libgnome-keyring0
  3. Once GitKracken is installed, log in to your github account using it
  4. Now add your computer's SSH key to your github account using: File->Preferences->Authentication->Github.com->Add_SSH_Public_Key
Installing Password Cracking Programs:

Install Hashcat (September 7, 2018):
Yes there are pre-built binaries for Hashcat, but I highly recommend using the github based source code to stay up to date with all the latest changes, fixes, and features.
  1. Install Hashcat using your git tool of choice. If you are using GitKracken, import the following repo: git@github.com:hashcat/hashcat.git
  2. Full instuctions for installing Hashcat can be found at: https://github.com/hashcat/hashcat/blob/master/BUILD.md
  3. You'll need to update the OpenCL Header submodule. This can be done in GitKracken by importing Hashcat using the above link and then in gitkracken "viewing Left Hand Side" at SubModules, right clicking on the deps/OpenCl-Headers, and selecting "Create" or "Update", If you are not using GitKracken, follow the instructions listed in step #2
  4. In a terminal, select "make", and then "make install"
  5. By building from source, you can periodically pull from the Hashcat repository and re-build it to add new features before an "official" release is published
Benchmarking Hashcat With New Install, (and gratuitous plug for NetMux's Hashcracking Manual which is awesome)
Install John the Ripper (September 7, 2018):
John the Ripper is my favorite password cracking program. If you are doing any sort of academic research or tool development, I can't suggest it enough. I'll admit though that if I'm only concerned with cracking standard hashes I generally use Hashcat instead. Regardless, I'd recommend installing John the Ripper on any password cracking rig you configure. Furthermore, you really need to install the magnum-ripper bleeding edge version of John the Ripper since the base version hasn't been updated in years. New patches, fixes, and features are normally pushed weekly, so building it from source, and constantly re-building it is highly recommended.
  1. Install the following branch of John the Ripper: https://github.com/magnumripper/JohnTheRipper./
  2. Install SSL libraries: sudo apt-get install libssl-dev
  3. cd ./JohnTheRipper/src/
  4. ./configure
  5. Note: The following does not have OpenCL support. I'll try to circle back to this later to figure out how to add it.
  6. make -s clean && make -sj4
  7. cd ../run/
  8. ./john --test
Install MDXFind (September 12th 2018):
I've been told I really need to start using MDXFind so since I'm starting a new cracking platform this is certainly the right time to install it. 

A quick aside, most people might question why I need three different password cracking programs on the same computer. I'm sure it's a lot like how chefs view their kitchen knife collection. Yes they all cut, but the right one depends on what you are trying to do.

While certainly not set in stone, as a general rule of thumb I use John the Ripper for research, CPU cracking sessions, cracking file encryption "hashes", and a few other hash types that don't translate well to GPU like SCrypt/BCrypt. It also has the best support for non-English data-sets.

I use Hashcat for most GPU cracking that I do. Yes, John the Ripper GPU support has been getting more robust, but I've had better luck with Hashcat. For example, I'm cracking large lists of unsalted MD5, Hashcat is my go-to cracking program.

MDXFind seems tailored to cracking large "messy" data-sets. Think of a lot of the major password dumps that become public. It's fast and can handle data-sets going into the millions of password hashes. It also has support for cracking nested hashes which have a way of ending up in some of these dumps. Oh, and it seems to be the password cracking tool of choice for CynoSurePrime and they know a few things...
  1. Obtain the latest copy of the source-code from https://hashes.org/mdxfind.php
    • MDXFind is only provided as a pre-compiled binary so you don't need to build it. Grab the 64bit Linux variant.
    • Download and copy the file to the directory you want to install MDXFind into
  2. Make MDXFind executable
    • chmod +x mdxfind
  3. Install required dependencies
    • sudo apt install libjudydebian1 libmhash2 librhash0
  4. Test MDXFind
    • ./mdxfind 
Other Quality of Life Installations:

Install Text Editor:
  1. I like Kate. To install it: sudo apt-get install kate
  2. You might also want to install Atom which has more features. I'm hesitant to recommend it with Microsoft buying GitHub, but it is free and has a ton of features: https://atom.io/
Change Login Background (September 7th 2018):
Not really important, but I always do this because it helps my gumption level:
  1. Find a picture you want to see when typing your login picture.
  2. sudo cp Pictures/FILENAME_OF_PCITURE_YOU_WANT_TO_USE /usr/share/backgrounds/login.jpg
  3. vim /etc/alternatives/gdm3.css
  4. Find: #lockDialogGroup  background: #2c001e url(resource:///org/gnome/shell/theme/noise-texture.png) background-repeat: repeat; }
  5. Replace it with
    #lockDialogGroup {  background: #2c001e url(file:///usr/share/backgrounds/login.jpg);
      background-repeat: no-repeat;
      background-size: cover;
      background-position: center; }

Monday, September 3, 2018

Netmux's Hash Crack Challenge Writeup

"Good luck is when opportunity meets preparation, while bad luck is when lack of preparation meets reality" -Eliyahu Goldratt
This last week I participated in Netmux's Hash Crack Challenge, and this happened:

So I figured the least I could do was make a blog posting about it along with my analysis of Netmux's One Time Grids, which the challenge was based on.

TLDR/Bottom Line(s) Up Front (BLUF): 
I was lucky enough to be checking Twitter right when Netmux posted his final hint, and that was the only reason I won. As to the security of One Time Grids, they share a lot of similarities to other password books, which can be both good or bad depending on your threat model. Compared to other physically written down password books, the One Time Grid approach pushes users to stronger passwords at the expense of usability. It is *very* secure against your typical online hacker, but shares the weakness of other password books in that it may be weak against people in physical proximity you, (such as ex-boyfriends, nosy parents, nosy children, etc). I didn't find any weaknesses that could be exploited by an online attacker. Long story short, I wouldn't recommend it due to the usability issues, but if you have fun with it, feel free to use it.

What is a One Time Grid and how does that apply to the contest?
Netmux does a better job explaining it in his blog here, but it basically is a password creation book that you can buy from Amazon, available here, that provides a bunch of One Time Grids for creating and storing passwords. The contest was an attempt to crack two different raw-SHA1 password hashes generated using a One-Time-Grid. They were:
Hash1: fe0c9f335b35c45e92d5e7d07c5933b6c4c0a522
Hash2: 120c249bc0f301ef3cba7a0fcbff463aaaded486
As to the One Time Grids themselves, they are either a 7x7 grid filled randomly with one of the following 84 characters:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890-!@#$%^&*=?[](),.;{}:+
hash crack challenge one time grid
One Time Grid used in the contest

Or a 3x26 grid filled with random words:


One Time Grid Word Grid
Example word based One Time Grid. Not used in the contest
The One Time Grid used in the challenges was composed of random letters, so this blog post will focus on that. When it comes to the security of a One Time Grid though, most of the statements I'll make will apply to both unless otherwise specified.

Netmux also suggests three different ways to turn a One Time Grid into a passwords, a "basic" random grid, a "pattern" random grid, and a "scatter" random grid. Only pattern and scatter were used in the contest, so I'll focus on them, but a "basic" grid is simply a "pattern" with no bends. Aka all walks go in a straight line. Below are examples he gave for pattern and scatter on his site. Note, these examples do not use the contest One Time Grid.


Example "Pattern" Password Creation rules



Scatter One Time Grid password creation, taken from Netmux's site

Contest Start:
The first thing that should be apparent is that without the One Time Grid that a password was based on, no attack can be run that has a hope of being successful against passwords longer than 9 characters. Even 8 characters would require significant horsepower. 84^8 = 2.4 quadrillion keyspace which is quite big, even for GPUs. This assumes that the One Time Grids are generated using a true random number generator, yada yada yada, but for the purposes of this contest, no effective attacks could be started. Which is ok, because it gave me time to prep some tools and do some research.

Side note, I'll give Netmux credit that doing a "search inside" check of his Amazon One Time Grid book didn't accidentally share any of the real grids. Not that I've abused that feature in other contexts before...

First Clue: "Pattern" & "Scatter"
Sometime around this point Netmux released his first clue: "Pattern" & "Scatter". This pretty clearly indicated that the above two methods were used to generate the password, so I started to develop some scripts to generate walks of One Time Grids in anticipation of when the actual grid would be released. I originally started out investigating if I could use a custom keyboard layout with Hashcat's kwprocessor, which generates keyboard walks, but quickly realized I would have to significantly modify it to target One Time Grids. That's because kwprocessor was set up to crack 4 row keyboards vs 7x7 grids, along with some other optimizations it made for keyboard quirkiness which is great for normal cracking, but would cause problems with what I wanted it to do. So I wrote my own script, which I posted on github and is available here. It admittedly went through several rounds of improvement throughout the contest, but here is a general overview of how it works, and the constraints I added to reduce the key-space:

  • one_time_grid_walker.py only targets the "Pattern" random grids. "Scatter" random grids need a lot more information to effectively target them. I'll dig into that more later
  • The first constraint I added to it was that all "walks" had to start and end on the edge of a grid. This was based on my reading of netmux's examples and how I expected a typical user to interpret his suggestions. Examples of "valid" and "invalid" walks can be seen below.
Valid walk of contest grid
Invalid walk of contest grid
  • The second constraint I added was a walk could not double back on itself or cross a part of itself. In the above example, a walk could no go, "8oyIyo8". This admittedly was a naive assumption on my part, but I made it once again to reduce the keyspace and based it on my reading of the examples given.
  • The third constraint that I struggled with but felt when coding up my script that I needed to make was to limit the maximum size of a walk. As the maximum length increased, the keyspace also did, which would cause problems later when running a combinator/Prince attack. Len8= 4081, Len9= 7268, Len10=12011, Len11=19131. This on its own would be trivial, but when you start combining multiple walks together, can be significant. For example, 19131^2 = 365 million. 19131^3 = 7 trillion. This admittedly was where I probably made my biggest mistake, prematurely optimizing this.
  • Skipping ahead a bit, I later optimized my approach further to limit the number of "bends" that a walk could make. If I only allowed one "bend", (or change in direction), there were only 575 possible walks for a current grid. This allowed combining many different walks practical. I felt for a typical user following the advice given, this represented what I would expect to see them do.
As far as weaponizing this goes, I was tempted to use the Prince attack, but when talking with Chick3nman, he gave the helpful advice that if you didn't need the optimizations that Prince uses, a straight combinator attack with Hashcat was much faster for easy hashes like raw-sha1.

And then I pretty much waited. Well in reality I tried some attacks against the sample One Time Grids to bide my time, but I didn't expect to crack the first hash. I was a bit cocky though, and expected that I'd crack the first hash within minutes of it being released.

Second Clue: One-Time Grid attached below
Yes! The target one time grid was finally released. I'll admit I said a few choice words that it was released as a picture though, which led to some squinting and me questioning if letters were lower or uppercase. Oh, and also one typo when entering it into my code that I nearly missed, but luckily Hops pointed it out to me. In any future contests, it would be really nice if items like this could be released as text that allowed copying/pasting.

Another challenge I ran into was that I wasn't at my cracking computer, so couldn't run any effective attacks myself. Luckily Chick3nman agreed to run my script and try to crack the first hash for me. Unfortunately he wasn't successful. I want to stress that was my fault since he was running my scripts and attacks.

There was a lot of head scratching, and variations of walks plus the suggested PIN and random word, but long story short, even when I got back to my computer and ran attacks myself, I was completely ineffective at cracking that first hash. I'll admit it really annoyed me in a good way like any fun problem does. I want to give a huge shout out to Boursier Etienne, who actually managed to crack it first. I'd love to hear what Boursier did.

Third Clue: Birthday Paradox
I may have uttered a few more choice words over this clue. I'm well versed in the birthday problem, but that doesn't seem to be applicable to One Time Grids. Yes some individual characters appear more often than others, but the heart of the "scatter" problem is a "Choose X with no replacement" problem. Aka, the first character has 49 different options. The second character has 48 different options. The third character has 47 different options. And so on. This is not related with generating collisions between multiple inputs as far as I can see.

Fourth Clue: Are all cell values equally probable?
I see where Netmux was going with this. For a scatter password, if you were modeling it, cells 3/26, 6/25, and 7/23 all contained periods ".". If you selected any of them when generating a password guess, it didn't matter which order you picked them which can reduce the effective keyspace. The problem comes when trying to weaponize this info. I did some back of the napkin calculations and if your guess generator took into account the "choose and no replacement" aspects along with the "several characters show up several times", you could reduce the keyspace by roughly a factor of 10 for the password lengths I thought the password might be. This sounds great, but one problem I've run into many times before, is that more effective guess generators take time to generate guesses. So while a script that I coded might reduce the keyspace by 10x, it would probably take 100x more time to generate a guess against a raw-sha1 hash then just using a custom mask. Therefore trying to optimize my solution would actually make it worse.

Now admittedly someone could take the time to create a custom solution in Hashcat or John the Ripper that would be fast, but that wasn't going to happen in the time this contest ran. More importantly though, for a 10 character password generated by a "scatter" method, it didn't matter. The keyspace was so large that even a 10x speedup wouldn't be enough to make it practical.

Fifth Clue: str(PIN)[:-1]
This hint was a good clue that the PIN, minus the last character of the PIN, was part of one or both of the passwords. Aka "71997" could be found in the password. This was good info to have when trying to crack the password, but I'll admit I was a little annoyed since guidance to apply mangling rules like this wasn't in the instructions for using One Time Grids. By that I mean, it's totally within the bounds of someone doing this in real life. In fact, I'd recommend it, as it explodes the keyspace of One Time Grids. But based on the instructions I wouldn't expect a typical user of One Time Grids to do mangling rule like "remove the last character of the PIN". Now, most of my password cracking techniques are based on targeting "typical users". If everyone was unique I'd be the worst password cracker out there. But people typically follow standard behavior patterns which makes password cracking possible. I'm biased, but I like to see that reflected in contests. Needless to say though, this wasn't enough information to crack either one of the two password hashes.

Sixth Clue: scatter_cells + str(PIN)[:-1]
This clue said that the PIN-1 would be at the end of the scatter cells password, which was helpful without being useful. They keyspace for likely scatter cells passwords was so large that knowing any additional mangling didn't make a difference.

Seventh Clue: Use seven of the possible ten "repeats" to mask your way to the other half of the scatter_cells solution.
This provided a lot of useful information without being actionable. It said the "scatter" portion of the password was 14 characters long, with 7 of those characters being a repeat item, and the other 7 being unique characters. This meant 7 characters had 10 possible values, and the other 7 had 29 possible values. What's more, the second set was a pure chose with no replacement, so the 7th character would technically only have 22 possible options. The problem once again was making use of this information. For example, I didn't know which positions would take from either set. So for a 14 character password, that increases the keysize by 2^14 = 16,384, which is a problem because the current mask setups for JtR and Hascat don't support that kind of selection. In retrospect, I realized I could have created a script to generate all 16k masks and feed them into Hashcat, but during the contest that didn't occur to me. Long story short, this was the point where if given six months it's possible someone could have cracked the second hash, but it was unrealistic to do it in a day or two.

Eighth Clue: Hash #2 = print(len(scatter_cells + str(PIN)[:-1])) = 19
While this made explicit that there were no other mangling rules or surprises for the second password hash, it didn't make the problem more crackable compared to the previous clue.

Ninth Clue: No cell values have been reused in the composition of scatter_cells.
“q$*????????)wc” + str(PIN)[:-1]
This is where I got really lucky. I managed to check Twitter at the exact right time and saw the following tweet by Netmux:

Therefore I was at my computer and ready to go for the final hint. When he posted it, I quickly created the following mask attack using hashcat:

hashcat64.exe -m100 -O -a 3 ..\contests\netmux\netmux.hsh -1 IA9GV8oyILM.!03WKH+epP{TxJz3hbu\? q$*?1?1?1?1?1?1?1?1)wc71997

By Netmux giving me 6 of the scatter characters used I only had to bruteforce a 8 character password, and there were only 32 possible characters per posision, making this significantly easier than a Lanman password hash. All told, it took me around 5 minutes to crack the password hash, which admittedly was a heart pounding five minutes since I was sure other people were running the same attack as I was. I was sweating the whole time and my adrenaline was pumping. As proof of the timing to run the attack, here is me re-running the cracking attack on my system. It took 9 minutes to exhaust the whole keyspace, but I got my crack around five minutes in.

Cracking the 2nd Hash. Path information and the actual hash plaintext redacted.
For comparison, I have a single NVidea GTX 970 in my computer. Not even a Ti. Really what it comes down to was that I was very lucky, to the point where I feel a little bit guilty about it. In the future I'd advise contest creators to publish set times when they will release hints so that way everyone is on an even field when it comes to making use of this information.

Conclusion:
First of all, I'd like to give thanks to Netmux for putting on this competition. I had a lot of fun and I hope this blog post points that out. There's many "contests" out there but putting my time into this was way more enjoyable than dealing with the drama of hacking Bitfi. Also dealing with a new type of bounded problem like One Time Grids was very interesting.

I'd also like to thank Chick3nman, Hops, and Royce Williams, for lending cracking hardware, giving advice, and all the heckling ;p

As to the security of One Time Grids, let me back up a bit.

When doing any threat analysis or security review my first step is to categorize the adversary. A good rule of thumb brought up by James Mickens is the "Massad vs. not-Massad" categorization. I highly recommend following that link because the write-up is hilarious, but it boils down to if you are worried about the Massad, well there's nothing you can do because you are going to f***ing die. But if your adversary is someone else, there's effective strategies you can take to protect yourself. Now admittedly there's variations of this, but basically if you are worried about nation level attackers, then don't use One Time Grids. If you are worried about typical hackers though, One Time Grids can be extremely effective. I'll freely admit that I'm not the best password cracker out there, but the fact remains that if Netmux hadn't given me the One Time Grid, along with 11 characters of an 19 character password, I'd never have cracked it. Also One Time Grids are such a niche technique that even after this contest I don't see myself incorporating the lessons learned into any of my normal cracking strategies.

There's two major problems I see with One Time Grids though. The first is they don't produce memorable passwords. If you don't want to write the passwords down, you'll need to take your book with you, which is a pain. And if you do write your passwords down, I'd recommend using a traditional password manager instead. Most of which have built in random password generation tools which are just as effective as One Time Grids for creating strong passwords.

The second problem is that One Time Grids share the same issue as many other password "books". They have the potential for horrible failure if your adversary is someone you know and/or love who has access to it directly. Ex-boyfriends/girlfriends/husbands/wives are the big ones, but nosy children or parents also pop up. I'm always very sensitive to this threat vector since while dealing with an abusive ex is bad, dealing with an abusive ex who has access to your e-mail and facebook is way worse. Password management programs can help in this regards, but written down books are problematic. Yes, someone could avoid writing down their "patterns" for One Time Grids, but that doesn't scale as having unique passwords for sites is more important than strong passwords in my opinion. You have no idea how sites are storing their passwords, so the best way to minimize your risk of a site storing your password in plaintext is to use different passwords for different sites.

I guess what I'm trying to say is I'm a big believer in hike your own hike. If you enjoy using One Time Grids, I haven't seen anything to caution against it. You are probably way more secure than most people who don't do anything special. While I'm biased to suggest standard password management programs like 1password, I'll readily admit that programs like 1password have usability problems too. If you really want to have a physical password book, free options include diceware, but if you like the idea of One Time Grids, quite simply, I'm not going to crack those passwords without a whole lot of help.

Bonus Snark

 While doing research on One Time Grids, I came across the following on Amazon and my first thought was, "I bet whoever owned that copy previously was *really* important!!!" /jk

Only $4.67 for shipping though...