On PBKDF2 iterations | Hacker News Reader

On PBKDF2 iterations

neilmadden.blog

62 pointsrainworld52 comments

It should be noted that PBKDF2 and similar key derivation algorithms are obsolete, precisely for the reason explained in this blog posting, that just doing a reasonable number of iterations of the key derivation function does not increase enough the difficulty of finding a weak password.

PBKDF2 and similar key derivation algorithms are acceptable only when the key derivation must be run on some kind of microcontroller with limited resources, so the security requirements must be modest and it is understood that any really powerful adversary will be able to break the encryption, e.g. by using a large number of FPGAs or GPUs.

Otherwise, a modern key derivation algorithm should be used, for instance Argon2, which also needs a very large amount of memory, in order to prevent fast parallel implementations of the key derivation function.

So, Argon2 is great and everything, and in an economic security model it certainly is more secure than PBKDF2, given what we currently know about costs of operations. However, it doesn't really fundamentally change the argument of the article. Although the model is more complicated for Argon2, you'd still have to crank the parameters up to fairly insane levels to get the kind of security guarantees that are expected by modern cryptography. IMO, if you want secure long-term encryption then the only reliable choice is to use a high-entropy password/phrase/key in the first place. And if you do that, then the password on its own is resistant to brute force and so you don't need PBKDF2 or Argon2.

(There is some "sweet spot" of hard-ish passwords of say 80 bits of entropy, where PBKDF2 or Argon2 would push it over into cryptographically-secure territory. But such a password is already extremely hard to remember, which means you are probably writing it down or storing it in a password manager already. So you may as well just make it longer).

So a diceware-style passphrase of six random words is around 80 bits, and for 128 I would need about ten words in my passphrase, right?

I tend to have a significantly easier time recalling a six-word passphrase than ten. So by your logic, key stretching makes sense in my case, am I following you correctly? Or is my math off?

(I quite enjoyed your article, thanks!)

bits not bytes

Frankly, does the article have an argument? It claims this...

> A lot of the discourse around password hashing gives the impression that there is some magic number you can pick that actually makes passwords safe to use for this kind of thing. There isn’t. They are not. Either your password has sufficient entropy to resist brute-forcing, in which case it is already probably a cryptographic key, or it doesn’t – in which case it will eventually be cracked no matter how many iterations you apply to it.

...but I'm not seeing anything to back that up. Using the article's own example of a 72-bit password entropy that would imply that an attacker is willing to spend up to 4722366482869645213696 times as much brute forcing the password as you are to unlock it normally.

That seems like a fairly remarkable claim to make with little to back it up.

For a sense of scale, even if you're password stretching to just 0.01s, that's 1,496,458,366,089.87 years. You can parallelize that, but let's say you used just 64MB in argon2, and memory costs just 1$/GB - if you're willing to spend 30 billion on ram and get energy and everything else for free, then you can reduce that time to just 50 years; a human working life. And of course, those settings are very light; a spending 10 times time+memory more would barely affect the user, yet cost the attacker 100 times more to hit that 50 year deadline.

Put another way, if the attacker spent the entire US annual GDP buying brute force crackers at 1GB/$ and then a year cracking, that could merely reliably brute-force a 1GB Argon2 stretched password up to 156ms.

I'm sure better hardware would help a bit here, and using PBKDF2 rather than Argon2 surely is weaker (I'd be curious how much, though) but this really isn't a a trivial problem, and the claim from the article looks at the very least unsupported.

If you’re the sort of person that already uses 72-bit passwords and you want to make sure something is secure over the long-term, then the best thing you can do is add more bits of entropy to that password. Adding extra characters increases the cost to an attacker much more effectively than PBKDF2 or Argon2 do.

The point of PBKDF2 and Argon2 is to add some extra protection for the relatively weak passwords that users typically pick, which are closer to 40 bits or less of entropy. For online authentication these KDFs are fine. But for long-term (decades) protection of encryption keys, it’s nowhere near enough.

Using your own example, a 40-bit password stretched to 0.01s would take about 348 years if purely sequential. But this is highly parallelisable, so crackable in less than a year in reality (much less on GPUs).

Now, maybe you are willing to bet that the costs of such an attack (memory and CPU/GPU time) will not change too much over your lifetime, and so are willing to accept this. But, as I say at the end of the article, this means you are adopting a non-standard model of security as far as cryptography is concerned and should be clear about that. (Cryptography defines security in terms of Turing machines with unlimited memory).

One issue with Argon2 (not a security issue, but a practicality one) is that it assumes you have a certain amount of RAM, eg. 1-4GB. That is surely true on, say, a modern desktop PC, but it's not true in some places.

We are deploying a lot of small VMs with container-like workloads. This enhances security for those workloads by using CPU virt capabilities to isolate them. (It's also required for Confidential Containers because of how the hardware works.) But at the same time because these are container-like, we only give them a few dozen or hundred MB of RAM. No one wants to be giving containers gigabytes of RAM each. This prevents accessing LUKSv2 filesystems using Argon2 from these containers.

So several useful security mitigations conflict in unfortunate ways.

All that Argon2 does over PBKDF2, or indeed even older alternatives, is move a narrow range of "Not good" passwords into the "Maybe adequate" category.

Very good passwords (e.g. generated randomly by typical modern password managers) are unaffected, you can't guess or brute force them, so Argon2 isn't making a difference.

Very bad passwords (e.g. your username, 12345678, password) are also unaffected, despite Argon2 the bad guys can just guess the password.

What's really "obsolete" is the password itself. Memorable† Shared secret authentication has been a bad idea for decades. At the point where people were really excited about Rainbow tables because Microsoft are incompetent, we should have been gently insisting people stop using passwords, but we got sucked into telling them about better password hashing instead and now here I am talking about Argon2 again, not to a weird niche audience who genuinely have to use shared secrets, but to people who thought that looked simpler. Ugh.

† As originally posted I didn't write Memorable here. Shared secrets aren't great anyway, but there are a lot of practical applications if we don't need to memorise them. The faster re-connection to a modern web server when you visit HN again later today relies on a shared secret to make it work but it's not a memorable secret, it's just arbitrary data stored in a computer. Passwords are intended to be "memorable" so that a human can remember what they are.

I'd say passwords are nice as a second factor. They're terrible as a first factor, but as an optional addon memorized secrets do improve security.

The obvious problem is that we treat "something you have" items like Yubikeys, phones (webauthn), TOTP tokens, and fingers (biometrics) as second factors instead of as the primary factor.

WebAuthn, and FIDO underlying it are both happy to provide both factors. A good smartphone is itself "something you have" and is capable of verifying either "something you are" via local biometrics or "something you know" in the form of a password.

Passwords are the only "warrant-proof" encryption method we have. A government can force you to provide either "something you have" (e.g. yubikey) or "something you are" (biometrics). For those in repressive regimes that's extremely important.

It is worth noting that passwords + HSM are a very strong approach. Of course HSMs aren't infallible either.

Argon2 requires a ton of RAM, that servers could use for more interesting things.

bscrypt looks like a better alternative nowadays: https://github.com/Sc00bz/bscrypt

It’s not obsolete, the post is saying it is not magic. You need some number of bits to be secure in the next decade. PBKDF2(100k) gives you 16bits for free. For 80 bits the minimum password should have 64 bits, which is 5 Diceware words. Since most people have terrible passwords the extra 16 bits is not enough to reach an acceptable # of bits.

If you take it from the attacker perspective they won't generate all possible passwords to crack a password hash.

They'll run through a dictionary of passwords in order of popularity trying each one.

Services that rely on passwords to wrap private keys should check those passwords against known password breaches. i.e. https://haveibeenpwned.com/ with half a billion passwords.

Then using a suitable hashing algorithm i.e. argon2id and a salt you get a high level of usability for the user and secured data.

It depends on what their goal is. If there is a database leak and they want to bulk-scam then yes, they probably will only try common passwords. But if it is a targeted attack they may be willing to spend white the resources brute-forcing the password of a high-value target.

The article has a good explanation to quantify the security that password hashing / PBKDF2 gives, but I disagree with the conclusion. 18 bits can make the difference between a password being trivial to crack, and practically impossible to crack with current technology.

128 bits is not some magic number that needs to be achieved to have strong security.

Would you be happy if a service you used encrypted your private data with 56-bit DES encryption? Because that is basically what you are saying. If a password is estimated to have 40 bits of entropy on average (as per Wikipedia), then adding 18 bits of protection takes it to 58 bits. Two decades ago we were able to crack DES keys in less than 24 hours: https://en.wikipedia.org/wiki/DES_Challenges

It still helps if you're not actually using passwords.

I use a Mooltipass (https://www.themooltipass.com/) loaded with keys generated with pwgen -s 16 (fully random, alphanumeric, 16 chars)

That seems to give about 95 bits per password, plus 18 brings it up to 113, which I think is not bad at all.

I'm pretty sure I can count on my passwords not ever being cracked by brute force. Anybody stealing a password database will have time and effort constraints, and will likely be happy with just cracking the easier set.

If a government wants my stuff it's much easier to just convince the service provider to give them the data directly.

If you’re not actually remembering these passwords and you want to increase security from 95 to 113 bits, then it is much more efficient to simply add a few more characters to the password. pwgen -s 19 provides the same extra protection as 300,000+ iterations of PBKDF2.

From the article:

> Either your password has sufficient entropy to resist brute-forcing, in which case it is already probably a cryptographic key, or it doesn’t – in which case it will eventually be cracked no matter how many iterations you apply to it.

What a weird thing to say. The vast majority of passwords, probably even the majority of "password1234" passwords, won't be cracked. Whatever they are guarding are just not worth even the minor effort of checking "password1234".

The corollary is most of the time you don't need 128 bit security. You just need enough security to make it not worth the effort. PBKDF2 does raise the bar on that effort by a few bits. That is is worthwhile, which seems to be the reverse of what he is saying.

In the end 128 bits is not much more than a short cut. If you have less that 128 bits, you have to weigh up the value of the data you are protecting versus the effort of getting more entropy. But at 128 bits you can stop weighing up and just assume there will be a weaker link in the chain.

I recently switched to 1password instead of bitwarden precisely because 1password combines a long secret key along with your password to decrypt the vault. If im understanding the article correctly, it seems like that approach avoids the main pitfalls of using PBKDF2.

Attackers who can obtain the password database to crack it offline can also obtain the long secret, can't they?

Assuming there's an association that links my encrypted vault to my identity, they would have to break into my home and either find a printout of the secret key or much more likely simply steal phone and computer.

I'm pretty sure 1password uses PBKDF2 to get to the decryption key of the vault.

Aa I understand it, 1Password uses your master password alongside a "secret key":

https://support.1password.com/secret-key-security/

> Your 1Password account password protects your data on your devices. Someone who has access to your devices or backups won’t be able to unlock 1Password without your account password, which only you know.

> Your Secret Key protects your data off your devices. Someone who attempts a brute-force attack on our servers won’t be able to decrypt your data without your Secret Key, which we never have.

If I understand this article correctly (and there is a reasonable chance I don't) the PBKDF2 iterations they do on top are little more than security theater.

The main pitfall of PBKDF2 has nothing to do with that.

The main pitfall of PBKDF2 or similar key derivation functions is that the only way to increase the work for the attacker is to increase the number of iterations, but that is limited by how many seconds the user is willing to wait for the decryption.

The user may be willing to wait less than 10 seconds until PBKDF2 is executed on a slow laptop, while the attacker may be willing to wait 10 days, while using a multi-FPGA or multi-GPU system that might run PBKDF2 ten thousand times or even one million times faster. The attacker might try 10^9 ... 10^12 passwords (30 ... 40 bits), so a weak password will probably be found.

Any decent password-based encryption method uses the password only to encrypt a secret full-strength key or to make a one-way derivation of the secret key from a random value. These two ways are equivalent.

If the encrypted secret key or the random value from which the secret key is generated is not stored or sent together with the encrypted text and the attacker does not have it, then the attacker must break AES or whatever cipher is used and the key derivation function does not matter.

When the attacker also has the encrypted secret key or the random value from which the secret key is generated, then they will try the easier way of breaking the key derivation function, instead of breaking the main cipher.

If a password manager mixes an additional internal secret value in the key derivation, there are two cases, either that secret value can be saved externally for backup or it cannot be saved.

If you have an external copy, then there is a way for the attacker to get it, so it provides no additional security. Any measure usable to protect the additional secret value could be also used to protect the password-encrypted secret key without an additional secret value, with the same effect.

If there is no external copy, a bricked password manager leads to the catastrophic loss of all encrypted data. The risk of suffering such a data loss is far more serious than the risk of being attacked by a strong adversary.

It's not really a pitfall as much as it not being magic. It does the job it was designed to do. It can't magically make "password" a good password.

I think the greatest strength here is large password databases -- if somebody nabs a million logins to Paypal or similar, then such measures slow down the speed at which accounts can be broken into, give time for the service provider to notice and react, makes it very unlikely for people with good passwords to be compromised, and probably completely protects nuts like myself that use fully random 16 character passwords.

Yeah, some accounts will still be broken into, but it'll take more work and reduce the damage.

Right. I believe Apple also do something similar with their built-in password manager: the password/PIN alone is not enough to decrypt, you also need access to a per-device secret key.

FWIW, I am the article author and I use 1Password myself, partly for this reason, and also because their online security blurb actually contains technical details (https://support.1password.com/1password-security/). Like the fact that they are using AES-GCM-256 rather than just "AES-256".

This was my understanding too, but I believe the wording in their (Apple's) whitepaper is unclear now. See this comment chain on HN: https://news.ycombinator.com/item?id=33900004 , with the relevant bit being If two-factor authentication is enabled for the user’s account, the device passcode is used to recover an escrowed keychain. (https://support.apple.com/guide/security/secure-icloud-keych...). I think there must be some misunderstanding here because I can't believe a PIN would be stored by itself, hashed or not, off-device.

Interesting that 1Password switched to GCM. They were previously using CBC with E-t-M HMAC-SHA256.

Other than more convenient UX, with Bitwarden or any other password manager you can just generate an equivalently entropic "secret key" that you store in a file and that you manually concatenate with the password when unlocking your vault. The threat model that 1Password describes for its secret key is essentially the same as what you'd get handrolling it: https://1passwordstatic.com/files/security/1password-white-p... (it should be assumed that an attacker who gains read access to the user’s disk will acquire the Secret Key)

KeepassXC and derivatives also support Yubikey's proprietary hmac-challenge, wich generates the functional equivalent of the secret key off-OS, and FIDO2 devices with the hmac-secret extension provide that same functionally but with SHA256 instead of SHA1 for the HMAC. I don't know any mainstream password managers that support it yet.

Informative article! Regarding password length - it's been said many times that the easiest way to improve password security is to require longer passwords. 12 characters minimum, preferably 20. However, in practice, I've found out it's difficult to push through management/product people. It's completely fine to burden users with 10 different rules about upper/lower case, special symbols, etc., however requiring long passwords is out of the question. Would it not be much simpler to have one rule (for example, "Minimum length is 20 characters")?

> Regarding password length - it's been said many times that the easiest way to improve password security is to require longer passwords.

Often wrong. Longer passwords help with unlimited brute force attacks, but you can also do things like rate limit remote access (eg captchas after login failures) and use a more resource intensive key protection scheme like high iteration pbkdf2 or argon2

I agree with other commenters here. For a long time offline secret that needs to derive an encryption key, the solution is a longer passphrase. Diceware is fairly able to make passwords that are pretty strong. A 6 word Diceware with no additional complexity like separators or capitalisation is already 77 bits of entropy. 10 words is approx 128 bits.

The most familiar use of PBKDF2 for me is server-side hashing of client-supplied secrets wherein the hashed results are kept server-side and never revealed publicly. In this context of use, PBKDF2 is explicitly intended to slow down the server, not the [attacker/user]'s machine. Combine with heavy amounts of salt, and an attacker shouldn't be able to do much harm - even if the hashes are compromised.

Are we saying PBKDF2 is used in other contexts and is less secure when used in these ways? Am I missing something?

It looks strange to use "computational time" in order to slow down the server.

In such scenario you are describing I believe an explicit delay like "thread_or_task.sleep()" would be even better?

I believe that the "computational time" should be increased exactly for the "client-side" brute force. For example, if the attacker already have the password hash, the salt etc.

The purpose is to limit the damage in case the database is leaked.

I think I am seeing the light now.

Assume the database is compromised. Does it really matter how many iterations if you are up against a nation state attacker? I agree with the article on this one.

Assume the database cannot be compromised (i.e. my original case of simply defending the login form from brute force). Using any form of computationally-intensive hashing is a total waste of energy. I agree - Task.Delay(xxx), not arbitrary PBKDF2 iterations. Taking to the absolute extreme - does hashing even matter if you can hypothetically guarantee no inappropriate access?

Taking the extremes for what they are, I might be inclined to look at storing passwords as simple salted SHA256 or worse. All of this password hardening crap is starting to sound like a half-hearted attempt to protect users from themselves and provides little value to site operators. Being able to tell the public "well at least we used a billion iterations of argon2" doesn't make the root cause of that whole situation sound much better.

It needs to be slow for attackers if the hash gets stolen like was the case with the LastPass breach.

I have a genuine question.

Why every online password manager (lilke lastpass, 1 pass etc) uses PBKDF2 instead of Argon2id, scrypt, bcrypt, Lyra2?

I would guess: age, code availability, inertia, and lack of benefit.

PBKDF2 is old, and had time to get adopted. Code is widely available for it, even included in many frameworks. Once you implemented something like this, unless it's really broken it's a lot of hassle to change it.

I fairly recently looked into implementing password hashing, and my requirement was that somebody already did the job for me, because I'm not a pro cryptographer and don't trust myself to do it right. So since Qt supports PBKDF2, PBKDF2 it is.

And Argon specifically is RAM hungry, which limits applications on things like low end virtual machines and mobile devices.

Lastpass and 1 pass launched before any of those existed except bcrypt. And I am guessing PBKDF2 was selected over bcrypt because its PBKDF2 just had more academic review.

One thought is that it is explicitly mentioned in NIST recommendations.

If you were attempting formal compliance, that would be how to do it.

Instead of requiring 12+ char passwords with special symbols and driving people mad, require a long passphrase.

Everyone knows a verse from a song or a passage from a book and most people now have decent typing speed when it comes to text without $#^& and mixed case. So it's as fast to enter, much easier to recall and has a higher entropy even for phrases that aren't excessively long.

The ballpark estimate of the entropy of English test is between 1.0 and 1.9 bits per character, e.g. see [0]. This means that even a short passphrase like this:

  And I thought passwords were the best option.

would have between 40 and 80 bits of entropy.

[0] https://www.sciencedirect.com/science/article/pii/0960077994...

Except that then you have a list of common phrases that you can check.

How many passpharses would be: "in god we trust" or "I love you". Figure out song titles and book titles, and you have a great list to check.

Clearly the minimum length restrition should still be there and be reasonably high, so none of these would qualify.

Your "see also" is about "multiword passwords", which is not the same.

You can not just look at a secret post-facto to reliabibly evaluate its strength, you have to include the process that was used to create the secret. And humans are notoriously bad at being RNGs, so anything chosen by a person is intrinsically weak as a secret.

My phones auto-complete shows how predictable English is. Lets start by guessing "And".

I see predictions: lastly also I

Let's pick "I".

Next I see: will believe am

If type "t" I get: think thought.

Let's pick "thought"

Next I see: I you it

I'll help it out and enter passwords.

Next I see: was would were

Let's pick "were". Etc.

A passphrase containing the word "password(s)" seems like an easy thing to guess especially given how popular "password" is as a password. Use of "thought" vs. "believe(d)" may just be my preference (curious if others see "thought" as a prediction).

I suspect if you had a sample of my writing, you could learn my word preferences and prioritize words I regularly use. I'm seeing half the words in auto-complete's first three guesses. Most of the rest are synonyms of a top three guess. Only the word "passwords" broke that pattern. I wouldn't recommend such a predictable passphrase like that.

How many words is that passphrase actually choosing from? Maybe 200? Three of them are "and", "the" and "I" which would probably be among the top 10 words used in a pass phrase.

In practice, pass phrases probably work well right now because they aren't used much, but if they were more commonly used and thus specifically attacked against, you would need passphrase strength rules.

A rule I use is to include a word that is not in a standard dictionary.

Just to mention, 200 choose 8 is roughly 10e14. If you could assuming 3 of the words are "and", "the" and "I", you limit the other word selection to 200 choose 5 ~= 10e10. Add an extra order of 4-5 for word order, and it's not like this is a small solution space.

But a randomly generated 9 character password is still stronger. There is a big over-confidence in pass phrases. As pointed out by other comments there is a predictible ordering to words in a passphrase. If you slip up like the parent commenter you end up with something that is actually weak. Pass phrases need rules (like requiring a non-dicitionary word).

> Everyone knows a verse from a song or a passage from a book

These do definitely don't have the 1.0 to 1.9 bits of entropy the paper you posted is talking about.

If what you're suggesting were to be "best practice" attackers would try, say, the 1 million most famous songs and the 1 million most famous books and take every sentence/verse from, say, the starting word of every sentence/verse up to 3 to 8 words.

This would be, what, very ballpark, a 34 to 36 bits keyspace?

Known text doesn't make for a good passphrase source.

Reply on news.ycombinator.com