Apparently Yahoo was hacked yet again with up to a billion user accounts being compromised. The article says Yahoo uses MD5 for password hashing.
Are the hackers likely to be able to crack the passwords too? How long will it take to crack 1 password? Is the time to crack 1 billion , just 1B * t ?
Yes, they were likely able to crack many of the passwords in a short time.
From the official Yahoo statement:
For potentially affected accounts, the stolen user account information may have included names, email addresses, telephone numbers, dates of birth, hashed passwords (using MD5) and, in some cases, encrypted or unencrypted security questions and answers.
MD5 is a disputable choice for password hashing because its speed makes cracking MD5-hashed passwords really fast. Also, they are likely not salted, since Yahoo would have certainly let us know. (A salt would have helped to prevent the use of rainbow tables while cracking.)
You can see the drawbacks of simple MD5 hashing when you compare it with the Ashley Madison breach in 2015 which leaked 36 million accounts. In that case, they used bcrypt with 212 key expansion rounds as opposed to Yahoo's plain MD5 which is why back then researchers could only decipher 4,000 passwords in a first attempt.
From the article:
In Pierce's case, bcrypt limited the speed of his four-GPU cracking rig to a paltry 156 guesses per second. [...] Unlike the extremely slow and computationally demanding bcrypt, MD5, SHA1, and a raft of other hashing algorithms were designed to place a minimum of strain on light-weight hardware. That's good for manufacturers of routers, say, and it's even better for crackers. Had Ashley Madison used MD5, for instance, Pierce's server could have completed 11 million1 guesses per second, a speed that would have allowed him to test all 36 million password hashes in 3.7 years if they were salted and just three seconds if they were unsalted (many sites still do not salt hashes).
So, cracking a large portion of the Yahoo passwords is a matter of seconds (while some stronger passwords will remain unbroken). An exact answer would depend on the available computation power and the password security awareness of Yahoo customers.
1As @grc has noted, 11 million hashes per second appears rather slow. @Morgoroth's linked 8x Nvidia GTX 1080 Hashcat benchmark (200.3 GH/s for MD5 total) is a good resource for more up-to-date measurements.
(Summary is in the last paragraph.)
How long will it take to crack 1 password? Is the time to crack 1 billion, just
1e9 * t?
Imagine I have this hashing algorithm:
function hash(password):
hash = 0
foreach character in password:
hash = hash + toNumber(character)
return hash
If you call hash("ab") it might return 3, since the first character's numeric value could be 1 and the second could be 2, and it adds them up, resulting in 3.
Now if you have a database full of numbers, like 583, 140, 8582, etc., how long would that take to crack?
In this example, hash("ab") would result in 3 as well as hash("ba"), which is called a collision (two inputs mapping to the same output). In md5 this does not happen so easily. The order matters and you cannot derive any information about the input given the output. Not even the length.
So you have to resort to just trying all possibilities until you find one that gives you the right output. If someone has a strong, random, 20-character password, it could take centuries. But most people use passwords like "horselover49", "letmein" or "penis" (though the latter might be too short), which are much easier to crack.
The reason everyone's complaining about using md5 is because it's fast. But hashing algorithms are made to be fast. MD5 might be broken for other purposes, but it isn't for password hashing. You just shouldn't use a single pass of any hashing algorithm, be it md5 or sha1 or sha512.
Better algorithms, like bcrypt/scrypt/pbkdf2/etc. use a hashing algorithm a million times (among other things). Now instead of being able to run the algorithm once for every guess, you need to run it a million times for each guess. That takes a lot longer, allowing you to try fewer passwords, which better protects weak passwords.
So yeah, the same is going to happen as with other breaches that used MD5: lots of passwords will be cracked. But they won't all be cracked and definitely not in linear time. The stronger ones will take exponentially more time.
Remember that time to start getting usable passwords out of the system is much less than time to find the password of any one particular user. Pick a password, hash it, find all the users whose password hashes to that value (extremely fast if you've previously stored the users in a hashtable keyed by the password hash), repeat. In this large a pile of users, almost any password is likely to have someone using it, and common/sloppy passwords will have many people using them.
We don't know without additional information.
First, it has been said "they used MD5". Taking a password and hashing it with MD5 is very, very fast. As has been said, there are machines that can make 28 billion password guesses and calculate MD5 hash codes per second. That would be bad. However, they might have used multiplie rounds of hashing with MD5. They might have hashed the password, then hashed the result of further million times. Now the number of passwords that can be guessed and the hash calculated is "only" 28,000 per second.
Second, we need to know whether the passwords were "salted". "Salted" password means that for every user, a different "salt" is added to the password. For example, if I stupidly used the password 1234 and you stupidly used the same password, then our "real" passwords might be k39fja0eflaei-1234 and oe0vnda9afnlad-1234. So even if my password is cracked, this doesn't help cracking your password. Every password has to be cracked individually.
With unsalted passwords, each of the 28,000 password guesses will succeed if any of the billion users used that password. So with a few billion guesses, all the easier passwords will be cracked. With salted passwords, it takes a few billion guesses will only get you a few easy passwords. But if they used plain MD5, then 28 billion password guesses per second will crack things quite quickly, even with salting.
