9

If no two users use the same password, then in theory salting the password hash is not needed. How often, in practice, do two users have the same password?

Mark
  • 34,390
  • 9
  • 85
  • 134
  • 41
    you can *always* assume that salting is needed. – AK_ Jun 21 '14 at 20:32
  • 10
    They're useful against bruteforce attacks regardless, they are always needed. – Andrew Hoffman Jun 22 '14 at 06:41
  • 2
    This is just the [Birthday problem](http://en.wikipedia.org/wiki/Birthday_problem). Even in theory (with a uniform distribution of the passwords) there are quite high chances of non-unique passwords for a moderate number of users. – Bakuriu Jun 22 '14 at 10:15
  • 4
    @Bakuriu: Not really, because the space of possible passwords is so huge that you would essentially never have duplicates by chance. The key is that the distribution is nowhere near uniform. – R.. GitHub STOP HELPING ICE Jun 22 '14 at 13:06
  • 1
    Do you really want your system to tell new users who are signing up "Sorry, this password is already taken. Please choose another." – Mr Lister Jun 22 '14 at 15:58
  • 5
    In practice, 30% of all passwords are either "password", "fuckyou", or "password1", or the user's name. So, even leaving everything else out of consideration, hashing without salting is unwise. – Damon Jun 22 '14 at 18:30
  • 1
    I've seen a collision in a small company. Passwords are nothing like random. – Loren Pechtel Jun 23 '14 at 05:24
  • 6
    I saw another question the other day in which someone (not the questioner, their manager) was making the same wrong assumption that salt is only needed if there are password collisions. Where does it come from? – Steve Jessop Jun 23 '14 at 07:38
  • What happened to good old "love", "sex", "secret" and "god"? – Simon Richter Jun 23 '14 at 10:15
  • 1
    @Simon password length restrictions, naturally - so now it's just secret or sexgod I guess... – corsiKa Jun 23 '14 at 14:29
  • http://security.stackexchange.com/questions/61585/convincing-my-manager-to-use-salts this is very similar – Cruncher Jun 23 '14 at 15:24
  • @SteveJessop: I think lots of introductory material on salting talks about how, without salt, identical passwords have identical hashes, and readers *naively assume this scenario is the security problem* rather than understanding that the real issue is that the attacker's copy of the password in his/her dictionary (or rainbow table) of hashes is the relevant duplicate. – R.. GitHub STOP HELPING ICE Jun 23 '14 at 17:30

3 Answers3

70

The assumption is already wrong. Even if every password was unique, you'd still need salts.

Without salts, the attacker can go through his list of possible passwords just once, compare the hash of each guess and check if the result matches any of the stored hashes. In other words, the attacker only needs a single calculation per guess. This has nothing to do with whether or not the passwords are unique.

Salts prevent this, because they make it impossible to reuse a calculated hash accross different user accounts. The attacker has to do one calculation per guess and user.

But even if you ignore this for a moment and only look at salts as a way to hide duplicate passwords, your scenario is still unrealistic: It's not enough for the passwords to be unique within your system. They need to be unique accross all systems which use the same hash algorithm. Otherwise, an attacker might find duplicate passwords by comparing your hashes with the hashes of some other application.

Since it's very unlikely that an average user will come up with a universally unique password, you need salts in any case.

Fleche
  • 4,024
  • 1
  • 17
  • 20
  • A slight correction: the password merely needs to be universally unique across systems that use the same hash function. – Mark Jun 21 '14 at 20:46
  • I've actually said that in the answer: “As soon as any other application has hashed the same password with the same algorithm and no salt, ...”. – Fleche Jun 21 '14 at 20:49
  • The paragraph isn't consistent with itself. – Mark Jun 21 '14 at 20:56
  • 2
    +1 for the first half of the answer, but the second half is confusing and possibly misleading because whether there are duplicate passwords or not is utterly irrelevant to the need for salts. (Or, stated differently, there's always a duplicate password: the one in the attacker's dictionary/brute-force-generation.) – R.. GitHub STOP HELPING ICE Jun 22 '14 at 13:03
  • 1
    Those are two entirely different problems. On the one hand, salts prevent the attacker from reusing calculated hashes. This has nothing to do with whether or not the passwords are unique (as I've already pointed out in the answer). On the other hand, salts hide password duplication, because the hashes are different even if the passwords are the same. This is probably what has lead to the original question: “If there are no duplicate passwords in the first place, why do I need salts to hide duplicates?”. The second paragraph covers the second problem, but it obviously needs some rewording. – Fleche Jun 22 '14 at 23:49
23

It is frighteningly frequent that many users use the same password. Two years ago, Yahoo lost passwords to half a million accounts. According to the password project, only 77% were unique. These were the most frequent passwords and the number of users who used them:

|   Word    | Count |
+-------------------+
| 123456    |  1667 | 
| password  |   780 | 
| welcome   |   437 | 
| ninja     |   333 |
| abc123    |   250 | 
| 123456789 |   222 |
| 12345678  |   208 |
| sunshine  |   205 |
| princess  |   202 |
| qwerty    |   172 |

To their defense, many of these accounts could be throw-away email accounts the owners didn't really care about, but there are likely also a lot of accounts there which are the primary mail accounts capable of resetting the passwords to lots of important services.

A password policy forcing users to use a minimum number of characters and at least one capital letter, lowercase letter, number and special character might prevent a lot of these trivial passwords, but given enough users, you are likely to spot the same "trivial upgrades" to the same weak standard passwords some people tend to use (like password becoming Password1!).

Philipp
  • 48,867
  • 8
  • 127
  • 157
  • 7
    Requiring capital/lowercase/number/special does not improve password strength; in reality it tends to reduce it. See http://xkcd.com/936/ or http://www.openwall.com/passwdqc/. – R.. GitHub STOP HELPING ICE Jun 22 '14 at 13:04
  • 8
    @R.. Neither source you linked seems to support your claim. – Alexis Beingessner Jun 22 '14 at 16:36
  • 5
    Proof that ninjas exist. They're just not good at hiding online. – l0b0 Jun 22 '14 at 17:02
  • You'd think one of those numerical passwords would be `8675309`. – Panzercrisis Jun 23 '14 at 14:22
  • @R.. restrictions lower the password space yes, making in theory passwords less secure. However, it prevents the **really** bad passwords. – Cruncher Jun 23 '14 at 15:00
  • @AlexisBeingessner: Neither prove it, but both deal with the issue and suggest that greater password strength can be achieved with passphrases without any stupid restrictions on characters used. Other research for which I don't have a link handy suggests that placing restrictions on the characters used encourages users to generate weaker passwords by reusing the same basic word(s) and applying trivial mechanical transformations to meet the particular site's requirement (e.g. changing all i's and l's to 1's). – R.. GitHub STOP HELPING ICE Jun 23 '14 at 17:28
  • @Cruncher: p@s5w0rd is a really bad password. – R.. GitHub STOP HELPING ICE Jun 23 '14 at 17:28
  • @R.. doesn't compare to "password". Also, people that would use "password" probably won't use p@s5w0rd. They'll just throw numbers after a word. – Cruncher Jun 23 '14 at 17:30
  • @Cruncher: It does compare in the sense that both are cracked by an attacker within less than a second. – R.. GitHub STOP HELPING ICE Jun 23 '14 at 17:34
  • @R.. I doubt it. I mean you could define the algorithm as one that first checks "password" and then "p@s5w0rd", but I could also define an algorith that checks "F4#%sag%hH6" – Cruncher Jun 23 '14 at 17:40
  • What matters is not how many passwords are unique, but rather how many accounts use the thousand-or-so most common passwords. If a half-million users picked six-digit numbers truly at random, a significant fraction of users would have duplicated passwords, but the result would be more secure than if six-digit numbers were chosen in some fashion that guaranteed uniqueness. – supercat Jun 25 '14 at 14:43
13

The numbers vary from leak to leak, but there are some general trends. For example, in the Adobe leak in 2013, 1.5% of users used "123456" as their password, and 44% of accounts had a non-unique password. In a 2009 leak from RockYou.com, 45% were non-unique.

In short, people aren't very good at picking original passwords.

Mark
  • 34,390
  • 9
  • 85
  • 134