13

I am learning Rails, at the moment, but the answer doesn't have to be Rails specific.

So, as I understand it, a secure password system works like this:

  • User creates password
  • System encrypts password with an encryption algorithm (say SHA2).
  • Store hash of encrypted password in database.

Upon login attempt:

  • User tries to login
  • System creates hash of attempt with same encryption algorithm
  • System compares hash of attempt with hash of password in the database.
  • If match, they get let in. If not, they have to try again.

As I understand it, this approach is subject to a rainbow attack — wherein the following can happen.

An attacker can write a script that essentially tries every permutation of characters, numbers and symbols, creates a hash with the same encryption algorithm and compares them against the hash in the database.

So the way around it is to combine the hash with a unique salt. In many cases, the current date and time (down to milliseconds) that the user registers.

However, this salt is stored in the database column 'salt'.

So my question is, how does this change the fact that if the attacker got access to the database in the first place and has the hash created for the 'real' password and also has the hash for the salt, how is this not just as subject to a rainbow attack? Because, the theory would be that he tries every permutation + the salt hash and compare the outcome with the password hash. Just might take a bit longer, but I don't see how it is foolproof.

Forgive my ignorance, I am just learning this stuff and this just never made much sense to me.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
marcamillion
  • 32,933
  • 55
  • 189
  • 380
  • possible duplicate of [Where do you store your salt strings?](http://stackoverflow.com/questions/1219899/where-do-you-store-your-salt-strings) – blowdart Oct 23 '10 at 20:16
  • Nope. I am not advocating or asking if it makes more sense to store the salt elsewhere than the db. I am trying to explore the idea of how a salt is actually more secure, in an age when computing resources are so cheap. – marcamillion Oct 23 '10 at 20:22
  • SHA-2 is a hashing algorithm. Hashing is a different concept to encryption. – wulfgarpro Nov 23 '16 at 05:52
  • See the accepted answer to this question; https://stackoverflow.com/questions/1219899/where-do-you-store-your-salt-strings It explains how the hash thwarts rainbow attacks. – nickd Oct 23 '10 at 20:13
  • This does explain the idea behind the rainbow table to me (i.e. going against the notion of doing a str8 up brute force of every permutation by doing pre-calculations/guesses in the form of a rainbow table). But I still don't understand why it's so impossible to crack in a day and age when computing resources are so cheap. – marcamillion Oct 23 '10 at 20:21
  • It's not impossible - with enough time you could brute force a salted hash. This is why you still make some attempt to keep your database private :) And of course it's not the only consideration. Others include using a good hashing algorithm - many of them focus on being fast at hashing, which is the opposite of what you want when hashing passwords. – Nick Oct 23 '10 at 20:40
  • @Nick. Quite. Many standards suggest hashing salted passwords multiple times (typically >1000) because the extra computation required does not greatly hinder the checking of one password, but does significantly hinder brute-force attacks. – dajames Oct 26 '10 at 12:13
  • BCrypt is one of the algorithms that has this sort of protection built in. Even better is that you can configure the number of encryption rounds, so as computers get faster you can just keep increasing the complexity for new hashes. – Nick Oct 26 '10 at 18:45

3 Answers3

8

The primary advantage of a salt (chosen at random) is that even if two people use the same password, the hash will be different because the salts will be different. This means that the attacker can't precompute the hashes of common passwords because there are too many different salt values.

Note that the salt does not have to be kept secret; it just has to be big enough (64-bits, say) and random enough that two people using the same password have a vanishingly small chance of also using the same salt. (You could, if you wanted to, check that the salt was unique.)

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Oh ok. So the idea is that the attacker won't be doing a brute force attack (comparing the salted string with the pw hash in the db) because it takes too much - provided that the salt + pw hash are long enough (64-bits a piece)? If that is the case, doesn't that not make much sense in a day and age when vast computing resources are getting cheaper/free? For instance, if an attacker has access to a botnet of 1 million computers, why could he not write a script to just do that brute force comparison of each salt with those million machines? – marcamillion Oct 23 '10 at 20:19
  • 3
    It takes a rather long time to brute force a hash, and even if it were as easy as you're implying, you'd still stop anyone without a million computer botnet at their disposal. – ceejayoz Oct 23 '10 at 20:30
  • 2
    The goal is to make it harder to break passwords than other methods of attack. If the attacker can read the database AND has sufficient computing time available to build a rainbow table for the salt value for each account the attacker wants, then either you or the attacker misjudged the risk / value of breaking into your site. – Slartibartfast Oct 25 '10 at 04:08
  • Sure, this makes brute-force a pain. It doesn't make it any harder if the attacker has indeed compromised the password database where the salt is stored in plain-text. – wulfgarpro Nov 23 '16 at 06:01
8

First of all, what you've described isn't a rainbow attack, it's a dictionary attack.

Second, the primary point of using salt is that it just makes life more difficult for the attacker. For example, if you add a 32-bit salt to each pass-phrase, the attacker has to hash and re-hash each input in the dictionary ~4 billion times, and store the results from all of those to have a successful attack.

To have any hope of being at all effective, a dictionary needs to include something like a million inputs (and a million matching results). You mentioned SHA-1, so let's use that for our example. It produces a 20-byte (160-bit) result. Let's guess that an average input is something like 8 characters long. That means a dictionary needs to be something like 28 megabytes. With a 32-bit salt, however, both the size and time to produce the dictionary get multiplied by 232-1.

Just as an extremely rough approximation, let's say producing an (unsalted) dictionary took an hour. Doing the same with a 32-bit salt would take 232-1 hours, which works out to around 15 years. There aren't very many people willing to spend that amount of time on an attack.

Since you mention rainbow tables, I'll add that they're typically even larger and slower to start with. A typical rainbow table will easily fill a DVD, and multiplying that by 232-1 gives a large enough number that storage becomes a serious problem as well (as in, that's more than all the storage built in the entire history of computers, at least on planet earth).

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Ok fair enough. Your math makes sense. I can see how this attack is not foolproof, but enough to deter 'undetermined' attackers. But it is fair to say that using a hash + salt can still be cracked, right? For example, that 15 years can be cut down significantly with 100,000 computers doing the computation or even 1 million. If you assume that the attacker has essentially unlimited computing resources to throw at the problem (e.g. say they hacked Google and have axs to all of Google's servers - far fetched, but just illustrating a point) then doing a dictionary attack makes sense, right? – marcamillion Oct 23 '10 at 20:34
  • 2^32-1 bits = 4,294,967,295bits = 536MBytes. Unless you meant 2^32-1 * 32-bits, then that's not much storage. Even then, 2^32-1 * 32 = 17.179GB. – marcamillion Oct 23 '10 at 20:38
  • @marcmillion: you also have to coalesce the results, so even with a lot of servers, you also need good communication, coordination, etc., to do it (but yes, it's ultimately possible). Not sure where you're trying to go with your math. Each bit you add to the key doubles the size of the dictionary. – Jerry Coffin Oct 23 '10 at 21:03
  • 2
    @marcamillion The attacker would need that much storage _per_password_, if they wanted to generate every hash for every salt. Of course, in practice, they'd need less due to the way rainbow tables work, but the amount of storage required is still prohibitive. – Nick Johnson Oct 23 '10 at 22:36
  • I agree and was just wondering if it is ultimately possible. @Nick, Ahh...that makes sense. Interesting. Thanks for explaining that. – marcamillion Oct 24 '10 at 01:33
1

The attacker cannot do a rainbow-table attack and has to brute-force which is a lot less efficient.

Florian Mayer
  • 3,041
  • 24
  • 17