3

So, as I understand it, you prepend a password with salt before you hash it so that the resulting hash can't be used with a rainbow table to find the original password, as you could if the password alone was hashed. But what's to stop someone from recomputing a new rainbow table with the salt prepended if the salt is known? I thought knowing the salt wasn't supposed to matter security-wise?

Andrei Botalov
  • 5,317
  • 10
  • 46
  • 73
John
  • 2,262
  • 2
  • 28
  • 45
  • maybe also read: [http://stackoverflow.com/questions/1645161/salt-generation-and-open-source-software/1645190](http://stackoverflow.com/questions/1645161/salt-generation-and-open-source-software/1645190#1645190) – Jacco Jul 02 '12 at 07:35

3 Answers3

12

One word: cost.

It is much more costly to built the table than to directly try to break the password. Trying to brute-force the password requires only a trivial amount of memory; a rainbow table requires a huge storage space.

The only point of a table is that someone else has computed it and you can now use it. Many people using one table (or the same person using the table several time) pays up for the cost of building that table. If you are going a table once (for one password), there is just no point.

If every password in a given (really big) password database was using the same salt, that would be a different story. But would be a gross misuse of the salt: the point is that every password uses a different salt, so a rainbow table can never pay up.

Salting does not imply that you cannot try to break-force the password directly. Not only you can, but it is not more difficult when there is a salt. What you cannot do is reuse previous computing efforts (unless the system so broken as to not be able to generate a different salt each time).

curiousguy
  • 5,038
  • 3
  • 25
  • 27
  • So salting one particular password does not protect the password any better? – John Jun 30 '12 at 02:38
  • @John In a world where there is exactly **one** hashed password with a given hashing function? No, it does not. – curiousguy Jun 30 '12 at 04:05
  • 1
    +1 "One word: **cost**." It is amazing how many people use one universal salt. I blame the books with titles like "Learn A in B minutes" – Kurt Jun 30 '12 at 07:50
  • 3
    Car factories are very efficient ways to make cars. But if you only need one car, you wouldn't go to the trouble of building a factory just to make it. Rainbow tables are like car factories. Expensive to build, but worth it because they can make attempts on *many* passwords. Salting makes rainbow tables useless. It's more work to make the table than just try to brute force the password. – David Schwartz Jul 01 '12 at 12:30
  • @DavidSchwartz "_car factories_" Great comparison. – curiousguy Jul 01 '12 at 13:34
  • Ok, so the main reason why I asked is that I have a desktop application that I'm developing that I want to lock down with a log in. But if I store the hash of the chosen password to validate on login, is there a risk that the password could be hacked? – John Jul 01 '12 at 17:17
  • 1
    @John "_is there a risk that the password could be hacked?_" Do you store enough informations to check the user password? _If not, you couldn't even verify the provided password._ If so, **with these informations**, an attacker can check any number of passwords. For example, an attacker can try dictionary words, dictionary words plus one digit, etc. You could slow down that process, but you can't prevent it. May I ask why how the attacker would get the hash? – curiousguy Jul 01 '12 at 19:23
  • Well, the application will run offline. I need to store the hash of the password chosen on installation to verify the offline login. I'm realizing as I do more research, though, that my cryptographic function that I use to generate the hash needs to be so expensive to run that it makes brute forcing impracticable. The salt only prevents precomputing, not brute forcing. – John Jul 02 '12 at 15:03
  • @John Who chooses the password? Is it randomly generated? If the password is _randomly generated with enough entropy_, bruteforcing it will _not_ be possible (a salt is not even needed), but the password will not be pretty. – curiousguy Jul 02 '12 at 16:52
  • The password is user-chosen but I plan to implement reasonably strong password rules so that the user should be forced to pick a strong password. – John Jul 02 '12 at 16:56
  • @John "_implement reasonably strong password rules_" such as? – curiousguy Jul 02 '12 at 17:00
  • At least 8 characters, upper and lower case and symbols. – John Jul 02 '12 at 17:01
  • @John so `Passw0rd.` is considered "reasonably strong"? – curiousguy Jul 02 '12 at 17:03
  • Yes, technically. – John Jul 02 '12 at 17:05
  • @John These rules are annoying. They do not (and cannot) guaranty strong password (= good entropy), but they make passwords harder to remember. Choosing a good password is hard, and these rules make it even harder. My advice is to explain the user what a good password is, and how to make one, and have a function to randomly generate a password if the user prefers. – curiousguy Jul 02 '12 at 17:09
  • We need to enforce certain password requirements for security audits, most likely. However, do you know where I can find a function that generates secure, easy to remember passwords? I know Mac OS X can do this. Anything .NET that you recommend? – John Jul 02 '12 at 17:50
  • let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/3964/discussion-between-curiousguy-and-john) – curiousguy Jul 02 '12 at 17:57
1

Absolutely nothing: you can calculate a rainbow table for each salt just like you do for an unsalted hash. The rainbow table is a space/time trade-off, and the purpose of the salt is to make that more costly.

Every bit of salt you add doubles the storage requirements. So, one bit of salt means twice the storage space. 8 bits of salt, 2^8 or 256 times the storage requirement. 32 bits - 4 characters - of salt, 2^32, or 4,294,967,296 times the storage space to fully calculate the rainbow table.

Daniel Pittman
  • 189
  • 2
  • Since the salt for a password is know, it is suggested to compute a rainbow table for just this particular salt value, not a generic table for every possible salt. Which is of course costly and pointless. – curiousguy Jun 29 '12 at 23:35
  • 1
    @curiousguy: There would be no point in computing such a table. You might as well just try to brute force that one password. What advantage does the table give you other than wasting a bunch of storage space? – David Schwartz Jul 01 '12 at 12:32
  • @DavidSchwartz Establishing records? I thougth rainbow tables were about establishing new records in size. – curiousguy Jul 01 '12 at 13:32
1

When you build a rainbow table, you compute the attacked hash function on many inputs. Any input value which you did hash during table building will be attacked successfully; and the table will not break any other. Due to some unavoidable quirks in the building process (that's a byproduct of the rainbowness of the table), you will hash some input values several times. Taken all together, a rainbow table which can break N possible passwords has a building cost of about 1.7*N, i.e. 70% more than simply hashing all these passwords in a basic brute force cracking.

So table building is worth the effort only if the table can be used at least twice, to (try to) crack two passwords or more. Salts prevent that. With salts, each table would be specific to a single hashed password (strictly speaking, to a single salt value).

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955