[Cryptography] Secure password verifiers (Re: Passwords (Smallest feasible work factor today?))

[Jeffrey Goldberg]

On Jan 31, 2023, at 16:57, Nico Williams <nico at cryptonector.com> wrote:
> 
> On Wed, Sep 07, 2022 at 11:20:34AM -0400, Phillip Hallam-Baker wrote:
>> Folk, what are people's thoughts on the smallest work factor that can be
>> considered acceptable today? I am thinking 2^80.
> 
> Sounds about right, but that is only assuming traditional password
> verifier files/databases.

I disagree. (Though as you will find further below, I do fully agree with your recommendations)

I believe that guessing and testing passwords in bulk is about 2^20 times slower than guessing and testing  keys. If testing a password is a single hashing operation, then the bottleneck is in the guess generation. If the verification involves any kind of slow hashing then we hit other sorts of constraints.

A few years back, we (1Password) ran a completion to get an idea of how much it costs to crack against PBKDF2-H256 with 100,000 rounds. The very rough estimate is that for those doing this with setups that achieve substantial economies of scale is that it costs about 6 USD to make 2^32 guesses. See

  https://blog.1password.com/cracking-challenge-update/


> Back in 2012 I "came up with" a scheme for secure password verifiers
> that I thought was worthy enough of a patent search that I bothered to
> pay for one, but sure enough the search came up with some prior art, so
> I let it be.  Yet here we are in 2023 and many sites still use plain old
> password verifiers...
> 
> The gist is that you split password validation between the server that
> wants to do it and a trusted device (possibly remote, possibly a local
> TPM).  And you trust that device is secure because it's got a very small
> attack surface and is stateless.

Yup. Typically the scheme is to have your HSM or TPM perform an HMAC with a high entropy key that never leaves the module.

> This isn't hard.  It exists, even.  Here's the prior art my lawyer's
> search turned up ten years ago:


> Apple and Google and others probably had such solutions long before then
> too. 

I believe that many banks do this. They fear password reuse much more than the fear weak passwords which is one of the reasons why they often specify password composition requirements that are deliberately incompatible with what other services do. They are only worried about online accounts. 
> 
> There are several ways to do password validation with TPMs such that
> what one stores in a database are wrapped verifiers that only the TPM
> can unwrap and use.  One can use keys that are duplicated to all the
> TPMs on all the relevant servers.

> Server compromise would still be a problem, since passwords used while
> it's compromised would also be compromised, and because trial rate
> limits could be exceeded if they were imposed by the server (which we
> can expect they would be).

Augmented PAKEs are a nice approach. No secrets are transmitted to the server. But it requires that clients support them. 

>> My thesis here is that if we are going to get rid of passwords, we need a
>> combination of THREE technologies. The FIDO/Passkey folk are doing
>> themselves no favors trying to kill what they appear to imagine to be
>> rivals.
> 
> We'll never really be fully rid of passwords.  Not unless Neuralink
> delivers and becomes commonplace, and even then!

I have seen “password killers” come and go for 30 years now. FIDO2/Passkeys are the only thing I’ve been optimistic about for a long time. I agree that it won’t kill passwords, but it stands a real chance in making a real dent.

> I shudder at the thought of losing all access to all things just because
> my neuralink device dies or something.  I also wonder what it will feel
> like when the battery on a neuralink device runs down all the way.

This, of course is a real problem with FIDO, but FIDO2 doesn’t require the long term secrets be stored in some hardware enclave. So it is possible for something like a password manager to act as a passkey device. 

> We really need to make sure that traditional password verifiers
> everywhere are replaced with ones based on HSM/TPM/similar.  Then we
> can still haz passwords, even fairly weak ones.

I do agree. As you correctly said, the technology and proposals to prevent off-line attacks isn’t new. But this needs to be really plug and play and cheap for people deploying services. One reason that traditional passwords and traditional password verification remains so prevalent  is because there is a great deal of very easy to deploy mechanisms to set up services with those systems.

Cheers,

-j