8

When it comes to hashing passwords, it is nowadays practice to do 100'000 or 200'000 iterations of SHA256/SHA512, or at least something in that ballpark.

But my question is, why is it not safe enough to just do a very small but unusual number of iterations that is unlikely to be guessed?

For example, let's say I use 153 iterations of SHA512 to hash the user passwords. Now a hacker breaches the database and steals all password hashes. They will never guess that I'm using exactly 153 iterations and they don't have access to the source code, also nobody will have created a lookup-table for 153, or 267, or 1139 rounds of SHA512 password hashes, correct? (Though lookup-tables are useless anyway if the passwords are salted before hashing)

AndreasKralj
  • 103
  • 3
csstudent1418
  • 231
  • 2
  • 8
  • 33
    Have you heard of Kerkhoff's Principle? It states that everything about your cryptosystem, except the key, should be assumed to be public. Other than that, SHA256 is not a password hashing algorithm because it is very fast. – Gamer2015 Jul 29 '21 at 11:25
  • 1
    In addition to what @Gamer2015 points out, it would be simple for the attacker to just compare the result of each iteration to the password hash. – mti2935 Jul 29 '21 at 11:29
  • @mti2935 That's not simple at all, let's say in a normal system he may only check the output of 10'000, 100'000 and 200'000 hash rounds, amounting to 310'000 hashes, but here he would have to compute (200'000+199'999+199'998+...+3+2+1) = ~20'000'000'000 hashes in the worst case for a single password which is *much*, much more effort. Even if my secret hash round number is just 1139 that amounts to 649'000 hashes jut to check a single password (like "asdf1234"). – csstudent1418 Jul 29 '21 at 11:45
  • 2
    @csstudent1418 And they would need to run this set of calculations only for one password. Once they get the number, they would be very easily able to crack the other passwords. – pri Jul 29 '21 at 11:53
  • @pri But from the hacker's POV, assuming that I am using a secret, small and odd number is already a huge commitment? Why would a hacker ever do that? Granted 1139 seems too small but lets use 6577 instead, it would take him roughly 21 Million hashes for a single password ("asdf1234"), which makes it, divided by 310'000, still a whopping 70x harder to crack the first password than if he correctly assumed that you are using either 10'000, 100'000, or 200'000 as most do. – csstudent1418 Jul 29 '21 at 11:58
  • 7
    Why would it be 1+2+3+...+n? If someone hashes for 100000 times, and after each iteration compares the result, wouldn't it cover all the cases from 1 to 100000? – pri Jul 29 '21 at 12:01
  • 3
    He just needs to calculate 200'000 hashed to compare all the hashes from 1 iteration to 200'000. He can just use the intermediate values for the comparison – Gamer2015 Jul 29 '21 at 12:02
  • Take 100 worst passwords (that are *guaranteed* to be used by someone on the database), throw in a dedicated hash cracking rig (around 10,000 MH/s), and go from 1 to 1,000,000 iterations. It will exhaust the search in seconds and discover how many rounds you use. – ThoriumBR Jul 29 '21 at 12:04
  • 1
    @pri and Gamer: Y'all are right, silly mindbug i had there. – csstudent1418 Jul 29 '21 at 12:07
  • 17
    This question just seems to be a specific version of "why is security by obscurity bad?" – Herohtar Jul 29 '21 at 21:19
  • 4
    @cssstudent It sounds like a great idea (just as all the other trickeries about changing public information of some hashing algorithm) until you realize that the hacker can just create an account themselves. I leave how that additional information will help figure out the details of the hashing algorithm to you. – Voo Jul 29 '21 at 21:32
  • 2
    "odd number of iterations" - What's the significance of using an **odd** number of iterations? – MrWhite Jul 31 '21 at 13:51
  • 1
    @MrWhite None. The point is, odd as in odd vs 10'000 / 100'000 ... , not necessarily odd as in `x%2 == 1` though all my examples were picked like that. – csstudent1418 Jul 31 '21 at 17:41
  • 1
    In that case, perhaps "irregular" (rather than "odd") would be a better word to avoid that confusion. (Or remove the word "odd" altogether?) – MrWhite Jul 31 '21 at 19:37
  • I think the post should be edited to change "odd" to "unusual." (I would submit an edit request, but I think it may be rejected by a reviewer who doesn't know whether or not the word "unusual" would fit the author's intent.) – Tanner Swett Aug 01 '21 at 14:10
  • Another consideration is that the '153' needs to be stored somewhere, so the legitimate system know how many iterations to do. This is the same for salting, where the salt is stored alongside the hashed password. If the attacker has stolen the database, they are likely to also have this information, and it's no longer useful as a security treatment – Tony Aug 03 '21 at 23:09
  • @Tony The point was that it is hidden in the source code, my assumption being of course that the hacker doesnt have access to it. – csstudent1418 Aug 04 '21 at 07:44
  • @csstudent1418 That would be worse, because now you have a 'secret' embedded in your code; much harder to protect across the development lifecycle, difficult to protect when deployed, and also to change if compromised – Tony Aug 05 '21 at 11:53

3 Answers3

43

The idea of a large number of iterations is not to be part of the secret, but to take more time.

Having a database with a large number of passwords means someone will have a weak password, and it's trivial to test the dictionary of worst 100k passwords in minutes, no matter if you are using 200k iterations, or 153 as you are using. A dedicated password cracking device from 2018 achieved 9392.1 MH/s (mega hashes per second) doing SHA256, so trying 100 worst passwords from 1 iteration to 200,000 iterations would take the attacker just seconds to deduce how many rounds you are using. And that goes all your secrecy.

That's why you don't use SHA or MD5 for password storage: they are fast hashes. They are very good for checking the integrity of a download, or the data on Bitcoin blockchain, but not for password storage. And you should use a tunable hash for that, like Argon2 (as CBHacking reminded me).

Compare the 9392.1MH/s for SHA256 with 43551 H/s for BCrypt with Blowfish, and 124 H/s for Veracrypt PBKDF2-HMAC-Whirlpool + XTS 512 bit. It's not practical to do a dictionary attack with a large sized dictionary against a decent configured Argon2 password database.

The main point of the password hashing algorithm is that you can tune them to be as slow as you want without committing a self-inflicted DoS. If you put so many rounds that it takes 10 seconds for your server to process a login request, an attacker can hammer your server with login requests with bogus passwords and essentially kill it.

ThoriumBR
  • 50,648
  • 13
  • 127
  • 142
  • Great points and some nice info. I probably shouldn't have used SHA in my questino as it is indifferent to the actual hashing algorithm used. – csstudent1418 Jul 29 '21 at 12:09
  • 4
    The point still stands: take 100 worst passwords, bruteforce from 1 to infinity until they get a match. It's very unlikely nobody would have a password on the "worst password list" and have an account at your service. – ThoriumBR Jul 29 '21 at 12:12
  • Sure, that's why I accepted your answer. I also just realized that a single person using a dumb password compromises not only their own but the whole community's security in a way then. – csstudent1418 Jul 29 '21 at 12:15
  • 8
    Exact. That's why you use random unique salts for each user. – ThoriumBR Jul 29 '21 at 12:16
  • @csstudent1418 Another aspect of this might be security audits. You probably want someone to check your security and not break it trivially afterwards. – Gamer2015 Jul 29 '21 at 12:27
  • 13
    Also in some cases they might have or be able to create an account of their own the site beforehand, and then all they need to do to figure out the hash count is to test their own password against their own hash. – ilkkachu Jul 29 '21 at 14:33
  • @ThoriumBR: Couldn't this be mitigated by storing a copy of the “worst password list” on your server and rejecting users' attempts to use a password on that list? – dan04 Jul 29 '21 at 20:41
  • 2
    Not at all. The attacker would only need to create an account, set his own password, and leak the database again. – ThoriumBR Jul 30 '21 at 00:00
  • 4
    Good answer, but I must say: PBKDF2 and bcrypt are very old algorithms, and neither has a tunable memory cost (or a very meaningful one by modern standards, though bcrypt at least tried). The password hashing competition that ended five years ago crowned argon2 the winner, and it's been widely-enough used and tested since then that I really don't see a good reason to *not* use it. There are libraries available implementing it for basically every programming language. – CBHacking Jul 30 '21 at 06:49
  • @CBHacking good point! I will update my answer. – ThoriumBR Jul 30 '21 at 12:25
  • Wondering if it would be at all useful to use a random number of hashing rounds between N and N+k (where N >> k, e.g. 100k and 1k) so they're still individually 'hard', but not consistent across your storage. But I'd think the random salt basically does the same thing. – Nick T Jul 30 '21 at 17:40
  • Remember: `There's no right way to do the wrong thing.` Do the correct thing so you won't spend all your life patching messy things around. – ThoriumBR Jul 30 '21 at 18:45
  • @NickT: Yes, it does, but better. A naïve implementation of your idea would allow all hashes of a password with up to *N* iterations to be computed and tested using little more effort than a single *N* iteration password. (Sort the hashes by iteration count and take the lowest count; iterate up to that count, then check for a match; then keep iterating up to the next lowest count, and so on.) There are ways to work around that issue, but they all basically boil down to "use the iteration count as a salt." In which case you might as well use an actual salt. – Ilmari Karonen Jul 30 '21 at 18:47
11

Because hashing is iterative, if the attacker doesn't know the number of rounds, they can compare the current result after each iteration to the target (stopping at some large limit like 216–218).

This approach falls squarely in "security through obscurity" territory, and undermines the purpose of iterating the hash.

erickson
  • 1,783
  • 11
  • 13
3

In addition to the other answers about iteratively checking weak passwords until you get a hit for some account, consider this:

What if you already know one of the passwords in the DB? Perhaps it's yours, or belongs to somebody you know who agrees to help out. Perhaps it's from a breach on some other site, and the user re-used passwords (never do that).

If you're checking a specific password against a specific hash, it doesn't even have to be a weak password. All you need to know is the necessary iteration count, and that will be extremely easy to find by iterative testing.

CBHacking
  • 40,303
  • 3
  • 74
  • 98