They say the hashes were peppered. What does that mean? If it's similar to a unique salt per user, I find it hard to believe they could crack that many very strong looking passwords.
All peppering does is make it trivially more difficult to check for duplicate passwords. A system with a decent amount of GPU power can try passwords against SHA-1 at billions of attempts per second.
What does peppering mean though? I don't even know the definition.
Per-user unique salts are definitely helpful in leaks like this. With 400,000,000 users, it would take 400,000,000x more compute power to crack the same number of passwords.
Not really, because the exponential scaling with strength of password dominates the sub-linear scaling in quantity of passwords.
The passwords in the dataset will neatly divide into "trivial" and "intractable".
A single password with 80 bits of entropy (16 characters, random lowercase/numbers) will take more time to crack than 1,000,000,000 strong human-chosen passwords under 40 bits.
Most of the passwords will be so weak that it might not be worth doing the sorting and preprocessing needed for the parallel attack on multiple passwords with the same salt.
Once you're using just plain hashing you've already lost and instead of using ad-hoc salting schemes you should be using a proper PBKDF (PBKDF2, bcrypt, whatever)
Going to take it from the top. Skip down for the actual pepper information if you're already familiar with hashing and salting (I assume most people will be).
Let's assume you want to store a password. The first, obvious step, is to store it in plain text. This is obviously brain dead, but well, we live in the world we live in.
$user_pw = $password;
The second step is to hash it. This means that the password can't just be read out of the database.
$user_pw = hash($password);
The problem with this approach is that with the amount of computing available, it's fairly trivial to just bruteforce everything, and with the advent of rainbow tables (pre-cracked hashes), it gets even easier.
The next obvious step is to salt the password. Salting means that you add a random piece of information to what you hash, in order to disable the use of rainbow tables. Every password has to be cracked individually. The salt needs to be included in the stored form of the hash, because otherwise you can't calculate incoming authentication requests against it.
This makes a targeted attack possible, but mass attack over a long list of passwords gets quite a bit more difficult.
The problem is that now, you have the salt always stored with the password. This means that if your database gets stolen/dumped, an attacker has all the information required to crack specific hashes.
In order to alleviate this, you can use a pepper, which is similar to a salt, except that it is global and unique to your application, and doesn't change all the time. It is a static piece of data that gets hashed as well, but isn't stored alongside the hashes in the database.
This obviously only changes anything if your pepper doesn't get stolen alongside the database, so this is usually an application-specific constant that doesn't get stored in the database.
I've never heard of this before (at least not called "pepper") - I think I've heard similar things called stuff like 'sidewide salt' and 'per-password salt'.
"peppering" as described is conceptually similar to storing passwords as HMAC's under some key not stored in the database.
