2

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.

  • 2
    I think you are mixing online vs offline attacks. – Johannes Kuhn Aug 2 '17 at 21:45
  • 2
    Out of interest, what gets transmitted on login, and what gets stored in the cookie? – struthersneil Aug 2 '17 at 21:51
  • 1
    I believe this conference presentation is relevant to your question: youtube.com/watch?v=lbKvQTzg6ZE Unfortunately the audio is absent from the first half of the video, and I don't think the slides were ever posted elsewhere. – PwdRsch Aug 2 '17 at 23:00
  • 2
    @PwdRsch Actually, the presentation and sample code are here: github.com/jaegerindustries/passwords14 – Mike Ounsworth Aug 2 '17 at 23:38
  • 1
    What exactly do you mean by 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. ? The point of a certificate is to link your public key to the domain name. That's it. Certificates make no claim about how well or poorly you run your site. – Mike Ounsworth Aug 3 '17 at 1:28
2

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(2password_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.
  • @AndrolGenhald Uggg I don't want to get into this debate again. Yes there are subtle differences between /dev/random and /dev/urandom, both between each other, and between their implementations in Linux vs BSD vs Solaris. Yes, to write cryptographically secure software you need to know the nuances and know when you have enough entropy to safely use /dev/urandom (ex servers that have been up for a while are fine, headless embedded devices fresh off the assembly line: not so much). – Mike Ounsworth Aug 3 '17 at 14:32
  • Fair enough, I just hesitate when I see it called "usual" since, as far as most people are concerned, urandom should be the default source. – AndrolGenhald Aug 3 '17 at 15:01
  • @AndrolGenhald Ah. See I work in the world of FIPS and Common Criteria crypto for embedded systems where any mention of urandom gets your product automatically rejected unless you have a really convincing argument (usually in the form of empirical data from a modified linux kernel) that your RNG can not possibly drop below 128 bits of seed entropy - even on first-time boot. – Mike Ounsworth Aug 3 '17 at 15:05
  • 1
    @AndrolGenhald And as for the article: I agree 100%. /dev/urandom is completely safe once it has been properly seeded, but if your process or daemon starts on boot then how do you know when it's properly seeded and safe to use? *You don't*. In the past I have used a hybrid approach: boot script reads 128 bits from /dev/random, waits for the block, then launches the daemon on /dev/urandom. This is essentially hacking the Linux RNG to behave the same as FreeBSD RNG. – Mike Ounsworth Aug 3 '17 at 15:19
0

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.

  • Why is storing h bad though? – guest Aug 3 '17 at 1:39
  • @guest h is effectively the password. As such, if it is stolen, the only way to fix the compromised account is by having the user change the password. This is nigh-impossible to do quickly. When a session id is stolen (or even suspected of being stolen) the leak can be fixed by simply invalidating the session id. This can be done automatically by the server with only a minor inconvenience to the legitimate user (i.e. they are logged out). – Conor Mancone Aug 3 '17 at 2:03
  • If the client's system is so compromised that someone could steal their cookies then I believe they have bigger problems. – guest Aug 4 '17 at 9:12
  • @guest And yet such compromises happen on a fairly regular basis. A successful XSS attack will allow an attacker to steal information stored in cookies that unless they are marked as http-only. An successful XSS attack will let an attacker do whatever they want as the compromised user. That is certainly bad. However, an application setup like this also allows the attacker to walk away with the user's password after a successful XSS attack. That is much worse. – Conor Mancone Aug 4 '17 at 13:31
  • 1
    @powersupply My original point was that you never store the hash or password client side. Normally the login API returns a session id or login key which can be stored. If that is stolen the account is still compromised, but you can fix the problem by simply invalidating the key. This locks out the attacker but leaves the original password in place, which is only a minor inconvenience to the account owner (they just log back in). Ideally you have active monitoring on server side to detect any unusual activity related to an auth token and can automatically invalidate as needed. – Conor Mancone Aug 4 '17 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.