Comments

(newest first)

bendra | Tue, 17 Jul 2012 22:04:51 UTC

Hello,

Interesting article and comments!  One thing this has me wondering is: if GPUs are so darn good at hashing, is there anyone who is using GPU-based hashing on the server to log users in?  It would take quite a load off the server, particularly if you are using a slow adaptive hash no?

Michael | Thu, 14 Jun 2012 09:45:17 UTC

@Cory House:
Eh, the salt and algorithm should not need to be secret. The password should. If the channel is safe enough to transmit a plain text password, it is also secure enough to transmit a hash of that password.

If the channel is being sniffed, it is also better that a hash is discovered, which is only valid for a single website, due to the salt, while a password is likely valid for many websites.

Cory House | Wed, 13 Jun 2012 15:37:24 UTC

@Michael - Login should use https to assure sending the plain text password is safe. The password must be hashed on the server to avoid exposing the hashing algorithm and salt in client-side code.

Michael | Tue, 12 Jun 2012 15:32:57 UTC

@PB | Fri, 08 Jun 2012 09:08:17 UTC 
"Could it be changed even sooner than that by generating salted hashes of the stored hashes? Then when someone logs in you can simply try both?"

Shouldn't the hash and not the password be transmitted over the internet? This also distributes the computation issue to all user computers instead of a single webserver.

Poul-Henning Kamp | Tue, 12 Jun 2012 10:27:54 UTC

@Anon:

Please see the SHARCS conference presentation linked to in the article for stats.

Anon | Tue, 12 Jun 2012 00:05:48 UTC

"Recent research has managed to get a GPU processor very close to 1,000,000 md5crypt operations per second ... and that means that any 8-character password can be bruteforced in approximately two days."

Your calculation assumes an 8-character lowercase a-z password, not "any 8-character password". If you assume that your password can be made from the 52 upper and lower case letters, the 10 digits, the 32 keyboard symbols, and spaces, your time goes from 2 days to 200 years.

shackrock | Sun, 10 Jun 2012 15:36:59 UTC

I always have used this webpage as a guide: http://elbertf.com/2010/01/store-passwords-safely-with-php-and-mysql/ - which seems to cover all of your statements from the article, agreed?

Nate | Sun, 10 Jun 2012 04:37:30 UTC

If you had an existing salted, SHA1 password database, couldn't you convert everyone instantly to a new combined algorithm that first computes the salted SHA1 and then passes it through bcrypt using the same or (even better) a second salt.  Then, assuming your system is un-compromised, you'd have a very secure password hash without requiring users to log in or change passwords.

Any opinions on whether that would work? Seems like it would in my opinion.  I'd rather not wait for users to log in/change passwords to ensure the password db could not be compromised by brute force.  The one I'm dealing with is already salted, but uses SHA1 and I'd like to take it to the highest standard.

Ben | Sat, 09 Jun 2012 12:37:52 UTC

"The 6.5 million hashed passwords in all likelihood represent far more users than that, because everybody who chose "qwer5678" as a password shares a single entry in that file."

So how are the password statistics concerning this leak even possible when no other information but those pw hashes are available?

Mike | Sat, 09 Jun 2012 07:38:16 UTC

@Matt:

In your calculation where you came up with 600,000 years, you used the ops/sec of md5crypt (1,000,000/sec)

LinkedIn was not using md5crypt, but SHA1, which can be brute forced much faster. 

You are also assuming a single computer.  Presumably the attackers would have a botnet with tens of thousands of computers or more.

RobD | Sat, 09 Jun 2012 01:29:50 UTC

No salt was their achilles heal.  The salt also should be using the full character set.  A 16 char salt plus the password would make rainbow tables unusable except for a single user and brute force would take a long time and be worse if itterated.  Most people are saying the password file looks old.

So itterate your salt+password.
Use a full character set salt to extend the password.

Andrew | Sat, 09 Jun 2012 01:15:42 UTC

I worked for a healthcare technology company once where all the production servers and databases shared a *single* password which was kept in a text file in the code repository. Even though I pointed out how stupid this was to the CTO he remarked "we trust our employees" and nothing changed. Probably LinkedIn had people who were horrified at what was being done but the leadership didn't care.

Jon | Sat, 09 Jun 2012 00:50:08 UTC

@Ross - My co-workers and I were discussing this. One of their salts was actually stored in a file on the production machine, and never entered into the database, nor into version control, to keep the system from being compromised if either was touched by malicious entities. 

A particularly paranoid solution might be to store one solely in the DB, one solely in the VC, and one solely in production. Even within an organization, it is possible to do the 'Missile Launch Keys' thing and spread your salts wide.

Ross | Fri, 08 Jun 2012 23:01:53 UTC

No matter how strong you make the hash, there is another fundamental problem: storing all of the hashes together in a single system.  An attacker who finds a single hole gets access to all the treasure.

Nuclear missile silos required two keys turned by two people to fire the missile.  What if you could incorporate a two-party system into hash storage? Cut the hash in half, and store it in two different systems, physically separate, and designed and built by two independent teams using diverse techniques.  Thus an attacker would have to compromise two different systems to gain any usable data.  Yes, this would be a lot of added complexity and expense, but since we have reached the level of storing credentials numbering in hundreds of millions, perhaps it is justified.

Basic Security | Fri, 08 Jun 2012 22:46:09 UTC

Basic password security these days:

When users select a password, check whatever the user submitted against a set of common password dictionaries - ideally, apply some rules to it (733t speak translation, add numbers or symbols to the beginning or end, capitalization games, etc.). This should help prevent P@$$w0rd (8 characters, upper case, lower case, numbers, symbols - it must be a great password!)

Also note that attacking SHA1, a computer full of top end GPU's can crack in excess of 15 billion (15,000,000,000) single SHA1 hashes per second, for about $3,500.

Bill | Fri, 08 Jun 2012 21:53:28 UTC

The LinkedIn blog says, 'Finally, our current production database for account passwords is salted as well as hashed, which provides an additional layer of security.'.

This sentence is odd.  The passwords themselves are not discussed, but their "production database", whatever that is, is salted now.

decora | Fri, 08 Jun 2012 20:05:16 UTC

Because management at Linkedin obviously didnt value security. They could easily have hired a person to try to analyze their own system and find faults in it. This is an extremely basic one. They would rather spend the money on whatever they spent it on (executive bonuses? advertising?) It went IPO in 2011.. how much of their income went to hedge funders and investment banks instead of into a kid programmer or two who could have found this flaw in a week and explained the fix?

Jay | Fri, 08 Jun 2012 19:45:25 UTC

A coder at one of my former employers salted the passwords but he did it after the hash was applied. I let him know repeatedly it wasn't a good idea. If an expert mentioned it in a public forum perhaps it might carry more weight than just my words...

David F. Skoll | Fri, 08 Jun 2012 18:25:18 UTC

@Barry: Your "easy salting" is not that secure.  The User-ID is likely to be known, so its hash can be precalculated.  If the secret value leaks out, that can be precalculated too, so you're back to simply breaking the hash.

For more secure salting, you want something like:

hash(password | random_salt | secret_salt)

where the pipe symbol denotes concatenation.  That way, the attacker can't easily precompute anything.

David F. Skoll | Fri, 08 Jun 2012 18:22:25 UTC

I no longer have a LinkedIn account.  When I did, the associated email address was [email protected] (which was randomly generated).  My 16-character randomly-generated password was not in the list.

Interestingly, on May 10th 2012, the email address [email protected] started receiving spam attempts, in spite of the fact that *nobody but LinkedIn* was supposed to know it.

From this, I believe that LinkedIn was compromised at least as early as May 10th and that the attackers have login names as well as passwords.

Barry | Fri, 08 Jun 2012 18:17:58 UTC

Easy salting:
Hash the user ID, hash the password, hash a third value known only to the application, exclusive-or the three, store that.

Poul-Henning Kamp | Fri, 08 Jun 2012 16:50:06 UTC

@Daniel:  Look at md5crypt source code, none of current MD5 attacks are relevant.

@Matt: yes I did: I will not rule out such rainbow tables.

Remember criminals have access to 100.000+ machine botnets.  1GB each place ("WINDOWS_UPDATE.DAT") is a LOT of storage.

Matt | Fri, 08 Jun 2012 16:24:21 UTC

@Mike

Poul commented above "I certainly rule out that they [rainbow tables] have reached a depth where such a password might be therein".

I wonder whether maybe Poul dropped a "cannot", i.e. wrote the opposite of what he meant.

The password I have is 11 characters long, lower, upper and a number. The rainbow tables I found appear to be limited to passwords up to 7 characters long, i.e. no use:

   http://freerainbowtables.mirror.garr.it/mirrors/freerainbowtables/sha1/
  
but maybe there are bigger tables in circulation. How long does it take to crack the password I described, i.e. 11 characters, with such a table?

anon | Fri, 08 Jun 2012 16:19:27 UTC

@Matt: I read somewhere that the attackers had changed the login page...

Aleksey Korzun | Fri, 08 Jun 2012 16:01:38 UTC

What they basically did is salted hashes now and disabled all of the current passwords so the users are forced to update their 'encrypted' hashes with new salted hash.

The thing that worries me, while that is great.. how did the attackers get the data in the first place? What else were they able to obtain? LinkedIn is not really disclosing any of that information at this point (as far as I'm aware).

Daniel Turner | Fri, 08 Jun 2012 15:17:45 UTC

Not only are rainbow tables a very feasible attack on MD5 hashed passwords, it should also be noted that there are now ways of attacking an MD5 hashed password that does not rely on just simply generating the MD5 of evey possible password.

Flame was recently found to have an entirely new attack against MD5 coded into it.

Mike | Fri, 08 Jun 2012 14:25:54 UTC

@Matt -

I think one thing that you're missing is, as was mentioned- rainbow tables. These tables usually already exist for most hash functions (I'm sure they're available for SHA1). They took a long time to create initially, but that upfront work has already been done.

Since they were unsalted, you can snag a rainbow table offline for SHA1 and go to town. There are many good articles talking about them, but he's the obligatory CH: http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracking.html

Christian | Fri, 08 Jun 2012 13:32:53 UTC

I believe that those of you asking "why not just accept both passwords" or thinking that you can "upgrade" the storage of the old passwords are mistaken for at least one obvious reason: the cat's already out of the bag; the unsalted, trivial hashes are already out there. If you transparently allow people to use either password or upgrade the hash without enforcing a password change, their account is still extremely vulnerable. An enforced password change is absolutely necessary to invalidate the compromised password data.

On the other hand, the "upgrade password hashing at next login" could be perfectly viable if the service had not already been compromised.

Ralph Corderoy | Fri, 08 Jun 2012 11:39:33 UTC

It would seem the password database could be upgraded instantly if the method is added too or already stored as it can record that an additional hashing step is being used to the existing hash in the DB, e.g. if md5crypt was used for all of them then md5crypt+scrypt would mean the next password entered by the user should be run through the old md5crypt and that result put through scrypt.  If it matches then the more direct scrypt version can be written back to the DB.

scrypt is aimed at being stronger than bcrypt.  http://www.tarsnap.com/scrypt.html

Matt | Fri, 08 Jun 2012 11:38:49 UTC

@Rowan: I'm reducing it compared to 11 random 8 bit characters, but I'm not reducing it compared to the 64 bits of (hopefully) random data I started with.

Perhaps your underlying point (and Poul's) is that 64 bits is not enough, especially when there is no salt.

How much is enough? I'm not an expert in the field, but taking the figure in the article above, i.e. "1,000,000 md5crypt operations per second ... means that any 8-character password can be bruteforced in approximately two days." and guessing that the calculation was

   26 ^ 8 = 208827064576                               // number of uppercase 8 letter passwords
   208827064576 / (1000000 * 3600 * 24) = 2.4 days

then using the same reasoning for 64 random bits gets me

  2^64 / 1000000 = 600000 years

Seems like it shouldn't have been crackable. And mere 'bad luck' seems far too unlikely. Where am I getting the numbers wrong?

Rowan | Fri, 08 Jun 2012 11:09:24 UTC

@Matt perhaps due to a SHA-1 collision means your password has the same hash as a much simpler password? Also by using base64 you're reducing the search space for a hacker as there are no symbol characters

Poul-Henning Kamp | Fri, 08 Jun 2012 09:27:52 UTC

@Matt: I think you overestimate the strength of a password created that way.

Because LinkedIn did not salt their passwords, the criminals could exploit the preexisting and precalculated 'rainbow' tables for SHA1, and I certainly rule out that they have reached a depth where such a password might be therein.

One other thing people overlook when generating passwords the way you propose, is that it is perfectly possible that base64 spits out the danish word "Angstskrig" which falls to trivial dictionary attacks.

Poul-Henning Kamp | Fri, 08 Jun 2012 09:20:55 UTC

Good security would dictate that only the application where the user changes password have write access to the database, any application just checking the password should only need and have read-only access.

I realize that in many web-based systems that distinction does not exist, and for that subset you are right.

Matt | Fri, 08 Jun 2012 09:13:43 UTC

There's something more to the linkedin leak which I haven't seen an explanation for.

I checked the file of password hashes for the hash of my password. It's there. It's marked as cracked (some of the hashes start with 00000, this seems to mean 'this one is cracked'). My password is strong, an 11 character string I generated from like this: dd if=/dev/random bs=8 count=1 | base64

I can think of at least three explanations:

1. My password isn't actually cracked, 00000 means something else.

2. The person who did the cracking had access to more information than just a hash. Perhaps linkedin keep plaintext passwords for at least some accounts. Perhaps there's was a log somewhere with some plaintext passwords. Perhaps the hack was larger than just obtaining hashed passwords.

3. It's easier to brute-force SHA-1 than I think.

PB | Fri, 08 Jun 2012 09:08:17 UTC

Could it be changed even sooner than that by generating salted hashes of the stored hashes? Then when someone logs in you can simply try both?

Ken | Fri, 08 Jun 2012 08:06:08 UTC

"You can change your SLOW_HASH() function any time you want, provided you also store which function was used in addition to the salt and the scrambled password. This means that as computers get faster, you can increase the complexity of the function to slow it down, or if somebody finds an analytical attack that weakens your password scrambler, you can switch to a stronger one. The next time your users change their passwords, the extra strength kicks in."

Isn't the situation then even better than that?, i.e., you can upgrade a user's stored password the next type they *type* it, the next time they log in to your service.  That's probably a lot sooner than the next time users *change* their passwords!

Sign up for QueueNews

Upcoming Conferences

acmqueue app

Join ACM

Comments