Mitigate timing attack threat against password recovery page

Question

We recently had an external security review performed on a public-facing website we manage. They noted that on the "recover password page", there are different response times when providing existing and non-existing usernames. They claim this could make it easier for an attacker to test for existing usernames. The suggested change to eliminate this attack vector, is to always execute the same logic for every password recovery attempt.

In our case, the password recovery logic consists of (roughly) the following steps:

1. Load the user from database.
2. Send an email to the user with a password reset link.

If the user exists, both steps are carried out. If the user doesn't exist, only step 1 is executed.

In terms of database lookups etc, this is easily solved. But when it comes to interacting with external systems, in this case sending an email, it's less trivial.

I supposed introducing a random delay will not help much, as there would likely still be a detectable difference in the response time distributions.

Another idea is to set up an email account somewhere, and send an email there for every non-existing username.

What would be best practice in this situation?

Answer 1

Let's ask the real question here :

Is the list of usernames associated with your application secret?

Kind of but mostly NO. Usually, each username is unique in an application so it's very hard if not impossible to keep it a secret. For example, a way that will very often work (if not always) to find username associated with your application is to simply create a new account. When you enter a username, the creation process will tell you if it's already taken or not. Hence, you can slowly build a list of valid username.

Overall, it doesn't make much sense to try to keep the username secret and is probably impossible, so just give up on that part.

Interesting read about how Your Username is Not a Secret.

What should try to protect?

You need to protect the secrets associated with the username ; password and any other form of authentication. It's here that it makes sense to bother about timing attack. For example, your password verification code need to take the same time if the first 2 characters match than if no character match at all.

Additionnal note

Protecting your multi-factor authentication is another interesting topic. It's not directly a timing attack but it's the same principle. For example, if you have a password and a phone code required to login into an app. If the application, only ask you about the phone code when the password is correct, it makes it much easier for the attacker to find the password than if the application was asking the password AND phone code every time. But there is some issue about the privacy of the phone number if you ask it every time...

Answer 2

You could choose to perform the actions asynchronously, giving the appearance of having linear time. In terms of pseudo-code, you could always do something like this:

Sleep 1000 ; Sleep for a second
Output template ; Show a confirmation page
Close Socket ; Make the browser/client believe we're done
Lookup User From Database ; Try to load the user
If User Found
    Send Email ; Send an Email
End If

I know of at least one service that does this; the user will always see a confirmation message ("Great. Now check your email.") without actually confirming if the user exists and/or an email was sent. This eliminates all variable timings under your control, including database search times and whatever time it takes for the email to be sent.

Not all languages support this type of model directly, but you may be able to use fork() to spawn a process (or whatever method your language provides) to perform the code asynchronously.

This leaves timing issues only to the OS's task scheduler and not based on actual logic performed. Introducing an artificial delay will also mitigate some types of programs that aren't multithreaded, as they'll have to wait a second for each attempt (not a good defense, but many "hacking" tools aren't massively multithreaded anyways).

Even without the delay, however, they'd still be unable to confirm if the user account was actually valid or not, so the attack would be mitigated. The only thing you need to do is stabilize the amount of time it takes to receive a response; a successful lookup and a failed lookup should take the exact same amount of time.

Answer 3

I've seen this done in a couple of ways, one you've already mentioned using random time additions (I'm not a fan of this), two by making the task asynchronous as phyrfox has said (this works well if you can do it), but most recently three; by having an enforced minimum duration for page response. I'm not sure exactly what I think about this vs method number two, but I'll detail it below anyway:

The basic logic in your situation might look like:

1. store system timestamp
2. load user from database
3. Send an email to the user with a password reset link
4. check time difference between now and the timestamp from step 1. If the difference x is less than minimum duration
5. delay response completion by x minus elpased time so far.

This has a couple of good points and a couple of bad points..

good:

• Some other lower level mechanisms focus on getting each atomic step to take the same amount of time, in your scenario you need to ensure that the total time of all steps take is the same, this is a catch all way to do this.
• it's a quick and easy code implementation.

bad:

• if someone can cause a delay in one component, it can extend the time taken beyond a hard coded minium ammount. For example if on average the round trip took 1 second, you might enforce a minimum duration of 1.5 seconds. If the database server response time is increased due to benign or malicious activity, it might push the average response time up to 2 seconds, beyond your minimum duration. You could try to get around this using a dynamic minimum duration, based on the average duration of recent requests for example (but with a set minimum value).
• you're making it easier your system to suffer a DOS by multiple requests to pages with this type of mechanism. The place I saw using this trick recently viewed this risk as the lesser of two evils.

Edit

Since I can't comment on other answers yet I just wanted to note that on systems which don't have open registrations, you want to try and keep the username's secret, and regardless unless your usernames are exposed by design during normal use of your system - defence in depth people! Why make it easier than it needs to be?

Just off the top of my head: if you can enumerate thousands of users quickly, it increases the number of accounts which might have simple passwords to brute force, or perhaps you'd be exposing your users to other attack vectors such as spear phishing or social engineering attacks. The less information the bad guys have about your users the better.

Answer 4

Randomization of any kind will only mitigate the attack, requiring more statistics before a difference in timing can be observed. That is not a good solution, unless it is the best that can be done.

My suggestion, instead, is to have a background process that sends out emails. The actual recovery process would not even check whether the username is valid, it would only send a message to the background process (through whichever IPC method is convenient) saying to send out the email for username so-and-so and immediately return the "done" page.

The background process would handle actually seeing if the username is valid and send the email if so, but its results and timing should not be observable to a remote attacker.

Answer 5

To solve this all you have to do is only allow the program to send the response page at certain wall-clock intervals. This way as long as the actual time required to finish processing is shorter than the time between one interval, it will always respond in a way that is useless for this attack.

So when choosing an interval, be generous.

What I mean is: Password recovery page can only respond say 4 times a minute.

[00:00]

[00:07] Processing Begins

[00:09] (Processing Completes For Invalid Username)

[00:14] (Processing Completes For Valid Username)

[00:15] (waiting...)

[00:30] (Response sent)

[00:45]

[01:00]

...

If the processing finishes between any of those intervals, it waits until the next interval to respond.

Answer 6

I think there is a very simple solution to this problem and I'm a bit surprised it hasn't been mentioned. Putting aside all the questions about whether usernames are secret or not, all you need to do is change the logic.

Instead of verifying the user is valid and then displaying the message to the user, simple respond with the one standard response for all password reset attempts and do this BEFORE making any attempt to verify the account. Just send back a response along the lines "If you have a valid account on this system, a password reset link will be sent to your mail address". If you do this first, you will get (roughtly) the same response time for valid and invalid requests. After sending the response, then verify the data and if it looks legit, send the email.

The only compication will be that you would need to setup this such that the stage which handles the sending of the email link will need to be done in a separate process so that you can respond and end the initial web connection. This can easily be done by just logging the request to a database table and having another process which looks for new records in this table on a regular schedule and processes them accordingly.

Answer 7

Add a random amount of sleep time that overlaps the difference in time between existing/non-existing user names.

i.e. if the current scenario is,

A) Existing User Name response time = 50ms

B) Non-existing user name response time = 120ms

Add 70-100ms of random sleep time to A (120-150ms)

Add 0-30ms of random sleep time to B (120-150ms).