Brute forcing passwords

So in my last post I talked briefly about the importance of a good password policy, and there are a number of reasons this is important. I wanted to talk a little bit more about one specific attack vector and why I believe this is such an important consideration for software developers.

The stolen database

Many people don’t consider brute forcing of passwords to be a significant issue. These days many (but not all) systems use retry limits, delays, captcha’s and other techniques to stop any significant number of attempts to login to a system. This ignores the damage someone can do with direct access to a password database. This could be either through a direct attack, leaked details, or (most commonly) an attack or theft from within an organisation.

Once our attacker has the database they can then attempt to break any protection we’ve added using brute force. This means using raw computing power to try every single possible variation of a password until we find the correct hit. Brute forcing is going to be the subject of this blog post.

Passwords not only protect critical data, they are critical data.

To quickly dispel a second myth many people also believe that the damage someone can do with a password is still limited. This should also be considered false – even if your system is the most vanilla in the world we, as software developers, have a duty to protect the data we are trusted with at all costs. And the password itself should be considered to be critically important information.

Unfortunately, as we all very well know, a very large number of users still use the same username and/or password across multiple systems. And even if the username is unknown there will usually be enough personally identifiable information to trace a user back to other accounts. So, if nothing else, we should strongly consider a users secret password to be one of the more important pieces of information we are trusted with.

A quick note on encryption and hashing

For the remainder of this post I’m going to talk about scenarios where a password is hashed, which is to say it is stored in such a way that it cannot be reversed. This is done through a series of algorithms (formulas) that produce a uniquely identifiable pattern of characters. Verification is done by hashing any subsequent password attempt, and then comparing it to the original value. The same input will always produce the same output.

I won’t deal with breaking an encrypted password – encryption of passwords is considered bad practice these days, and should not be done. Unlike hashing encrypted passwords can be reversed. This makes breaking them easier, and opens up additional attack vectors.

I’ll also note that the security of hashed passwords can (and should) be improved by using a salt. A salt is a known string of characters that can be added to a password before it is hashed. This increases the complexity of the hash, helps guarantee uniqueness and also prevents other types of attacks (such as through a rainbow table).

Brute force

Right, lets get straight down to it. Lets assume our attacker has a stolen database, but doesn’t know too much about it. The passwords are hashed, and may or may not be salted. Our attacker has chosen to try and brute force some passwords, so they can learn more about the system.

In this case our attacker has a single, fairly normal computer available to them – this is not government level cyber warfare. Imagine an average IT enthusiast with an axe to grind. They are running a standard 64-bit Windows 7 system, with a standard CPU and a NVidia gtx580 graphics card. Choose any other reasonable system components – they don’t really matter as these days the graphics card is the interesting component.

You see, in the pursuit of the latest 3d graphics hardware designers did something very interesting and useful. They created a piece of hardware capable of running a very high number of calculations in parallel. This is required to render all the different parts of a moving 3d image, but is also very useful if you want to try and run a large number of concurrent calculations… such as those used in hashing algorithms.

Our attacker is also using a free piece of software called hashcat. This application allows a user to test a variety of different hashing algorithms against a database, and takes advantage of our graphics card above.

The numbers

So, how many passwords can we generate at once, for our brute force attack?

Hash algorithm	Hashes per second
MD5	1894 million
SHA1	723 million
SHA256	328 million
SHA512	105 million
MSSQL (SHA1)	667 million
WPA/WPA2 (PBKDF2)	43 thousand

Note – that’s per second. And with some simple hardware or software upgrades we can push that up further. And this doesn’t even take into account the other optimisations I can achieve using smarter strategies, targeted password lists, or any other information our attacker learned about the system!

But these are pretty abstract numbers – we need some context to talk about these. So here is a table that shows relative password strength, and how they would hold up under different conditions:

Possible characters	Characters in password	Possible combinations	10,000/sec	100,000/sec	1,000,000/sec	10,000,000/sec	100,000,000/sec	1,000,000,000/sec
10	6	1 million	1.5 mins	10 seconds	Instant	Instant	Instant	Instant
26	6	308.9 million	8.5 hours	51.5 mins	5 mins	30 seconds	3 seconds	Instant
26	8	200 billion	242 days	24 days	2.5 days	348 minutes	35 minutes	3.5 minutes
52	6	19 billion	23 days	2.25 days	5.5 hours	33 minutes	3.25 minutes	19 seconds
52	8	53 trillion	169.5 years	17 years	1.5 years	62 days	6 days	15 hours
62	6	57 billion	66 days	6.5 days	16 hours	1.5 hours	9.5 minutes	56 seconds
62	8	218 trillion	692 years	69.25 years	7 years	253 days	25.25 days	60.5 hours
86	8	2.9 quadrillion	9,448 years	948 years	94 years	57 years	346 days	34 days

Lessons

There are a few important takeaways from this. Firstly, use a damn good hashing algorithm. There are too many damn companies still using MD5, and the story above alone should be enough to discount it – let alone that it has a number of other flaws to it as well.

Secondly, a good password policy is important – we can see broadening the range of allowable characters helps increase the password pool, but adding length to passwords is an even more effective way of driving up the complexity!

Thirdly, keep the password database safe! And make sure you keep your own passwords safe and secure (consider using a password vault!). Because if a database is taken it’s likely just a matter of time until the attacker finds users, who despite best efforts, have used bad passwords. And we might not even realise the data was stolen in the first place.

Image Credit: Chad Cooper