Crypto library should have a constant-time equality function

[jsha]

When comparing HMACs, it's important to do a constant-time equality test between two digests to prevent timing attacks. See http://codahale.com/a-lesson-in-timing-attacks/.

According to http://nodejs.org/api/crypto.html, it looks like Node does not currently have a constant-time equality function. One is available as a module at https://www.npmjs.org/package/buffer-equal-constant-time, but this should be a core part of the crypto library since it's essential to correct use of HMACs.

The current library leads to incorrect implementations that use the == or === operators, such as in this Stack Overflow question and answer: https://stackoverflow.com/questions/10305067/hmac-md5-validation-with-node-js-express-and-trialpay

[indutny]

Good idea, do you have any exact proposal?

I'm currently thinking about crypto.constEqual.

cc @trevnorris @bnoordhuis

[jsha]

constEqual is potentially confusing with const variables. A verbose name like constantTimeEquals might be better.

[indutny]

@jsha : this name makes me feel like we are writing Java, not JavaScript. May be cryptoEqual?

[jsha]

That would be fine, or perhaps crypto.equal.

Also probably valuable in terms of API clarity to provide Hash.equal and Hmac.equal, since those are the most common use cases.

[bnoordhuis]

OpenBSD has timingsafe_bcmp(), NetBSD has consttime_memequal(). Translating that to JS, you'd get crypto.timingSafeEqual() or crypto.constTimeEqual(). Kind of wordy but it accurately reflects what the function does.

About constant time comparisons, I'm highly skeptical that you can write them in vanilla C or C++ unless the compiler is sufficiently stupid. Consider OpenBSD's timingsafe_bcmp():

int
timingsafe_bcmp(const void *b1, const void *b2, size_t n)
{
    const unsigned char *p1 = b1, *p2 = b2;
    int ret = 0;

    for (; n > 0; n--)
        ret |= *p1++ ^ *p2++;
    return (ret != 0);
}

The (ret != 0) is potentially a data-dependent branch (bad) but what's worse, there is nothing that prevents a compiler from rewriting it to this:

int
timingsafe_bcmp(const void *b1, const void *b2, size_t n)
{
    const unsigned char *p1 = b1, *p2 = b2;
    for (; n > 0; n--)
        if (*p1++ ^ *p2++)
            return 1;  // Not constant time.
    return 0;
}

[indutny]

This is what OpenSSL is using:

int CRYPTO_memcmp(const void *in_a, const void *in_b, size_t len)
    {
    size_t i;
    const unsigned char *a = in_a;
    const unsigned char *b = in_b;
    unsigned char x = 0;

    for (i = 0; i < len; i++)
        x |= a[i] ^ b[i];

    return x;
    }

I suggest that we should just stick to CRYPTO_memcmp in openssl/crypto.h

[bnoordhuis]

Not constant time either, not in the presence of whole program optimization. I think the only way to reliably do constant-time comparisons is in assembly. Even then you have to be wary of software and hardware optimizers.

[jsha]

@bnoordhuis: Point well taken, and Brad Hill has a very cool fix for the problem called double HMAC: https://www.isecpartners.com/blog/2011/february/double-hmac-verification.aspx.

However, by the "don't roll your own" principle, I think it makes sense to use OpenSSL's implementation and separately address any shortcomings there.

[bnoordhuis]

@jsha Can you explain how that would work? I would summarize Hill's explanation as memcmp(hmac(a), hmac(b)) - at least, that is how I understand it. It's better than what CRYPTO_memcmp() does but it's still not fully constant time.

However, by the "don't roll your own" principle, I think it makes sense to use OpenSSL's implementation and separately address any shortcomings there.

I don't disagree with that but I would like to get it right from the start. A false sense of security can be more disastrous than having no security but at least being aware of that.

[jsha]

Yes, memcmp(hmac(a, K), hmac(b, K)) is a good summary. The value of K in Brad's example is the same key you are using to generate the original HMAC that you are trying to validate. I believe it would also be valid to use a random K.

A false sense of security can be more disastrous than having no security but at least being aware of that.

True, although in this case a number of Node users may already have a false sense of security from checking hmac(m, K) === b.

At a certain point we do have to trust our libraries, though. If CRYPTO_memcmp in OpenSSL is broken under typical compilation scenarios, I believe that means a huge number of other primitives are also broken.

[bnoordhuis]

I had a go at implementing a constant-time comparison function but I have to admit, it seems pretty hopeless. The interaction with the VM introduces many factors that turn a constant-time comparison into, for lack of a better word, arbitrary time.

For example, comparing two strings is complicated by the fact that strings have several internal representations, may not be contiguous in memory, may need to be flattened first, etc. We could restrict it to buffers and typed arrays only but even then a determined attacker can probably glean information from inducing page faults of triggering garbage collections.

[jsha]

@bnoordhuis: Is there any reason to implement it in JS instead of adding a binding to OpenSSL or another underlying library, as Node does for other crypto primitives?

[bnoordhuis]

Implementing it in JS or C++ doesn't make much difference for the things I described above. You're going to end up dealing with JS objects either way and then it becomes nearly impossible to guarantee constant-time operation.

[jsha]

Now I get it, thanks for clarifying. Java and Go address the representation issues by only handling byte arrays. Handling buffers might be appropriate in this case because that is what Hmac returns.

All that said, the representation issues are enough to convince me that it's worthwhile to implement double-HMAC and use that. We can be more confident in doing the constant-time comparison because we know the representation that will be output from each HMAC step, and can do the comparison without ever converting types out of C++.

[bnoordhuis]

I've filed a PR at node-forward/node#29. (Repo is private but ping me if you want access.) I'm still not sure if it's a great idea to add it because it's nearly impossible to make it truly constant time. I do make that abundantly clear in the documentation, though.

[hillbrad]

Hi. Double-HMAC is not constant time, it is random-time-per-guess, which blinds the timing channel against iterative brute force. It allows you to stop the attack even in situations where you can never guarantee constant-time program semantics. Seems like the ideal choice in Node, honestly. Happy to answer any further questions you might have here. Re-using the same key for the comparison as that blog post recommends is fine against remote guessing, but it does reduce the strength of the HMAC to a little above the birthday bound for the hash. (so still infeasible for remote attacks) If you want the full strength of the HMAC, you can do a random key for the blinding step. This might be necessary against local attacks that can be performed very rapidly, but is certainly overkill for anything machine-to-machine.

[bnoordhuis]

@hillbrad node-forward/node#29 is roughly the code below but in C++.

function constTimeEqual(a, b) {
  var key = crypto.randomBytes(32);
  var ah = new crypto.Hmac('sha256', key).update(a).digest();
  var bh = new crypto.Hmac('sha256', key).update(b).digest();
  for (var c = 0, i = 0, n = ah.length; i < n; i += 1)
    c |= ah[i] ^ bh[i];
  c |= (a.length ^ b.length);
  ah[0] = bh[0] = c;  // Assign for side effect.
  return c === 0;
}

@jsha commented that it's allowed to bail out early if the inputs don't match in length, and that it's not necessary to compare the digests in constant time.

That sounds reasonable but it seems to me that everything then hinges on the key's entropy. What would the ramifications be if, say, the PRNG is so broken that it returns only zeroes?

Something that bugs me is that there is a (probably theoretical) chance of hash collisions. Maybe I should just stick with CRYPTO_memcmp(a, b, min(a.length, b.length)) | (a.length ^ b.length)...

[hillbrad]

I would pick one strategy or the other: blind the timing channel, or do a constant-time compare. If you can get to a program abstraction layer where a reliable constant time compare is available, do that.

Regarding bad keys for this particular use.

1. If your crypto PRNG is really that bad, your system is probably badly broken some other important way.

2. The strength of the blinding depends only very minimally on the strength of the key used for the blinding. Even if it were always to return a fixed key known to the attacker, HMAC-SHA256 is still a PRF with strong pre-image resistance. So consider how the attacker would have to form iterated guesses: Find an input which produces an HMAC output with first bits: 0000000. Check timing. Now find an input which produces an HMAC output with first bits: 10000000. Check timing. Now 11000000. Repeat for 256 bits. This is a very hard problem (it's the same problem used for bitcoin mining) and for all practical purposes with reasonably sized and pre-image resistant PRFs it is impossible. You could blind with just SHA256 instead of HMAC. I recommend re-using the same HMAC because then you don't even need to think about how the blinding strength compares to your HMAC construction and in some cases HMAC is still adequately strong even if the underlying hash isn't (e.g. with MD5). But the failure mode of a bad blinding key with a good hash is still very, very strong protection agains the side channel.

3. If you pick a new blinding key on each compare, collisions don't weaken the strength of the blinding. If you always use the same key, collisions reduce the strength of the blinding to the birthday bound, so exploit is possible in that, multiplied by the number of guesses needed to exploit the timing channel. For SHA256 that is around 2^148 in real world conditions, so theoretically weaker but not practically so, especially for remote guessing.

[Zolmeister]

@bnoordhuis
Your example is unnecessarily complex.
Because you are hashing the value, comparing via === is acceptable.

 function constTimeEqual(a, b) {
  var ah = crypto.createHash('sha1').update(a).digest('hex');
  var bh = crypto.createHash('sha1').update(b).digest('hex');
  return ah === bh;
}

[sarciszewski]

@Zolmeister There is a strategy called "Double HMAC" wherein you generate a nonce, HMAC both HMACs with said nonce as the key, then compare them using a normal string comparison strategy. It does prevent the leak of meaningful timing information.

The reason "Double HMAC" works is because it uses a random nonce that the attacker cannot predict. If there is ever a RNG failure, this strategy becomes less robust. If there is a break in the hash function, we end up not much better off if we threw caution to the wind and left our code timing attack vulnerable. It's for this reason that most cryptographers employ a true constant-time comparison strategy rather than Double HMAC.

Your simple hash-based comparison code is like a broken Double HMAC strategy. SHA-1 is a poor choice for a hash function in 2015, for starters. You don't use a nonce (nor an HMAC construct). It really offers no security against side-channels.

The correct tool for the job would be, simply,

function constTimeEqual(a, b) {
  var key = crypto.randomBytes(32);
  for (var c = 0, i = 0, n = ah.length; i < n; i += 1) {
    c |= a[i] ^ b[i];
  }
  c |= (a.length ^ b.length);
  return c === 0;
}

[jsha]

@sarciszewski: The security of Double HMAC does not depend on the nonce being unpredictable. The security comes from the blinding property. Under Double HMAC the timing no longer indicates any information about the underlying data, and can't be used to guess the data.

The only requirement for Double HMAC is that the nonce not repeat itself very frequently. It would actually be fine to use a non-CS PRNG.

[sarciszewski]

It would actually be fine to use a non-CS PRNG.

Sure, but I wouldn't recommend using a non-CS PRNG if you have a CSPRNG available for any crypto operation, personally.

[jsha]

Sorry, I misspoke: It's not even required that the key be a nonce (i.e., not repeat itself). Like in Brad's example, it's fine for the key to be constant. My point was that @Zolmeister's code is not broken. See @hillbrad's earlier detailed comments on the topic.

[sarciszewski]

Like in Brad's example, it's fine for the key to be constant.

No it's not. If you send the same input 10000 times and always get the same output, then your underlying comparison operation is still dangerous. Blinding is helpful, but it doesn't actually remove the fact that some timing information is being leaked. Adding a nonce does achieve this.

[ircmaxell]

If we assume that H() is a perfect hash function with no pre-image attacks possible (1st or 2nd), then H(a) == H(b) does provide timing protection.

However, compared to Double-HMAC (r is a random key for each comparison, Hmac(a, r) == Hmac(b, r)) and iteration methods (CRYPTO_memcmp()), there is an important difference.

All three methods require brute-forcing b to find out a (they protect a in that sense). However, with H(a) == H(b), some of that brute-forcing can happen offline. In fact, the majority of it occurs offline.

Since the comparison is byte-wise, the attacker finds 256 versions of b that hash to incrementing first characters (a, b, c... etc). Then timing attack to deduce the first character of H(a).

From there, the attacker can offline attack b to find a new 256 set which has the first character set to what we attacked earlier.

The overall work done is the same in all regards, but in the single-hash version a large portion of it can happen offline in the datacenters of the attacker (on their hardware, using whatever resources they have at their disposal).

How practical this is depends on the possible keyspace of a. If a is a strongly produced random key >= 128 bits, there's no practical chance of brute-forcing it in any case. But if it's 64 bit, it's definitely within the realm of possibility to be attacked in days in an offline capacity. If it's a low quality "password", it would be trivial to attack this way.

Since there is no real added cost to doing double-hmac verification (pulling a random string and doing 2 more internal hash computations), the additional protection that it gives (especially guarding low-entropy secrets) is important.

[Zolmeister]

@ircmaxell

If it's a low quality "password", it would be trivial to attack this way.

Untrue, unless the crpytographic properties of H() are compromised.
To generate the 63-bit version of the hash (guessing 1-bit at a time) has no relation to the 64-bit version

Edit: my point being that the quality of the 'password' should have no impact on the attack time due to the leak

[ircmaxell]

@Zolmeister I meant in the sense of a dictionary attack.

Think along these lines:

Assume you go through two rounds and find the first two "hash" characters are 5b. Then a smart attacker could look at a dictionary of password-sha1 mappings, and see that sha1("password") is 5baa61.... Then they could just try sending "password" as the secret.

As far as the 64 bit part, I was more talking about if you knew some information about the source you could start enumerating the 64 bit key server-side, keeping only the guesses which match the prefix you found via timing attacks. So while you're executing the timing attack portion, the cluster could be building up a set of candidate keys that match the currently known key prefix.

So after deducing a sufficiently large prefix size (say 10 bytes), the number of 64 bit keys that fit the space starts to drop significantly to the point where you can switch from timing attacking the full 20 byte sha1 and instead trying the prefix-filtered permutations.

This style attack requires knowing something about a, but that's not out of the realm of possibility either (especially for a framework generic implementation).

[amingilani]

+1, atm I need to use a separate module just for this.

[toejough]

+1

[ChALkeR]

Was reopened as nodejs/node#3043, the discussion should move there.