1
$\begingroup$

People seem to mostly recommend scrypt these days, but I'm not sure if this should be the case? I'll structure this post by just making an argument for PBKDF2 over Scrypt and then you can reply telling me where I'm wrong.

Okay, let's say I'm Google and want to hash my user's passwords in the most secure way possible. Currently some of the most recommended ways are PBKDF2 (with SHA512 for example) and scrypt.

I want each password to take around 1 second to hash.

I look into PBKDF2 and see that the most efficient way to calculate hashes for it are using an ASIC.

I then look at Scrypt and see that the most efficient way to calculate hashes for it are through a balanced combination of CPU, RAM, and GPU.

Since I'm a webserver, I mostly just need CPU. I don't really need a GPU at all, only some RAM, but yeah, mostly CPU. Unfortunately, I can't even use that much CPU because I need it for serving all my concurrent requests. As a result my hashing will be weaker unless I purchase additional hardware.

In the case of PBKDF2, you will need to buy an ASIC to be ideal, and with Scrypt you will need to buy a GPU, RAM, and have a really strong CPU (yikes recent Intel security issues) to be ideal.

Is there a difference is between having X input rounds with PBKDF2 with ideal hardware (ASIC) vs having Y input rounds with Scrypt with ideal hardware (Proper balance of CPU, RAM, and GPU)? Assuming both operations take 1 second with the given input parameters, at that point aren't you mostly just guessing which will be harder in the future?

Also, it looks like either way you'll need to spend money on additional hardware.

Okay, now for my additional arguments in favor of PBKDF2:

  1. It's been around longer and is thus more time-tested and scrutinized
  2. It's NIST and FIPS compliant
  3. There is more native support for it (For example, node crypto has PBKDF2 and not scrypt)

Also, an insane amount of financial incentive has lead to the development of specialized hardware for grinding PBKDF2 hashes because of the cryptocurrency phenomena. As a result, I'd imagine that not only is SHA extremely secure, but that ASICs are near the asymptote for potential performance.

Comparably, Scrypt may yet have specialized hardware developed that will allow for much more efficient computation in the future.

Lastly, is it not the case that Scrypt databases can be cracked by a botnet? Since the ideal hardware for the Scrypt hashing algorithm is pretty close to consumer hardware (CPU, GPU, RAM), is there not a risk that an Scrypt database could be be parallelized across the Botnet? For example, it is currently a concern of some cryptocurrencies that use Scrypt-adjacent algorithms that a botnet may be able to someday near a 51% attack.

Thoughts?

$\endgroup$
  • $\begingroup$ Two remarks: 1) A primary line of defense should be that the password hash database is secret. The password hash is extra. 2) Nobody I know (and I guess not Google) use ASIC or even GPU for their password hash, thus "an insane amount of financial incentive has lead to the development of specialized hardware for grinding PBKDF2 hashes" is an argument against PBKDF2. That said, the last bitcoin mining ASIC I checked had become so specialized that it could no longer do PBKDF2-HMAC-SHA256; much less PBKDF2-HMAC-SHA512. I guess PBKDF2 cracker ASICs hunt for passwords, not bitcoins. $\endgroup$ – fgrieu Feb 8 '18 at 5:31
  • $\begingroup$ 1) Of course, but this is security through obscurity. Hashing is so you can still remain safe even after database exfiltration 2) Just because no one is doing it doesn't mean it's not better. 3) Perhaps I didn't articulate this properly. I mean that it is good that so much time and energy went into optimizing SHA hashes so that now we can buy ASICs and they'll be relatively future-proof compared to other hashing calculators (which are not as close to the physical calculation asymptote and thus may be more susceptible to large efficiency gains in the future). $\endgroup$ – John Smith Feb 8 '18 at 5:38
  • $\begingroup$ @fgrieu Even old BitCoin mining equipment cannot be used; SHA-256 is performed twice in a row. But even that doesn't matter: you start the miner and hopefully you get a result. There isn't a round trip with the result of a single round of hashing - and that's not likely to change as it would slow down the system to a crawl. And yes, I asked this on BitCoin.SE. $\endgroup$ – Maarten Bodewes Feb 8 '18 at 13:47
  • $\begingroup$ The Node.js crypto module started to support scrypt a while ago. $\endgroup$ – domenukk Nov 13 at 10:32
7
$\begingroup$

There's no point in using either an ASIC or a GPU to calculate a single password hash. That's true whether you use PBKDF2 or scrypt or Argon2 or whatever.

What massively parallel devices like GPUs or ASICs are good for is hashing millions or billions of passwords at the same time. That's useful if you're mining a cryptocurrency or trying to crack a hash for which you don't know the password, but not if you're just trying to test a single user-entered password to see if if it matches the account's password hash or not. For that, it's much easier and more efficient to just calculate the hash on the CPU.

Basically, what parallel devices like GPUs and ASICs do is give an edge to the attackers, who have billions of passwords to test and don't really care about latency (i.e. the time it takes for a single password to get hashed) as long as the throughput (i.e. the average number of passwords hashed per second) is good. That's why modern password hashing schemes like scrypt or Argon2 are designed to make GPU/ASIC hashing as hard as possible, so that the edge they give to attackers over legitimate authenticators is minimized.

(And yes, a botnet of compromised personal computers could indeed be used to crack scrypt hashes. However, especially if most of those computers had half-decent graphics cards, they'd be even better at cracking PBKDF2.)

$\endgroup$
6
$\begingroup$

The question correctly finds that

In the case of PBKDF2, you will need to buy an ASIC to be ideal

and proceeds assuming the legitimate server does that; or at least, uses a GPU as substitute. Which, in practice, does not happen. That's where the question's reasoning drifts from reality.

When we compare PBKDF2 to Scrypt, and conclude the later is vastly superior, that's assuming the same time on a CPU is used for both by the legitimate user. In the case of PBKDF2, the memory attached to the CPU is mostly idle during that time. With Scrypt, that memory is used, and the attacker demonstrably has to invest in purchasing as much memory as Scrypt uses for each cracker job running, when that cost does not exist for a PBKDF2 cracker. This considerably multiplies the investment cost for enough crackers to test a given number of passwords per second, with little drawback to the legitimate user.

$\endgroup$
3
$\begingroup$

Nobody wants to buy special hardware for hashing passwords. What we want is to use whatever resources I have anyway cheap give a modest compute budget to your hashing and still hope a well funded adversary will find it difficult to brute force or otherwise break a password.

You should choose a password hashing scheme which is efficient on the hardware you have on hand and the best possible setup wouldn't be way more efficient.

If you can afford giving only CPU you can't use a memory hard system. If you can afford in your compute budget both cpu and memory it makes sense to impose the same restrictions on the attacker.

$\endgroup$
  • $\begingroup$ Don't you already have to though? Often these servers won't even have a GPU, minimal RAM, and all their CPU is already going to serving concurrent requests. To hash securely you'll need to either buy CPU, RAM, and GPU for scrypt, or buy an ASIC for PBKDF2. And yeah I'm talking about companies like Google where spending some hundreds or thousands on hashing hardware is preferable to the nightmare of mass user password leaks. $\endgroup$ – John Smith Feb 8 '18 at 5:21
  • 2
    $\begingroup$ I have to allocate some compute budget to hashing. But no I don't have to buy any new hardware. Hashing should not dominate my budget nor determine the hardware. $\endgroup$ – Meir Maor Feb 8 '18 at 5:28
  • $\begingroup$ I don't see how this is the case. Your servers already have a GPU, tons of RAM, and little CPU usage? Also, for pretty much any company (and especially billion dollar companies), is it not worth it to spend some hundreds or a couple thousand on ASICs if it could avoid such a huge potential nightmare? I don't understand how this cost could not be justified via cost benefit analysis. $\endgroup$ – John Smith Feb 8 '18 at 5:31
  • $\begingroup$ Hashing passwords is one minor task a server has to perform. You very rarely get special hardware for each minor task the server performs. $\endgroup$ – Meir Maor Feb 8 '18 at 5:43
  • $\begingroup$ Password security of your users sounds so important. I still am not sure how this minor cost cannot be justified to companies worth billions. $\endgroup$ – John Smith Feb 8 '18 at 5:51
1
$\begingroup$

The point of password hashing functions is to make breaking the hashes more expensive for the attacker than computing them is for the defender.

The defender's hardware should therefore be the most cost-efficient way to hash the password.

Defenders already have CPUs, lots of RAM, and possibly GPUs. GPUs are less common, so lots of password hashes (Scrypt, Argon2id, etc) include data-dependent memory accesses to reduce performance on them and other SIMD devices.

The defender only needs to try a few possible passwords (from users with the correct password and users forgetting their password) for each hash. The attacker has to try large numbers of possible passwords for each hash.

The defender only has to use the resources for a few tries at most, and they already have systems with plenty of memory. They thus want a hash that's most cost-efficient on a system with a CPU & lots of memory.

Attackers want to try tons of hashes in parallel. They want a hash where SIMD works (GPU/ASIC optimal) and don't necessarily need to use existing hardware.

RAM is expensive in terms of die area on ASICs, and memory bandwidth is also expensive and important. Functions that require lots of memory with high bandwidth are very expensive to implement ASICs for. CPUs already have high bandwidth access to lots of memory.

Therefore Scrypt is more expensive to attack than PBKDF2, and thus more secure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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