Proof of Work as password hash a good idea?

Question

Our users log in with username/password, and have a cookie that allows them to remain logged in. Our users are expected to run updated versions of JS.

Assuming someone snags our database at some point,

Is it a good idea to reduce the entropy of our stored passwords by having the users perform a reasonable proof of work task on login and submit that as the password, and increase the difficulty over the years?

What this does:

• protect the users from having their weak passwords cracked and associated with their online identities

What this does not:

• provide a session key
• provide DDoS protection
• provide any other server security

clientside registration/login:

h = password
d = "0000f"
do: 
  h = hash (h + username + salt)
while (h > d)

send("login", username, h)

serverside login:

d = "0000f"
listen("login", username, h)
if h > d:
  user = database.get(username)
  if user.pass == h:
    send("accepted", true)
    session.user = user

clientside login part 2:

listen("accepted", accepted)
if accepted:
  set cookie("user", user)
  set cookie("h", h)

The advantage of this is that the user does not have to resubmit their password to update the difficulty.

I have implemented this protocol, but I haven't seen this anywhere else. And the first law of cryptodynamics is "Thou shalt never roll your own".

If this works, I would love to see this incorporated into a certificate to show the user that the server stores the user's secrets responsibly.

Answer 1

I'm not an expert here, just throwing around my thoughts since your idea is neat and I'd like to explore it.

As pointed out by @PwdRsch, the password14 talk [video], [slides and sample code] from 2014 (while not the strongest talk I've ever seen) is on exactly this topic.

---

I have a few issues with your scheme the way it is. First, to prevent replay attacks you should really have the server generate a nonce for each login and send this to the client (since the nonces don't need to be key-strength, and you don't want to present an easy DoS, get them from /dev/urandom rather than the usual /dev/random)

Second, both the attacker and the honest user need to do O(hash_prefix='0000') work, which will be a far bigger penalty to the honest user on their smart phone than it will be to the attacker on their 12 GPU hashing rig. Giving the advantage to the attacker is bad.

Let's fix these by doing something like this:

Client-side:

h = "0"
d = "0000f"
hashed_pw = pbkdf2( password )
do: 
  h = hash (h + username + hashed_pw + nonce)
while (h > d)

send("login", username, h)

Server-side:

listen("login", username, h)
user = database.get(username)
if "0000f" > hash (h + username + user.hashed_pw + nonce)
  send("accepted", true)
  session.user = user

Here the server has to do O(1) work (a single hash iteration), the honest client needs to do O(hash_prefix='0000') work, and the attacker need to do exponential work in the length of the password: O(2^{password_length-1}) * O(hash_prefix='0000').

---

Having hardened your algorithm a bit (but me spending an hour staring at it by no means implies that it's prod-ready), let's look at what it's accomplishing. I assume your threat model is to protect against online brute-force attacks to keep your users' accounts from getting compromised.

Drive-by / low-hanging fruit

In this attack scenario the attacker is looking to find the users dumb enough to be using a password on the most common passwords lists. Here the exponential speedup from forcing the attacker to guess over the password disappears because they are not guessing an exponential number of passwords. So for any user with a weak password, this scheme isn't really doing anything because a few extra milliseconds of hashing is insignificant to the attacker.

Targeted attacks

Here the attacker is trying to break into a specific account. If they really are guessing passwords at random, then this will slow them down, but given that network lag and fail2ban already make a social engineering / phishing attack better value than an online brute-force, I'm not sure you're adding value here either. Enable 2FA with the Google Authenticator if you're worried about this.

---

Bottom line: The idea is neat and I've enjoyed thinking about this, but

1. I'm not sure it's adding much value.
2. "Don't roll your own". I found a few holes in the scheme, so you'd need to spend a lot of time and effort hardening it before I'd be confident to use it in production.

Answer 2

I think that different parts of your plan vary in usefulness from "that's a different way to do it but won't hurt anything" to "that's a severe security vulnerability". In detail:

Possibly out of the norm

I don't normally hash the password client-side. That being said, I think there are other applications out there that do hash client-side for performance reasons, so this isn't crazy. However, I think in this case you have made some choices as a result of your client-side hashing that are bad.

Different, but probably fine

Having an increasing work function is perfectly normal and even good. The idea is that as time changes you increase the work value across your system to make it harder to crack passwords. As you obviously understand, the more "iterations" you have to go through to build the hash, the harder it is to crack a password, since any crack attempts have to match your number of iterations. In terms of actually doing that, there are some important considerations here:

1) (actually, a nitpick). Repeated hashing doesn't actually change your entropy at all. High entropy = more secure, so if your algorithm is decreasing entropy (as you said in your answer), that would be a bad thing. Either way, your increasing work function doesn't actually increase or decrease entropy.

2) The trouble with your plan, because you do things client side, is that you can't adjust the work function over time to account for advances in computing power. With server-side it is very easy to update your work function over time. If you want to make cracking more expensive, you just re-calculate the hash of the password with a higher work function the next time the user logs in. Then, you can store both the password and the work function in the database. Because your server never sees the password, you can't update the hash without additional back-and-forth between the client and server.

Potentially large security hole

This is a gigantic problem, I think:

set cookie("h", h)

The issue is that you are sending the hash back to the client in a cookie. The other part of the issue is that the server accepts this same hash directly to login the user. Therefore, you are effectively storing the user's password in a cookie, which is about the least secure place ever. Someone who managed to steal that cookie would then be able to login as the user until the user changes their password.

Normally the only thing you store in the cookie is a session id, and on the server side you associate that session id with the logged in user. If the session id is stolen (or even suspected of having been compromised), you can simply invalidate the session id. The attacker then loses all access and the legitimate user just has to log back in.

Never, under any circumstance, store either the password or the hash of the password in a cookie. Both should be completely forgotten (client-side) after a successful login.