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

[Nico Williams]

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.

If you have verifiers that are not subject to offline dictionary attack
upon theft, then you don't need 2^80 work factor.  Then all you need is
that the attempt rate allowed be low enough that the attacker cannot
guess the password by trying interactively.

With verifiers not subject to offline dictionary attack and a
sufficiently low trial rate the acceptable password complexity can be
quite low.

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.

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

  http://www.technologyreview.com/news/429498/to-keep-passwords-safe-from-hackers-just-break-them-into-bits/
  https://www.skirsch.com/oneid/TwitterBreach.htm
  https://blog.habets.se/2011/07/Yubico-is-awesome.html
  https://github.com/ThomasHabets/yhsmpam

Apple and Google and others probably had such solutions long before then
too.  The idea is really much too obvious -- so much so that in
retrospect paying for that patent search was a waste of time and money.

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.

But, OK you say, TPMs are slow!  True enough of discrete TPMs (chips).

One could use a high-performance network HSM in much the same way.

Heck, one could build a network HSM out of a software implementation of
TPM 2.0 and general purpose HSM-like hardware and so still use TPM 2.0.
The protocol spoken by TPM 2.0 includes a light-weight TLS-like protocol
that allows for encryption of secrets and integrity protection of
plaintext and ciphertext in the protocol, so it's suitable for use over
a network.

The idea of using TPM 2.0 for this is appealing because dTPMs and fTPMs
are fairly ubiquitous today, and TPM 2.0 can be used over a network, so
we could have high-speed networked TPMs.

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).  Imposing trial rate limits at an HSM/TPM is
hard to do if you want them to be stateless.  TPM 2.0 has a way to lock
itself out when the failed attempt counter exceeds a threshold, but this
is TPM-wide not key-/user-specific so it's not really appropriate for
use as a trial rate limit.

> 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 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.  I
imagine it will be like a phantom limb, and maybe even painful.

Recovery codes, security questions, etc, are all password-like.  And
plain old passwords remain.

2FA/MFA help, for sure, though they also add more failure mores and are
hard for some users to use.  Punting to third party systems (e.g.,
login-by-email) is just that: punting, and makes security somewhat worse
for users overall.

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.

Nico
--