constantEquals is not constant time

[brianmhunt]

The function

constantEquals = function constantEquals(x, y) {
    var result = true,
      length = (x.length > y.length) ? x.length : y.length,
      i;

    for (i=0; i<length; i++) {
      if (x.charCodeAt(i) !== y.charCodeAt(i)) {
        result = false;
      }
    }
    return result;
  },

is not constant time. In particular, the assignment of result will add instructions to the loop when the characters are inequal, exposing timing signatures.

I will post a comment momentarily with a thought on a possibly better option.

[brianmhunt]

Mimicking the well designed itsdangerous:constant_time_compare:

constantEquals = function constantEquals(x, y) {
    var result = (x.length === y.length ? 0 : 1),
      length = Math.max(x.length, y.length),
      i;

    for (i=0; i < length; i++) {
      result |= (x.charCodeAt(i) === y.charCodeAt(i) ? 0 : 1)
    }
    return result === 0;
  },

I have not given this enough thought for it to be considered vetted, but I hope it may be a start.

-- There are two assumptions worth noting:

1. The charCodeAt is the same speed whether or not the index is outside the bounds of the string (otherwise one could garner the length of the other string);
2. The comparison between strings is the same as the comparison between a string and undefined (same problem; possible workaround, assuming empty string compare is the same as a non-empty string compare: result |= ((x.charCodeAt(i) || '') === (x.charCodeAt(i) || '') ? 0: 1))

[ericelliott]

Hi,

Thank you!

Would you consider writing some tests for these ideas and submitting a pull request with a better implementation?

[ericelliott]

BTW, there's a prize involved: #8 (comment)

[brianmhunt]

Many thanks @ericelliott -- I will try to have a look in the near future as I may, but of course will defer any prize benefit to anyone who posts a usable PR sooner than I. :) Cheers

[ericelliott]

I really appreciate your help on this. I've added you as a collaborator. Please be sure that you get a security expert to sign off on every pull request before merging. If you need help finding one, ask me and I'll tap my contacts.

[brianmhunt]

Thank you @ericelliott, it is an honour (and a pleasure) to be of help on this. I will of course have any PRs vetted before merging. Cheers

[ericelliott]

👍

[brianmhunt]

Closing in favour of PR #13

[ericelliott]

Reopening so that we can easily track all open issues. PR #13 does not have any corresponding open issue without this. =)

[brianmhunt]

👌

[madbence]

I'm not saying that constant time comparison is not important, but imho timing attacks are useful against fast operations (like hashing). pbkdf2 is designed to be slow, so the comparison time at the end of the algorithm is not really measurable.

I'm definitely not a crypto expert, so maybe I'm wrong 😄

[tjconcept]

I'm definitely not a crypto expert, so maybe I'm wrong

That's key here.. We all have some feelings but no data to back it up.

[brianmhunt]

A short-circuit of the pbkdf2 is definitely observable, even on the last comparison. You can verify this with a t-test like I've done in the constant comparison.

Remember, it's not the length of time it takes to run a test, but the difference (the delta) in times over a large set.

You can see this in the BlackHat 2010 presentation I referenced.

[ericelliott]

👍

[madbence]

Well, now I'm not sure that we need constant time comparison in the first place:

http://security.stackexchange.com/questions/9192/timing-attacks-on-password-hashes

there is no danger doing short-cut comparison of salted hashes of passwords, if the salt is hidden to the attacker.

The attacker has no control over the result hash, he can change only the input. A small change in the input (eg. 1 bit) causes significant change in the result (every is flipped with 50% probability). With timing attack the attacker incrementally constructs the correct hash, but since he cannot construct arbitrary hashes, he cannot use timing attack to guess the correct hash.

[ericelliott]

@madbence Yep. We are aware of this, but we have decided not to remove the feature in the short term. Maybe in the long term we'll strip it out, if we have enough confidence that the hashes are indeed protective against timing attacks. We'll probably want to prove that with tests.

[madbence]

Sure, thanks for the info! 👍

[tjconcept]

http://php.net/manual/en/function.hash-equals.php
This newly added function suggests that hashes are vulnerable to timing attacks.. Confusing world.