[tryeng]

That's not a good article to make people read.

I find it strange that it doesn't mention lack of salting among the most common mistakes. Also, I didn't think SHA1 broken in any way that makes breaking password hashes easier than e.g. the SHA2 family? I might be wrong, though.

PS: I'm not advocating using anything other than a good PBKDF for hashing passwords.)

Edit: Re-reading the article it seems like lots of BS in there:

Example 1, regarding hashing something several times: "In order to retrieve the original password a hacker has to crack multiple hashes instead of only one." Nah, guessing is only more time-consuming.

Example 2, regarding the same thing: "The first reason is pretty easy to bust: simply add more hardware (or better hardware) and you're good to go." This applies for bcrypt as well.

And for his "attack" on "Hashing a password N times in the form of hash( hash(password) ) * N" you would need a working preimage attack for the hashing function used.

EditN: Rewrite

[Cushman]

I think you're looking for something more complex than that post brings to the table. As a community, we're trying to circle our wagons around a simple piece of advice about code that stores passwords: do not write code that stores passwords. Even if your algorithm is secure, your code is likely not. Include your language's best-supported secure password library (meaning one of bcrypt, scrypt and PBKDF2) and ship it.

So that post may be incomplete regarding the technical details, but the critical information is there: Just use bcrypt. (...and use the recommended work factor.) I know hackers hate that sort of thing, but this is really one of those things we just have to drill.

[tryeng]

His advice is good, but that's still no excuse for making invalid arguments for what he is advocating.

Edit: In fact, if I hadn't heard of bcrypt before and saw that article, I would probably not trust his advice either.

[jiggy2011]

Bcrypt has a tuneable "cost function", so you get to decide how hard to make it. It's effectively designed to be slow and hard to do in parallel.

The SHA family on the other hand are designed to be fast, (for checksums etc) so it's possible that later SHA algorithms are actually worse than earlier ones for password hashing.

Modern computers can do a lot of MD5/SHA1 every second so even with a salt, one round of SHA1 is likely to be not very good at all.

You can probably find a significantly large X and do SHA1 enough times to make it slow enough today, but for future-proofing you are better off just using an algorithm that is actually designed for such purposes.

[tryeng]

I'm not saying that that bcrypt isn't a better choice, it is, but some of the "flaws" he is pointing out in that article are just ridiculous. If he's going to argue for something, he should be using correct arguments.

[YorickPeterse]

Hi, said author here. The particular article was written around 2 years ago (April 2011 to be exact) when crypto was still a fairly new concept to me. As a result there indeed are some flaws with the article. Having said that, some extra explanation can't hurt.

> Example 1, regarding hashing something several times: "In order to retrieve the original password a hacker has to crack multiple hashes instead of only one." Nah, guessing is only more time-consuming.

I'm not entirely sure what you're trying to say with this example. The particular list item was meant as one of the examples why I think people would do it that way. It's not too uncommon that I read some article about a developer doing that because it is supposedly more secure.

> Example 2, regarding the same thing: "The first reason is pretty easy to bust: simply add more hardware (or better hardware) and you're good to go." This applies for bcrypt as well.

Bcrypt introduces a weight/cost (whatever you'd call it) factor who's sole purpose is to prevent this. The higher the factor the slower the process takes. The nice bit about it is that with a weight of N the hashing process always takes the same (due to some bcrypt voodoo that is beyond my knowledge) amount of time. You also can't change the weight since that will result in a different hash being produced (it would be fairly useless otherwise).

Having said that, I agree that the article could've been written in a better way but it will remain as is, simply because I try not to edit articles after I've published them.

[tryeng]

Hi, I see that I misread the "In order to retrieve the original password a hacker has to crack multiple hashes instead of only one." as your argument, not an example of a false argument. I stand corrected.

Regarding the cost, bcrypt only increases the number of iterations (exponentially) with increased cost. The operation will take the same amount of time on one specific CPU, but go faster on another. However, because of higher memory usage than SHA variants, GPU implementations of bcrypt don't benefit as much compared to CPU implementations.

We still agree your advice to use bcrypt, though.

[ajanuary]

    I find it strange that it doesn't mention lack of salting among the most common mistakes.

True. I believe bcrypt requires a salt, so you can't forget it. Bringing that up would have strengthened the case.

    In order to retrieve the original password a hacker has to crack multiple hashes instead of only one." Nah, guessing is only more time-consuming.

The article is using that as an incorrect argument for repeated hashing, and goes on to detail why it isn't necessarily more time-consuming because it increases the probability of finding a collision.

    This applies for bcrypt as well.

You can tune the work factor, so in a few years when computers are nearing fast enough to brute force your hashes, you only need to increase the work factor, not re-write all your code. You can't do that with something like SHA. The article could probably be clearer on that.

    And for his "attack" on "Hashing a password N times in the form of hash( hash(password) ) * N" you would need a working preimage attack for the hashing function used.

I don't see why. If there is a probability of a collision existing for a hash, repeated hashing will increase that probability, turning something that has a low number of collisions into a high number of collisions. The more collisions, the easier it will be to find one.

[tryeng]

You can increase the number of rounds of hashing as well, without rewriting your code.

I can't argue with your last point, simply because I don't understand it. How exactly does this "turn something that has a low number of collisions into a high number of collisions?"

In my mind, what we're doing is hashing "mypasswordmysalt" n times, and storing the resulting hash, the salt and n in a user table. If the user table is leaked, and n is 3 (for simplicity's sake, it would normally be _much_ higher), can you explain how this could be worse than doing one round of hashing?

[ajanuary]

Every hash function has a probability of collisions. For illustration, let's imagine a really bad one where every output has another input that results in the same value.

With a single round of hashing, there are two possible inputs A1 and A2 that can produce the final output O. With a sufficiently large number of potential inputs, it will take you a while to brute force and enumerate all possible inputs before you hit on either A1 or A2.

With two rounds of hashing, there are two possible inputs A1 and A2 that can produce the final output O, and two possible inputs B1 and B2 that can produce the intermediate hash A1, and two possible inputs B3 and B4 that can produce the intermediate hash A2.

With three rounds of hashing you end up with something like this:

    C1  C2  C3  C4 C5  C6  C7  C8 
     \  /    \  /   \  /   \  /
      B1      B2     B3      B4
       \      /       \      /
        \    /         \    /
          A1             A2
           \             /
            ------O------

So with each round of hashing you are increasing the number of collisions, meaning you're likely to brute force an input that will hash to O much quicker.

[Edit] Of course, with each round you're also increasing the amount of time to compute O, but given most hashing algorithms are designed to be fast I'd say it's probably not enough to counter it. Not sure though, I've not actually looked at the maths.

[ajanuary]

[Replying to tryeng]

    No, there is an infinite number of inputs that produce the final output O.

Only with an infinite number of inputs. If we restrict our domain to things that are likely to be passwords, say string under 1000 characters in length, then we're increasing the number of inputs in our domain that can produce O.

    you have to find something that generates O after exactly n rounds of hashing

I was using an increasing number of iterations to demonstrate how each iteration potentially increases the number of collisions. Taking n=3, you don't need to know any of the intermediate states A1, B1, B2, B3 or B4 to take advantage of the fact that in our domain of strings under 1000 characters we only have to find one of 8 possible inputs rather than one of 2.

    I said will be true for all relevant hashing functions.

All relevant hashing functions have a probability of collisions in any useful input domain. Okay the tree won't be as dense as the one illustrated, but you're still increasing that probability by repeated hashing.

You need to find some way to mitigate the collisions, at which point you've basically got bcrypt.

[tryeng]

[Replying to ajanuary]

Thank you, now I actually do see your point. I would still not think of it a considerable weakness. To find such a collision would take more time than bruteforcing any likely password.

There doesn't yet exist a single example of any SHA1 or SHA2 collision, and if we use SHA256 as an example, we could probably not find one the next few years by bruteforcing even if we used all the world's current computing power and storage.

Edit: Actually, that whole argument falls to pieces, because if we can search through enough possibilities to find any collision, the output size of the hashing function is too small to for the hashing function to be secure.

[ajanuary]

Indeed. This is where I agree with to that the article is a bit weak. It overstates the problem of repeated hashing and doesn't explain how bcrypt solves that problem at all. It makes it sound like a completely different and magical solution rather than repeated hashing with collision mitigation.

It's more a case of "hey, here's a potential problem you might not have thought of, here's an algorithm that addresses it."

[tryeng]

Then I guess we might agree.

The only advantage I know of with bcrypt over multple SHA2 is that GPUs are very bad at it compared to most hashing functions, so the CPU cost (on my server) and the GPU cost (the crackers' cost) are not too different. (Anyone, please correct me if I'm wrong.)

Off-topic: This exponential reply delay is really annoying.

[tryeng]

"With a single round of hashing, there are two possible inputs A1 and A2 that can produce the final output O."

No, there is an infinite number of inputs that produce the final output O. And you have to find something that produces O after exactly n rounds of hashing, it doesn't help to find something that produces O after one or two rounds.

Edit: Sorry, didn't see your assumption when I first posted, but I guess what I said will be true for all relevant hashing functions.