Iterated SHA1 hashing and the effect on rainbow table computation

Question

Scenario:

1000 distinct keys are each prefixed with the same salt, and SHA1 hashed. The hash output is then iteratively SHA1 hashed x times. Let's start with x is 100. The specification of the keys is 10 chars length exactly, lower case letters and digits only, therefore the entire key space is not that huge.

The keys should remain secret of course, but it can be assumed the hashes (the final post iteration ones) are public. UPDATE: Assume as well that the salt is also public - therefore not a pepper.

Given the constant salt used here, rainbow tables could certainly be computed for this scenario. My question is this:

Does making x 100, 1000, 100000, 1M make any significant dent in the difficulty of the rainbow table computation? Does a switch to SHA256 make any appreciable difference? Hash functions are designed to be fast after all.

[Yes I know the salt should be different per key, but assume that isn't possible or feasible or whatever.]

From what I've read, it looks like using PBKDF2 (with the requisite high iteration count) to produce the hash seems a better option as it makes the hash calculation much much slower. Again just assume the salt needs to be fixed here.

Answer 1

SHA1 is indeed pretty fast and should be considered breakable, especially when the space your values come from is that limited. Whether or not increasing iterations will increase the difficulty should be rather obvious: If one hashing operation costs you 0.001ms, 1000 hashing operations will cost you 1ms. Thus, increasing the iterations does indeed increase the difficulty of breaking that final hashed value.

There are however better suited candidates than SHA1 for that job, BCrypt and PBKDF2 come to mind.

If you use such a function and make the iterations a significant factor to make brute forcing unfeasible, you should keep in mind that this could mean an easy DDoS-attack surface on layer 7 if you use that for password checking:

If it takes your server 1s of 100% CPU load to check a login, sending you a login try every second will kill your system easily. If you choose something below say, 1ms (such that an attacker needed at least 32 machines with 16ms ping), it would again be crackable using brute force and some huge EC2 instances.

This, by the way, is because of your fixed length key space.

If your pepper (what you call "salt" in the question) is sufficiently large and unknown, this will increase the difficulty for breaking the first hash significantly, yet after that (if it's known that that's a pepper) it's easy to iterate through the remaining 10 bytes of plain text to break all other hashes.

For example, when your pepper is abcd and the keyspace is only one character, while you have to iterate from aaaaa up to abcda, as soon as you found a, you also found the pepper and thus only need to iterate from abcda to abcdz.