[Cryptography] Passwords (Smallest feasible work factor today?)

Jon Callas jon at callas.org
Thu Sep 8 01:36:24 EDT 2022



> On Sep 7, 2022, at 08:20, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
> 
> Folk, what are people's thoughts on the smallest work factor that can be considered acceptable today? I am thinking 2^80.
> 

I removed the following text, but I basically agree with you on all the following. It's your problem statement I want to discuss.

The main thing I want to discuss is that you haven't given a threat model. You've implied a threat model, but haven't stated one. And without a threat model we can't have an answer. I'm going to be mildly contrarian, with my tongue in my cheek as well.

If you're talking about a password for a web site, you may not need 80 bits. 

On the other hand, most of my passwords on web sites these days are ones that are generated by a password manager. A bunch of those (the older ones) are ~71 bits of entropy (a guess because it's 12 characters of upper-lower-numeral with some dashes in there) or the new ones that have ~107 bits of entropy because it's 18 characters. So yeah, sure -- my present policy of having my password manager generate a random password is in line with what you're saying. However, note that what this really means is "get/use a password manager and let it do it for you."

Back to threat modeling.

Most attackers to a web site are not after *your* account, they're after *some* account. And in all of those, they're not going to brute force the password. They are going to spew some subset of the million most common passwords at random accounts and whichever one pops first is what they want. In this case, you just really need to have your password not be in some dictionary. In this world, something like "p!Assw4d" is pretty darned good (assuming of course that I actually picked a stupid password that's not in the massive list of cracked passwords).

The point there is that you're looking at it from a work-factor aspect, not what the savvy guesser is going to do. They are not going to try aaaaaaaa and then aaaaaaab and so on. The guesser is going to try commonly used passwords and then move on.

Now, if the attacker wants *your* password, they're not going to do a billion (30 bits) of tries. Come on. The round-trip time of each try makes it infeasible. A bit of a hand wave is that a million (20 bits) seconds is about a fortnight. (Actually closer to ten days; work with me.) So that means 25 million in a year, and thus a 30-bit password takes 40 years. If the attacker can do ten per second (100ms total round trip) it's a mere four years, which is still not anything an attacker is going to do.

That's the threat model of a password-only microservice-ish thing, attacked over the net. You don't need 80 bits.

Okay, so let's take the threat model of an attacker who leverages a break of the server, escalates to get the password database and hammers on *your* password. Now we're back to something akin to the sort of cracking you described -- but we still haven't discussed what they're after, and thus we haven't looked at constraints on it. If it's some government, even though they have massive resources, that resource is going to compete with all the other govvies who want to crack someone else's password. That massive compute engine can still only do 365 compute-days per year, whatever the power is of a compute-day.

Some time ago, the US government built a password-cracking cluster out of retired PCs, and I know one case where they would only give a very high profile case a compute-week because there were other people who wanted to use it!

Think back to the old days of batch compute runs. That's what we're talking about here, competition for CPU time on a batch run.

I'm going to assert you don't need 80 bits of security in this world. 

Some reasonably simple additions to the password, like a PBKDF2 spin loop adds a lot to the strength of the password because it is back pressure. And sure, yeah, Argon2 or something else is even better, but that just proves my point here. We're only arguing about *which* spin loop we use.

Okay, now a new threat model. There's TOTP involved.

Well, for many use cases, it's game over. You lost.

For others, not so fast. If we go back to the case where the adversary stole the password database and they got the TOTP secret, too, they're back in business, but every one of the complications I mentioned above is also back in play. There are also a whole lot of other contingencies that could totally disrupt the attack, and a bunch of ways that a sufficiently savvy attacker can mitigate on their end.

Another threat model: the sysadmins are adaptive. One place I worked the IT security people had a background job where they lazily tried to break your password and they used all of the advantages of being sysadmins (they not only have the password database, but they can cheat -- ways to cheat are left as an exercise for the reader). If they broke your password, they just went to the server and flipped the flag on your account that said the next time you logged in, you had to change your password. This is a huge mitigation, because it strips out a lot of the low-hanging fruit, and kneecaps a lot of obvious things the attacker can do. Oversimplifying, we can guarantee that all passwords are not in the million most-used passwords. So now we're back to 30 bits probably being good enough because we know that 30-bit password is not a dumb one, it's got to actually be brute-forced, and in this case, latency is the defender's friend. (Heck, throw some latency in on purpose, like an artificial 300ms delay.)

This is why many attackers just decide to spearphish you.

Okay, new threat model. It's an encrypted file -- like a PGP keychain, or some cryptocurrency wallet, or something like that.

In this case, maybe it's an advantage to the attacker, because there's no round-trip network delay. On the other hand, this is also a case where PBKDF2 or Argon2 or something else can make it kinda infeasible, especially in the cases where the attacker has only a CPU-week on the cracker.

I could go on. Note that I have not talked about FIDO or WebAuthN tokens, 'cause that's also game over for the attacker. (Well, they have to use phishing or something.)

I think that the bottom line is that someone should use a password manager that generates a reasonably strong password and yeah, that's probably in the 80 bit range if not more. Use a password manage, have it generate passwords, and stop worrying.

Still, though, I don't know your threat model. I'm still guessing. I don't know what problem you're trying to solve, unless it's the obvious abstract problem.

	Jon



More information about the cryptography mailing list