Page 1 of 1

Securing login forms from brute-force attacks using queues. Rate Topic: ***** 1 Votes

#1 Atli  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3719
  • View blog
  • Posts: 5,991
  • Joined: 08-June 10

Posted 10 August 2013 - 07:59 PM

*
POPULAR

Login forms in online systems are often easy targets for brute-force attacks; attacks designed to go through all possible values (or at least all probable values) for a password to "guess" a correct one. Securing your forms from such attacks is important, but it can be tricky to do in an effective manner without adversely affecting the user experience of your normal user.

The method I am suggesting in this article is that of queuing login attempts in an effort to limit how many attempts an attacker can execute per second.

Why Queuing?
There are alternative methods commonly used, also designed to prevent brute-forcing, but many of them have problems that make them less than ideal for this purpose. Before I go into the queuing, first let me explain some of the pitfalls of some of those alternatives.

  • A very frequently seen method is to track the number of login attempts made through a session - or just a cookie - and if too many failed attempts are detected, the client is locked out for some period. The problem with this method is that it relies on the user-agent to maintain a session/cookie. Those can be blocked or deleted very easily, which would bypass the block entirely.

  • A variation on the above method is to log the IP address rather than using a session or cookie. This solves the unreliability of the cookies, but it introduces other problems. Firstly, IP addresses are not necessarily unique. By blocking an IP, you could in fact be blocking large number of unrelated users. Secondly, IP addresses are easily changeable. Advanced hackers may in fact be using large networks of dummy terminals to hack you, giving them access to a large amount of IP addresses. - In general, any security mechanism that relies on IP tracking is unreliable.

  • To overcome both the above, some simply remove the reliance on client identification and instead block the users themselves, so that if too many login attempts are made for the same user, regardless of the source of the attempts, the user is locked out for a time. The obvious problem here is that any prankster could easily keep large amounts of users blocked indefinitely by routinely sending a number of invalid login attempts.

  • Yet another attempt to defy brute-forcing is to slow down the requests themselves, making brute force attacks too slow to be of use. This - in theory - is an good plan, and is in fact the basis of the queuing method I will be demonstrating. However, many implement this rather poorly. We've seen people simply drop a sleep(1); into all login code, making the request take 1 second before it completes. The issue with this approach is that even though you are slowing down the request, you aren't really preventing the hacker from making an obscene amount of attempts. It'll just take one second longer for the results to start piling in. Issuing 50 requests per second won't cause those 50 requests to take 50 seconds, it'll only cause them to take one second + the time it takes each request to execute.


Problems with queuing
So is queueing free of all those problems? No, definitely not. The main problem you may face with a queueing system is DOS attacks. Similar to that of the third method I describe above, a prankster could easily keep the queue full of invalid requests and make normal login requests take intolerably long. An attacker may also try to continually execute several requests per second, which would in no time overload the server with queued login attempts, potentially even crashing it. (Depending on the server config.)

However, there are ways to minimize these risks:

  • By adding a total queue size you could stop the server from becoming overloaded with login attempts. It would simply drop login requests once the queue has reached a certain size.

  • By splitting the queue into per-user queues, at least a prankster would not be able to stall all attempts by keeping the queue full, only those meant for specific users. (Unless the number of targeted users allows them to exceeds the overall queue size.)

  • By only allowing one queue entry per IP address, you would prevent simple attacks from a single source. An attacker would have to use several IP addresses to make any difference. (Not that it would stop anybody determined, but it may be enough to get script kiddies just messing with your queue times to lose interest.) - It's worth noting that, as always, any restrictions based on IP addresses are not exactly reliable, and can cause issues for some users. Organizations, for example, frequently fall under the same network routers or proxies, and all the users within that network will therefore share an external IP. Only one of those users could use the system at a time if an IP restriction like this is put in place. - Consider it very carefully before deciding to add such a restriction.


In the example I will be implementing here, I will demonstrate all three of these measures. Don't take that to mean you should necessarily do so as well!

The Theory
The key to deterring brute-force attacks is to delay each request long enough for the attack to become impractical. If you can only test one password per second, then it'll take forever to test them all. They can still try, but it's a pointless effort. There are just too many possibilities to go through that slowly. However, a normal user will hardly notice if their login attempt is taking a couple of seconds to go through.

So, how do we implement this in PHP? My solution to this is to set up a database where each login attempt is entered and an ID is generated for it. The attempt with the lowest ID will then be allowed to be processed, after which it is removed from the database, and the attempt following it is allowed to proceed. - Ideally I would want there to be a background process that handles the validation; finding the first unprocessed attempt, validating it, updating it's status in the database, and moving on to the next one. Requests for login attempts would add their entries to the database, and then periodically check it to see if their attempt has been processed yet, after which they remove the attempt from the database and return the result to the user.

However, background processes can be troublesome for many PHP hosts, so for the purposes of this article, I'm opting for a solution where each request is responsible for validating their own attempts. They add an entry to the database, then periodically check the database to see if their entry is the first entry listed, then process it, and finally remove it. Simple enough.

Implementation
The first thing we need to do here is set up a database. Because of it's general availability in the world of PHP, I'm going to use MySQL as my database. Note, however, that you may just as well use in-memory systems like Memcache or the APC extension's user cache mechanisms. Those would in fact most likely perform better.

The table I'm going to use will contain four columns:

  • An ID column that we can use to order the attempts, and find out which attempt is next to be processed.

  • A last_checked column, which will be updated by each attempt each time the code checks if the attempt is ready. This last_checked column will be used to filter out dead attempts; attempts added by requests that have since been killed off. If we don't take this precaution, any dead request will stall the entire queue until it's manually removed.

  • An ip_address column, which will store the unsigned integer representation of the client's IP address. This column will have a UNIQUE key restraint on it, to make sure that each IP can only exist once in the queue. (You could just as easily store the IP string, but I have a thing about wasted storage space.)

  • A username column, to store the name of the user that attempt is waiting for. This will be used to split the queue up into per-user queues. This means that even if there are ten attempts queued up for one user, an attempt for another user will not have to wait.


CREATE TABLE `login_attempt_queue` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `last_checked` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    `ip_address` INT UNSIGNED NOT NULL,
    `username` VARCHAR(100) NOT NULL,
    PRIMARY KEY (`id`),
    UNIQUE KEY(`ip_address`)
) ENGINE=MEMORY;


Additionally, since this is a user login system, I will be using this as the table where the password hashes we are validating are stored:
CREATE TABLE `users` (
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `username` VARCHAR(100) NOT NULL,
    `password` CHAR(60) NOT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB;



To manage the entire thing, I've put together a class that can be used to create login attempts, wait for them to be processed, and then handle the validation result.

Note that this code uses the PHP 5.5 password hashing functions. If you do not have PHP 5.5, there are 3rd party libraries that let you easily add this functionality to older versions. (Down to 5.3, with that particular library.)

<?php

/**
 * Provides everything needed to manage and use a login queue.
 * The login queue will store each login attempt in a database table
 * and process the entries one at at time, with a delay between
 * each one. The idea here is to make brute-force attacks on the
 * login system impractically slow.
 *
 * @author Atli Jonsson (http://www.dreamincode.net/forums/user/391059-atli/)
 * @date 2013-08-11
 * @modified 2013-08-22 Split into per-user queuing, added max queue size and
 *                      added the single IP restriction.
 */
class LoginAttempt
{
    /**
     * @var int The number of milliseconds to sleep between login attempts.
     */
    const ATTEMPT_DELAY = 1000;

    /**
     * @var int The number of milliseconds before an unchecked attempt is
     *          considered dead.
     *
     */
    const ATTEMPT_EXPIRATION_TIMEOUT = 5000;

    /**
     * @var int Number of queued attempts allowed per user.
     */
    const MAX_PER_USER = 5;

    /**
     * @var int Number of queued attempts allowed overall.
     */
    const MAX_OVERALL = 30;

    /**
     * The ID assigned to this attempt in the database.
     *
     * @var int
     */
    private $attemptID;

    /**
     * @var string
     */
    private $username;

    /**
     * @var string
     */
    private $password;

    /**
     * After the login has been validated, this attribute will hold the
     * result. Subsequent calls to isValid will return this value, rather
     * that try to validate it again.
     *
     * @var bool
     */
    private $isLoginValid;

    /**
     * An open PDO instance.
     *
     * @var PDO
     */
    private $pdo;

    /**
     * Stores the statement used to check whether the attempt is ready to be processed.
     * As it may be used multiple times per attempt, it makes sense not to initialize
     * it each ready check.
     *
     * @var PDOStatement
     */
    private $readyCheckStatement;

    /**
     * The statement used to update the attempt entry in the database on
     * each isReady call.
     *
     * @var PDOStatement
     */
    private $checkUpdateStatement;

    /**
     * Creates a login attempt and queues it.
     *
     * @param string $username
     * @param string $password
     * @var \PDO $pdo
     * @throws Exception
     */
    public function __construct($username, $password, \PDO $pdo)
    {
        $this->pdo = $pdo;
        if ($this->pdo->getAttribute(PDO::ATTR_ERRMODE) !== PDO::ERRMODE_EXCEPTION) {
            $this->pdo->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
        }

        $this->username = $username;
        $this->password = $password;

        if (!$this->isQueueSizeExceeded()) {
            $this->addToQueue();
        }
        else {
            throw new Exception("Queue size has been exceeded.", 503);
        }
    }

    /**
     * Creates an entry for the attempt in the database, fetching the id
     * of it and storing it in the class. Note that no values need to
     * be entered in the database; the defaults for both columns are fine.
     */
    private function addToQueue()
    {
        $sql = "INSERT INTO login_attempt_queue (ip_address, username)
                VALUES (?, ?)";
        $stmt = $this->pdo->prepare($sql);
        try {
            $stmt->execute(array(
                sprintf('%u', ip2long($_SERVER["REMOTE_ADDR"])),
                $this->username
            ));
            $this->attemptID = (int)$this->pdo->lastInsertId();
        }
        catch (PDOException $e) {
            throw new Exception("IP address is already in queue.", 403);
        }
    }

    /**
     * Checks the queue size. Throws an exception if it has been exceeded. Otherwise it does nothing.
     *
     * @throws Exception
     * @return bool
     */
    private function isQueueSizeExceeded()
    {
        $sql = "SELECT
                    COUNT(*) AS overall,
                    COUNT(IF(username = ?, TRUE, NULL)) AS user
                FROM login_attempt_queue
                WHERE last_checked > NOW() - INTERVAL ? MICROSECOND";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute(array(
            $this->username,
            self::ATTEMPT_EXPIRATION_TIMEOUT * 1000
        ));

        $count = $stmt->fetch(PDO::FETCH_OBJ);
        if (!$count) {
            throw new Exception("Failed to query queue size", 500);
        }

        return ($count->overall >= self::MAX_OVERALL || $count->user >= self::MAX_PER_USER);
    }

    /**
     * Checks if the login attempt is ready to be processed, and updates the
     * last_checked timestamp to keep the attempt alive.
     *
     * @return bool
     */
    private function isReady()
    {
        if (!$this->readyCheckStatement) {
            $sql = "SELECT id FROM login_attempt_queue
                    WHERE
                        last_checked > NOW() - INTERVAL ? MICROSECOND AND
                        username = ?
                    ORDER BY id ASC
                    LIMIT 1";
            $this->readyCheckStatement = $this->pdo->prepare($sql);
        }
        $this->readyCheckStatement->execute(array(
            self::ATTEMPT_EXPIRATION_TIMEOUT * 1000,
            $this->username
        ));
        $result = (int)$this->readyCheckStatement->fetchColumn();

        if (!$this->checkUpdateStatement) {
            $sql = "UPDATE login_attempt_queue
                    SET last_checked = CURRENT_TIMESTAMP
                    WHERE id = ? LIMIT 1";
            $this->checkUpdateStatement = $this->pdo->prepare($sql);
        }
        $this->checkUpdateStatement->execute(array($this->attemptID));

        return $result === $this->attemptID;
    }

    /**
     * Checks if the login attempt is valid. Note that this function will cause
     * the delay between attempts when first called. If called multiple times,
     * only the first call will do so.
     *
     * @return bool
     */
    public function isValid()
    {
        if ($this->isLoginValid === null) {
            $sql = "SELECT password
                    FROM users
                    WHERE username = ?";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute(array($this->username));
            $realHash = $stmt->fetchColumn();

            if ($realHash) {
                $this->isLoginValid = password_verify($this->password, $realHash);
            }
            else {
                $this->isLoginValid = false;
            }

            // Sleep at this point, to enforce a delay between login attempts.
            usleep(self::ATTEMPT_DELAY  * 1000);

            // Remove the login attempt from the queue, as well as any login
            // attempt that has timed out.
            $sql = "DELETE FROM login_attempt_queue
                    WHERE
                        id = ? OR
                        last_checked < NOW() - INTERVAL ? MICROSECOND";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute(array(
                $this->attemptID,
                self::ATTEMPT_EXPIRATION_TIMEOUT * 1000
            ));
        }

        return $this->isLoginValid;
    }

    /**
     * Calls the callback function when the login attempt is ready, passing along the
     * result of the validation as the first parameter.
     *
     * @param callable|string $callback
     * @param int $checkTimer Delay between checks, in milliseconds.
     */
    public function whenReady($callback, $checkTimer=250)
    {
        while (!$this->isReady()) {
            usleep($checkTimer * 1000);
        }

        if (is_callable($callback)) {
            call_user_func($callback, $this->isValid());
        }
    }
}




Usage
To sum up the functionality of the class, we only have two public methods we need to concern ourselves with.

  • __construct creates the attempt, taking the username, the password and a PDO instance. It sets their respective class attributes to those values, and then triggers the addToQueue function, which goes on to create a new database entry for the class and set the attemptID attribute.

  • whenReady is our "listener", so to speak. It takes a callable function as the first parameter, and optionally a delay timer value as the second parameter. It will keep calling the isReady function in a loop, each iteration delayed by the value of that second parameter, until it returns TRUE, thus reporting that the attempt is next in line to be processed. Then it will go on to call the the isValid function, which checks the validity of the attempt and removes it from the database. Finally it calls the callback function, and passes the validity value with it as it's only parameter.


Here is an example of how this could be used on a login form's action page:
<?php
require "LoginAttempt.php";

if (!empty($_POST["username"]) && !empty($_POST["password"])) {
    $dsn = "mysql:host=localhost;dbname=test";
    $pdo = new PDO($dsn, "username", "password");

    try {
        $attempt = new LoginAttempt($_POST["username"], $_POST["password"], $pdo);
        $attempt->whenReady(function($success) {
            echo $success ? "Valid" : "Invalid";
        });
    }
    catch (Exception $e) {
        if ($e->getCode() == 503) {
            header("HTTP/1.1 503 Service Unavailable");
            exit;
        }
        else if ($e->getCode() == 403) {
            header("HTTP/1.1 403 Forbidden");
            exit;
        }
        else {
            echo "Error: " . $e->getMessage();
        }

        // Note here that it may be advisable to show the
        // same response for error messages that you show
        // for invalid requests. That way it'll be less
        // obvious to attackers that their requests are
        // being rejected rather than processed and
        // invalidated.
    }
}
else {
    echo "Error: Missing user input.";
}



For PHP 5.2 or lower, the above method of using a closure for the whenReady function is not possible. Instead you would have to define a function, and then pass the name of it as the first parameter to whenReady:
function onReady($isValid) {
    echo $isValid ? "Valid" : "Invalid";
}

$attempt = new LoginAttempt($_POST["username"], $_POST["password"], $pdo);
$attempt->whenReady("onReady");



Final Thoughts
If using this method, be mindful of two things. First, making sure the ATTEMPT_DELAY value is appropriate. My value of 1000 ms is just a suggestion. Depending on how busy your server is, you may want to adjust this. - Second, make sure the execution time of the login script is also appropriately set. Requests may need to wait in line for some time, so make sure PHP won't cancel the request before it gets a chance to finish. Don't set it too high either; request lingering open forever isn't a good thing. You need to find a balance that works for you.

Edited, 2013-08-22:
- Added the portion discussing the problems with queuing, and implemented the three suggested anti-DOS prevention methods.

Special thanks to CTphpnwb and adn258 for the discussion that inspired this tutorial, as well as suggesting some of the improvements to it.

This post has been edited by Atli: 22 August 2013 - 03:37 PM


Is This A Good Question/Topic? 6
  • +

Replies To: Securing login forms from brute-force attacks using queues.

#2 chris98  Icon User is offline

  • D.I.C Addict

Reputation: 26
  • View blog
  • Posts: 827
  • Joined: 06-July 13

Posted 30 June 2014 - 06:33 AM

Can you do this without a class and as a normal function instead? I understand most of it and would like to use it but I think classes are a bit too advanced for me and don't understand them.

EDIT: Never mind, it wasn't as hard as I thought it would be to modify. Thanks for the great tutorial!

This post has been edited by chris98: 30 June 2014 - 07:50 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1