How can crackers reconstruct 200k salted password hashes so fast?

Question

I'm researching for a small talk about websecurity and I found one article about the formspring hack, which made me curious. They claim to have used SHA-256 + salt

We were able to immediately fix the hole and upgraded our hashing mechanisms from sha-256 with random salts to bcrypt to fortify security (July 10th, 2012)

… nevertheless the attackers claimed they have found ~200k passwords within the 400k published datasets (They have 11m users, it's IMHO likely that most of them have been copied).

About half of the 400,000 hashes have already been reconstructed by password crackers. (July 11th, 2012)

This looks suspicious to me. I know that without using PKCS#5 or similar techniques, the security of SHA-256 is limited, but how much calculation power would they need to find so many passwords so quick?

My guess is that formspring was lying about the hashing. Has someone some insights on that?

Answer 1

None of the existing answers cover the critical part of this question to my satisfaction: what about the salts?

If just the password hash values were posted, other crackers can't possibly know:

1. The actual per-password (supposedly random, per the source) salt value.

2. How the salt is mixed with the password in the code.

All they have is the final, resulting hash!

There are lots of ways the password and salt can be combined to form the hash:

sha256(pass + salt)
sha256(salt + pass)
sha256(sha256(pass) + sha256(salt))
sha256(pass + sha256(salt))
sha256(sha256(...(salt + pass + salt)...))

But if the salt is the recommended 8 characters of pure randomness …

sha256("monkey1" + "w&yu2P2@")
sha256("w&yu2P2@" + "monkey1")

… this means a "typical" 7 or 8 character password becomes extremely difficult to brute force, because it is effectively 15 or more characters! Furthermore, to crack password hashes that you know are salted, unless you also have the salt, you have no other choice except brute force!

Based on research I did using GPU cracking, I achieved 8213.6 M c/s using two high end ATI cards brute force cracking MD5 password hashes. In my benchmarking this meant I could try:

all 6 character password MD5s   47 seconds
all 7 character password MD5s   1 hour, 14 minutes
all 8 character password MD5s   ~465 days
all 9 character password MD5s   fuggedaboudit

Note that SHA-256 is 13% of the speed of MD5 on GPUs using Hashcat. So multiply these numbers by about 8 to see how much longer that would take.

If the salts were not known, that means you're essentially brute forcing the equivalent of 12+ character passwords. That is far beyond the realm of any known computational power.

Now if you want to argue that …

1. The original crackers also obtained the salts, but chose not to post them.

2. The original crackers also have the source code (or it's open source) so they know how the passwords are salted, but chose not to post that information.

3. Formspring is lying and their passwords were not salted or salted improperly such that the salts had no effect.

… then yes, cracking 200k of 400k password hashes in a few days is easily possible.

Answer 2

---

Edit: All of the below assumes that the salts are known, because that's the industry-standard use of the word salt (3rd line).

Just as an example of how this often looks in the database, have a look at this SHA-256 Unix Crypt output:

$5$rounds=80000$wnsT7Yr92oJoP28r$cKhJImk5mfuSKV9b3mumNzlbstFUplKtQXXMo4G6Ep5

.. where wnsT7Yr92oJoP28r is the salt in plaintext. The Python Passlib documentation has good descriptions of many common hashed password formats, and most of these store plaintext salts concatenated together with the hashed password representation.

The 'un-known to the attacker salt' which @Jeff Atwood discusses is frequently called a "pepper". See Password Hashing add salt + pepper or is salt enough?

---

In 2009 Daniel J. Bernstein wrote a highly optimized SHA-1 implementation for NVIDIA's CUDA framework. Back then they managed 690 million SHA-1 hashes per second on a single server using four graphics cards.

Brute force attacks against hashed passwords are an "embarrassingly parallel" workload. In 2010 Thomas Roth demonstrated brute force attacking ~10 hashes for ~2$ using Amazon EC2. This could easily be scaled up, if the rate isn't high enough, then just add more EC2 instances.

So essentially it's not a question of how long it will take to bruteforce the passwords. It's more a question of how much computational power the attacker is willing or able to pay for in order to get results faster.

the attackers claimed they have found ~200.000 passwords

One reasonable explanation is that the attackers didn't target specific hashed representations, they just went for the "low hanging fruit". In other words, they only looked for passwords that are 'easy to guess'. Perhaps something like:

• A candidate list of the most common passwords in plaintext, built from publicized lists of actual user passwords. (Over the years there have been several leaks of real user passwords.)
• And perhaps they additionally tried all pronounceable lowercase passwords up to a low upper bound, for example up to 6 characters. (In the 2006 MySpace data set above it was found that 17% of all end user passwords were of 6 or fewer characters.)

My guess is that formspring was lying about the hashing.

If I understand your links correctly, then the hashes were discovered on a forum on the 7th of July. But they could have been stolen from Formspring weeks or months before that?

Given what I describe above, it doesn't seem unreasonable to me that a single round of SHA256 with a unique salt per password was used, as Formspring said.

It all depends on how much time and effort the attackers put into the brute force cracking. But within the resources that a small group of individual hackers might have, it does seem plausible to discover 200.000 weak passwords from a data set of 11 million simple SHA-256 hashed representations.

Answer 3

Cracking unsalted hashes is fairly trivial: you just look up hash in a pre-computed table and find your answer. No sense brute-forcing the rest because your rainbow tables already cover your brute-force dictionary.

But cracking salted passwords is still simple; slower but still simple. In most brute-force attacks, the attacker goes for breadth not depth. Rather than trying 1 billion passwords against 1 account, he tries tens or hundreds or thousands of common passwords against ALL the accounts. Certainly rainbow tables are faster, but salt alone doesn't impede the classic brute-force methodology. Start at the top of your dictionary and try that password against all of the accounts: this obviously involves recomputing the hash for each account, but on the other hand, your chances of a hit are pretty high (that's precisely what "common password" means, anyway). Next, take your next most common password, then the next, etc.

In the end, you may only get through several thousand passwords, but statistically speaking, there's probably hundreds of accounts with the password "123456" in your list, and a fairly large number who use "password1" and "111111" and "test".

200K out of 11M is believable; only about 2%. 200K out of 400K less so. Not impossible but not as likely. The law of diminishing returns kicks in there somewhere; I'm not sure how far in but it's probably a really simple ratio like 1/e or something. Beyond that I get skeptical.

Answer 4

It stands within reason that they are not lying.

1. As @Jeff noted that access to the salt is essential for fast cracking, but as @Remus Rusanu noted: "if they obtained the hashes then is hard for me to see how could they not obtain the salt as well" since they must be stored in a such a way that they can be associated with each other. I would assume that: at least the initial hackers had access to the salt.¹

2. @Jeff also states that they must have access to the source code to know how the salt and the password are combined. I propose a different approach to find out how the salt and password are combined:

   1. let's assume that they have a formspring account before the attack (a pretty reasonable assumption)
   2. look for that specific account (salt, hash) in the obtained list
   3. knowing the password, the salt and the resulting hash, it should be easy to build a small script to test all the reasonable (and some unreasonable) ways of combining password and salt (no more that a few thousand ways?)
   4. ???
   5. profit!

3. they claim to have "tens of millions of members" which makes @Jesper low hanging fruit theory sound very reasonable.

Ok, they can still be lying but at least it sounds reasonable that they aren't.

_{1. If this assumption is wrong - the initial hackers didn't publish the salt AND didn't try and crack the passwords themselves - the rest may not be possible.}

Answer 5

hashcat can do just over 1 billion SHA256 hashes per second on Radeon HD7970, which is only half the speed of SHA1 and a quarter of the speed of MD5. However, this isn't even the bottleneck:

One more thing before we move on; did you notice the speed of the cracking was “only” 258.7M per second? What happened to the theoretical throughput of a couple of billion SHA1 hashes per second? The problem is that the higher throughput can only be achieved with “mutations” of the password dictionary values or by working through different password possibilities directly within the GPU. In other words, if you let the GPU take a dictionary value then transform it into a number of different possibilities it can work a lot faster. The GPU can’t be fed passwords fast enough to achieve the same level of throughput so effectively having a list of passwords is bottleneck.

So using SHA256 (or even SHA512) is no more secure than using SHA1 or MD5 against these kind of attacks.

Answer 6

Neither post makes mention of whether or not the perpetrators gained access to Formspring source code. If this were the case, the method of hash construction and random generation of the salts would be available to the attackers. This would make the task of cracking significantly easier, particularly if the method of generating the "random" salts limited them to a comparatively small set values.

Given the apparent speed with which this limited set was cracked, my best guess would be that this is the case.

Answer 7

If they were using hashes with a unique salt per password, then it normally would take a considerable time before one could crack these passwords. Unless the passwords were extremely weak or the passwords were words in the dictionary. Pure bruteforcing seems a bit unlikely if they were strong.

Tom's hardware has an article on GPGPU password cracking. Weak passwords (not more than 10 characters including uppercase,lowercase, signs,...) can be cracked in a matter of minutes, even with a salt if the salt is known.

Otherwise, it will take many days, months, longer passwords even thousands of years. But this is without a salt. With a salt it will take forever.