Well some of the passwords are safe. Bcrypt doesn't offer much protection if your password is on a list of the 10,000 most-common passwords [1].
Ashley Madison's highest priority should be to tell users to change their password on the Ashley Madison website, and any other website where they have used the same password.
Bcrypt includes a (large) random salt so is not subject to rainbow table attacks. I believe therefore that will protect against identifying passwords contained in a known list.
If I'm wrong about this I'd love someone to explain why to me.
I haven't heard of rainbow table attacks being used much at all anymore. It's completely practical to individually brute force every person's password using their specific salt in parallel.
Let's say they cranked up bcrypt to take 10ms to run (so their system can login 100 people per second). That means it take me 10 seconds to try all 10,000 weakest passwords against an individual hash. If I can do, say, 1000 hashes in parallel, then I can try the top 10,000 passwords against 100 users' hashes a second. If their DB is 100,000,000 passwords then that's only 11 days to try the top 10,000 passwords on everyone, which is super reasonable and will get you tons of low-hanging-fruit.
In practice you can probably try a password faster than this, and massively more parallel. So that's just gravy. Also keep in mind I don't need to try all 10,000 on everyone -- if you have the most common password I can stop right away. Further, if you identify a user who's password you really want to crack, you can redirect all those resources at just that user with the full might of John the Ripper or Hashcat and try 1,000,000,000,000 common passwords and mutations against that user in the same amount of time (using my pessimistic numbers for how fast you can run).
For reference, password cracking rigs are usually talked about in terms of gigahashes/second (billions of hashes per second).
this is not about rainbow tables, just about brute forcing. The only theoretical protection would be a site salt, but that has to be stored somewhere as accessible as the database, so it's fruitless to assume somebody who can get their hands on your db can't get the site salt.
"It’s important to note that salts are useless for preventing dictionary attacks or brute force attacks. You can use huge salts or many salts or hand-harvested, shade-grown, organic Himalayan pink salt. It doesn’t affect how fast an attacker can try a candidate password, given the hash and the salt from your database."
That salt is a public value. The security of salted password schemes is meant not to depend on the secrecy of the salt.
Every time this topic comes up, 15 people chime in with various schemes in which some of the "salt" is derived from the hostname and some of it is stored in an encrypted vault and some of it is inferred from the color of the user's eyes. This is why Coda is making fun of "Himalayan pink salt".
It does prevent simple rainbow attacks, but it does not prevent a simple bruteforce of the common passwords. It can increase the cost a bit, but still in the realm of feasible.
I am mainly trying to warn against the false sense of security. Salting does not magically make weak passwords secure. It makes certain types of attacks harder, but a bad password is still bad.
That being said the problem is less that we are not asking users to provide strong enough passwords. It is that the industry seems to be completely incapable of protecting their users data. This race to the least crackable hashing algorithm is only adding more lipstick on the pig.
Having seen a major leak pretty much every week if not every day the past 3 years, I am now of the opinion that I should provide zero personal information to anyone. Disposable email addresses, fake names and address will now be my norm.
If they hashed PASSWORD + USER_SPECIFIC_SALT + SITE_SALT, storing USER_SPECIFIC_SALT in the user table and SITE_SALT in the application config, both data and site config would have to be leaked.
Ashley Madison's highest priority should be to tell users to change their password on the Ashley Madison website, and any other website where they have used the same password.
[1] http://www.passwordrandom.com/most-popular-passwords