Hacker News Reader

Comment by woutifier | Hacker News Reader

Defense against rainbow tables is obtained via salt, not via slow hashes. A rainbow table is a space-time tradeoff (you give space, and you get time), so using a slow hash only "encourages" (for lack of me knowing a better word) creating rainbow tables.

Adding long salts on the other hand requires the attacker to create an infeasible number of rainbow tables (one for each possible value of the salt).

View on HN

Technically this class of trades also incurs a lot more hashing (and so the expense of the hash function is important), the trade is valuable because you get to do all the work once, up front, and not spend that time on any particular password hash once you have it.

So e.g. computing a rainbow table for all possible Windows 2000 passwords (up to 14 characters but you're actually only doing 56-bit inputs) in the LANMAN scheme took ages, and produced a fairly large file, but having done so that's it, you, or anyone you give the file to, can reverse LANMAN hashes into working passwords almost instantly.

(Microsoft's LANMAN hash lacked salt, and is stupid in various other ways, MD5 would actually have been a better choice than LANMAN, because you allow arbitrary input passwords and thus good passwords are stronger instead of impossible even though MD5 is much too fast for a good password hash)

> Defense against rainbow tables is obtained via salt, not via slow hashes.

And bcrypt includes stores a unique salt next to the hash for every password, making rainbow tables completely useless.

https://en.wikipedia.org/wiki/Bcrypt

Nobody is saying bcrypt isn't a good choice here, they're saying that rainbow tables (and all time-space trades) are made infeasible by salt regardless of whether you're using a good password hash like bcrypt.

But both you & GGP are talking about bcrypt as though it was only a password hash. If someone says, "I'm using bcrypt", then they are using both a password hash and unique per-password salts, or they're not using bcrypt. What makes bcrypt and other such systems nice (and makes this kind of mistake basically inexcusable in 2022) is that if you're using a library or package which implements it (which you should), you don't need to think about salts; you just call GenerateFromPassword(<new_password>) and CompareHashAndPassword(<entered_password>, <stored_hash>) and forget about it.

EDIT: I mean, I understand maybe why in 2006 you used md5 without salt. But a few years ago I when I tossed together my first webapp (a scheduling system for the community I'm involved in), I just googled "password hash" and immediately bcrypt came up as a recommendation; there was a package in my target programming language, so after half an hour of research and 5 minutes of programming I was done. I don't understand how the opensubtitles team, after having had their password database compromised, came up with "use sha256 without salt" instead of "use bcrypt or one of the many libraries which takes care of all of that for you".

This, _and_ bcrypt is slow. Many wrapping libraries' hashing functions accept an optional parameter to specify just how slow it should be.

I mean, sure, but, notice that you're still way behind state of the art for the end of the 20th century. I blame Tim (Berners-Lee, the man whose toy hypermedia system we're all stuck with because it became popular)

You note that when you googled "Password hash" you got pointed to a decent password hash. But, knowing what questions to ask is half the battle. Too many people figured hey, I should use a cryptographic hash and got pointed to MD5 (or SHA1 or even SHA256) because that's what those are.

The words you should have googled weren't "password hash" but maybe "web authentication" and then the answer is clearly you shouldn't use passwords or any sort of shared secret.

You can have a copy of the authentication database for the toys system I maintain, but it wouldn't help you sign into it because all the information in it is public, a trick we've known how to do in principle for decades, and which works today, on the public Web, with readily available devices (e.g. my phone) and yet, here we are on Hacker News discussing which password hash is best like it's still 1985.

> with readily available devices (e.g. my phone) and yet

I'm pretty sure it wasn't anywhere near ready to use five years ago when I wrote v1 of my webapp. And googling again, it's still not clear whether it would work on whatever random software setup some of my zealous-for-software-freedom colleagues use. With passwords I don't need to worry: if they can render the HTML+CSS (even the JS is optional, because some of my colleagues prefer NoScript), they can log in.

True, I might be mixing names. What I mean is that now with fast hashes it's feasible to take for each user and compute a table with the 1,000,000 most common passwords and their specific salt, and repeat for all the users. With a modern homemade GPU rigs making billions[1] of computations per second, you are testing thousands of users per second with a 1M word dictionary, so you are going to find matches.

[1] https://hackaday.com/2012/12/06/25-gpus-brute-force-348-bill...

Where do you store the salt?

The salt can be stored directly in front of the hash in the same string in the DB (a lot of crypto hash functions will output this). It can be plaintext since the goal is to add a random component so rainbow tables wouldn't be possible since there's always more to the string being hashed. That's where it becomes a time problem.

Yeah, you could rebuild a rainbow table yourself u til you find the collision, but you have to search every bit of the potential hash space.

Reply on news.ycombinator.com