3

Maybe I'm missing something obvious...

Are all passwords stored in common, unsalted hash algorithms able to be attacked via rainbow tables?

CodesInChaos
  • 11,964
  • 2
  • 40
  • 50
Keltari
  • 261
  • 2
  • 8
  • 1
    You are using the term 'insecure' too broadly. What do you mean by the term? Even salted hashes are 'insecure' if a rainbow table exists that includes that salt... – schroeder Jan 13 '15 at 23:47
  • insecure in that basically their are dictionaries of passwords that can be matched to the hash. isnt the whole point of salting to take a random piece of data unique to that user and adding it in some way to the password to then make the password itself unknown, even if the hash is cracked? – Keltari Jan 13 '15 at 23:50
  • 1
    salts increase the security of a hash, and should be considered standard practice, but it is an error in logic to then conclude that unsalted hashes are 'insecure'. They just aren't as secure as they could be. It all depends on the threat you want to secure against. – schroeder Jan 13 '15 at 23:56
  • 1
    @schroeder Salts are standard practice _for a password hash_. As far as I know, they aren't standard practice for hashing algorithms in general. – cpast Jan 13 '15 at 23:59
  • Also: None of the main three password hashes even _work_ without a salt; they all use the salt as part of their algorithm (it's not just prefixed to the ciphertext, it's used separately in the algorithm). Using the common hashes that do work without a salt is already bad (even if you use a salt stuck onto the front of the password) because they're too fast. – cpast Jan 14 '15 at 00:13
  • @cpast you're mixing terms. MD5 is a hash that is used for passwords and does not use a salt by default. Yes, there are password hashing functions that require salts, but that's a different discussion. – schroeder Jan 14 '15 at 00:34

5 Answers5

4

Not all passwords. When the password is sufficiently long and random to not appear in a reasonably-sized rainbow table, salting is indeed unnecessary.

The purpose of a salt is to increase the length of the password to a level where rainbow tables are unfeasible. When the password already has enough entropy, the salt becomes redundant.

When your salts are 32bit, demanding about 5 more characters of mixed case, letters and special characters without a relation to a dictionary word would be equivalent.

However, passwords used by the average user do not have enough entropy to be rainbow-table-proof. So unless you have the ability and authority to enforce a strict password policy and users who understand that they must not try to find loopholes (hey, Password123! is 12 characters mixed case with letters and special chars!), you should still use salting.

Philipp
  • 49,017
  • 8
  • 127
  • 158
  • 1
    Interesting. I thought the salt was not for adding length. But for adding an unknown element to the password. So even if the the hash was cracked, the hacker still wouldnt know what the actual password was. – Keltari Jan 14 '15 at 14:05
  • 1
    @Keltari no, that's incorrect. When you crack a salted password hash, you usually know the hash and the salt and then bruteforce `possible_password`+`salt` until you have a password which matches the hash when hashed together with the salt. When you are successful, you know the password. – Philipp Jan 14 '15 at 14:10
  • maybe thats where my disconnect is. How would you know what the salt is? I thought the salt was some a pseudo-random piece of of info from the user. Like all user IDs even divisible by 4, take their birth month and add it to the beginning of the users typed password and their birth year at the end. Then do a hash of the concatenated string. This means even if you had a rainbow table containing that string unhashed, you would still not know what the password is, as it contains extra data. – Keltari Jan 14 '15 at 14:23
  • 1
    @Philipp You can't crack a salted hash with a rainbow table, though. A rainbow table does *not* leave the attacker in control of what preimage they find; therefore, the odds that the preimage of a hash that happens to be represented in a rainbow table just *happens* to be prefixed with the salt is astronomically low. – cpast Jan 14 '15 at 14:44
  • 2
    @Keltari Salt should be random, and is normally stored alongside the password hash. If you have broken into a database and stolen a user's password hash, you probably have the salt too. It is not the salt's job to be secret; it is the salt's job to increase the space of possible hash inputs in order to make precomputation attacks such as rainbow tables infeasible. – Nefrubyr Jan 14 '15 at 14:47
  • 1
    Also, the purpose of a salt isn't to increase _length_, it's to increase _entropy_. "Increase length" makes it sound as if having the same salt for every password is secure; it's not, and the idea of a salt is to make it so that even the same user changing his password to the same password has a totally different hash (for that matter, the main 3 password hashes, i.e. PBKDF2, bcrypt, and scrypt, treat the salt completely separately from the password to be hashed). – cpast Jan 15 '15 at 05:09
3

Yes, though some unsalted hashes, like the outdated Windows LM hash, are even worse due to cryptographic deficiencies.

Asking about salting or not means the asker is interested in storing and securing passwords, not in securing their own account. Even with 128 character fully random passwords, an administrator with access to two sites will be able to see if that 128 character password was reused, unless there is a salt. So yes, all unsalted hashes have an inherent insecurity, even if a given password is safe from a rainbow table attack.

Another problem with unsalted hashes is that two users with the same password will have the same hashed password. This means that if the password hashes are accessible, whether by compromise or malicious insider, then duplicated passwords are obvious. Even if they cannot crack the hash, a social engineering attack on one grants access to all. (Or one of the users sees that they can access the others)

Salting is extremely cheap and there is no reason to be implementing a password storage system without it.

Better yet, ask yourself if you really need to be storing passwords

SecsAndCyber
  • 616
  • 5
  • 4
1

If you are referring to "common" password hashing algorithms like SHA1 and MD5 that are used without salt you do not even need a rainbow table, a reverse hash lookup database is sufficient for the majority of poorly chosen end user passwords. Ie: md5("password") will always result in 5f4dcc3b5aa765d61d8327deb882cf99 so when you find the hash 5f4dcc3b5aa765d61d8327deb882cf99 you know it's going to be password. Try searching google for 5f4dcc3b5aa765d61d8327deb882cf99 or any other hash you happen to have.

wireghoul
  • 5,755
  • 2
  • 17
  • 26
1

As always, please first read Thomas Pornin's answer to How to securely hash passwords?

The summary for salting, assuming you have more than one password in your database, and that database is leaked (see Sony, Adobe, Forbes, et al.) so an attacker (cracker, criminal, security researcher, bored high school student, competition cracking team, etc.)

  • With a unique salt per user, and a good hash
    • the attacker must hash each candidate password once per user and then compare it to the hash, because there's a different result for each salt.
    • The more users you have with as-yet uncracked passwords, the longer it takes to try each candidate.
    • There is also no way to tell which users have the same password.

  • With a single salt for all users, usually called an "epic fail"

    • The attacker already knows which users have the same password as another user, which is useful information
    • The attacker must hash each candidate password once total, and then compare that single result to every password hash.
      • Therefore, this is N times worse than unique per-user salts, where N is the number of user records
    • If the attacker gets your salt, then the attacker can also start computing candidate password hashes BEFORE getting your passwords; a big time saver.

  • With no salt at all, or a single salt that's been used before by that attacker (such as "salt")

    • The attacker already knows which users have the same password as another user, which is useful information
    • The attacker must hash each candidate password once total, and then compare that single result to every password hash.
      • Therefore, this is N times worse than unique per-user salts, where N is the number of user records
    • If you used any common hashing algorithm, the attacker can simply pull out previous records of hashes they computed in the past and compare those against your database
    • The attacker can also start computing candidate password hashes BEFORE getting your passwords; a big time saver.
Community
  • 1
Anti-weakpasswords
  • 9,850
  • 2
  • 24
  • 52
0

A salt is basically random values that are appended to a password before they are hashed and stored. The result is that one persons password of "potato" will look different to another persons password of "potato".

Ranbow tables are a massive list of hashes for a long list of different terms and phrases, most commonly for the use of passwords. If your password potato is in a rainbow table a salt will prevent it being broken. If your potato password isn't salted AND it exists in the rainbow table then you are probably out of luck.

The main saving grade you have against an unsalted password is the hope that it is not contained in the rainbow table attacking you. For example, people may create rainbow tables for all the words in the dictionary, but if your password is not in the dictionary and not salted, that rainbow table wont get you.

Toby
  • 101
  • 1