When were talking 5B tries per second, that means trying the most common 100,000 passwords against each of the 50M accounts in under 20 minutes. The most common 1,000,000 passwords against all 50M accounts in under 3 hours; the most common 10M passwords against all 50M accounts in a little over a day.
Hashing is good, salting is better, but unless there was a work factor involved like PBKDF2, bcrypt, or scrypt, it seems like it's protection against people who don't know what they're doing more than against people who know what they're doing. I'm not the type to say that we need to protect against people who have the money to make ASICs (app-specific integrated circuits likely used by governments), but I do think protection against nVidia chips is warranted.
Now, it's genuinely possible that by "hashed and salted", they mean they used bcrypt or PBKDF2 (and simply aren't giving details in the email). But, if it's a salted SHA1, I think phishing would be harder than cracking a substantial proportion of them.
That's why you might want to use Bcrypt instead of SHA-1 or SHA-256.
EDIT: Just realized that the salts have to be stored somewhere and the attacker probably grabbed those as well. I think that answers my question.
Short of finding an exploit in GPG, you'd have to crack the public key used which would be near impossible if a long key was used. This assumes you keep that key safe.
So why not literally make a key pair and throw away the key?
If you used the same key for all your site's passwords an attacker could build a rainbow table so you don't even get to not salt.
It would be a lot slower than a normal hash so it'd be harder to brute force, but you can get the same protection in a simpler, more predictable system by just using PBKDF2 with enough repeated hashes.
I don't subscribe to one "scheme" for passwords since the easiest method (to implement, not crack) will be the avenue malicious hackers also pursue.
This is why most of my custom jobs involve an application specific salt per installation, in addition to the user-unique salt + password hash and then CFB encrypt the salt using another app-specific password + username hash.
Edit: My standard response
http://eksith.wordpress.com/2013/04/08/diy-hashing-if-you-mu...
It turns out LivingSocial was actually using SHA-1 with a 40 byte salt [1].
> LivingSocial never stores passwords in plain text. LivingSocial passwords were hashed with SHA1 using a random 40 byte salt. What this means is that our system took the passwords entered by customers and used an algorithm to change them into a unique data string (essentially creating a unique data fingerprint) – that’s the “hash”. To add an additional layer of protection, the “salt” elongates the password and adds complexity. We have switched our hashing algorithm from SHA1 to bcrypt.
A 40 byte salt? "_additional_ layer of protection"? "elongates the password"? It's clear they thought they were implementing extra security (hey, let's use a 40 byte salt instead of 16, mega protection!) but failed miserably because they did not know what they were trying to combat.
Login load is nothing compared to the rest of the app.
An attacker could simply put together a dictionary of 10,000 common passwords then hash them against each user's salt value and see they they get a match for that user's password Hash. Assuming Hashes are stores as SHA-256, with a GPU hashing setup they'll be able to scan through 50 million users in very little time at all.
I get that this is a bad idea that won't work, blah blah security by obscurity and so on. But when I was asked why it doesn't work, I was unable to give a very satisfying answer.
I mean, there is a certain logic to what you're suggesting. Let's say you're cpervica and you know what you're doing. You make mistakes like any human being, but you know crypto. So, some cracker gets access to your database. OK, they're probably not smart enough to find a weakness in what you've done and might not even be able to figure it out. But there might be a weakness there.
Plus, you have to think: what if someone gets my code and my database? Then they have the modification you made. If the modification doesn't require more computation, then it's just unknown without the source code. So, with the source code, we're back to the trivial to cracking case.
The thing is: there are solutions out there to handle this by making the calculations take longer. PBKDF2, bcrypt, and scrypt all exist. They deal with this specific problem in a way that even if someone gets your hashes, salts, and code, you're less vulnerable.
tl;dr: with the obscure case, you're not gaining protection if they get your code along with your database.
Edit: See udk1 below -- he's right, sha1 is an outdated algorithm for this purpose. Poor example choice on my part.
I've heard it referred to as a pepper (to go along with salt) and is in the application code.
bcrypt(password, salt, pepper) => hash. So even if they grab the db with the salt, the effective password to crack turns into 'password3jkl453jklgfuja9oph4mn" instead of just 'password'. Impossible.
And if they do get your site's code, you're back to a strong hashing algo and a salt.
Most people should use bcrypt with enough rounds to make it difficult to brute force. scrypt is also an option, though newer (good / bad: http://security.stackexchange.com/questions/26245/is-bcrypt-...).
That's the "theoretical" answer. The real answer is, popping someone's database virtually always --- you know what, let's just assume always for now --- gives you a remote shell, and from the the actual code.
The point you and others make that if the database is compromised then the code almost certainly is too, is clearly the best answer though. I am now prepared for the next time I encounter my interlocutor at extended family dinners!
Cryptographically, you can address the problem you've set out for yourself simply by hashing a 128 bit random number along with the password, and keeping that number a secret. If attackers can get your code, it doesn't matter how you obscure your hash, because they'll have the algorithm. But through trial and error, an attacker might figure out how you tweaked an algorithm; all the atoms in the solar system (or something like that, I can never remember) could be computers trialing and erroring against a 128 bit random number and they'd never figure it out.
2^128 = 3.4028E38
solar mass = 1.9884E30 kg or about 9E56 atoms.
256 bits is the one where the hosting costs start getting not merely planetary but intergalactic.
2^256 = 1.1579E77
atoms in Milky Way = 2.9E76 atomsThis secure stuff is hard. Remember when debian made a "simple fix" to open ssh and made all the ssh keys for 2 years brute forcible? Do you think you can do better? It's wiser to leave this to the experts
This could have (and often does) happen to any software. It's not a good example of someone attempting to design their own or modify an existing crypto primitive algorithm.
It's called "salting" the password. Everyone does it. It works really well.
Of course, if they can steal your salt (from your source, or a config file) then you lose.
Since salts are random, and unique per password, you shouldn't be storing them in a config file.
The long answer is that security experts are expensive and trying to figure out security systems from first principles is very hard and fraught with disaster. The result is that almost all security practices are transmitted via folklore.
Also, the documentation for security software is often dense and hard to understand, while the documentation for non-security software provides advice that is simple, actionable, and terrible: http://dev.mysql.com/doc/refman/5.7/en/encryption-functions....
* The undocumented-algorithm PASSWORD() function that mysql uses to hash passwords apparently defaults to unsalted double-SHA1
* You are helpfully advised not to use this function to store user passwords, instead you're advised to use MD5 or SHA2.
* Salting is not discussed at all.
* Key stretching functions are not provided or discussed.
Many tutorials and reference documents use MD5 and SHA1 in their coding examples, so right from the get-go novice developers are at an automatic disadvantage.
It's much more important to know what algorithm they were actually using, e.g. scrypt, bcrypt or PBKDF2, and what the settings/work factors/iteration counts for them are/were. If a company is reluctant to disclose that, they're likely using something that's highly vulnerable to parallelization/efficient brute force cracking, regardless of what kind or size of salt was used.
It could have been MD5!
LivingSocial is a big enough company I wouldn't be surprised if their authentication code was all or mostly custom.
What I am saying that if the attacker gets a row from the database that has the user's id, the password will be in a column labeled 'password'. Next column is likely to be the salt generated for that user's password, and let's say that this column name is 'salt'. With the salt and password for each user, you can run a dictionary across each combination at a furious rate.
25 late 2012 vintage GPUs gets you 180 billion MD5 tries per second. With a fairly modest budget you can rent a whole lot more GPU power than that. A little Googling gets me several companies offering password hash cracking as a service.
But we're assuming, at the very least, that they're not using MD5 and are instead using SHA-2/SHA-256 or (s|b)crypt.
There's an order of magnitude difference between brute forcing MD5 and brute forcing something better.
MD5 is 2-3x as fast as SHA-1
MD5 is 5-7x as fast as SHA-256
I don't know why anyone would assume they are using anything better than MD5/SHA-1 considering the history of incidents like this.
Shocker!
Thought most email notifications are annoying, they can be useful (or crucial).
One nice feature from gmail/yahoo/outlook/etc.: temporary email addresses that forward to your email. This would solve the problem.
Or, maybe alternative notification methods are preferred? If they wanted, a user can input an email address with a plus (if they're using gmail) and then receive notifications only on that. If the user wanted, then they could block all incoming messages that match that generated email.
However what I've seen happen after this attacks is usually they attacker use the e-mail addresses to do phishing attacks and just get passwords that way. They already know their e-mail and that they are living-social customers. Expect a phishing e-mail that looks like coming from living social.