Cheap GPUs are rendering strong passwords useless

What do you love about LastPass? What do you hate about it? Tell us why you like it, why you don't, and why.

Moderators: admin, anatoly_LP, chantie, robyn, JoeSiegrist

Cheap GPUs are rendering strong passwords useless

Postby Lars » Thu Jun 02, 2011 1:09 am

Interesting and scary ZD-net article
ZD-net article wrote:Think that your eight-character password consisting of lowercase characters, uppercase characters and a sprinkling of numbers is strong enough to protect you from a brute force attack? Think again!
The average length of your passwords should be at least 15-16 characters long.. Once again I'm thankful for LastPass. :D
Lars
 
Posts: 2169
Joined: Wed Jul 14, 2010 10:48 pm
Location: So Cal

Re: Cheap GPUs are rendering strong passwords useless

Postby quotidian » Thu Jun 02, 2011 2:03 am

>1 billion/sec, wow, that's more than I expected, but I think the title is slightly hyperbolic, this is not the death of passwords.

It should I hope be the death of using fast hashes for password authentication though. If it's possible to compute 3 billion hashes per second, then you need to come up with a hashing algorithm that takes a thousand times longer to run, and then you can only brute force 3 million hashes per second.

For example, lastpass uses 100,000 rounds of PBKDF2. If computers get 10 times faster they can just up that factor to a million and it will still take the same amount of time to brute force. At various times the number of bits being used behind the scenes will probably need to increase, but that can be transparent to users.

Of course, I don't trust every site on the internet to do this, so yes, hurray lastpass :)
quotidian
 
Posts: 180
Joined: Fri Nov 26, 2010 9:40 pm

Re: Cheap GPUs are rendering strong passwords useless

Postby postman99 » Thu Jun 02, 2011 11:02 am

PASSWORD SECURITY: A New Approach for Creating Super Strong *AND* Easy-To-Remember Passwords: https://www.grc.com/haystack.htm
postman99
 
Posts: 11
Joined: Wed Oct 13, 2010 7:34 am

Re: Cheap GPUs are rendering strong passwords useless

Postby Israel » Thu Jun 02, 2011 11:42 am

This should be noted that they're cracking NTLANMAN md5 hashes, windows logins. Virtually unencrypted, I was cracking these on my pentium II ten years ago in a matter of hours.

SHA-256 with salting and key obfuscation is an order of magnitude slower - these figures don't apply.
Israel
Site Admin
 
Posts: 1475
Joined: Tue May 04, 2010 9:40 am

Re: Cheap GPUs are rendering strong passwords useless

Postby kilgry » Thu Jun 02, 2011 12:27 pm

I've updated my Password Recovery Speeds (Moore's Law applied) chart to reflect these new findings (see attached). The chart now goes up to 100,000,000,000 attempts per second. The chart is in PDF.

Yes, 15-16 is a good length but it appears 13-14 would do for most as well.

Overall, I don't think there is much reason to panic. But, it is impressive to see such high numbers of attempts per second being achieved.

Am glad to see LastPass requiring 100,000 rounds though.

BTW, can we suggest that LastPass password generator (in "simple" view) generate passwords of at least 12 characters? The current 8 character length is much too small.
kilgry
 
Posts: 817
Joined: Sun Feb 13, 2011 5:41 pm

Re: Cheap GPUs are rendering strong passwords useless

Postby Israel » Thu Jun 02, 2011 1:55 pm

Those numbers of attempts per second wouldn't be sustained with SHA-2... this is for SHA-1 only.
Israel
Site Admin
 
Posts: 1475
Joined: Tue May 04, 2010 9:40 am

Re: Cheap GPUs are rendering strong passwords useless

Postby kilgry » Thu Jun 02, 2011 2:32 pm

Hi Israel,

Is this because of the weaknesses in SHA-1?

The article makes it sound like they are testing 33 billion passwords a second, which I would assume is the same between hashes unless rounding is used (time required to run each password test).

Just showing my ignorance here.
kilgry
 
Posts: 817
Joined: Sun Feb 13, 2011 5:41 pm

Re: Cheap GPUs are rendering strong passwords useless

Postby Israel » Thu Jun 02, 2011 5:02 pm

Israel
Site Admin
 
Posts: 1475
Joined: Tue May 04, 2010 9:40 am

Re: Cheap GPUs are rendering strong passwords useless

Postby quotidian » Thu Jun 02, 2011 10:42 pm

Israel wrote:Those numbers of attempts per second wouldn't be sustained with SHA-2... this is for SHA-1 only.


Cryptographic hash functions are generally designed to be as fast as they can be given an acceptable level of security. This is because one of their primary uses is signing large documents such as certificates, binaries, etc.... It's also why on their own they're completely unsuitable for password authentication. Something designed to be fast enough to sign multi-megabyte binaries, will never be slow enough to defeat a brute force attack against a 10 character input.

As far as I'm aware, SHA-256 is no different than SHA-1 in this regard. The benchmarks I can find seem to back this up: http://www.cryptopp.com/benchmarks.html.

SHA-256 in the context of a good key stretching algorithm such as PBKDF2 is a whole different story, but unless I'm mistaken the hashes Lastpass lost prior to switching to this are theoretically as vulnerable as anything else.

kilgry wrote:Hi Israel,

Is this because of the weaknesses in SHA-1?

The article makes it sound like they are testing 33 billion passwords a second, which I would assume is the same between hashes unless rounding is used (time required to run each password test).

Just showing my ignorance here.


This is not because of the weaknesses in SHA-1. The (still only theoretical) weaknesses in SHA-1 relate to better-than-brute force attacks for generating collisions. This is just a standard brute-force attack. That said, all hash algorithms are not the same. Those numbers were for MD5, which is about 3 times faster than SHA-256, but 1 billion / second is still a big number.
quotidian
 
Posts: 180
Joined: Fri Nov 26, 2010 9:40 pm

Re: Cheap GPUs are rendering strong passwords useless

Postby quotidian » Sun Jun 12, 2011 2:44 pm

In looking into Bitcoin, I think I came across good numbers for brute forcing SHA-256. Mining for bitcoins essentially involves solving the equation:

SHA256(SHA256(input)) < value

Similarly the lastpass auth hash is computed as:

SHA256(SHA256(username + password) + password) = auth hash

So brute forcing the two should take roughly the same amount of effort. There are some benchmarks of GPU implementations of Bitcoin here: https://en.bitcoin.it/wiki/Mining_hardware_comparison

A good GPU seems to get you 500-800Mhash/s, with multi-gpu setups surpassing a billion hashes per second. My own ~2 year old mid-range card was good for about 100Mhash/s.

There is still the open question of what Lastpass did with their login hashes before storing them prior to the breakin. If it was simply one more SHA256 with a salt, then it would take 50% longer.

Israel, I realize this is somewhat sensitive given that these hashes may be in the wild, but could you give us a rough estimate of how many additional rounds of hashing occurred before you persisted the hashes to your local DB?

Thanks
quotidian
 
Posts: 180
Joined: Fri Nov 26, 2010 9:40 pm

Next

Return to Feedback

Who is online

Users browsing this forum: pezza and 8 guests