# Hashing SHA-512 1000 times

SageMathCloud security (http://goo.gl/dCujW1) is as follows:

Only the hash of your password is stored by the server, which uses 1000 iterations of the sha-512 hash function, with a salt length of 32.

While that does sound like a nice salt, I am a bit doubtful of the 1000-iteration idea. While this does make brute force attacks 1000 times slower, isn't it true that every extra iteration squares your chances of collision?

-
Collisions in a 512 bit hash are extremely improbable. So even if you try trillions of times you still have a negligible chance. – CodesInChaos Feb 20 '14 at 8:52

Baring an improbable tremendous theoretical breakthrough, any odd of any kind of collision among SHA-512 hashes, for any cause except identical input or computing failure, is negligible in practice; we'll thus handle this from a theoretical standpoint.

Let $s=512$ be the hash width; $k=1000$ the number of hash iterations; and $q>0$ the number of stored iterated hashes.

The question worries about chances of collision, I assume in the stored hashes. Such collisions, even if they occurred, have little potential to help an adversary to get access or recover a password, but for the sake of the argument let's consider them anyway (say, the login system searches among all iterated hashes without using the salt as primary index).

If there was no iteration, odds of collisions would be $\approx q\cdot(q-1)/2^{s+1}$. That's also about the odds considering iterations if the salt is rehashed at each step (which is common and would match the question's statement).

With iteration and just re-hashing the previous hash, we have to worry that collisions among the result of the $q\cdot k$ total hashes could also cause a collision of the stored hashes. Because we can neglect that a cycle also gets involved and has just one of the few length that could matter, only collisions occurring after the same number of iteration need to be accounted for, and the odds of collisions among stored hashes are $\approx q\cdot(q-1)\cdot k/2^{s+1}$.

Thus with the worse possible interpretation of the question's quote, odds of collision among stored hashes grow only about linearly with the number of iterations.

The main issues to worry about:

• 1000 iterations is MUCH insufficient; that might have been useful when PBKDF2 was created, but no longer provides adequate protection against brute force password search in the event of a leak of the password hashes.
• Better slow key derivation functions provide much better protection at equal computing cost, see scrypt.
-

a Using a moderate number of iterations is a standard approach in password based key derivation (see for example, http://en.wikipedia.org/wiki/PBKDF2, RCF 2898 http://tools.ietf.org/html/rfc2898). It can also be used in the sceanrio described. In this case if an attacker gets access to your password database it should slow down the attacker by a factor linear in the number of iterations.

The issue with collisions that you address is not really a concern here. My guess what you mean is, that if I make $q$ (distinct) hash evaluations then my probability of having a collision (i.e., two messages $M$ and $M'$ such that $H(M) = H(M')$ ) is less than $q^2 \cdot 2^{-s-1}$ (assuming that the function is more or less random), where $s$ is the output length of the hash function. In case of sha-512 we have $s=512$. This probability is minute. As an example, even for a large database of say $10^6$ (one million) passwords the probability of a collision is $10^{18} \cdot 2^{-513} < 2^{-453}$ wheras without the $1000$ iterations this probability would be $\approx 2^{-473}$. In other words, the extra $1000$ iterations make up a loss of a factor of $2^{20}$ in the collision probability.

In any case, this is not a problem, as collisions that do not occur in the same iteration (@fgrieu thanks for pointing this out) won't lead to the same password.

-
when we have $10^6$ passwords we have $q=10^6*10^3$ as each password takes $1000$ iterations. As for the second observation and the sign mixup you are absolutely right. thanks for pointing this out. i've corrected the answer accordingly. – Arno Mittelbach Feb 19 '14 at 21:36