Many Hash Iterations: Append Salt Every Time

Many hash iterations: append salt every time?

In short: Yes. Go with the first example... The hash function can lose entropy if feed back to itself without adding the original data (I can't seem to find a reference now, I'll keep looking).

And for the record, I am in support of hashing multiple times.

A hash that takes 500 ms to generate is not too slow for your server (considering that generating hashes are typically not done the vast majority of requests). However a hash that takes that long will significantly increase the time it will take to generate a rainbow table...

Yes, it does expose a DOS vulnerability, but it also prevents brute force attacks (or at least makes them prohibitively slow). There is absolutely a tradeoff, but to some the benefits exceed the risks...

A reference (more like an overview) to the entire process: Key Strengthening

As for the degenerating collisions, the only source I could find so far is this discussion...

And some more discussion on the topic:

1. HEKS Proposal
2. SecurityFocus blog on hashing
3. A paper on Oracle's Password Hashing Algorithms

And a few more links:

1. PBKDF2 on WikiPedia
2. PBKDF2 Standard
3. A email thread that's applicable
4. Just Hashing Is Far From Enough Blog Post

There are tons of results. If you want more, Google hash stretching... There's tons of good information out there...

System.Web.Helpers HashPassword Salt and Iterations?

You are correct in saying that storing the salt and iteration count is better for future planning, just look at PHP's password_verify().

Not only has the iteration count (called cost, not exactly iteration count but based on the same concept) and salt been stored with the derived key, the algorithm is stored too in case the algorithm needs to be replaced in the future.

The System.Web.Helpers.Crypto class uses PBKDF2 to hash passwords which internally uses a hash algorithm over a defined number of iterations to hash a password. Since the internal operations are all non-reversible and that the "iterated" segment isn't the final segment, performing additional hashing does not work. The whole password needs to be rehashed from its original plaintext source.

Generally, the procedure of rehashing passwords occur when the user next logins in again. At this point the system can determine if the user's password needs to be rehashed and proceeds to do so accordingly if required. Not only does this avoid the cost of running a major rehash operation which may cause downtime, it is the only time the user's plaintext password is available again. Passwords should be rehashed if there is a possibility of vulnerability in the near-future as opposed to the time a vulnerability is fully exposed as it may be too late at that point.

If security of data is a concern as well as planning for the future, I suggest you use another class (perhaps make your own) which allows for a custom number of iterations and stores all the relevant data within the derived key/hashed password itself.

Can per-user randomized salts be replaced with iterative hashing?

The salt helps protect against an attacker using a precomputation or dictionary attack. When a salt is used, the attacker needs to create a separate dictionary for every salt value. However, if the salt isn't random you give the attacker an advantage, because they can create dictionaries that are more likely than others. For example, they could create a dictionary using a salt of jsmith (or hash of jsmith). For this reason, it is generally a good idea for the salt to be random.

Comparing a precomputation attack against a hash(username) salt and a random salt: let's say for example the attacker decides to create dictionaries for the most common 1000 usernames and, say, half a dozen different hash algs; that's 6000 salts and so 6000 dictionaries. If a random 32 bit salt is used that's 2^32 or circa 4.2 billion dictionaries. So when the salt space is dramatically reduced (like it is by using hash(username)) precomputed attacks become much more feasible

Password salts: prepending vs. appending

Do neither, use a standard Key derivation function like PBKDF2. Never roll your own crypto. It's much too easy to get it wrong. PBKDF2 uses many iterations to protect against bruteforce which is a much bigger improvement than the simple ordering.

And your trick pre-calculating the internal state of the hash-function after processing the salt probably isn't that easy to pull off unless the length of the salt corresponds to the block-length of the underlying block-cypher.

Bcrypt(4) (=4 iterations) versus SHA512 or something different with unique salt per password?

Security is always about what you are trying to secure.

If you are more concerned about your resources than about your security, bcrypt(2) is already overkill. No hacker will ever try to break that for a normal application, having easier target sites like LinkedIn and many others, which just use functions from the sha family, with a single iteration, and unsalted. They will go for the 'low hanging fruit'. Or they could keep trying to hack your application, just not in the password encryption part.

SHA-512 is not much more secure than SHA-1 as password hashing algorithm [1], it has not been designed for that purpose. They can still be used as primitives for creating secure cryptographic algorithms though, but that's something no single person should do. To be considered secure, crypto algorithms must be public to be peer reviewed, and must pass the test of time. And obviously, must be designed for what you are going to use them. MD5, SHA-X, etc. are cryptographic algorithms, but weren't designed for storing passwords.

Just add or remove rounds to your bcrypt. In this case I would use 1 or 2. Also keep in mind that 1 round != 1 iteration. They are increased exponentially. If you read about how bcrypt works, you will see that there is much more to it than just iterations. For example, you mentioned 'unique salt per password'. Bcrypt already has that.

[1] For other things it's obviously more secure

Using a random sha512 salt with a sha512 password

All this sound wuite complex ; using a single combinaison of salt+sha1 should be quite enough, I suppose, from a security-related point of view.

Here are a couple of questions/answers that might get you some more informations (there have already been quite a lot of questions about password and salting and hashing in the past -- some of those could probably help you) :

• Going from unsalted to salted MD5 passwords
• Salting Your Password: Best Practices?
• Non-random salt for password hashes
• Need some help understanding password salt
• Should We Mask Passwords?
• Is using a ‘salt’ all that good?
• Password hash and salting - is this a good method?

Cryptographically hash multiple keys

Either hash the whole structure directly if it contains only POD (i.e. nothing allocated within and its sizeof is a constant): either you can use an union to get a proper byte array, or you use a cast to obtain a char* to provide to hash function.

If you have dynamic data inside your struct/class, you need to serialize all data and send them to the hash function - obviously, its size will vary during execution, because of dynamic data. But you must call hash only ONCE per data structure, and in NO WAY adding hashes together - that's a nonsense.
You can also use a framework feature that will serialize your struct/class to a text stream (often XML or JSON format), and hash this serialization instead of the binary structure.

How to do all this is obviously platform-dependent - which cryptography API do you use, if you prefer.

By applying these principles, the collision (totally unavoidable, mathematically proven) won't be more than for any other kind of hashed data.

Do I need a random salt once per password or only once per database?

A new salt should be randomly generated for each user and each time they change their password as a minimum. Don't just rely on a site wide salt for example, as that defeats the point of using a salt in the first place.

Using a unique salt for each user is so that if two users have the same password they won't get the same resultant hash. It also means a brute force attack would need to be mounted against each user individually rather then being able to pre-compute a rainbow table for the site.

You then store the result of hashing the salt and password in the database hash(salt + password), along with the salt for each user. You can store these in separate columns, or all in one column (separated by some character not used in the hashes, so ; for example). As long as you can retrieve both you'll be fine.

However, if your database is compromised, either due to someone gaining local access or via SQL injection attacks, then both the salt and final hash will be available, which means a brute force attack on the users' passwords would be trivial. To combat this, as suggested by The Rook you can also use a sitewide secret key stored in a file locally as another input of your hashing method so that an attacker would also need to know this to mount an effective attack. Which means your DB would have to be compromised AND the attacker would need access to local files. So using hash(hash(salt + secret) + password), etc.

While in most algorithms you aim to make things as fast as possible, for password hashing you want to slow it down, this is called Key Strengthening (or sometimes Key Stretching). If it takes 0.00001 seconds for your hash function to return, someone can try brute forcing 100,000 passwords a second until they find a match. If it takes 1 second for your hash function to spit out the result, it's not a big deal as far as someone logging into your application is concerned, but for cracking the password it's a bigger deal since each attempt will now take 1 second to get a result, meaning it would take 100,000 times as long to test each brute forced password than it would using your original hash function.

To make your hash function slower, you just need to run it multiple times. For example, you could do new_hash = salt + password + previous_hash 100,000 times. You may need to adjust the number of iterations to a higher value if it's too quick. If you want to be able to change the value later, make sure to store the number of iterations with the user record so that you don't affect any passwords previous stored.

Your user record should now have a field formatted something like this "$<algorithm>$<iterations>$<salt>$<hash>" (or as separate fields if you want).

When the user enters their password you can retrieve the salt and number-of-iterations from the DB and the sitewide secret from a local file and validate that when you run the same number of iterations with the salt and password, the resulting hash matches what you have stored.

If the user changes their password, then you should generate a new salt.

The hashing method you use doesn't matter (but the hashing algorithm does*). Above I suggested hash(hash(salt + secret) + password) but equally it could be hash(hash(salt) + hash(secret) + hash(password)). The method you use doesn't change the effectiveness of your password storage, one is not really any more secure than the other. Relying on the design of how you hash the password and salt together to provide security is called security through obscurity and should be avoided.

*You should not use MD5 or SHA-1 as these are considered insecure. Use the SHA-2 family instead (SHA256, SHA512, etc). (Ref)

---

Related Topics