Timing-safe string comparison in high-level languages

Question

I'm looking for a reliable solution to compare two strings without leaking their content through time differences. The length of the strings is not secret.

The background is this: I'm implementing password-based authentication for a web application. The passwords are hashed with bcrypt and stored in a database. Rather than giving the application direct access to the hashes so that it check the password, I'd like to delegate this to the database system itself. The application only hashes the password and then passes the hash to a database procedure. This procedure has special privileges to access the stored hashes and compare them with the provided hash. The goal is to protect the hashes against SQL injection attacks. A similar idea is described in this presentation.

Obviously, this scheme is only effective if the procedure does not leak any information about the stored hashes. So the string comparison must be timing-safe.

I'm aware of the following method (pseudo-code):

string_comp(str_1, str_2):
    if str_1.length != str_2.length:
        return false
    else:
        result := 0
        for i := 0 to str_1.length - 1:
            result := result | (str_1[i] ^ str_2[i])

        return result == 0

However, this is rather cumbersome, and I'm not sure if it works as expected in high-level languages like SQL.

Another common suggestion is to hash the strings and then compare the hashes. This would be much simpler than the code above.

Which method is preferable? If I were to use the hash solution, which algorithm would I choose to not degrade the strength of bcrypt (not even theoretically)? SHA-256? SHA-384? SHA-512?

Answer 1

Note that you can't compute the bcrypt hash in the application and pass it to the database unless you store the salts separately from the hashes. If you do that, you'll incur the overhead of performing a SELECT first, then the bcrypt, and then the password verify step. Doing as the presentation suggests (having the DB calculate the hash) might make the most sense. Postgres 9's crypt module does support bcrypt as a built-in hash type.

If you want to do the hashing in the application anyway, comparing with a hash is probably the simplest (least likely to have implementation issues). Since bcrypt is based on blowfish, it only considers up to 448 bits of input, so you can safely hash the output with SHA-512 and mathematically will not lose any strength. In reality, SHA-256 is fine as well, as users passwords essentially never contain more than 256 bits of entropy. Even 256 bits of perfectly random printable characters would take 56 character long passwords. Comparing using a hash is likely to have the most straightforward implementation, and since you already have the overhead of bcrypt, the cost of 2 additional hashes is trivial.

(This part of the answer is based on a misinterpretation of the question as being concerned about timing attacks against the application, not the database, but I'm leaving it here for reference.)

If you're using bcrypt, you've already hashed the password, so you don't need to be concerned about the timing results. Even if someone could deduce the hash of the password, they'd still need to find a plaintext to provide to the application, which should be computationally infeasible (or bcrypt is broken).

Timing attacks are only useful if the attacker can iterate over the values being compared to find a useful comparison. (i.e., A, B, C...) With a hashed value, this is not possible, as they cannot iterate over the output of the hash (for cryptographically strong hashes). Small changes in the input to bcrypt result in large changes to the output. A user providing the input to bcrypt has no way to try out prefixes and then extend the prefix. An attacker would not know anything about either side of the comparison, and thus timing attacks do not leak any information about the value of the hash.

Answer 2

Rather than giving the application direct access to the hashes so that it check the password, I'd like to delegate this to the database system itself.

Why do you want to delegate it? It's simpler to just fetch the hash for the username given, and do a constant side string comparison (using pseudo-code above) with the fetched hash.

Every successful login will give the web application running on your server both the entered password as well as the computed hash of the password.

Granted what you want is fairly straightforward to do within for a given database using its procedural langauge (PL). For example, in postgres you could write:

CREATE OR REPLACE FUNCTION user_with_correct_hash(username TEXT, app_hash TEXT) RETURNS BOOLEAN AS
$$
DECLARE
    user_hash TEXT;
BEGIN
    user_hash := SELECT hash FROM users WHERE "name" = username;
    IF (user_hash IS NULL) THEN
        RETURN false;
    END IF;
    RETURN constant_time_string_compare(user_hash, app_hash);
END
$$
LANGUAGE plpgsql;


CREATE OR REPLACE FUNCTION constant_time_string_compare(user_hash TEXT, app_hash TEXT) RETURNS BOOLEAN AS
$$
DECLARE
    result INTEGER;
    index INTEGER;
    hash_length INTEGER;
BEGIN 
    hash_length := CHAR_LENGTH(app_hash);
    IF CHAR_LENGTH(user_hash) != hash_length THEN
        RETURN false;
    END IF;
    index := 1;
    result := 0;
    WHILE index <= hash_length LOOP
        result := result | (ascii(substr(app_hash, index, 1)) # ascii(substr(user_hash, index, 1)));
        index := index + 1;
    END LOOP;
    RETURN (result = 0);
END
$$
LANGUAGE plpgsql;

Granted be very careful to give your constant time string comparison several test cases to make sure it is behaving properly.