This is in response to an email I recently received (edited a bit for clarity)
With our current resources we can test passwords to their hash in fractions of a second allowing for well resourced groups to test thousands of passwords every second. This means, given enough time and resources, you can crack any password within a reasonable length and as you increase length you increase the likelihood of people resorting to identifiable patterns in order to remember it.
Solution idea (not unique but not used from what I can tell): Use the hashing function 1000 times on the password. The hash is not any more secure but the time to brute force would change from hours to years. From what I can gather online I heard that multiple hashing creates larger hashes which lead to collisions. This doesn’t make sense to me because I created the example below and I don’t see how it would lead to a change in collision frequency. I do understand that it would guarantee someone the opportunity to “know” the size of the input and do 999 hashes to find the final but considering the size of the hash and the fact that it still doesn’t give you the original input I fail to see how it would matter. Additionally, if there is something I am missing about the collision frequency increasing could we not add a different salt between each function … what are your thoughts?
Please read my original post, Let’s talk about hashing passwords, before reading this post.
What do we accomplish by hashing a password
When we hash a password, we put time between the attacker and the plaintext. For starters, we need an intractible function. For passwords, cryptographic hash functions serve this purpose. An attacker must now guess plaintexts, hash them, and compare ciphertexts.
However, there’s a problem: Many cryptographic hashes are fast. In fact, cryptographic hashes are designed to be fast. If our goal is to add time between the attacker and the resulting plaintext, we need a way to slow the attacker down.
Rolling the hash
“Rolling” the hash is the process described above in the email. This is a commonly accepted method for hashing passwords. It’s used everywhere from WPA2 PSK keys to Unix crypt(). Why does it work?
With every iteration of the hash, we add additional work the attacker must perform in order to check and verify a plaintext does hash to the desired result, AKA the stored password hash. If we have
crypt = hash(plaintext)
for i 1 -> 1000
crypt = hash(crypt)
then we have just forced our attacker to hash through 1000 more iterations of our hash function. An attack that originally took days now takes years. Note: you should probably hash(crypt+plaintext), as this is going to make an attack on the resulting hash much more difficult if preimage resistance comes in to play.
Salting the hash
We can attack multiple hashes with the same data. For example, if we only rolled the hash, but we had 1000 password hashes we were trying to attack, we could do the work for one plaintext and verify the result against all of our hashes. We still have to perform the same amount of work per plaintext, but because we can share this work among the hashed passwords our total amount of work per hashed password decreases.
To offset this, we include a salt. The salt is a known and unique (not necessarily random) value which we hash in addition to the plaintext. For example, assume we have three users, and they all use the same password, FuZZy(BunnY)Sl1pp3RS. We would pick three unique salts for each user, perhaps 0×0001 0×0002 0×0003, or 0x2dc4 0x1f8a 0x9c4c. Now their hashes look like this:
plaintexts = {"FuZZY(BunnY)Sl1pp3RS," "FuZZY(BunnY)Sl1pp3RS", "FuZZY(BunnY)Sl1pp3RS"}
salts = {0x0001, 0x0002, 0x0003}
passwords[0] = salts[0] + hash(salts[0] + plaintexts[0])
passwords[1] = salts[1] + hash(salts[1] + plaintexts[1])
passwords[2] = salts[2] + hash(salts[2] + plaintexts[2])
Our attacker must now attack each hash by itself, one at a time. We have now added more time between our plaintexts and the attacker.
An example of a salted password in the real world may look like:
$6$9A8d$y/fbCk464oLuGcmCQO1rIoeVf8nnkloi1GysMMi1kYW8yvVMRJJXjC/LZJ2kBMhRDKF76kh5Vl6anRUYuMkbf.
This is a unix crypt password. It follows the following format:
$id$salt$encrypted_password
Where an id of 6 stands for SHA-512, 9A8d is our salt, and the rest is the base64 encoded representation of our sha512 hash.
So how should you implement your password hashing schemes?
If you’re reading this article, the best answer is find a library implemented by smart crypto people for hashing your passwords. People have messed this process up before, and when password hashing is messed up, the results are pretty disastrous.
The short answer to your question is that repeat hashing without a salt is indeed at best unproductive and at worst counterproductive. The problem lies in the fact that trying to reverse a hash for passwords does not actually rely on recovering the true password, simply an input that results in the same hash.
Now, lets look at the example of SHA-512 which reduces a 512-bit input into a 128-bit output. This implies that on average there are 4 inputs for every potential output. In a straight rehash of these outputs, we’ve now further reduced our input space to 128-bits. Furthermore, due to the properties of the hashing function the distribution of collisions is random which implies collisions will occur in all successive rehashings. These collisions slowly reduce the potential output space (and hence the input space for the next iteration). The real problem is that while this reduction is less for each successive iteration, it cannot be reversed even through salting.
An interesting way to attack this from a purely brute-force standpoint is to pick a start-value and immediately hash it 1000 times (tracking all of the intermediate values along the way). At this point we keep rehashing until we obtain either a result that matches the target hash (in which case we’ve won) or a result that matches a previous hash value. If we’ve found a previous hash, we check all values in the hash loop to see if one matches the target (in which case we’ve won). Otherwise we start with a new seed and essentially repeat the process. This process essentially has the same complexity as the diminished output-space since the 1000 iterations only affect the initial start from a seed and are insignificant compared to the probable number of iterations before a loop is reached. Additionally, this is a simple attack that does not even attempt to exploit the structural issues further so it is likely that far better attacks exist.
As with single hash password attacks, salting in this case only defeats the pre-computation attacks, but does not increase the complexity of attacking the hash itself. Unfortunately, using the same hash for each iteration does absolutely nothing to reduce the effectiveness of the method mentioned above. It requires a fresh attack against each individual password, but it does not increase the complexity.
If, however, rotate through a finite number of unique hashes as we iterate through the rehashings, then we do reduce the effectiveness of the brute force listed above by an amount approximately equal to the number of unique hashes we’re utilizing (this is actually only true if the GCD of the number of hashes and number of iterations is 1). Unfortunately, in the grand scheme of cryptography this is an ineffective approach as its actual effect on the complexity is relatively insignificant and can be easily countered by increasing the processing power you attack it with proportionally to the number of unique salts. Even in this case though, the security has already been compromised due to the reduction in the size of possible outputs.
I would like to clarify that although my explanation of why this method does not improve security only looks at brute-force attacks, it is very likely that similar adjustments to faster attacks also exist as is often the case in cryptography.
Link | November 10th, 2011 at 23:17