The Blog

Preventing Brute Force and Dictionary Attacks can be a tricky thing – especially without taking great lengths or causing valid users painful hoops to jump through.  There are lots of articles out there explaining ways to stop brute force attacks but a lot of these make the same inaccurate assumptions about your attacker.

I will discuss some realistic ways of preventing brute force attacks, taking a valid user’s experience into account, explain why a lot of tutorials out there on brute force prevention are not effective, and a solution to the problem.

Why Do I Need Brute Force Protection?

Actually, hopefully you don’t.  There are great services out there that you can outsource your authentication to like OpenID, Facebook Connect, and Google Auth (OpenID).  The same way you probably outsource your comment spam protection, these services have more resources tasked to prevent unauthorized access to accounts than you can bring to bare.  In addition, some of these services offer a form of two-factor authentication to their users, usually in the form of an SMS message, making the task of brute forcing an account very difficult if not impossible.

If you are unable or unwilling to integrate an external authentication service, and its pretty common to offer them only as an option anyways, then you will need a brute force solution.  A typical username/password authentication system, especially with public user registration, is very susceptible and most guides you read typically only talk about preventing SQL Injection.

Why Are Most Other Tutorials Wrong?

Most sites and forums suggestions suffer from two major design flaws: they punish valid users (CAPTCHAs, account locking) and they expect the attacker to act like a regular user (Session or IP tracking).

Turing tests are a usability problem.  They can generally have a high defeat rate, sometimes in the range of 90%, and can greatly lower your site’s conversion rate.  They punish real users and don’t stop automated attempts significantly enough.

Account locking (X failed login attempts locks your account for an hour) opens the avenue for a DoS attack on your website. Continuous brute force attempts cause accounts to be locked, locking accounts generally produces a different error message, so when an account gets locked the attacker can start to map valid usernames, further making it easier to lock them out.

Another incorrect assumption is that you can use Cookies, Sessions, or IPs to prevent brute force.  Sessions are based on a cookie or a URL parameter, and if you’re attempting to brute force a login, you aren’t going to allow the target to track your attempts by helping them save your state: Session’s can’t be trusted.  IP tracking is not going to help an attack as you can spoof or use proxies to change your IP.  Also, a large number of users behind a particular proxy or NAT’d router could give you a false-positive: IPs can’t be trusted.

So How Are We Going to Do This?  Punish the Machines.

Brute force works by trying all permutations until it stumbles across the correct one.  Generally this would be done by a machine because the key space of a reasonable password policy is too large to do manually.  We can exploit this man vs. machine to make sure our valid users are kept happy while punishing machines.

The faster password attempts can be made, the faster the password will be found, so lets exploit this by introducing 3 pieces of entropy: speed, scope, and complexity.  We can introduce each of these items in a way that does not punish valid users with the assumption: A valid user will not try their password X times without starting to experience unwanted effects. Several permutations is insignificant for a brute force attempt, but likely a lot for a valid user, and we’ll bring the onset of unwanted effects slowly, to help steer the user to the recover password system.

Speed: by increasing the response time of our authentication request, it takes longer for each attempt, which takes longer to find the correct password.  At a certain number of attempts we can determine that it is likely not a valid user and begin to increase the response time artificially to a point where each attempt takes a maximum amount of time making the entire permutation unreasonable.

Scope: We can greatly increase the size of the problem of a brute force attempt by having the same response, regardless if the username is a valid one or not:  the attacker doesn’t know if its attacking a real account or just wasting time.  Any error messages and response times should be the same.

Complexity: Increasing the complexity of each attempt simply makes it more difficult, causing the failure count to go up, which will increase the time per request.  By introducing a Turing test at a certain time, like after 10 failed attempts, we are likely to avoid the valid user and just punish the machine, changing the form and introducing a third problem to solve.

Putting It All Together

Below is a example pseudo-code-ish implementation using reCAPTCHA as the Turing test.  This should be easily ported to C#, PHP, Java, or Ruby.

protected void Login()
{
    string email = this.textboxEmail.Text.Trim().ToLower();
    string password = this.textboxPassword.Text.Trim();
 
    if (String.IsNullOrEmpty(email) || String.IsNullOrEmpty(password))
    {
        // TODO: Display "form is incomplete" error message.
        return;
    }
 
    User user = UserFactory.ByEmail(email);
    // We have a Database Table or Cache of keys and counts; in this
    // case: email address and failed attempt count. Since we track
    // failures whether the user account exists or not, we store this
    // value separately from the user.
    int failedAttempts = UserFactory.GetFailedLoginCount(email);
 
    // Run our Brute Force Proection, regardless if the user is valid.
    bool captchaRequired = BruteForceProtection(email, failedAttempts);
 
    // Check that the user submitted and passed a captcha. If they
    // didn't redirect them back to the login using a URL parameter
    // to indicate to show the captcha, and increment the counter.
    if ((captchaRequired) && ((!Captcha_Submitted) || (!Captcha_Passed))
    {
        UserFactory.IncrementFailedLoginCount(email);
        // TODO: Display "captcha failed" error message.
        Redirect("/LoginPage/?captcha=1");
    }
 
    // The user doesn't exist or the passwords don't match.
    if ((user == null) || (user.Password != User.EncryptPass(password)))
    {
        UserFactory.IncrementFailedLoginCount(email);
        // TODO: Display "invalid login" error message.
        return;
    }
 
    // Account is authenticated successfully.
 
    // Clear failed attempts count.
    UserFactory.ClearFailedLogins(email);
 
    // Log the user as you normally would:
    Authenticate.Login(user);
 
    Redirect("/Profile/");
}

private bool BruteForceProtection(string email, int failedCount)
{
    // The metrics used are somewhat arbitrary, but seem to work well.
    if (failedCount >= 30)
    {
        // At this point we are pretty positive its a brute force attempt:
 
        // At the 30th failure, we send an email to support about the brute force attempt.
        if (failedCount == 30)
            Email.SendEmail("Brute Force Attempt Detected.",
            String.Format("Attempted brute force of email: {0} from IP: {1}", email, RemoteIP));
        // Sleep between 30 seconds and 1 min per request
        Thread.Sleep(Math.Max(failedCount * 1000, 60000));
        // Enable Captcha
        return true;
    }
    else if (failedCount >= 15)
    {
        // Sleep between ~9 and ~21 seconds
        Thread.Sleep(failedCount * 600);
        // Enable Captcha
        return true;
    }
    else if (failedCount >= 3)
    {
        // Sleep between 1.5 seconds and 7 seconds.
        Thread.Sleep(failedCount * 500);
        // No Captcha
        return false;
    }
 
    return false;
}

As you can see, as the number of failed attempts increase, the time and complexity increase.  At a certain point, we are notified of the brute force, and the entropy increases to the point where each request takes long enough that brute force becomes an unreasonable.  We are also notified, via email in this case, of the offending IPs and at risk usernames, so we have ample time to do something about it.

Problems to Watch For:

• Horizontal Brute Force – We’ve looked at brute force attempts vertically, attacking a username, but an attacker could use a common password and attack the system horizontally, trying different usernames.  You can simply add hashed password to the key table from the above solution, storing a count for each failed password attempt and lock them down that way.
• Password Recovery: Your authentication system might be top notch, but often password recovery functionality is not.  Ensure you don’t give away valid usernames and that your recovery system is well implemented.
• Account Locking: We don’t actually “Lock” accounts, but we do implement a large enough timeout to make it uncomfortable for real users if a DoS attack is attempted – requiring them to wait when logging in.  The email sent above should help mitigate DoS attacks, and its much better than actually locking the account.  You could potentially lower the max second wait time, or decrement the failed login attempts after a specific time frame, so over time it goes back to zero.
• Registration - If an account that doesn’t exist is attempted to be brute forced and that account is later registered by a valid user, the initial login time for our new user could be a long time, so perhaps clear the failed login count on newly registered accounts.