Ah, yes, PBKDF2 is very expensive in terms of CPU – in fact it’s explicitly intended to be expensive.
Yes, I’m aware, would have actually loved it if Bcrypt or Argon2 was officially supported
Now that i know the limit is enforced at a later stage, it makes more sense so thanks for that, now i can stop pulling my hair trying to find a reason
Now that I’ve run even larger load-tests, the CPU exhaustion happened again at ~50K requests for about 13% of requests.
Seems that it accumulates somehow?
It sounds like your average request time is slightly over 50ms, but due to random noise a significant number of them are coming in slightly under 50ms, hence some requests succeed and some fail.
For now, there’s nothing you can do except try to reduce the time further. In the future we hope to add the option to pay for more CPU time.
Yeah, I lowered it again, but now it’s at a limit where it’s not strong enough.
PBKDF2 in SHA256 with 25K iterations of salt, 32-bit salt length
In comparison, Django’s default is 180K rounds and 64-bit salt key length.
Which means, storing password hashes for anything sensitive, might not be enough.
But, I guess that since you already encrypt the database contents, it shouldn’t be a problem and if the code-base is compromised, the hashing doesn’t matter anyway.
Unfortunately PBKDF2 may simply be a bad fit for Workers right now, due to the CPU time limit.
The security of PBKDF2 is proportional to how much CPU time you spend on it. The whole idea is that an attacker performing a brute force attack has to do that amount of work for each guess, so the longer you can make it take, the slower the attack runs. So e.g. if you do 25k iterations, then a brute force attack takes 1/4 as long as it would take if you did 100k.
Naturally, since Workers limits you to 50ms, the best you can do is force the attacker to do 50ms of work per guess. Meanwhile, guidelines for using PBKDF2 usually aim in the range of hundreds of milliseconds. Unfortunately, these guidelines are inherently incompatible with the Workers CPU limit as it stands.
To make matters worse, PBKDF2 is sort of obsolete because it can run much, much faster on a GPU or ASIC. A GPU can brute-farce PBKDF2 something like 1000x as fast as a CPU can, while an ASIC could be 10,000x or more. The time taken will still be proportional to the number of iterations, but it’s not clear if any number of iterations that can reasonably be performed on a CPU will really get you that far against a dedicated attacker. (Modern password-hashing algorithms like scrypt are better because they are harder to implement in GPUs and ASICs.)
@KentonVarda I’m well aware, I’d rather use bcrypt or Argon2, but that’s not possible. I’ll try scrypt.
Nevermind, I see scrypt is not available in the Web Crypto API.
@KentonVarda I see that even scrypt has ASIC implementations now. Argon2 seems safest.
I guess I’ll have to setup an external API just for the hashing, which is kind of silly.
Maybe a paid feature/function just for hashing/crypto can be added to Workers?
We’d like to let people pay for longer CPU limits, which would solve the problem, but I’m not sure yet if/when that will happen.
We could maybe add better algorithms to the WebCrypto implementation as well, but probably not useful until we have longer CPU limits in place, since I think all of them try to use multiple-hundred-milliseconds. (To be honest I’m not really sure why we added PBKDF2…)
@KentonVarda I’d like to know the attack-area, considering that the database entries are encrypted at rest and decrypted only during a request - the plausible password leaks here are all code-based and if someone has access to the worker account/code, then they can capture the actual passwords anyway and the hashing doesn’t matter. Or am I missing something here?
Have you considered Rust/WASM?
That’ll get you scrypt and PBKDF2, might be faster…