Let's talk security

[Jeff Mott]

Right, pre computed hashes. So if i know the salt for the entire db, I rehash my dictionary with that salt. How long will that take? One could write a pretty simple application that takes the salt from each record, re hashes the dictionary for that single record, checks for a match, moves on to the next.

Does anyone know how large dictionaries usually are and how long it might take to rehash the entire db once through on a decent machine?

If the DB has only a static salt, then here's what an attacker would probably do: hash(Salt + common password such as "abc123"), then search the database for that hash. If any user in your entire DB used that password, then in one fell swoop, the attacker would have identified the password for one or maybe multiple users. But if every user has a unique salt, then the attacker can't check all passwords at once. He would need to re-compute the hash for each user.

How much time it would take depends on the objective and password strength. If the attacker is looking for any random user with a weak password so that he can exploit that user on other sites, then it probably won't take much time. Let's say he has a list of 5 thousand most common passwords, 1 million users in your DB, and 1 ms to compute a hash, then it would take about 2 months to identify the users with weak passwords. (Though, password strengthening can increase that compute time by 100x or 1000x.) On the other hand, if the objective were to attack your site specifically by brute-forcing the admin password (hopefully a strong password of at least 8 mixed case, numbers and symbols) then it would take a couple hundred thousand years.

[K. Wolfe]

If the DB has only a static salt, then here's what an attacker would probably do: hash(Salt + common password such as "abc123"), then search the database for that hash. If any user in your entire DB used that password, then in one fell swoop, the attacker would have identified the password for one or maybe multiple users. But if every user has a unique salt, then the attacker can't check all passwords at once. He would need to re-compute the hash for each user.

How much time it would take depends on the objective and password strength. If the attacker is looking for any random user with a weak password so that he can exploit that user on other sites, then it probably won't take much time. Let's say he has a list of 5 thousand most common passwords, 1 million users in your DB, and 1 ms to compute a hash, then it would take about 2 months to identify the users with weak passwords. (Though, password strengthening can increase that compute time by 100x or 1000x.) On the other hand, if the objective were to attack your site specifically by brute-forcing the admin password (hopefully a strong password of at least 8 mixed case, numbers and symbols) then it would take a couple hundred thousand years.

Assuming the hacker has read access to your source code since he rooted you. He can found out where your salt is being applied before hashing:

..Actually.. After starting to write out a loop I realized this can probably be done with one query once syntax was worked out.

select
u.user_name, u.hashed_password, u.salt, h.common_pass
from
common_passes h
inner join users u on md5(h.common_pass||u.salt) = u.hashed_password

Not sure if you can access u.salt in this way, but I'm positive there's some way of doing it, perhaps with some sub queries, or a WITH clause. (I think I hear @r937 ; coming)

[Jeff Mott]

I'm not at all suggesting that you try to hide the salt. If the attacker has access to both your DB and your code, then it wouldn't do any good anyway.

[Lemon Juice]

I have an idea for increasing password security and I wonder what you think about it as I've never seen anyone mention anything like it. Basically, I would not store the salt either in the application code nor in the database so the intruder would not find it there. The salt would be stored on a separate remote server, most probably in a different location, and the main site would contact (for example a php page through https) the remote server for the user's salt each time it is required during authentication. Therefore the salt is not stored anywhere except in PHP memory for a split second of the script duration. Obviously, the intruder would see the PHP code needed to retrieve the salt and he would know the remote URL so he could run it himself but the remote code would check the requester's IP and user agent and if it doesn't match the one specific to the main server then a wrong salt would be sent back without any warning to the intruder, however the remote script would immediately notify the site admin of a possible attack attempt.

This would work provided the attacker tries to contact the salt server using his own methods since the IP and user agent will be wrong and so he would get wrong salts. When he has wrong salts then he might waste a lot of time trying to brute force a password unsuccessfully. But what if he uses the attacked server to request the salt? I have come up with a second line of defense:

Each time a user tries to log in their login attempt is logged in the database of the main site. Each time the main site requests a salt from the remote server the remote server stores this request in its own database. So as you can see there are 2 databases with separate logs but these two logs have to match. One login attempt means one request for a salt therefore if the remote database contains salt requests that haven't been logged in the main database then it means someone is trying to break the system. A cron job could be run by the remote server (or any other off-site server) that would compare the logs every couple of minutes and notify the admin of any suspect activity. If the admin can act fairly quickly he may then take appropriate steps to secure his system before any serious damage is done.

Of course there's the question "what happens in the intruder gets the remote salts in the same way as the original authentication script with storing login attempts in the main database?". I think it would be very unlikely because first he would need to know that storing login logs is essential not to be caught red handed - how would he know that if the hidden detector is not on this server at all? He would need to break to the other server as well but he may not even think he needs to. Second, an intruder most probably doesn't want to leave any trace of his activities so he would certainly craft his script to fetch the salts without storing his actions in the log.

This solution would certainly require a separate secure and reliable server for keeping and serving salts but in my opinion it would make his job a lot more harder compared to a situation where all passwords and salts are available after breaking into the main server. The main help would be in having a mechanizm that notifies the admin that someone is trying to get to the passwords. What do you think about it? This is entirely my own idea and I wonder if it is any good

[Jeff Mott]

Seems like we keep moving the salt one more server away. First the salt was in the database. But what if the database server is rooted? Move the salt to the application. But what if the application server is rooted? Move the salt to some other remote server. But what if....

None of these solutions have fundamentally fixed the problem, because the problem is: "What if your servers are compromised." In that kind of scenario, you have to assume that the attacker knows everything and has access to everything.

[felgall]

Seems like we keep moving the salt one more server away. First the salt was in the database. But what if the database server is rooted? Move the salt to the application. But what if the application server is rooted? Move the salt to some other remote server. But what if....

None of these solutions have fundamentally fixed the problem, because the problem is: "What if your servers are compromised." In that kind of scenario, you have to assume that the attacker knows everything and has access to everything.

It is called "security by obscurity" and has nothing to do with security at all - it just makes the person implementing it feel like it is more secure even though it isn't. It is a really common mistake made by those who know very little about security.

What everyone needs to realise (as you and I already know) is that with an appropriate hashing algorithm you could have a JavaScript version of the hashing where everyone can see all the code and it would still be just as secure - because the hashing algorithm together with salt and pepper do not rely on obscurity at all in order for them to be secure.

[Lemon Juice]

If the attacker must break into two servers instead of just one in order to get to the passwords then isn't it logical that the system is more secure because it is more difficult for the attacker?

[K. Wolfe]

If the attacker must break into two servers instead of just one in order to get to the passwords then isn't it logical that the system is more secure because it is more difficult for the attacker?

Yes, but I think the ultimate goal is to keep everything within the same server. So I'm curious if something like I mentioned earlier is possible.

select u.user_name, u.hashed_password, u.salt, h.common_pass from common_passes h inner join users u on md5(h.common_pass||u.salt) = u.hashed_password

Assuming it is, what steps should be taken to hide how either the salt is implemented, or add in another piece of security.

[Jeff Mott]

I think that SQL query hides the fact that there will be thousands of common passwords to be tested against each user -- an n^2 operation. Effectively the query is trying to just guess passwords, one by one, and there's really nothing you can do to stop that except to make it computationally expensive. If you hash your passwords not jut once, but iteratively 100 or 1000 times, then you can significantly increase the time it takes to guess passwords. The 2 months I quoted earlier could become 200 months (~16.5 years).

[K. Wolfe]

I think that SQL query hides the fact that there will be thousands of common passwords to be tested against each user -- an n^2 operation. Effectively the query is trying to just guess passwords, one by one, and there's really nothing you can do to stop that except to make it computationally expensive. If you hash your passwords not jut once, but iteratively 100 or 1000 times, then you can significantly increase the time it takes to guess passwords. The 2 months I quoted earlier could become 200 months (~16.5 years).

My example was looking at a rainbow table rather than a brute force attack.

[Jeff Mott]

If you have a unique salt for each user, which your SQL query implies, then rainbow tables can't be used.

[K. Wolfe]

If you have a unique salt for each user, which your SQL query implies, then rainbow tables can't be used.

I was also supplying an example of how it might be used. I know the syntax is not 100% accurate but I know it can be done, depending on computing power. At worst, I can run a loop to rehash my rainbow directory for each record to check for a match, but I believe it can be done with one simple query (such as the one I posted twice)

[Jeff Mott]

At worst, I can run a loop to rehash my rainbow directory for each record to check for a match

This part right here is what makes it not a rainbow table. A rainbow table is a pre-computed table of hashes. But if you have to re-compute that table for each user, then it isn't a pre-computed table at all.

[cpradio]

This part right here is what makes it not a rainbow table. A rainbow table is a pre-computed table of hashes. But if you have to re-compute that table for each user, then it isn't a pre-computed table at all.

Ah but that begs the question, if you take an existing rainbow table, and recompute the hash, is it not still a rainbow table? You just rebuilt the hashes, because you saw in the source code that the "pre-existing" rainbow table you had would be insufficient.

Granted, the time it would take to generate new hashes for an existing rainbow table could be lengthy, but in the end if you are going to utilize the new re-computed hashes in the same manner you would have utilized the pre-existing rainbow table, is it not the same?

I'm not going to argue that one way over another, but it does strike me as an interesting consideration...

[Jeff Mott]

Ah but that begs the question, if you take an existing rainbow table, and recompute the hash, is it not still a rainbow table? You just rebuilt the hashes, because you saw in the source code that the "pre-existing" rainbow table you had would be insufficient.

Granted, the time it would take to generate new hashes for an existing rainbow table could be lengthy, but in the end if you are going to utilize the new re-computed hashes in the same manner you would have utilized the pre-existing rainbow table, is it not the same?

I'm not going to argue that one way over another, but it does strike me as an interesting consideration...

Technically, yes, it's a rainbow table, but it's the most useless rainbow table you'll ever make, because it's specific to only one particular salt/user. Basically you're brute-forcing a password and storing all the incorrect passwords in a table, and those stored results can't be reused.

[K. Wolfe]

This part right here is what makes it not a rainbow table. A rainbow table is a pre-computed table of hashes. But if you have to re-compute that table for each user, then it isn't a pre-computed table at all.

Oye, you're recomputing the rainbow table, of common passwords, call it what you want. Its still a table of common passwords no matter if I have to rehash it to a specific salt. And after a quick test, I was able to md5 1k records in .0311. So on my 2.1GHZ laptop, I'd be able to rehash my "rainbow" table of 1 million common passwords in 30 seconds. So it would take about a year to go through another 1 million uniquely salted records using a loop on my laptop to see if there are any matches.

Now that would be using a programmed loop on a slow machine, I think you'd see a big increase in performance if some simple SQL could be wrote to do the same thing such as the example I provided above.

But back on topic please: What extra steps might you take other than a unique salt on each record? I'm hoping for an additional layer that someone would hav e to get through in order to have hopes of working with my data, such as an encrypted executable (if this exists or makes sense) to send the password through first with a little extra salt added in the executable.

[cpradio]

Technically, yes, it's a rainbow table, but it's the most useless rainbow table you'll ever make, because it's specific to only one particular salt/user. Basically you're brute-forcing a password and storing all the incorrect passwords in a table, and those stored results can't be reused.

True, and I get that, but I think that was the angle K. Wolfe was coming from. What would be interesting, is if you have a pre-existing rainbow table that you need to re-compute to use against a breached database dump, is it faster to brute force or to re-compute the rainbow table and then utilize it?

I don't know that anyone could specifically answer that question, in the end, I think it should be acceptable to say, either approach will take days to months to years to accomplish, and hopefully by then you were able to re-hash your live data, so the end result couldn't be used again (and block whatever hole the attacker used).

[K. Wolfe]

True, and I get that, but I think that was the angle K. Wolfe was coming from. What would be interesting, is if you have a pre-existing rainbow table that you need to re-compute to use against a breached database dump, is it faster to brute force or to re-compute the rainbow table and then utilize it?

I don't know that anyone could specifically answer that question, in the end, I think it should be acceptable to say, either approach will take days to months to years to accomplish, and hopefully by then you were able to re-hash your live data, so the end result couldn't be used again (and block whatever hole the attacker used).

I believe checking a common library, even while re-hashing for each salt will be faster than a brute force, and will yield more results, unless your goal is only one user.

Thinking back on my last post, this was only utilizing one connection and one db. I have no doubt that some multi threading and splitting the recordset into smaller chunks to spread out the load would make things much faster. I'd speculate with several server class machines, my 1 million record example could be run through within a week.

Perhaps password hashing isn't the correct subject, maybe we should look at encoding and decoding social security numbers?

[Jeff Mott]

Oye, you're recomputing the rainbow table, of common passwords, call it what you want. Its still a table of common passwords no matter if I have to rehash it to a specific salt.

Consider these two scenarios: 1) You use a user's salt and the list of common passwords, hash them one by one, and as you go, check if any of those hashes match the user's hash. This is a brute-force search. Or 2) you use a user's salt and the list of common passwords, hash them one by one, and store those hashes in a table. After the table is completed, you check if the user's hash is in that table. (The table can't be reused for any other user.)

Both options are effectively a brute-force search, and the step where you create the table is actually redundant. The table is only useful if you can reuse it for other users, but due to user-unique salts, you can't.

And after a quick test, I was able to md5 1k records in .0311. So on my 2.1GHZ laptop, I'd be able to rehash my "rainbow" table of 1 million common passwords in 30 seconds.

In my math, I presumed a list of 5000 common passwords, and you'd have to rehash those 5000 passwords for each of your 1 million users. That means you have 5 billion hashes to compute, at a speed of 1000 hashes per 0.0311 seconds, means it'll take about 2 days. If you introduced key strengthening (that is, when your application hashes a user's password, it does so iteratively 100 or 1000 times or more), then you can increase that 2 days to 200 or 2000 days or more, respectively.

But back on topic please: What extra steps might you take other than a unique salt on each record?

Key strengthening.

[K. Wolfe]

I do believe you're missing my approach, either way I'd like to move on please.

[ServerStorm]

Hi Kyle,

Have you looked into the CRYPT_BLOWFISH cypher offered in PHP. This is a very slow cypher to attack, excruciating slow when using a Salt and you don't need to store the salt in the db as it is enclosed in the hashed string.

You can also see if the Portable PHP password hashing framework will help you.

For the record I currently favour using this as it gets away from having to worry about storing the hash in the database (other than the entire hashed password string). As hackers won't know the cypher length you've chosen and combining this with a per password salt you've got quite a good hash. It won't protect you from dumb passwords like 'password' or '12345' but you can use JavaScript with a fallback to PHP to make sure that passwords are a suitable length, have a proper mixture of upper/lower case letters, numbers, and symbols.

Recently a Blowfish security hole was fixed so for now I feel good about the cypher.

If I've missed your needs then I apologize

Regards,
Steve

[Lemon Juice]

It won't protect you from dumb passwords like 'password' or '12345'

Isn't this true that all these techniques for strong passwork hashing, key strengthening, etc. are used because people often have weak or not very strong passwords? If someone has a long and unique password that is guaranteed not to be in any rainbow table then even if it is hashed with plain md5 with no salt then the attacker won't be able to find it in any practical time frame? The only requirement is that the hash function is really irreversible. Am I correct?

[ServerStorm]

Isn't this true that all these techniques for strong passwork hashing, key strengthening, etc. are used because people often have weak or not very strong passwords? If someone has a long and unique password that is guaranteed not to be in any rainbow table then even if it is hashed with plain md5 with no salt then the attacker won't be able to find it in any practical time frame? The only requirement is that the hash function is really irreversible. Am I correct?

No you are forgetting brute force attacks. Using insecure hashes such as Sha1 or MD5 passwords can be cracked

It is why you cypher needs to be up to modern hardware and better design for security such as crypt blowfish available in php.

[Lemon Juice]

No you are forgetting brute force attacks. Using insecure hashes such as Sha1 or MD5 passwords can be cracked.

Maybe I didn't write about them above but I din't forget about brute force attacks, that's why I said using long passwords. If a password is long enough then it would take very long to brute force it even with md5. The question is how long the password should be - but if it's around 50 characters of mixed types then I think it would be extremely difficult to use brute force.

[Jeff Mott]

If an attacker zeros in on one particular user who happens to have a weak password, then the attacker can just guess the password. Nothing we can do about that. Our job is to make sure that, given a database of passwords, an attacker can't identify which passwords are the weak ones, and can't take any shortcuts to brute-forcing. If we just hash, then an attacker can reverse most hashes in O(1) time (using a rainbow table). If we add static salts, then an attacker can reverse most hashes in O(n) time (a one-time rainbow table re-compute). And if we add user-unique salts, then an attacker can reverse most hashes in O(n^2) time (number of passwords times number of users). Even so, computers are fast. But if we use key strengthening, then we can increase the attacker's compute time by 1000x. An attack that once would have taken 1 day would now take almost 3 years.