You Shouldn’t Be Using BCrypt and Scrypt

What they're saying is that a 4-digit PIN with a T=1000 work factor provides the same difficulty as a 7-digit PIN with T=1, and less difficulty than an 8-digit PIN with T=1.

But that's just for illustration. An 8-digit PIN is trivial to crack, whether using scrypt or not. So if something like an 8-digit PIN is too complex to expect most people to remember, then the game is over.

PBKDFs can't save you from weak passwords because weak passwords are just too weak, especially when you take cloud computing into consideration--people don't build FPGAs to crack your password, they pay or steal distributed computing power in a way that makes it trivial to overcome any symmetric work factor budget you could possibly tolerate.

Exactly as you admit, if you can expect and depend on passwords to be sufficiently long such that a linear work factor hurdle imposes a substantial, additional burden, they're either already long enough or you can expect them to be even longer; users would unlikely to be entering such passwords from memory.

Similarly, if you can assume they're using unique passwords rather than reusing the same password (which effectively makes your efforts futile), they're likely not remembering them.

The window where PBKDFs could possibly have any real value is extremely narrow, niche, and ephemeral; and pretty much non-existent for applications where it's typically relied upon, particularly on the web. Neither iPhone nor Android rely on PBKDFs for password security, even though they may use them for appearances; they rely on time-based or counter-based lock-out mechanisms and store secrets on unhackable, physically impenetrable ICs.

Other than avoiding passwords, the last unequivocally responsible strategy as an authenticator and keeper of secrets using general purpose software is to salt your password database, which goes much further than PBKDFs in raising the cost of whole-database dictionary attacks and analysis (e.g. identifying reused passwords), hopefully forcing targeted, per account attacks. But once you're in the realm of targeted attacks, linear cost functions aren't buying you anything substantive. What they're costing you, far beyond some misspent CPU cycles, is denial and delay.

No cryptographer nor knowledgable security engineer would suggest linear cost factor increases as mitigations to patch over exploits in TLS, for example. "Oh, CBC can leak headers; just run 10,000 more iterations of AES or throttle your network throughput to minimize injection rates." "You were using 768-bit RSA, which is now considered crackable? Just switch to 1024-bit RSA."[1] Nobody says these things!

Yet for some reason many of the same engineers who readily admit the insufficiency of such mitigations buy into the notion that identical mitigations somehow add meaningful security to password databases? (Few if any of those people would be professional cryptographers, mind you. I know NIST requires them, but NIST also required mandatory password rotations before backtracking. PBKDFs are widely considered harmless, so even if you've changed your mind why stir the pot?)

The only reason I can think for why so many people buy into the delusion is because it's too difficult to fathom moving away from passwords altogether. And perhaps they're right--maybe we can't yet move past simple, memorized passwords. Certainly it wasn't realistic when PBKDFs with cost functions became popular. But just because the only palatable remedy is snake oil doesn't make the snake oil legitimate.

[1] People have said that it's okay to stay with 1024-bit RSA for awhile, but nobody advised moving to 1024-bit from 768-bit, which provides a work factor increase analogous to the aggressive PBKDFs. They said to move to 2048-bit or 3072-bit RSA, which provides work factor increases far beyond the most aggressively parameterized PBKDFs (and possible beyond what they're even capable of using 64-bit input parameters), even though there presently exist technical hurdles, like practical resident data set sizes, between factoring 768-bit RSA and 1024-bit RSA similar to those hurdles touted by PBKDFs like scrypt and argon.