I think the idea behind the article was to explain why people are encouraged to stop using passwords from Site A if Site A gets 'hacked,' even on Sites B, C, D, etc. It's not just that encryption was broken on one site. It's that now that password has been matched up to a hash, so its strength is kaput.
I do think the message got a little lost in the post though, with the follow-on discussions of salting, bcrypt vs. md5, etc.
But hasn't the password + salt been matched up, not just the password? Or is his point that you don't know, so you need to treat it like the password is compromised (which I agree with). But the password is compromised either way (hash or encryption). I'm confused, maybe I need to go back and read it again.
Compromising the hash and salt, since they must be stored close together, makes it possible to identify if the salted hash is a password in a corpus of previously compromised passwords. An attacker can do Hash(PW, Salt) for all PW in a list of leaked/cracked plaintext passwords. If they've guessed your password and it's shared across multiple services, lateral compromise. Salting only prevents the rainbow table attacks, where an attacker precomputes all possible hash values for a known keyspace (like, say, 8 alphanumeric length passwords) and just look up for a match. Encryption is concerning because it necessitates the ability to decrypt since they're often inverse operations of each other, and presumably there's a shared key stored somewhere to do the comparison, which means it's likely trivial to recover the password compared to hash cracking and undermines any strength or complexity benefits. This also likely points to other bad behaviors utilizing this "feature", such as helpfully emailing you your plaintext password when you forget it.
... we can build a function that takes the output from hash(password) to deterministically create a new candidate password, let's call this function pass(hash), and then chain the hash and our new function together as many times as we want. This lets us store much less data, while doing more work during our look-up phase.
Now if I find a hash 92fe87 in a password hash file, I do not learn that the password was jimmy, instead I need to compute pass(hash(jimmy)) and that's the password I was looking for. And if I find 39a4e6 which isn't in my list, I calculate hash(pass(39a4e6)) and discover that's 213eea, then I look this up in the table and I discover the password I need was 12345678. Obviously real Rainbow Tables don't just run the hash twice like this, but instead some fixed number of times chosen by the creator to trade off less space versus more work to find a password.
I should actually fix this. What I've described above is basic "chaining", but Rainbow Tables are a further improvement still by Philippe Oechslin. The additional insight in Rainbow Tables is that we can reduce collisions in our hash-pass-hash-pass back and forth if we modify that pass function so that its behaviour varies by depth, this way if a collision occurs but at different depths in different chains (e.g. maybe the chain starting with password "password" hashes immediately to 5f4dcc but in another chain the value 5f4dcc is found for the password "j58X_m04" after six steps) the next call to pass() will diverge again, so the collision only wastes a small fraction of our precomputation effort. If the collision does happen at the same place in the chain, the final hash output will be identical to another chain, so it's easy to discover this problem and apply whichever mitigation seems appropriate.
Interesting, I haven't worked with rainbow tables very much since by the time I got into the world of hash cracking it had either been deprecated by salting or wasn't relevant (i.e. NTLM). That is a clever trick of trading back some of the space for extra time; I remember some of the rainbow table file sizes being ridiculous to the point of almost unusable haha.
If one uses bcrypt for hashing passwords, as currently the best practice recommends, building basically a salted rainbow table becomes rather expensive, too. Not impossible, since the amortized cost for many common passwords is relatively low, but still sort of expensive.
Ideally a machine that generates and checks the hashes should be a box without a NIC, connected to the rest of the servers via a bunch of RS-232 ports. This would make extracting the salt much harder, down to effectively impossible. Few orgs can afford such a setup, though, due to the hassle of administering it.
> Not impossible, since the amortized cost for many common passwords is relatively low, but still sort of expensive.
This statement seems like it gravely underplays the numbers.
Traditional Unix crypt uses a 12-bit salt. So this means your precomputation (whether a Rainbow Table or not) is 4096 times more expensive. That's just about plausible though already uncomfortable ("Sorry boss, I know you said the budget was $10 but I actually spent forty thousand dollars").
But bcrypt uses a 128-bit salt. So now your precomputation is so much more expensive that if the equivalent ordinary brute force attack on a single password cost 1¢ and took one second on one machine, you'd spend a billion dollars per second, over a billion seconds, on each of a billion machines, and still not even have scratched the surface of the extra work you've incurred to do your precomputation.
Rainbow Tables are a precomputation "time-space tradeoff" attack. You do a bunch of preparatory work which is amortized over multiple attacks and results in needing space to store all your pre-computed data. This is nice for two reasons:
1. You get to do all the hard work before your attack, leaving less time between the attack and your successful acquisition of the passwords compared to work that's necessarily done after stealing the credential database.
2. You can re-use this work in other attacks
But if you're waiting until you know the salt you don't get either of these advantages, so Rainbow Tables are irrelevant.
It's like if somebody mentions the F-14 fighter jet in a discussion about the fastest way to get from Times Square to Trump Tower. Yes the F-14 fighter jet is a fast aeroplane, but it can't go to either of those places so it isn't relevant whereas Usain Bolt is a very fast human so he really could run from one to the other.
It does make logins on other machines difficult. You may open up your password manager's web interface on your friends laptop, but then you opened up all your passwords to potential malware,including banks etc. When you just wanted to log in to Reddit, where you have an account you somewhat care about: you spent years under that username, but its not a huge catastrophe if it's taken away, unlike, say, your domain registrations, your email password, your e-government logins, banks etc. The "all eggs in one basket" still bothers me.
We haven’t lived through a big password manager leak yet. But a password manager gives the list of usernames, passwords and websites. This kind of compromission is probably worth a million dollars per user. That’s a lot of data in the same vault. Just saying.
Mist people arent worth a million dollars, that downright silly.
But i do agree that centralised storage of everyone's passwords does not make sence.
I've decided to use KeePass and store the encrypted password file in cloud storage - that way it syncs between my phone and conouters, and i can always get at it if i really need to. But it does make logging into reddit on someone else's oc very difficult.
I do think the message got a little lost in the post though, with the follow-on discussions of salting, bcrypt vs. md5, etc.