77

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 ?

  • 24
    This cannot be properly answered since anyone who simply used one of the most common insecure passwords like 12345 or Password123 will be done in seconds. But secure and longer passwords will take a lot more time. – Julian Knight Dec 15 '16 at 7:44
  • 4
    Some team build a computer that could do 350 billion guesses per second... and that was in 2012. – Jacco Dec 15 '16 at 8:13
  • 47
    Don't forget this happened in 2013 - most of the passwords could already be cracked. – grc Dec 15 '16 at 12:24
  • 11
    To quote from the site “Based on further analysis of this data by the forensic experts, we believe an unauthorized third party, in August 2013, stole data... – xanatos Dec 15 '16 at 13:51
  • 4
    Most likely the correct question would be "how long did it take"... – Mehrdad Dec 18 '16 at 0:42
68

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.

  • 29
    11 million guesses per second seems quite slow for MD5. – grc Dec 15 '16 at 7:52
  • 40
    "Also, they are likely not salted, since Yahoo would have certainly let us know" - How on Earth could a tech company as large as Yahoo not have been salting their password hashes?!? If this is true, it's inexcusable. – aroth Dec 15 '16 at 12:06
  • 30
    @aroth Really? Is this your first time hearing of a big hack? Until fairly recently it was pretty common to hear about passwords stolen in plain text. Its still totally inexcusable, but you shouldn't see it as so surprising. – David Grinberg Dec 15 '16 at 15:02
  • 16
    @Luc the thing is if you say "MD5 is fine for password hashing provided you use a big number of rounds" most people hear "MD5 is fine for password hashing" completely ignoring the rest. This way saying that MD5 is unsuitable for password hashing will at least prompt some people to ask "Okay, so WHAT is suitable?" and maybe this way we can propagate the knowledge about how to do things rights. – Maurycy Dec 15 '16 at 15:08
  • 7
    @Luc Anyone who doesn't already understand that "MD5 is broken for password hashing" implicitly refers to the simplistic, single hash has no business trying to roll their own many rounds hashing scheme using MD5. If a person doesn't know enough about hashing to have a discussion about it, they should be using standard implementations that handle those details for them. Full stop. Besides, isn't even multiple round hashing of MD5 more easily optimized in GPUs than others, which makes it inferior as a password hashing algorithm? – jpmc26 Dec 15 '16 at 16:47
21

(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.

  • 2
    Won't running MD5 multiple times still be vulnerable to rainbow tables? I'm still getting my head around rainbow tables so I could be way off here. – JimmyJames Dec 15 '16 at 14:48
  • 57
    'But most people use passwords like [...] "penis" (though the latter might be too short)', please tell me that was intended. – Brian H. Dec 15 '16 at 15:40
  • 5
    @Brian some people just can't resist that joke :-) – John Dvorak Dec 15 '16 at 16:01
  • 2
    @JimmyJames Most rainbow tables assume the hash was only calculated once on the original password. You could build a custom rainbow table using a specific number of multiple hashings, but it would really only be useful if the leaked passwords used a matching hash count. That could be hard to predict. You're almost certainly better off just cracking that type of hash. – PwdRsch Dec 15 '16 at 16:32
  • 4
    @Brian Yes. – Luc Dec 15 '16 at 17:17
5

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.

  • This is only true if the passwords were hashed without salt. If salt is used, no two hashes will match even if you have millions of identical passwords. If you use a slow enough password hashing algorithm (bcrypt, scrypt or even pbkdf2), then brute-force guessing one password hash at a time will be slow enough to hopefully give users enough time after the discovery of a breach to change their passwords on the live sites so that the brute-forced passwords are no good to the bad guys. Especially for users who chose long, strong passwords to begin with. – Craig Dec 18 '16 at 17:58
3

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.

protected by Rory Alsop Dec 16 '16 at 22:13

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.