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++.