The Password Arms Race Heat Up

A Radeon GPU, image by Eastwind41
via Wikimedia Commons 

Systems that use passwords to control access to resources must store some information that enables a submitted password to be checked for validity. Large organizations often manage tens of millions of passwords. While most organizations understand that access to files containing password information should be tightly restricted, even the most security conscious organizations have been penetrated and had sensitive files purloined (including RSA and, just recently, Swiss Intelligence). 

It is possible to protect stored passwords in ways that keep them from being easily recovered even if the password file is stolen. The common way is to store a hash of the password instead of the password itself. Done right, this can provide a high degree of security. Done wrong, it is almost worthless. For example, Jeremi M Gosney  and a colleague were able to crack 90% of the 6.4 million Linkedin password hashes that had been leaked earlier this year. (http://securitynirvana.blogspot.com/2012/06/final-word-on-linkedin-leak.html) The LinkeIn password hashes were not protected by salt. (See my earlier essay on the importance of salt). 

Still further improvement in the ability to attack password reposetorie has been presented by Gosney at the Passwords^12 Conference just held in Oslo, Norway. Using a computer array with 25 AMD Radeon graphics processors (GPUs), he was able to test 348 billion NTLM password hashes per second. (http://securityledger.com/new-25-gpu-monster-devours-passwords-in-seconds/) Gosney's slides are available online at http://heim.ifi.uio.no/hennikl/passwords12/www_docs/Jeremi_Gosney_Password_Cracking_HPC_Passwords12.pdf

Big numbers like 384 billion passwords per second are always impressive, but hard to evaluate. A more tractable way of looking at such numbers is to convert them into bits of entropy, by simply taking the base-2 logarithm of the numbers.

Here are the password testing rates Gosney gave for different password hash algorithms and their equivalent in bits of entropy per unit time:

• NTLM 348 G/s = 38.5 bits of entropy per second
• MD5 180 G/s  =  37.4 bits of entropy per second
• SHA1 63 G/s  = 35.9  bits per second
• LM 20 G/s   =  34.2  bits per second
• md5crypt 77 M/s = 26.2 bits per second
• bcrypt (05) 71 k/s  = 16  bits per second
• sha512crypt 364 k/s = 18.6  bits per second

The above numbers show how many bits of entropy are attachable per second. To get values for an hour, day, month or year of attacks, add the following numbers to the bits per second values above:

• per hour, add 11.8 bits 
• per day, add 16.4 bits 
• per month, add 21.3 bits
• per year, add 24.9 bits 

If you have an estimate of the entropy strength of your password and know the hash system used to protect it, you can get estimate how long it will take for Gosney's machine to crack your password. on average.

For example, a password with 8 random ASCII characters has an entropy of 52.5 bits. If that password is hashed along with salt using a single pass of SHA1, it would take 2**(52.5 - 35.9) = 2**16.6 seconds or about one day to crack using Gosney's machine.  And that's assuming a truly random password--something that looks like }wg?3Fy6 --not your dog's name plus a digit and a special character.  Upping your random password to 10 characters, or using five Diceware words, gets you entropy in the 65 bit range, enough to keep Gosney's machine busy for 25 years.  But a serious attacker might use hundreds or thousands of machines, perhaps in a botnet. Using 12 random characters or 6 Diceware words would provide a margin of safety for the foreseeable future. 

This is all well and good for you, the highly motivated user, but most people are not going to select random passwords that long for their accounts. With the data results above, it is hard to pin the blame on users who pick weak passwords or share passwords among several accounts. Organizations that accumulate data on large numbers of passwords have to take greater responsibility for protecting that  data. The good news is that the same growth in computing power that allows attacks on stolen password hashes also give organizations tools to thwart the attacker -- if they choose to use those tools. 

In my next postings, I'll talk about what can be done now and in the future to protect password repositories.