Public SRP verifiers or public hash chain “public keys” when secret is low entropy password

Question

I want to set up the following:

• An untrusted server should host user sessions and authenticate users without knowing their passwords or being capable of creating a fake user session in the user's name.

• This is accomplished by making all sessions publicly verifiable by making public the information necessary to prove that the client was able to demonstrate their knowledge of a secret.

• The secret the client holds is of password-level entropy.

Now, a few things come to mind here. For starters, either SRP or hash chain authentication could be used for this purpose, and would actually work pretty well if the secret was of key-level entropy.

Secondly, a password can be pushed towards key-level entropy by using key derivation.

So my question is this: Is it reckless to use a key derivation algorithm to create a secure password to use with an auth scheme like SRP or hash-chaining in which the untrusted server and the general public will know the resulting verifier or "public" key? Or are KDFs only suited for providing some hope that not all passwords are goners for when a trusted server is broken into by an attacker?

I know PBKDF2 is essentially "useless" against anyone with a GPU rig and I have read that bcrypt is "useless" to anyone with an FPGA setup. Scrypt, the final alternative people discuss is "young" and at the end of it, it seems intuitively like it's very hard to pretend low-entropy can ever truly become high-entropy, except by simply making it a bit harder for attackers of today.

So, is there any solution to this set up or is this ultimately a case where a user must have some key-like password? If so, would this be a good use case for assigned passwords that are actually keys translated through word lists? For example, if you enforce a Diceware password scheme of 10 words, you end up with what the author claims is 12.9 * 10 bits of entropy, or 129 bits of entropy which seems pretty good for being forced into remembering 10 words.

Let's also assume the users are somewhat onboard because they are motivated by the product itself but they also shouldn't have to put up with too much. They aren't lay-users being forced into a system more complicated then they are used to but they also shouldn't have a terrible experience with logins.

Answer 1

I know PBKDF2 is essentially "useless" against anyone with a GPU rig and I have read that bcrypt is "useless" to anyone with an FPGA setup.

Neither is useless. Newer alternatives like scrypt and the eventual PHC winner make better use of the defenders' resources, but even a thousand iterations of PBKDF2 is useful, compared to doing nothing.

If you assume that $2^{80}$ hash function invocations is infeasible for the attacker (reasonable, though not particularly conservative), then $2^n$ rounds of PBKDF2 allow your passwords to have only $80-n$ bits of entropy. Since $n=20$ is often reasonable, you would remove a fourth of the required password "length", all things equal.

So, is there any solution to this set up or is this ultimately a case where a user must have some key-like password? If so, would this be a good use case for assigned passwords that are actually keys translated through word lists?

Still, typical user-chosen passwords certainly do not have even that much entropy, so yes, this could be a good case for assigned passwords. Even if the users are unwilling to remember the assigned password, writing it down would not let a typical eavesdropper attack it. Also, users cannot make the passwords they use elsewhere (in situations where offline attacks are prevented) vulnerable by reusing them here.

So, to answer your actual question:

Is it reckless to use a key derivation algorithm to create a secure password to use with an auth scheme like SRP or hash-chaining in which the untrusted server and the general public will know the resulting verifier or "public" key? Or are KDFs only suited for providing some hope that not all passwords are goners for when a trusted server is broken into by an attacker?

No, I do not think it is necessarily reckless, at least with your idea of assigned passwords (which cannot cause a leak of some reused password). However, it would still be preferable to prevent such offline attacks in the absence of a compromise of the server. I.e. use a trusted server for authentication if at all possible.

Answer 2

I will clarify for future readers, I ended up pivoting on my requirements. I realized with help from the posters here that passwords cannot be keys, no matter how much they are stretched, which is what I kind of expected. Therefore, attempting to find a way in which password logins can be publicly verifiable is a fruitless endeavor.

Instead, I switched over to a solution in which sessions and logins don't need to be verifiable by the public, but a true digital signature solution (with real keys) is necessary for certain actions. This fit the bill more with what I needed. Focusing on the session was a red herring, it ended up being more prudent to simply have sessions for convenience and true digital signatures for user actions.