Defend against credential stuffing attacks with proof of work

Good password practices and multi-factor authentication are thankfully becoming more and more common amongst mainstream internet users. But it’s still far too easy to guess passwords, and password reuse is still prevalent. As long as this remains the case, and data breaches continue to give them source material, attackers are going to continue to try and crack accounts on popular sites. For example, the username and password that you were using on LinkedIn in 2012 is probably now public knowledge, one of many huge data breaches in recent years. If that is still a combination you’re using on other sites today, you are highly vulnerable.

Site operators wield powerful tools to thwart these kinds of attacks. It’s common to see CAPTCHAs being required when logging in, but as an intervention, CAPTCHA is not user friendly. What if you could implement a security check that requires no user interaction, but still makes automated attacks against your login system extremely hard?

Expensive to solve, cheap to verify

Attackers rely on the ability to try thousands of permutations of usernames and passwords against your login system in a short period of time — often known as “credential stuffing.” Other than CAPTCHA, we could deploy rate limiting as a solution to this. But rate limits require server-side state (a counter), which is expensive to do globally and at scale, especially in a way that is safe under heavy attack.

Instead, let’s create a math problem, and require the browser to solve it in order to attempt login. This needs to be very hard: something that will tie a modern CPU in knots for a few hundred milliseconds, but something that we can verify as correct without any cost at all. Here’s how we can do it with Fastly:

1. User navigates to the login page.

2. From cache at Fastly, we serve a login form and add a signed CSRF nonce (simply a large, random number).

3. The user fills in their username and password and clicks submit.

4. The browser creates a new JavaScript variable called counter and sets it to 1.

5. The username, password, nonce, and the value of counter are combined into a single string, and passed through a hashing function such as SHA-256.

6. If the result is a string that begins with “000”, then the counter and the nonce are added to the form in hidden fields and the form is submitted.

7. If not, then the counter is incremented by 1, and we go back to step 5.
   

It takes a long time to come up with a valid SHA-256 that starts with 000, because the probability of this happening is 1 in 3,375, and each successive attempt is essentially like rolling a giant die with 3,375 sides until you roll a specific number.

Here’s a demo of this concept, showing how long it takes to generate a valid result, and how many attempts were required. Hit the GO button to start the calculation.

See the Pen
Proof of work by Andrew Betts (@triblondon)
on CodePen.

I ran this on a variety of devices, to find the average computation time per hash over 100 valid hashes:

From an end-user perspective, nothing appears to be slow: the pause happens when you click the "sign in" button, and the user tends to expect a pause at that point anyway, and the calculation can be done in a worker to avoid jamming the main thread.

However, for an attacker, we just made their life very hard indeed. For a given amount of server hardware, the number of requests you’re capable of making per second is now vastly reduced.

Verifying the requests at the edge

Of course, the secret to all this is the ability to verify these requests at Fastly, preventing any credential floods that fail to set the correct hash from reaching your origin.  This is extremely easy. Knowing the counter that the browser ended up with, we can perform just one hash calculation, and go directly to the answer for that counter value. If the result starts with 000, we can let it go to origin. If it doesn’t, we return a synthetic 403 error to the browser.

Here we’re using the built in crypto and hashing functions within Fastly to perform a SHA256 in VCL, and then triggering an error if it doesn’t match.

Something for the toolbox

I would never suggest that any one technique will entirely prevent attacks against your login page, and all we can do is find ways to make attacks harder without making genuine logins harder. Proof of work is a useful tool to have in your arsenal, and one that will often provide a better user experience than CAPTCHA.  Try it!