Tuesday, February 14, 2017

Password Maths Hurt the Brains

Every now and again I find myself figuring out the answers to some math questions related to passwords.  The answer usually revolves around me writing the equation on a napkin and then punching the numbers into my cell phone calculator and then moving on with my life.  I finally got around to making a generic spreadsheet that does all the heavy lifting for me, more on this later.

One of the fundamental tenets of cryptography is that the strength of the cryptography needs to outlive the usefulness of the data being encrypted.  For example, transactional data that has a useful lifetime of a few minutes or less doesn't need to be encrypted at the same strength that something that needs to remain secret for 20+ years.  We are specifically talking about hashed passwords that are used for a variety of things from logging into a system to protecting documents.

Most of the questions revolve around cracking passwords with the latest technology.  These numbers tend to move around quite a bit, but there have been some benchmarks posted with hashcat and multi-gpu rigs.  This gist has numbers from a rig of 8 NVIDIA GTX 1080 cards from Sagitta (https://sagitta.pw/) running benchmarks for Hashcat Beta 3.0. Mucho Kudos for posting those numbers, as I'm using this as the basis for my calculations... more on that later on... first some math...

Password Calculation Basics

UPDATE - I like to be as technically correct as I can when it comes to stuff I put out.  I want to thank @scoobzt for correcting me here on something I overlooked.  Keyspace = CharacterSetLength ^ PasswordLength.  So in all of the following, the word 'Keyspace' is used incorrectly and should be substituted with CharacterSetLength.  At some point in the future I will get around to updating the images below...

It all starts with a basic equation, shown below.

In this equation, there are 4 variables we can solve for, Hashrate, Time, Keyspace, or Password Length.  Now, we know the values for Hashrate (from the gist posted above for the various hashing algorithms) so in reality we are solving for one of the remaining three values.

Solving for Password Length

Since Password Length is an exponent of Keyspace, we need to use logarithms to get the answer.  

It is worth noting that the base of the logarithm is immaterial, so we will use the typical 10 as the base.  You could use natural logarithms and the numbers will be the same.  Yay math!

Solving for Password Length yields:

Solving for Keyspace

Solving for Keyspace size (in characters) involves solving for the Password Length root of the left side of the equation as shown below.

Solving for Time

Solving for Time is the most straightforward of the bunch since it is simple division of the original equation

Let's talk about hashing algorithms

Various hashing algorithms perform differently based on a number of different factors from the age of the algorithm to salting to brute-force cracking resistance (increasing the rounds of encryption required or making the algorithm require a lot of memory to run, etc)...  A discussion of these topics are beyond the scope of this post.

The benchmark mode for Hashcat provides a hash calculation rate for only a single hash, so cracking multiple hashes will naturally degrade the performance.  However, for the numbers I am using, I took the aggregate numbers from the gist and averaged it by 8, namely the number of cards provided.  I also added 10% to assume some measure of overclocking or some other sort of efficiency.

Ok, so what?

So why is this at all interesting?  

First, I often field questions from customers relating to passwords and how often then should change them.  There is a lot of numbers thrown around, but not a ton of explanation as to why those values are chosen.  Doing the math makes some of these discussions easier.

Secondly, when developers have to choose a hashing algorithm, once again, there is often a lot of noise regarding what they should choose.  Providing some real numbers can help guide the decisions appropriately.

Thirdly, sometimes you just want a napkin calculation regarding how quickly you can brute force some password for whatever reason...  

The moment you have all been waiting for...

Here is the link to a google spreadsheet which does the math for you.  You will need to make a copy of it to be able to edit it. Notes:
  • Generally speaking, both the 'password hash type' and the 'keyspace' are selectable values from a list on the second page (except when keyspace is being solved for).  
  • The values in the green cells are what are being solved for
  • Hashrate gets looked up based on the hash value
  • Yes, symbols have 33 values, don't forget the 'space' character...
  • No, I didn't use anything other than plain US ASCII characters
  • These numbers should be considered highly optimistic, YMMV
  • You can generally edit the following values unless they are being solved for: number of GPUs, length of time (days), length of password

Thanks to Andrew for helping make the spreadsheet pretty...