I think PBKDF2 may be better than Scrypt? Looking for someone to point out my logical error

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.