Miloslav Homer

The humble password needs no introduction. It's a basic security tool: I know this secret/text/code, you don't. Therefore my stuff is secure unless you figure this string of characters out. Password policy is a similarly famous concept. To ensure your password is strong → follow these simple rules (or not so simple - check out this funny game).

But what exactly does this mean for an attacker? Can we measure the attacker’s effort in dollars? I have an idea.

If you already have the basics of passwords and cracking down, feel free to skip to Renting GPUs and The Cost of Time. If you trust that I got the data correct (check out the source code), feel free to skip to Policy Complexity Calculations to see the conclusions.

Password Storing Basics

If nobody ever told you:

DO NOT STORE PLAIN PASSWORDS ANYWHERE!

Of course, there are caveats, the most notable being the password manager.

That being said, use a hash function with salt.

Salt is a small random value that you generate when setting the password for the first time. Append this salt to the password and run the whole string through a hash function. Store the hash value and the salt. To verify the password, you rerun this process - append the salt, and apply the hash function. If the hashes match, you know your user entered the correct password, and as a bonus, your database doesn’t contain those passwords at all.

Not all hash functions are created equal - there are some specifically designed for password storage such as Argon2id, scrypt, bcrypt in this order of preference.

I'd avoid MD5 and SHA256 as well - you'll see why shortly.

Password Cracking Basics

Let’s do a quick and incomplete overview of password attacks:

• Brute-Force: trying all of the possible combinations. That’s what I am doing here. The slowest approach, but it’s simple to implement.
• Dictionary Attack: since passwords are often created by humans, we can restrict ourselves to known words and their combinations (+- some variations). Much more efficient than the brute-force approach, but it’s harder to implement well.
• Password spraying: an honorable mention, instead of guessing the passwords you’d take a list of most common passwords and you’d find usernames that use them. Ridiculously effective, especially a variant that uses previously leaked passwords to these accounts from other sources. But I am getting distracted now.

Since I am using the brute-force approach I am arguing for an upper-bound cost of the attack as it’s the most time-consuming one of them.

There are generally two ways of brute-forcing passwords:

Online

You need to interact with the service (usually a webpage) to get information about password validity. You have many obstacles in your way:

• Calls over the network are “slow”: around 0.5s per password attempt is unacceptable for a large dataset,
• Lock-out policies: most sites implement a lock-out that temporarily stops you from attempting more passwords after several failed attempts. There are many ways of implementing this, from a hard block, through slowdowns to a captcha (another slowdown),
• Web Application Firewalls (WAFs): in this case, it’s more of the same - after several attempts you are not able to make guesses anymore. Your IP might even get permanently blocked.

That being said - unless you somehow hack the site to get the user database for offline usage (or find it publicly available), you are condemned to this slow and risky approach.

Offline

Also referred to as password cracking.

If somebody gave you a set of hashes and salts, you have greater options. No more networking, no more WAFs, you might do whatever you like. But reversing these hashes is still a tall order.

Since the use case for this is obvious (look at all these entries that need cracking!), there has been quite some progress in these methods and tools. The single most important speed improvement was to involve GPUs for computation - you need to do a lot of relatively parallel and relatively simple computations.

There are also highly performant tools for this process taking advantage of the cutting edge research: Hashcat and John the Ripper are the most famous. A side note: Argon2 is not yet supported in hashcat - using it adds a nice layer of obscurity as the best tool is not able to crack these hashes right now.

If you have unsalted MD5/SHA1 or NTLM hashes (or perhaps others as well, these are the most common though), you migth try your luck with online databases that contain bilions of cracked passwords such as Crackstation, Onlinehashcrack and many others.

Renting GPUs and The Cost of Time

Calculating operating costs for a custom server with a lot of GPU cards (referred to as rig from now on) is complicated. It's much simpler to calculate renting costs for these rigs in big cloud companies such as AWS, Azure, or GCP.

In some cases (a single job you need to finish) it might even be a cheaper option than building a cracking rig on your own (+ a power plant required to operate it).

Benchmarks

You somehow need to figure out the rate of hashes you can go through in a second to get a feel of how costly is to try N options.

I have searched for a while and I was able to find somewhat recent benchmarks only for AWS. We thank Javy de Koning for the benchmarks - see repo.

As an example of how to read the benchmarks - take a look at the p5.48xlarge instance. There are 8 NVIDIA H100 80GB HBM3 GPUs and then we get a list of different hashes - the last line is the accumulated performance. I've picked the available previously discussed hashes for a somewhat short example. The following table is sorted by highest hash speed:

As you can see - there is a ~300000x speed difference between MD5 and bcrypt!

Then I stumbled upon these benchmarks from onlinehashcrack.com. Then I searched further, and I've found a set of benchmarks from Chick3nman.

The idea right now is to get the data for the respective cards and search for rentable rigs that contain these cards. I need the data over time in a usable format - let's get coding.

Pricing

The second piece of the puzzle is the cost of renting the rigs.

Getting all of the data is technical busywork, not really that interesting for the purposes of this article. Nevertheless, you can find the source code here, and some comments below.

AWS

In AWS they call the GPU instances the Accelerated Computing EC2 instances.

Azure

In Azure they call them GPU optimized VMs, pricing.

I am going to give kudos to Microsoft here - I found their pricing pages and docs easiest to use.

Also, their lowest prices are spot prices - very cheap instances with interruptions. Hashcat can handle interrputions and you are getting your notification - I am going for this option in calculation.

GCP

In GCP that's GPU Platforms, pricing.

Disclaimer

I am fully aware that there are some differences between the benchmarked cards and the rentable cards (e.g. A100 benchmark with 40GB memory vs rentable A100 with 80GB memory). There are also missing benchmarks - the relevant VMs are just omitted. Science is hard and I am doing what I can (without spending a lot of cash to run the benchmarks).

Policy Complexity Calculations

So now we know how many dollars we are paying for trying out N hashes. All that's left to do is a simple combinatoric excersize to figure out how many hashes we need to go through to get a hash that complies with our desired policy.

Yes, I am deliberately forgetting about time costs - assume either that our cloud providers have a boundless supply of GPU rigs or that we are very, very patient.

Examples

Different Hashes with Password Length 8

Let's start with the most common policy known to me: 8 characters, include upper case, lower case, numbers and special symbols (this set is referred to as ASCII printable sometimes). Comparing several hashes mentioned earlier:

We can see the drastic difference between the recommended hashes and not recommended hashes.

Nearly anybody can afford to crack the 8-character policy on weak hashes (MD5, SHA1, NTLM..), but you do really need a solid investment to try this approach on the better hashes such as bcrypt or scrypt.

As a side note, we can see that having the hashes with salt has pretty much the same time complexity. The benefit is in not having the hashes already cracked and widely available.

Lenght vs Password Complexity

MD5 is still out there, so let's use that. Also, let's start taking a look at the costs when increasing password lengths from 6. The same rules apply - using the ASCII printable character set, we can see that the price for the length of 8 matches the table above.

We can see that the cracking price rises fast with every added character (yes, it's exponential growth). Maybe we can get away with a simpler approach, let's review the same MD5 hash with only lower-case letters:

As we can see, even with a simple hash function, and even with a small character set, we can still create strong passwords by adding length. Related XKCD.

Still, for completeness sake, let's take a look at different character sets, MD5, length 12 (chosen to prove a point):

Including special characters does help. Moreover, it encourages usage of password managers, but that's a topic for another article.

Conclusion

Now you have an idea of how costly it could be for an attacker to break your password policy in the case of a hash leak. You might even be tempted to try it yourself - in that case: good luck with the cracking!

The biggest benefit is to use a tailored hash function (and salt!) such as Argon2id, scrypt or bcrypt, if you are not able to do that, then you need to use lengthier passwords (12 - 15 characters and more) with a diverse character set. Moreover, if your password has a length of 8 characters or less and it’s hashed with MD5 or SHA-*, consider it cracked immediately after it’s leaked.

Use a good policy that reflects the value of the asset you are protecting - your users needn't remember the passwords as they should use password managers, anyway.