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:

HASH CRACK CHALLENGE Hash #2 has been cracked by @lakiw. Congrats to our winner and thanks to everyone that participated! It was a bumpy ride but a lot of fun to create and host. Thanks again to everyone and look for the final write-up in the coming days!
— Netmux (@netmux) September 1, 2018

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-!@#$%^&*=?[](),.;{}:+

One Time Grid used in the contest

Or a 3x26 grid filled with random words:

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:

— Netmux (@netmux) September 1, 2018

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...