20

i was reading this tutorial, and i encountered the following discussion about encryption. At the end there's written

In the last line, we’ve hashed the salt with the password, yielding an encrypted password that is virtually impossible to crack

But in my opinion an hacker who has both the encrypted_password and the salt could do the "rainbow" trick exactly as if we were using the salt.

So, where i'm wrong?

Thanks!

$ rails console
>> require 'digest'
>> def secure_hash(string)
>>   Digest::SHA2.hexdigest(string)
>> end
=> nil
>> password = "secret"
=> "secret"
>> encrypted_password = secure_hash(password)
=> "2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b"
>> submitted_password = "secret"
=> "secret"
>> encrypted_password == secure_hash(submitted_password)
=> true

Here we’ve defined a function called secure_hash that uses a cryptographic hash function called SHA2, part of the SHA family of hash functions, which we include into Ruby through the digest library.7 It’s not important to know exactly how these hash functions work; for our purposes what’s important is that they are one-way: there is no computationally tractable way to discover that

2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b is the SHA2 hash of the string "secret".

If you think about it, though, we still have a problem: if an attacker ever got hold of the hashed passwords, he would still have a chance at discovering the originals. For example, he could guess that we used SHA2, and so write a program to compare a given hash to the hashed values of potential passwords:

>> hash = "2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b"
>> secure_hash("secede") == hash
=> false
>> secure_hash("second") == hash
=> false
>> secure_hash("secret") == hash
=> true

So our attacker has a match—bad news for any users with password "secret". This technique is known as a rainbow attack.

To foil a potential rainbow attack, we can use a salt, which is a different unique string for each user.8 One common way to (nearly) ensure uniqueness is to hash the current time (in UTC to be time zone–independent) along with the password, so that two users will have the same salt only if they are created at exactly the same time and have the same password. Let’s see how this works using the secure_hash function defined in the console above:

>> Time.now.utc
=> Fri Jan 29 18:11:27 UTC 2010
>> password = "secret"
=> "secret"
>> salt = secure_hash("#{Time.now.utc}--#{password}")
=> "d1a3eb8c9aab32ec19cfda810d2ab351873b5dca4e16e7f57b3c1932113314c8"
>> encrypted_password = secure_hash("#{salt}--#{password}")
=> "69a98a49b7fd103058639be84fb88c19c998c8ad3639cfc5deb458018561c847"

In the last line, we’ve hashed the salt with the password, yielding an encrypted password that is virtually impossible to crack. (For clarity, arguments to hashing functions are often separated with --.)

Abramodj
  • 5,709
  • 9
  • 49
  • 75
  • A duplicate of a number of other questions on SO. – Jonathan Leffler Mar 09 '11 at 22:24
  • possible duplicate of [How does using a salt make a pw more secure if it is stored in the db?](http://stackoverflow.com/questions/4005826/how-does-using-a-salt-make-a-pw-more-secure-if-it-is-stored-in-the-db) – Brendan Long Mar 09 '11 at 22:36

4 Answers4

33

Rainbow tables are expensive to compute. Without the salt, you can build a rainbow table once that can be used repeatedly, since the password "password" will always yield the same hash (md5=5f4dcc3b5aa765d61d8327deb882cf99, sha1=5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8) and is thus easy to identify in a password database.

With a salt, you have to compute a rainbow table for each salt you encounter. A good-sized salt, say 32 bits (ideally, 128 or even more), means you have to compute a rainbow table for every password you want to crack, thus largely defeating its purpose.

Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • But how do you compare the passwords later without also saving the random salt? If the salt is random, there is no way to know what it was without keep track of it, like saving it in your database. So if someone has the DB, they also have the salt! If someone has access to your DB, they probably also have access to your code too, so they could look and see what salt you use also! – Chloe Jun 07 '13 at 16:50
  • 1
    @Chloe: You save the salt along with the password. I usually break it up and insert the parts into the hash at predetermined (unpublished) locations, just to sow a little extra confusion for the hacker to contend with. But even if the hacker manages to isolate the salt, they still can't, in general, use rainbow tables for the reasons stated in my answer. – Marcelo Cantos Jun 08 '13 at 00:21
  • 1
    @Chloe: On another note, your point about having the code is incorrect. The most common way means of data theft is SQL injection attacks, which allow the thief to steal pretty much anything contained in the database, but generally doesn't provide access to code in the business layer. I'm not suggesting that code can't also be stolen — it can — but it's much more difficult, and one needn't presume that stolen data means stolen code. – Marcelo Cantos Jun 08 '13 at 00:30
  • @Chloe: And this isn't a trivial point. If you assume that stolen data = stolen code, you wouldn't bother obfuscating how the salt is mixed with the password, and then, when it turns out that only your data was stolen, you wouldn't have the additional benefit of the hacker not knowing how to discover the salt. – Marcelo Cantos Jun 08 '13 at 00:33
  • I don't believe salt is as important as it once was, nor rainbow tables. [Anatomy of a hack: How crackers ransack passwords like “qeadzcwrsfxv1331”](http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/) – Chloe Jun 11 '13 at 21:42
  • @Chloe: qeadzcwrsfxv1331 is a terrible password. It's a highly regular pattern on a qwerty keyboard. Every password they cracked was flawed. All you could possibly glean from that article is that salts won't turn bad passwords into good passwords (which isn't news). It doesn't invalidate their use. – Marcelo Cantos Jun 11 '13 at 21:48
  • Cannot edit comments! "But the thing about salting is this: it slows down cracking only by a multiple of the number of unique salts in a given list. That means the benefit of salting diminishes with each cracked hash. By cracking the weakest passwords as quickly as possible first (an optimization offered by Hashcat) crackers can greatly diminish the minimal amount of protection salting might provide against cracking." – Chloe Jun 11 '13 at 22:48
  • 1
    @Chloe: Sure, from a hacker's perspective, weak passwords will tumble early, reducing the work ahead of them, but that doesn't mean strong passwords are just around the corner. A unique salt for each password means starting from scratch for every single one, and strong passwords occupy an intractably large space (by definition). Without a salt, rainbow tables built on millions of CPU hours would bring orders of magnitude more passwords into their dragnet. – Marcelo Cantos Jun 11 '13 at 23:31
  • 2
    @Chloe: Incidentally, I agree that rainbow tables aren't as important as they once were, but that's because developers have learned to salt their passwords. If everyone stopped salting passwords, you can bet your bottom dollar that rainbow tables would suddenly become exceedingly popular. – Marcelo Cantos Jun 11 '13 at 23:46
  • yeah but if you know the salt you can create a new rainbow table, isn't it? – Giorgi Moniava Feb 27 '15 at 21:17
  • @gio: The second paragraph of my answer addresses this. – Marcelo Cantos Feb 28 '15 at 11:25
8

Salt is to stop someone from pre-computing a "reverse" lookup table that allows an attacker to quickly find a password that results in the target hash. Creating one of these tables is as much work, computationally, as brute-forcing the target password space, so it's only worthwhile if you can use the table on many targets.

Salt prevents this; the attacker would need to account for the salt when they generated the table, so the table would be good for only a single target, and the attacker is back to brute force.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • more than double I would say (for each bit added), you can position the slat typically at the start, end or middle of your strings if the hacker is serious about hacking, he would have to compensate for at least slat in the beginning and end hence probably tripling the storage space required. – Ali Mar 09 '11 at 22:30
  • +1, the second sentence of the first paragraph is the key observation. – President James K. Polk Mar 10 '11 at 00:49
  • @erickson: yeah but since salt is public he can create a new rainbow table isn't it? (the attacker) – Giorgi Moniava Feb 27 '15 at 21:18
  • @gio Why would he want to do that? – erickson Feb 27 '15 at 21:31
  • @erickson: i meant the attacker. It is claimed salt is used to make harder for attacker to precompute some tables. But as soon as he knows the salt he can then precompute the table again – Giorgi Moniava Feb 27 '15 at 21:37
  • @gio Who claims that "salt is used to make harder for attacker to precompute some tables?" My claim is that creating a rainbow table is more work than a dictionary attack, but provides no additional benefit to the attacker when the password is salted. That's why attackers don't create rainbow tables for salted passwords. – erickson Feb 27 '15 at 23:51
3

Yes, you are right, if somebody had knowledge of your algorithm and the salt, he could generate a rainbow table. However, generating a rainbow table takes a long time the more characters are allowed.

So for example, if you have an password consisting of 10 characters, which all are numbers, you have 10^10 possibilites. If you allow lower and upper case alphabetical chars, this goes up to 62^10 possibilites, a mere 8.39 * 10^17 permutations; and that's only for 10 character passwords, you also have to take into account any length below that and above, depending on the length of password you allow.

It takes a long time generate such a table, while rainbow tables for the algorithm itself might be readily available, the salt modifies the algorithm to make it your own, and the possibility for a table existing for that is very low.

Femaref
  • 60,705
  • 7
  • 138
  • 176
  • Good explanation. From what I understand, it basically just makes the password longer to decrease the probability of guessing it. – Despertar Jun 01 '12 at 10:02
  • 1
    Not really. It doesn't change the password, in the ideal case it would take exactly the same amount of time to brute force it, salted or not. The salt is a defensive mechanism if the attacker has the database. If you use a known algorithm, chances are there is a database of clear-text:hash mappings readily available. If you manipulate the clear text before hashing, these tables become useless, you'd need to generate a table for each salt. If you have a salt for every password in your database, you'd need to generate a table for each password. – Femaref Jun 01 '12 at 21:05
2

If you use salt (even if it is public but uniqueto a site) you will get a protection from hash-dictionaries, where often used passwords are already hashed.

If your salt is secure then they can not brute-force it using supercomputers. They have to check every possible password with your server (which let's hope has some form of bruteforce-protection).

vbence
  • 20,084
  • 9
  • 69
  • 118
  • 1
    If the have the hash value and salt, they can try to brute-force it on their own systems, so brute force protection on your servers will do nothing against this class of attack (when they've got your login information). We can safely assume they can get the algorithm. – David Thornley Mar 09 '11 at 22:30
  • 2
    @vbence: You don't use a single salt at a site. You use a different salt for each password. – Marcelo Cantos Mar 09 '11 at 22:34
  • Yes, that is exactly what I have written, public salt only protects against dictionaries, secret salt protects against them doing the cracking on their own system. - I'm not talking about hacking scenarios when they might get your salting algorythm together with your data. – vbence Mar 09 '11 at 22:35
  • @Marcelo Cantos I avoided that topic in my post as it can be the subject of a longer conversation I'd happily participate in. – vbence Mar 09 '11 at 22:38
  • @vbence: A fixed salt is weaker than a per-password salt. I don't how much discussion there is to be had on that topic. – Marcelo Cantos Mar 09 '11 at 22:43
  • Just like erickson said, if you use salt (any salt, specific to your site) then the dictionary has to be specially made for your site. If you include the username in the salt too then the dictionary has to be created for that single user, so it is not even a dictionary any more. Thanks for testing me, and as I said I'm looking forward to our conversation in an earlier hour. – vbence Mar 09 '11 at 23:01