Enough with the Salts: Updates on Secure Password Schemes

http://chargen.matasano.com/chargen/2015/3/26/enough-with-the-salts-updates-on-secure-password-schemes.html

by saturdayplace • 11 years ago

339 221 11 years ago

chargen.matasano.com

I've been saying "scrypt, bcrypt, PBKDF2, or bust" for years.

Also, there's a large industry trend of, "let's 'pepper' our hashes too!" whereby they have a sitewide salt. This is a mistake. If you want to add a site-specific layer of security to your passwords, encrypting them makes far better sense than adding to the salt.

https://github.com/lizardhq/php_bcrypt_aes

http://blog.ircmaxell.com/2015/03/security-issue-combining-b...

nmc• 11 years ago

Found the "unnamed blog" post giving the "terrible" salting advice: http://blog.codinghorror.com/rainbow-hash-cracking/

xxxyy• 11 years ago

The title seems to be misleading. Nowhere in the article does the author explicitly state that salts should not be used, because well, they should be used. His point was that salts are not enough, you need to couple them with a possibly slowest, yet acceptable hash function. And then hope that Moore's law does not breach your passwords.

MichaelGG• 11 years ago

Yes. But he's also pointing out tons of the advice given, perhaps by people that are well-known and respected-by-some, is just wrong.

Iterative hashing with per-user salts has been a known pattern. Practical Cryptography covered it in the first edition. The relevant parts should be derivable for most engineers. There's no reason there should be any confusion or crazy blog posts.

mdavidn2• 11 years ago

Salt has one other important property: Salt makes grouping users by password more difficult.

Some subset of your users will inevitably use the same terrible password as another user. Or one user will create multiple accounts using the same strong password. These passwords should appear unique in storage.

You still need salt, and that salt must be unique for each password. That's the peril of PBKDF2 password storage: I've seen applications completely botch salting by using one for all users. Bcrypt and scrypt avoid this common error by salting internally.

shadowfiend• 11 years ago

Computing the hash of a known password is trivial, though—once you know one user used Passw0rd$, it's easy to check every user for that password, even if you have a salt, because the salt is not hidden. So you're just running n password checks in the number of users—admittedly, this is still n checks, but the difficulty of that pales in comparison to brute forcing passwords, and while it's strictly slower than just checking “is anyone else using exactly this”, it's not that much slower in the larger scheme of breaking a set of passwords.

At least that's my understanding... I am not a security expert! :)

icebraining6• 11 years ago

Checking every user for a specific password is equivalent to a dictionary attack, using a single word. In fact, commonly found passwords from previous leaks are usually incorporated in such dictionaries.

nathanaldensr3• 11 years ago

I think this is why one is supposed to use random salts per password. That way, you can't use the successfully-guessed password's hash to assume other passwords with the same hash represent the same clear-text password.

mdavidn2• 11 years ago

That's a fair point, but an unsalted hash gives an adversary information before they brute force any password.

In the "user with multiple accounts but one strong password" scenario, for instance, grouping by password would highlight which users are inclined to use the same strong password with multiple accounts, perhaps on other web sites. Multiple accounts would give an adversary more identifiers to use when cross-referencing other leaked databases or the web.

hueving• 11 years ago

This is missing something pretty important about salts. They hide the fact that two users have the same password. That's a huge security risk if that correlation is leaked.

Correct me if this is mentioned in the article, but based on several mentions of how salts were effectively useless, I think this was overlooked.

homulilly• 11 years ago

I didn't get the impression the author was saying salts are useless, obviously you still have to use them and bcrypt and scrypt both do. The point is that a lot of programmers naively assume that a salt (or salt+pepper) will make their password storage secure on its own when that isn't really true anymore.

moxie• 11 years ago

It's easy to say "use bcrypt" or "use scrypt," but I think it's important to acknowledge the challenges of deploying those functions in large scale high performance environments.

It's straightforward and effective when password hashing happens client-side (like local encryption for a bitcoin wallet), but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget.

In practice, from what I've seen, this means scrypt is never used, and bcrypt is used with a work factor that's tuned low. I think this is just a fundamental asymmetry, and that at the end of the day people use bcrypt so that they can say "we used bcrypt!" and get a nod when their entire user database is compromised, even though it provides very little value the way it's deployed.

djb_hackernews3• 11 years ago

What is authenticating millions of users per second?

Facebook has 900M monthly users, 30M per day and probably most of those are cookied in. Even if not that's only 350 authentications/sec...

proksoup4• 11 years ago

Maybe each request needs to be authenticated?

nly• 11 years ago

You're right, authentication rates are low. But Moxies point of concern with regard to requiring a heavier CPU and memory commitment on the server is still valid, particularly when faced with malicious traffic.

You need to make sure your login system can handle malicious clients, brute-force attempts from individual IPs, or against particular accounts, dropping back to CAPCTHAs or some other means of resource control when things look bad. This isn't a particularly easy problem to solve, and if you do it incorrectly you open yourself and your users up to a denial-of-service.

IMHO, some of the new fancy password-based authentication protocols, like AugPAKE, which do hashing client-side, might ease this problem... but they're still stateful (SYN floods anyone?) and therefore still depend upon good DoS protection.

Edit: Oh poop, you're djb.

hackcasual3• 11 years ago

Not normally, but it does open up a DoS vector that at the very least will prevent legitimate users from logging in.

yxhuvud• 11 years ago

Think infrastructure rather than appliances like Facebook. What do you think happens if certain state keeping big authentication servers or routers reboot? We have a customer that has more than one million users on a GGSN (which is a glorified router). If that happen to restart every single customer will immediately and automatically try to reconnect.

The systems involved actually doesn't tend to handle this many in reality (the ISP in question restrict it to some 20-30k/s to our system). These systems are starting to be better at supporting keeping state through restarts, but there can still be pretty impressive spikes of authentication traffic if the wrong system is rebooted (or crashes!).

snowwrestler• 11 years ago

This makes sense, but--forgive my ignorance--what site needs to process millions of password authentications per second? Don't most sites hash/compare the password once at login, then issue an ephemeral token to maintain the authenticated state? Is Facebook, for example, hashing my actual password for every HTTP request that my Facebook mobile app makes?

scott_karana• 11 years ago

Even though the choice of scrypt might necessitate dedicated authentication servers at "web scale", I don't see any better options on the table.

Hardware is cheaper than trust, or litigation.

(And there's always rate-limiting)

enraged_camel• 11 years ago

>but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget.

Perhaps this is the real issue: lack of sufficient budget for CPUs that can reliably get the job done is a reflection on the priority organizations place on information security.

dsp12343• 11 years ago

For an attacker, a great way to cripple an organization that uses scrypt/bcrypt easily is just to attack logins. If each login takes 1 second of work, then it's easy to overwhelm any system system using a host of bots on distributed hosting systems. Say an attacker can hit with a mere 1 req/s from 100 hosts (very easy with aws/digitalocean/hetzner/etc), then that's 100 CPU-seconds of work just for logins.

Comparatively, if they hit with 100 req/s for normal front-end data, caches can easily handle that. So really, adding these types of login checks to any publicly available login page ends up creating an on-demand DDOS target.

From the password cracking side, the asymmetry comes from the fact that an organization has to have X amount of server resources to service Y number of requests, but an attacker can utilize the same X amount of server resources to service just one thing, breaking the exact password they are looking for. This is further exaggerated by the fact that generally for an organization those X server resources also need to more than just service logins (like actually serve content or API data).

bradleyjg2• 11 years ago

I think if the most efficient way to attack the hashes is to buy the same hardware you use to process logins than in some sense you've already won. It's where the attacker can buy GPUs or program an FPGA and dollar for dollar make orders of magnitude more guesses per second than you do verifications per second that you want to avoid.

To the larger point, I do agree that some of this starts to look to be a bit of security theater. If a user picks a laughably weak password, and the server is completely compromised, it doesn't much matter what password storage scheme you used, and on the other hand if the user picks a great password, especially if he never reuses it, the consequences of losing that hash is limited.

vectorjohn3• 11 years ago

I think maybe you missed it a bit. If attackers can spend a bunch of money to guess enough passwords to be useful in, say, weeks, then if you make it take 100 times as long, now it's years.

And using scrypt with a decent work factor isn't 100 times harder, its tens or hundreds of thousands of times harder.

Additionally, I think one of the benefits of scrypt is that it is specfically designed to deter GPU or FPGA attacks because it is memory intensive instead of just CPU.

j_s• 11 years ago

What are the downsides of avoiding this by using scrypt/bcrypt client-side (for a web app)?

bradleyjg2• 11 years ago

There may be other downsides, but the one that immediately comes to mind is that some of your client's devices may well be extremely resource constrained. The obvious type of device that comes to mind is mobile phones but there's also set top boxes and many other non-full-blown-PC web clients around.

What ever work factor downtuning you need to do to conserve server resources may well be dwarfed by the downtuning you need to do to get bcrypt to run in a reasonable amount of time on a mid range smartphone.

zwegner• 11 years ago

Correct me if I'm wrong (I'm no crypto expert), but doesn't client-side hashing take away the main point of hashing passwords in the first place? If a password database is compromised, the hashes don't even need to be cracked, they can just be sent straight to the server for authentication. The only thing it seems to help with for the client<->server case is password reuse between websites, and that's only if they don't use the same client-side hashing scheme.

Moxie seemed to hint at this problem by mentioning local bitcoin wallets--client-side hashing only makes sense if you're not sending the hash anywhere.

kej2• 11 years ago

The main problem (barring some fancy and probably patented new techniques) is that whatever gets sent over the wire from the client is a de facto cleartext password. If your system does the hashing client side and then stores that, an attacker with the login database can just submit the pre-hashed values.

To prevent this, you still need some transformation on the server between the login form and the database, which means you're back where you started.

Someone1234• 11 years ago

People have done it.

Few downsides that immediately come to mind:

- Some people run NoScript or have niche devices that mangle JavaScript (no login for you!)

- The client now has to generate the salt. So you'll want the client to be using a modern browser which supports window.crypto.getRandomValues(); (so IE 11 or newer)

- Low power (either electrically or performance wise) might struggle with the work factor and that might reduce the user experience (the browser might become unresponsive)

- Changing the crypto function is now quite annoying/work intensive. Effectively the client will now need to generate the old hash and the new hash, and send both. You'll need to check the old, check the new, and store the new if either are correct.

- There are some cross-site-scripting and forged request concerns. But those exist for all login pages frankly.

- You'll still need to do SOME work on the server to convert the raw client hash into a storable version (in case of compromise) so they cannot just re-send what is in the database for login (essentially the hash would be a plain text password for all intents and purposes). You could reduce the work factor, but not remove it entirely.

Essentially trusting a browser is a bad bet because too many browsers suck. I'd prefer to put my trust in a more known quantity, the web-server, even if it costs me a few cent in usage than do the extra dev', extra testing, and extra tech' support required to get browsers to do it.

Unfortunately there are still a lot of IE 6-8, Android 2.xx, and so on users who drag everyone down.

TheDong• 11 years ago

JS's bcrypt/scrypt performance will be pitiful. If it takes the client 1s in JS to bcrypt a password, a server will be able to do it in a 10th the time with a more efficient implementation. That makes client-side bcrypt have to use an artificially low difficulty factor due to the inefficient implementation language.

tptacek12• 11 years ago

1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults.

2. Even with a lower work factor, bcrypt is drastically better than salted SHA.

3. Companies with auth loads so high that they really need to tune bcrypt should also be using dedicated auth servers, which (a) improve security in other ways and (b) allow for a lot of flexibility in handling work factors.

hackcasual3• 11 years ago

If they're using dedicated hardware, why not use smartcards to salt the hash.

From the article, even 74kh/s is going to tear through a lot of passwords, but with a secure element in the mix, offline attacks go nowhere.

mtrimpe5• 11 years ago

1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults.

Isn't that a security risk of it's own though? Wouldn't creating a rainbow table for (non-salted) passwords hashed with the default bcrypt settings then make sense again?

mrb• 11 years ago

I think this is just a fundamental asymmetry

Actually the Password Hashing Competition has shown this asymmetry can be exploited to the server's advantage: one of the ideas being studied is called server relief.

For example instead of storing the scrypt hash on the server you store the SHA256 hash of the scrypt hash (and the salt alongside), and ask the client to send the scrypt hash to authenticate. This way the per authentication cost to the client is expensive (one scrypt hash) but the cost to the server is cheap (only one SHA256 hash).

Attackers cannot take shortcuts. They cannot send random scrypt hashes to the server while skipping the scrypt computation step, because the space of possible scrypt hashes is just too large to brute force.

The only downside of server relief is that you need custom code on the client-side to do the computation. So it works with javascript in browsers, but not with traditional clients like an IMAP or POP3 mail app.

Edit: @__david__: yes you could SHA256() only the hash part of the scrypt hash, as opposed to the hash & salt parts. It is an implementation detail --not really important. And regardless of how you do it, if the DB get stolen the SHA256 hashes are useless to authenticate.

Edit: @espadrine: no, breaking a SHA256(scrypt()) hash is no easier than breaking a scrypt() hash. Server relief with SHA256 introduces no weaknesses. It is strictly more secure than standard scrypt hashes.

Edit: @plantbased: I recommend against MD5(scrypt()), because it is likely preimage attacks will be found on MD5 in the near future, so someone stealing your database of MD5(scrypt()) hashes will be capable of computing an arbitrary scrypt hash that authenticates to a given user. But you could certainly do MD5-crypt(scrypt()) with MD5-crypt being the salted & iterated version by PHK.

__david__• 11 years ago

I like that idea. But why do you store the salted SHA256 of the scrypt hash and not the scrypt hash directly?

Edit: Thinking about it more, I'm guessing it is for the case where your DB gets stolen. With the salted hashes, attackers can't just send the direct scrypt hash down to the server to get authenticated.

espadrine3• 11 years ago

The only downside of server relief is that you need custom code on the client-side

That, and the major reason we do hashes even over TLS: if the server gets cracked and the attacker has access to the stored hashes, breaking a SHA256 is trivial (ie, brute-forcing b when knowing s = SHA256(b)). Then, the attacker can assume the identity of any individual whose SHA256 s got broken, by sending the bcrypt b directly from a crafted client, without having to find p where b = bcrypt(p).

moron4hire• 11 years ago

I see, so basically it's like forcing users to make long, un-dictionary-attackable passwords, without requiring users to remember long, un-dictionary-attackable passwords.

plantbased3• 11 years ago

mrb, this is awesome, thanks for sharing. Can you comment on storing the scrypt as an md5 hash and how that would impact security? [Asking because I'm confined to server side systems that only support md5]

IMHO While MD5 has a fraction of the keyspace of SHA2, it's still a very hard problem to reverse it and intuitively it seems this might provide a huge improvement over salted and stretched (multiple rounds) of md5 on the server.

Thanks again.

TheLoneWolfling• 11 years ago

The problem with the approach you mention is that clientside bugs can evilly break things. If the clientside code silently gives wrong results, not only will you not know, but, assuming they run it from the start (i.e. when they register), it will actually "work" - until the client moves to another machine or updates. That's not a good situation.

You may be able to detect this with testing, but not necessarily. And yes, it'll probably happen sooner or later, given the nature of JS compilers.

I don't know if there's a method that avoids this problem that still has the advantages that you mention.

kijin• 11 years ago

This is brilliant. But since we are often told that composing cryptographic promitives can turn out to be unexpectedly dangerous, can you point me to some articles where this technique is studied in more detail? Preferably by experts such as yourself.

spb• 11 years ago

This is something I've wanted in browsers since I was about 15 - I've written a proposal on Specifiction for discussion around putting this in the Web Platform: http://discourse.specifiction.org/t/html-server-relief-passw...

joesb• 11 years ago

The attacker would then intercept that scrypt hash sent from the client and use it to authenticate.

jjarmoc2• 11 years ago

You raise a good point, but one that's probably an issue to a minority of those implementing applications that require an authentication component. Sure, the Twitbooks, GooSofts and FaceLinks of the world that deal with large numbers of concurrent authentications have to think a bit more about this, and that's fine; I would expect that they would be well equipped to do so, and likely also run dedicated authentication servers and carefully considered systems.

I can probably count on one hand the number of times I've seen an application use bcrypt or scrypt and define their work factors. The common case seems to be sticking to the defaults that their chosen library ships with. While these may be somewhat less than ideal, it's universally true that these schemes are stronger than salted passwords fed to a fast cryptographic hash.

erkkie• 11 years ago

Examples of sites where this is an issue? Serious question, where does scrypt/bcrypt overhead get to be important enough compared to the rest of the traffic the site has to handle?

NKCSS• 11 years ago

It's been said before in previous discussions, but have not seen it here: Just make your own 'password cracking cluster' to make sure you can handle the auth workload with ease.

zaroth6• 11 years ago

Moxie hit the nail on the head. It's absolutely a fundamental asymmetry. Slow hashes can protect strong passwords, and not much else. And if you use a password manager to generate strong passwords, then you are going to throw that password out anyway.

In the time it takes for your users to give up on the hourglass, assume their login request is hung, and start double-clicking submit, you have now DDoS'd yourself. That's about 750ms I think...

Also, try this sometime -- clear your cookies and try to login to Google, or Twitter, or Facebook. Time how long it takes before you see the first byte of a session cookie. Hint: Not Long Enough.

Password hashing is embarrassingly parallel. The botnets don't cost the attackers anything to hash your password on 100,000 CPUs all at once, after they've decided to target you. Moore's law? Also not helping.

We need something better. I'm working on just that, I'm sure it will have more than it's share of naysayers, but I'm giving it my best.

djb_hackernews3• 11 years ago

I'd be interested to hear more about the approaches a hacker would take in each case if they came across the hashed passwords and have no knowledge of the salts, etc.

For instance in the first case where hash = md5('deliciously-salty-' + password)

I'm not sure how easy it is for an attacker to reverse the hash if they don't know the salt. (I understand you need to assume the attacker has the salt, but just posing a constrained hypothetical here)

icebraining6• 11 years ago

It's equivalent of attacking md5('deliciously-salty-'), since the password can be known, e.g., by using the hash from their own account.

Attacking md5 is not really that hard, nowadays - the article mentions 180 billion tries/second.

Yes, it requires a rig with 25 GPUs, but this is almost the perfect use for the "cloud" - you can rent those for a few bucks just for a specific attack. There are even dedicated services nowadays, with no programming knowledge required - you just submit the hashes, and out come the found passwords.

djb_hackernews3• 11 years ago

Hmm I still don't understand, but thanks for replying to my (downvoted) honest question.

If all you have is a hash and know the password you still dont know if it's

md5sum('salt:' + password) or

md5sum(password + '-salt') or

md5sum('salt+' + password + '=salt')

etc

I suppose you'd need to brute force a large key space and look for any results which contain your known password. Does that sound right?

Retra• 11 years ago

If the salt is a constant, the attacker doesn't need to know it simply on the principle that they don't need access to the constant parts of your site, it's the dynamic functionality that they want access to. Knowing the salt in that case isn't theoretically any more difficult than knowing any other static part of the process.

Consider an alternative: randomly generate salts with a constant password. It's the same amount of information, and it is obvious that it does no good to ask for a password if there is only one password that everyone shares. All you need is the dynamic part, and you have access. The dynamic part is the security and the data, and everything else is infrastructure that can be known simply by probing.

This is just how information processing works. You have a static 'language' and a dynamic 'meaning', and if you don't know the language, you can't possibly get the meaning -- but this means you can't even use the site at all (even with a password.) So obviously the 'language' has to be public so it can be known by the people who wish to communicate with the site legitimately.

danbruc• 11 years ago

There is one thing that I think is often omitted. A lot of user use trivial passwords and they reuse them. These users' passwords will fall essentially no matter what you do because making the check so slow that a dictionary attack with a couple thousand very common passwords becomes impractical is itself borderline impractical. On the other hand strong passwords will withstand an attack even if they are hashed with plain MD5 or SHA1 - at least right now, there are already some serious collision attacks.

The user group really benefiting from strong password hashing schemes is the one between the two mentioned extremes. So if you really want to protect all your users and use simple password authentication you have to enforce strong passwords policies which is itself not trivial and will definitely badly annoy some users.

jjarmoc2• 11 years ago

There is one thing that I think is often omitted. A lot of user use trivial passwords and they reuse them. These users' passwords will fall essentially no matter what you do because making the check so slow that a dictionary attack with a couple thousand very common passwords becomes impractical is itself borderline impractical.

Sure. This is something I touched on very briefly near the end of the post. Password re-use is a huge problem and could easily be an blogpost of its own.

On the other hand strong passwords will withstand an attack even if they are hashed with plain MD5 or SHA1 - at least right now, there are already some serious collision attacks.

For some value of 'strong' sure. If you're password is long enough, random enough, and of a broad character set then yes, an md5() of that may well be beyond the reach of most attackers. But that's not the sort of password most people, even security conscious people, choose. A preimage against MD5 would quickly change this too, and that's a risky gamble.

The user group really benefiting from strong password hashing schemes is the one between the two mentioned extremes.

The best we can do is make attacker costs a function of the password that the user has chosen. If someone makes their password 'password' there's no degree of magic that's going to help. Mostly, the benefit comes if/when disclosure occurs and there's an active incident response effort.

So if you really want to protect all your users and use simple password authentication you have to enforce strong passwords policies which is itself not trivial and will definitely badly annoy some users.

It's not a zero sum game. When a breach occurs, the rough points in time are something like:

1) Attacker compromises digests (let's just assume all are obtained in an instant, rather than exfiltrated over time) 2) Attacker recovers 1 password 3) Attacker recovers n passwords 4) Attacker recovers all passwords

Our goal isn't to eliminate these steps except hopefully the extreme of 4. Rather, it's to increase the time between 2 and 4, and make sure 3 is closer to 2 than 4.

On the other side of the coin, there's a few points in time:

a) Victim org. realizes digests have been compromised. b) Some credentials valid at 1 are made invalid. c) All credentials valid at 1 are made invalid.

If you accept my previous point that at some extreme there's nothing that can be done to prevent brute force, then you should also see that storing passwords in this fashion isn't meant to be a perfect defense. By minimizing the number of compromised accounts at a given point in time, we can maximize the benefits of our response. We can notify users and force resets, invalidating some set of credentials before they're recovered. We want b and c to be closer in time to 2 than 4, and minimize the value of n when we get there.

kpcyrd• 11 years ago

Password hashing is crypto, too. Don't roll your own crypto.

sarciszewski5• 11 years ago

I agree with this advice, even though I'm probably the worst offender. I have:

    - Rolled my own password library (linked elsewhere in this thread)
    - Rewritten an existing AES-CBC + HMAC-SHA-256 library to use a different 
      underlying driver (mcrypt is basically a mummy at this point)
    - Did both of these things in PHP, which a lot of people assume
      is inherently incompatible with security

However, everything I've done in this vein has been passed before people who are far smarter than myself, to which I received no complaints. And I constantly seek out criticism from people who understand crypto too. (Aside: Most crypto people are dicks. But they mean well.)

ZoFreX2• 11 years ago

One question: _Why?_

However many people have reviewed your code, far more people have reviewed libraries like bcrypt!

ryan-c7• 11 years ago

This article says salting hashes is only useful against rainbow tables. That does not make sense to me. Say you have a password database with 10,000 users in it. You want to see if any of them used "Passw0rd$". Without salt, you compute the hash once and check it against all the users (perhaps with a bloom filter). With per-user salts, you have to compute the hash for each user.

I think salting offers pretty clear benefits against other attacks if you have more than one user.

Edit: The point I'm trying to make here is that it is N_USERS times better to have a unique salt per user, regardless of the hash. One should use bcrypt/scrypt/pbkdf2 with unique per-user salts.

icebraining6• 11 years ago

A single hash per user is not any significant protection. As the article pointed out, the rig could compute 71000 bcrypt hashes per second, so even if you had 1M users, that would take less than 30s/password.

maxerickson• 11 years ago

That calculation can't be done without knowing the bcrypt costs used to benchmark the rig and on the unknown password (I was pondering a similar calculation on another story and the only thing I found was a brief statement that pw crackers report performance for cost=5 (just by habit/convention).)

kasey_junk3• 11 years ago

The salt is typically assumed to not be secret. With modern hardware recalculating the hash is not hard for "fast" hashes, regardless of salting. That's why choosing a slow hash is more important for this vector of attack than anything else.

Of course salting is better than no salting, but its orders of magnitude less important than choosing a good hashing mechanism. Luckily, the good hashing mechanisms do the salting for you so fixating on salting really just serves as a proxy for letting us know that you don't understand the attack vector.

panopticon• 11 years ago

I think you're severely underestimating the importance of salting. I agree that choosing the "correct" hashing algorithm is more important than salting, but not by magnitudes.

Even if you're using a "hard" hashing algorithm, you're significantly reducing the amount of computations an attacker would have to go through by forgoing salts. Especially considering that salting has very, very little overhead.

worklogin4• 11 years ago

Whether the salt is secret or not doesn't matter. If it's known that I salt passwords in the USERS database with the `uname` field, hashes for "workloginpa$$word" and "kasey_junkpa$$word" will look different, even though our passwords are the same. There's no easy way to compare passwords when they're salted, and that's the point to understand.

Yes, having a good hash in the first place is more important, but salting is right up there.

GhotiFish3• 11 years ago

forgive me, I haven't worked with a good hashing mechanism before.

How can it "salt for you" without you providing the salt?

This question is operating on the presumption of a unique salt per user.

fl0wenol• 11 years ago

A better argument for per-user, randomly-chosen-at-password-change-time salts is so that you can't determine that two users (currently or historically from a password history) are using the same password by comparing the hashes.

If you knew that a hash was used many times over in a system, then you'd try cracking that password first to get access to the most accounts.

With salting you don't get to prioritize, or compare to previous information trivially.

ryan-c7• 11 years ago

I don't think that's a "better argument". I think it's a second, also good, argument that I didn't repeat because it's been mentioned by several other people.

Your argument is about protecting trivial passwords. It's quite common for people to independently come up with the same crappy passwords - the adobe "crossword puzzle" leak was a particularly interesting example of that.

My argument is about protecting moderately good passwords. If you use, for example, PBKDF2 with a fixed salt and have a million users, an attacker can try close to a million times as many passwords vs random salts.

You can still prioritize cracking with salted passwords in many cases. Say you had a dump of hashes form hackernews, and they were bcrypted with random salts. You'd go after the admin accounts first, then the well known accounts with a lot of influence, then everybody else.

GhotiFish3• 11 years ago

That's the exact same argument, phrased differently.

serve_yay• 11 years ago

Yes, I was thinking the same thing. I am really mystified by their saying this.

joepie91_3• 11 years ago

The attack you are describing would just be a rainbow table. That's exactly the point.

teraflop4• 11 years ago

No, brute-force attacks are different from rainbow tables: http://en.wikipedia.org/wiki/Rainbow_table

tootie• 11 years ago

I fail to understand why salting is bad. Seems like he's saying it's not a cureall. We knew that. But it's at least marginally better than not salting and it's easy, so why the hell not?

amouat• 11 years ago

Yeah, salting definitely isn't bad, in fact it's actually essential. What the author is saying is that it's not enough - salting won't save you when your attacker can test 10s or 100s of thousands of hashes a sec. The article could have been phrased better.

dickfickling• 11 years ago

What he's saying is that a salt should be a no-brainer. FTA: "Storing passwords as unsalted hashes is a grievous mistake of course, and breaches disclosing poorly stored passwords are still too common."

He's simply saying that a salt isn't enough to keep your passwords secure - you should also be using a slow hashing / memory intensive hashing function.

masklinn• 11 years ago

Nobody's saying salting is bad, the blog is saying that salting is a given, if it's not you don't belong anywhere near passwords.

femto113• 11 years ago

I see the mantra ‘salt your password hashes!’ repeated over and over, when its only real value is against rainbow tables

This is dangerously incomplete reasoning. Salts real value is that if multiple password hashes are Leaked simultaneously then each must be cracked individually. In the Adobe leak password hints were included, which allowed for very easy guessing of passwords, and because there were no salts even if you had no hint if someone else had the same password and an obvious hint you were cracked.

worklogin4• 11 years ago

I was about to make the same post.

If a database is popped and people know John123's password, and his hash is the same as Worklogin456's hash, then they know my password.

nopar8• 11 years ago

I am extremely ignorant about this topic. But I don't think that's how it works. Can someone else weigh in please.

elchief• 11 years ago

Since the author didn't bother to mention any threat models, we can assume that the threat is the most common one, SQL Injection.

You don't need SQL Injection if you can directly read the database file, or can operate as the web server user, therefore if you're doing SQL Injection you don't have those privileges.

If you can HMAC or encrypt passwords (prior to hashing them) in the database with a key only on the web server, then that's an extra level of protection. You can't get that key with SQL Injection alone.

https://blog.mozilla.org/webdev/2012/06/08/lets-talk-about-p...

password_hash(base64_encode(hash_hmac("sha512", $password, $key, true)), PASSWORD_BCRYPT)

ajanuary• 11 years ago

we can assume that the threat is the most common one

No we can't.

DenisM• 11 years ago

If you are using .NET, you will be glad to know that .NET framework has a standard implementation of PBKDF2, one of the recommended choices in the article.

  var hash = new System.Security.Cryptography.Rfc2898DeriveBytes(password,
    salt, workfactor).GetBytes(32);

Using a NIST-approved function that's continuously supported by a large player seems like a good choice.

jameshart• 11 years ago

The implementation iterates HMACSHA1, which is fine, of course, but which raised concerns on at least one audit I went through because, well, why would anybody want to use SHA1 when SHA2 exists?

Wound up having to implement my own version of PBKDF2 that lets you specify the HMAC algorithm.

k__• 11 years ago

Does this mean we should drop the salts, simply scrypt and be done with it?

Or should we still include salts in addition to scrypt?

If yes, only one global or many user specific or both?

btilly2• 11 years ago

The need for unique passwords brings me to a stupid idea that I've had for a while.

Imagine a service which just stores hashes of every password that it can find from everywhere. Any site that wants can check whether a given password is in use..somewhere..and reject it if it is. Any site that wants can add more passwords to the list.

Internally the service would work from a bloom table designed for a fixed false positive rate. (You can actually layer bloom tables in front of bloom tables with parameters to make this possible.) So even if someone compromises that site, there is no direct record of the actual hashes for passwords.

Basically let sites say, "You have to choose a unique password, and do not reuse a password that anyone has used elsewhere!"

sarciszewski5• 11 years ago

This would only work if you could achieve this search with the use of a zero-knowledge proof. Actually disclosing your password to the service would defeat the point.

btilly2• 11 years ago

Yes, this is a weakness. The password would need to be disclosed in the form of a hash of the password, and the hash algorithm has to match what everyone else does.

If the service and your site were both compromised, then it would be possible to match up incoming hashed passwords to users by timestamp. But even so, the fact that no passwords were reused will hopefully make cracking the hashes harder.

So..probably a bad idea. :-(

wffurr• 11 years ago

Lastpass has a password-auditing feature that checks your passwords against a list of known-leaked common passwords.

jacquesm• 11 years ago

Compromises are not points in time, they tend to be intervals. A long enough interval could do more harm than good here.

throwaway832975• 11 years ago

http://research.microsoft.com/pubs/132859/popularityISeveryt...

noinsight• 11 years ago

It's not just the scheme that's important, it's also the implementation of it that's important. If I'm doing the smart thing and not rolling my own crypto, can I trust the existing implementation that I've chosen? It's hard to say. Does it have secure defaults or do I need to choose and why do I need to choose, why aren't the defaults secure? I'm not a crypto expert, I'm not qualified to judge and therefore I don't even care (as such) - why aren't the defaults secure?

For example, I'm writing an app that requires a password setup in Python so I was investigating this issue:

1. Passlib - https://pythonhosted.org/passlib/ - "implementations of over 30 password hashing algorithms" - What? I'm not qualified to judge what's secure so I don't even care, I just want something secure!

2. python bcrypt - https://pypi.python.org/pypi/bcrypt/1.0.1 - OK standard bcrypt, supposedly that's secure - "Author: Donald Stufft" - who is Donald Stufft? Is the code good? I don't know C and I'm not qualified to judge!

3. python scrypt - https://pypi.python.org/pypi/scrypt/ - OK it's Colin Percival's code, it's probably good, "Author: Magnus Hallin" - did Magnus Hallin screw it up though? "Burstaholic on Bitbucket provided the necessary changes to make the library build on Windows." Eh. Did "Burstaholic" ruin the crypto? Who knows.

Also, in my case I needed something cross-platform, primarily for Windows. bcrypt worked out of the box. The scrypt library required building on Windows with OpenSSL development headers or whatever and all that - I just said "pass".

Nacl is fantastic and simple to use, it can't get much easier than this: https://libnacl.readthedocs.org/en/latest/topics/public.html

Something similar should exist for passwords - I just want to call compare(password, storedhash) or whatever and be done with it, I'm not qualified to judge the crypto. And it should be cross-platform.

im3w1l3• 11 years ago

This is why I love the (modern) php approach. It's in the standard library and you don't need to supply an algorithm name or salt or anything. It is also designed so that a future version of php can have upgraded algorithms without breaking current code. It is trivially easy to write code that upgrades old hashes when the user logins in.

http://php.net/manual/en/function.password-needs-rehash.php

borski• 11 years ago

Jeff's and Thomas' posts are totally on the money. We wrote a piece as well, specifically to talk about how encryption and hashing are not the same thing. You'd be surprised how often people screw that up.

https://www.tinfoilsecurity.com/blog/store-data-securely-enc...

biot2• 11 years ago

The points made here are covered in Coda Hale's post: http://codahale.com/how-to-safely-store-a-password/

While it recommends using bcrypt, if you augment that with "or scrypt or PBKDF2" the same principles apply.

pstrateman3• 11 years ago

"The value of salts is limited to thwarting attacks leveraged pre calculated lookup tables such as rainbow tables."

This is absolute drivel.

Salts prevent checking an attempt against all the hashes in parallel.

That is to say if the attacker has a dump of 1 million salted hashes, they have 1 million times the work to do compared to 1 million unsalted hashes.

unreal37• 11 years ago

I am also suspicious of the claim that a fixed salt+password hash scheme is "just as insecure" as a no-salt password hash scheme. The salt (unknown to the attacker) has to add at least a few order of magnitudes more security just by turning "password123" into "somesalt65634734password123" right?

Just from the added password length alone it has to be "way more" secure, right? Would love some professional crypto opinion on this.

MertsA2• 11 years ago

If it's fixed it is limited to just preventing rainbow tables from being used in practice. If they have a copy of your database already ex-filtrated, there's a pretty good chance that they also have access to "somesalt65634734" so while the attacker certainly isn't going to be able to find a rainbow table with every password prefixed with "somesalt65634734" they certainly won't just check every combination of a 32 character password, they'll just check passwords 8 characters or less starting with "somesalt65634734" and if it's unique across your whole site and your site has N users then they just sped up their password cracking with a factor of N.

If N = 1000000 and it's just SHA("somesalt65634734" + password) then the attacker is just about guaranteed to be rolling in tons of cracked passwords in no time. Whereas with bcrypt or a unique salt per password you don't get that massive speedup by a factor of N.

pstrateman3• 11 years ago

Strictly speaking... it depends.

Lets assume the hash function being used is SHA2-256.

The input block size there is 512 bits (64 bytes).

So if adding the salt pushes the total length of the hash input past 512 bits then it doubles the runtime.

I do not see any particular advantage there over simply running the hash function twice.

minitech• 11 years ago

The salt (unknown to the attacker)

The salt is generally known to the attacker. The point of the salt is that it’s unique for each password hash, making it impossible to run crack attempts on every password at the same time; for a password hash to be checked, the salt has to be retrieved. This means they’re usually stored together and therefore also compromised together; keeping them apart is rarely useful (kind of like peppers, which is what you might be thinking of; they’re per-application rather than per-hash, and their purpose is to be unknown to the attacker, which is equivalent to encrypting things with a per-application key).

ZoFreX2• 11 years ago

When you can do 60 billion attempts per second, 1 million is a pretty small number.

Edit: That said, they do still provide value, by making password collisions less obvious.

caf• 11 years ago

60 billion divided by 1 million is 6 thousand, and 6 thousand is a much smaller number than 60 billion.

MertsA2• 11 years ago

I think in that case he's referring to having a global salt instead of a unique salt for every password, in which case he's right. However, that's kind of a silly statement because the example web framework that he was using doesn't just have some global salt and nothing else.

pstrateman3• 11 years ago

A global salt is not a salt.

Term people are using for a secret is pepper.

H(pepper | salt | password) type of thing.

kyberias• 11 years ago

Urghh... I hate these articles that list bad examples of salt use and then doesn't explain the reasoning why exactly these are bad. Just trying to prove to the world how smart the author is. Maybe he doesn't really know how to explain it?

codahale• 11 years ago

Use bcry—ah, fuck it.

seanwilson• 11 years ago

How about using a tested login library instead and consider using OAuth as well (e.g. Google account to login)?

Rolling your own login system, dealing with hash functions and checking passwords yourself is far too low level and dangerous for most apps (as this thread demonstrates).

zobzu• 11 years ago

while we're at it and throwing stuff around as if its an easy fix: lets stop using passwords. Use keys. Use a trust model on these keys. So many advantages.. you don't receive the cleartext password no more (because really I DONT CARE if you use triplezscrypt.. SINCE YOU GET MY PASSWORD IN CLEAR TEXT during authentication.. its not like if compromises were "on the database". Its always at the application level.)

Beside it makes rotation easier, and not having to remember multiple passwords, or having a password manager, etc. a thing.

Oh wait ;) Google and others are actually attempting to make this work with U2F:

https://support.google.com/accounts/answer/6103523?hl=en (yes it works with gmail. Right. Now.)

https://www.yubico.com/applications/fido/

ghshephard• 11 years ago

And, as always - these discussions about Salts/bcrypt/scrypt are only relevant to people where passwords/security are important, but not critical.

For anybody who has critical security needs, just use an HSM already. Sophos/Utimaco makes a nice one, and it is a nice foundation for password security.

Sami_Lehtinen• 11 years ago

How about not reusing passwords and always using a strong password? SHA256 alone is enough, when you just do that. And so what if someone got my password. If they had already access to the system, they could have also stolen the data they were after anyway. Today's password: .P`éA@O?/^2HNVSé%@ÖY it contains more than 256 bits of entropy. Based on this SHA256 collision attacks and cracking AES128 should be trivial. I personally consider passwords to be unique shared secret blobs / service.

slasaus• 11 years ago

I've recently found out about Diceware and the importance of a strong password [1][2]. Often users choose a really weak password to begin with. I've read [3] that if you have a strong password (like a 7 word Diceware password) even MD4 or MD5 would suffice :O. I'm really curious if this is true.

[1] http://world.std.com/~reinhold/diceware.html

[2] https://firstlook.org/theintercept/2015/03/26/passphrases-ca...

[3] https://github.com/freedomofpress/securedrop/issues/180#issu...

ps. for those that use bcrypt and want to ensure a constant user experience on their server see https://www.npmjs.com/package/bcrypt-speed

xai3luGi• 11 years ago

Why are we still using passwords in 2015?

Enough with the Salts: Updates on Secure Password Schemes

Related Stories