Short integer hashes to mitigate timing attacks on passwords

Question

Assuming we want to protect against timing attacks on our hashed passwords because even to know the hash may give to the attacker a significative advantage then we may want to perform a constant-time or fixed-time string comparison for our hashes.

However constant-time comparison is not a simple task as we may expect because compiler may be against us and simple random delays will just stop the most naive attacker.

With all these premises we may mitigate this issue (does we need to? passwords are often stored in databases/durable medium and in any real-world system this will add noise) using this pseudo-code:

// Possibly pre-computed or cached values...
string passwordHash = "550b1f8802ca3d7a987fc46a2af408c3";
int shortPasswordHash = SimpleHash(passwordHash);

// Function to validate a password
bool IsPasswordValid(string hashedPasswordToValidate)
{
    if (SimpleHash(hashedPasswordToValidate) != shortPasswordHash)
        return false;

    return hashedPasswordToValidate.Equals(hashedPassword);
}

Note that string comparison (on hashed password) is still vulnerable to a timing attack but chances to leak useful information to an attacker should be lower (and this algorithm is easily applicable in most languages - even those without a built-in constant-time password/hashes comparison).

Same reasoning is also applicable if we don't have an hashed password but directly plain-text (!!!) like this:

string password = "12345";
string longPasswordHash = BCrypt(password);
int shortPasswordHash = SumAllCharactersWithoutOverflow(longPasswordHash);

bool IsPasswordValid(string passwordToValidate)
{
    string longHash = BCrypt(passwordToValidate);
    int shortHash = SumAllCharactersWithoutOverflow(longHash);

    if (shortHash != shortPasswordHash)
        return false;

    return longHash.Equals(longPasswordHash);
}

Do we still want/need to use a better constant-time comparison function in any real-world non-academic scenario?

9192 says the opposite of what you claim; using comparison timing to learn a good password hash does NOT help the attacker. And 25607 says it isn't practical anyway. But your 'solution' for the plaintext case actually provides an excellent oracle, astronomically better than hash comparison timing. — dave_thompson_085, Jul 01 '16 at 00:55
I'm referring to http://security.stackexchange.com/questions/9192/timing-attacks-on-password-hashes#comment14744_9193. For what I understood (well...pretty possible I completely took it wrong) it won't help attacker on-line but it may help him to perform a brute force attack off-line. I didn't understand second part of your comment... — Adriano Repetti, Jul 01 '16 at 08:29
You should really ask yourself the "5 whys", starting with "why do you want to do this?" or "What does this solve?": https://en.wikipedia.org/wiki/5_Whys — A. Hersean, Nov 28 '16 at 13:44
@A.Hersean isn't it the first sentence in the question? _"Assuming we want to protect against timing attacks on our hashed passwords"_. Well, OK, we may ask _why_ of that but answer may simply be _"because it's a risk we want to avoid"_ (BTW I'm not asking because I actually need it but just for sake of discussion) — Adriano Repetti, Nov 28 '16 at 13:58
If you do not need it, don't do it. You'll just add complexity without any gain. The 2nd why to your answer: "when is it really a risk?" (Which threat and which attack vector? Is this attack feasible?). — A. Hersean, Nov 28 '16 at 14:43

Colin Cassidy · Answer 1 · 2016-07-01T05:14:19.307

1

Really you want to ensure that the comparison function takes the same length of time regardless of the success or failure of the comparison. Functions such as strcmp() etc may shortcut this and return failure on the first byte that does not match.

Likewise with higher level languages with string objects, where == and != can be used, we are reliant on the compilers implementation.

So to ensure constant time, a good solution is to always perform a byte by byte comparison of all the bytes of the hashed value, and then return true/false based on that comparison.

for example:

int contstant_time_compare(char *a, char *b)
{
    int i = 0;
    int len = strlen(a);
    int diff = 0;
    for(i = i ; i < len ; i++)
    {
         diff |=  a[i] ^ b[i]; 
    }
    return (0 == diff);
}

edited Jul 01 '16 at 05:14

answered Jun 30 '16 at 12:42

Colin Cassidy

1,880
11
19

True but (that's why this question) it's not an easy task because branch prediction and - for languages with a JIT compiler with run-time PGO - compiler optimizations will still leak enough information about our hash (or even our plain password) – Adriano Repetti Jun 30 '16 at 12:46
1

That should be `diff |=`. @Adriano: comparisons like `==` may turn into branches, even used for value. `^` and for that matter `-` won't. – dave_thompson_085 Jul 01 '16 at 00:52
@dave agree but my doubt arises for languages like Java where JIT compiler may simply _optimize_ our loop deciding that (after 1000 executions...) loop is seldom took to the end then it's better to _short-circuit_ as soon as diff is non-zero. – Adriano Repetti Jul 01 '16 at 08:27
in that case you could simply take the JIT compiler out of the equation, write the crypto module in a non-JIT language, verify that it is constant time, and link to the new library – Colin Cassidy Jul 01 '16 at 08:54
Most languages if not all provide special arguments, annotations or similar mechanisms to prevent the compiler/interpreter from optimizing operations: [Java without optimizations](http://stackoverflow.com/questions/5242405/how-to-make-sure-no-jvm-and-compiler-optimization-occurs), Python can use C libraries for this purpose without optimizations, I don't know about other languages – Mr. E Sep 29 '16 at 13:22

Short integer hashes to mitigate timing attacks on passwords

1 Answers1