3

Here's my understanding of a salted / hashed authentication scheme:

string plaintextPass = Request.Form["password"];
string salt = UserRecordFromDb.Salt;
string toHash = salt + plaintextPass;

string hash = bcrypt(toHash);

return(hash == UserRecordFromDb.HashedPassword);

The trouble is, the algorithm adds the salt in a predictable way. If I could use a rainbow table to get the plaintext including the salt I could find and trash the salt. There are enough users that use bad passwords anyway to make the salt adding pattern easy to recognize1.

For example, if I recovered these plaintexts from my rainbow table attack:

1: passwordW0fkvE
2: secretJEn3cx
3: t4k3nVdksE12
4: purplehorse1593vE1r

#3 doesn't tell me very much. It's a good password so the salt is unrecognizable. But from #1 and #2 I can see the salt is probably 6 characters added on to the end. I can use that information for #4 to figure out the password is purplehorse15.

1 Note: If you store the salt and the username / hashed pass in the same DB, I don't even need to guess what the salt is. It's right there in front of me. The extra step of guessing the salt is only necessary if the salt is stored in some other DB.

just.another.programmer
  • 263
  • 3
  • 11
  • 2
    You have a different salt per account. They can still attack it in the same way, but the salt means they need a new rainbow table for each account instead of one for all accounts. Plus it makes the overall hashed string longer and therefore harder to build a rainbow table for. – WDS Sep 10 '15 at 07:25
  • 1
    @WDS Having a different salt for each account does not make any difference if I can recognize and remove the salt from the plaintext. – just.another.programmer Sep 10 '15 at 07:26
  • 2
    Well I suppose what I said was in a sense two different presentations of the same concept. Sorry for that. Let me try this way. Imagine you are going to build a rainbow table that covers every possible combination of values up to 7 characters. That is hard enough. If the salt makes these strings 12 characters long, or whatever, that is much harder. You have the random salt making "password" become "passwordW0fkvE" So just to attack the common (bad) password "password" they cannot just have one entry. Now they need one entry for each possible salt value. – WDS Sep 10 '15 at 07:32
  • But if they make a rainbow table anticipating the salt of "W0fkvE" they do no better. That salt will only "hit" for them on that one account because you used a different salt each time. Same thing with "secret". Without a salt, they need one entry in the rainbow table. With a 6 char salt, they need millions of entries in the rainbow table just to attack the user password of "secret" – WDS Sep 10 '15 at 07:35
  • Now of course all of that also assumes the same caution is taken you mention in your note, that the salt is not right in front of them. If it is, their job is made much easier. – WDS Sep 10 '15 at 07:38
  • @WDS And once you know the salt you presumably also know the hash, at that point it will be pointless to build a rainbow table which can only be used for that one salt. A direct brute force attack would be faster than building a rainbow table. – kasperd Sep 10 '15 at 09:06
  • 1
    @kasperd Exactly. The salt doesn't make the attack impossible -- nothing can do that. But it does make a rainbow table impractical both in terms of storage and computation requirements. Once a brute force attack is the best the attacker can do, the salt has done its job and proved its worth. Because brute forcing those passwords individually would be a lot harder than a single rainbow table that would be possible if no salt were added. – WDS Sep 10 '15 at 09:11
  • 1
    @WDS I would say there is one and only one thing, which can make the attack impossible. That is a sufficiently strong password. – kasperd Sep 10 '15 at 09:15

2 Answers2

3

A couple of items to consider:

  1. It is important to note that a rainbow table works differently than a straight-up precomputed hash table. (althought a rainbow table with a chain length of 1 is essentially the same thing as a precomputed hash table -- most rainbow tables have many many chains though)

  2. Rainbow chains have trouble with passwords with LARGE salts. A short salt (6 chars) might not be a huge problem for them to deal with. (but again, exponentially longer for each additional char)

The problem with straight-up precomputed hash tables is that they get HUGE. Even generating a precomputed table of only digits, length 0-8 turns in to many gigabytes. If you start adding in alpha/symbols it gets gigantic. So the addition of even 6 characters of salt will increase the size of your lookup table greatly.

A rainbow table offers a mix between storing on-disk and computation by using chains. You would use less space than a full precomputed hash table, and it would probably be fine for short salts, but dealing with large salts would require a LOT of space.

Here is an excellent site that describes the actual steps and gives examples for how it works:

https://stichintime.wordpress.com/2009/04/09/rainbow-tables-part-5-chains-and-rainbow-tables/

This other post explains a bit more about rainbow tables: What are rainbow tables and how are they used?

To summarize -- it is plausible that you could use a rainbow table or a precomputed hash table to solve the passwords. The salts just add more entropy by adding characters to the length. It DOES make it WAY HARDER as you are essentially now brute-forcing a random password of n-chars + salt.

Lastly - to address the issue that if you already know the salt: I don't believe this would do you any good, as the hashes are one-way and because of how rainbow tables work you would have to have a custom reduction function in the rainbow table that generated plaintexts that ended in the salt. Otherwise since rainbow tables generate their next plaintext off the reduction of the previous chain, if you didn't use a custom reduction function it would be impossible to incorporate the salt to the end of the resulting plaintext. It would probably be simpler to use a plain precomputed hash table in that instance but again you would need one for each salt.

Community
  • 1
nyxgeek
  • 1,297
  • 10
  • 22
0

I would like to make several points about your issue. Salts have been designed to prevent rainbow table attacks. Rainbow tables offer a trade off between speed and space, basically you speed up the cracking process by looking in your precomputed table entries. In your case for each word, you would have to generate up to 2**48 entries, the amount of space you would need is huge! The next point i would like to make is that the hashing algorithm used is bcrypt. bcrypt can be very slow, especially if the set cost is high, rainbow table generation would take you weeks, months or years depending on your hardware. Rainbow tables are not the solution here.

Othman
  • 11
  • 2