Constant-time comparison: which approach is best?

[sdrapkin]

Which approach is best?

AndEq approach, used by internal and public Microsoft helpers:

static bool AndEq(byte[] a, byte[] b)
{
    bool f = a.Length == b.Length;
    for (int i = 0; i < a.Length && i < b.Length; ++i)
    {
        f &= a[i] == b[i];
    }
    return f;
}

OrXor approach (classic):

static bool OrXor(byte[] a, byte[] b)
{
    int x = a.Length ^ b.Length;
    for (int i = 0; i < a.Length && i < b.Length; ++i)
    {
        x |= a[i] ^ b[i];
    }
    return x == 0;
}

OrSub approach, recently advocated by Microsoft as the "better way" (no supporting evidence):

static bool OrSub(byte[] a, byte[] b)
{
    int x = a.Length ^ b.Length;
    for (int i = 0; i < a.Length && i < b.Length; ++i)
    {
        x |= a[i] - b[i];
    }
    return x == 0;
}

Some other approach?

[sdrapkin]

@blowdart, @bartonjs, @CodesInChaos, @jedisct1

[jedisct1]

Best approach is assembly, or using a dedicated function provided by the platform.

When using a compiler, even more a JIT, there are no guarantees that it won't perform obvious optimizations.

[sdrapkin]

@jedisct1 I get your point, but my question is about the confines of a safe, managed .NET environment (ie. JIT, GC, and all the other attributes of NETFRAMEWORK & NETCORE).

[henning-krause]

As @jedisct1 already pointed out, a platform-backed operation is probably a good choice. Since you already sprinkled some #ifdefs around, you can use CryptographicOperations.FixedTimeEquals on .NET Core 2.1.

[sdrapkin]

@henning-krause CryptographicOperations.FixedTimeEquals doesn't do anything special - it's OrSub.
Inferno already provides Xor-based constant-time comparison API. The new thing to me is recent Microsoft claims that OrSub-based approach is deemed better than the classic OrXor.

Does anyone know why Microsoft suddenly prefers OrSub over OrXor?

[henning-krause]

@sdrapkin, in the link you provided, MS claims that Sub has the best constant-time execution. No proof for that, however....

[CodesInChaos]

Personally I don't trust code involving booleans or the == operation in the constant time part, which rules out the and based code you posted.

Between substraction and xor I slightly prefer xor, since it never needs overflow checks, even when compiling with overflow checks enabled (which I often do).

---

CryptographicOperations.FixedTimeEquals doesn't do anything special - it's OrSub.

It is special, because it's maintained by the same party as the JIT. So if a change to the JIT breaks the constant time guarantee of that function, they can (and should) adjust the function at the same time.

IMO functions like this or secure zeroing should always be provided by the compiler maintainers, since they are the ones who can guarantee that they'll function correctly.

---

The xoring the length part is silly IMO, I'd rather use an if(x.Length != y. Length) check, since variable length comparisons can never be constant time. I'd prefer even throwing an exception in this case, but of course that's a breaking change so you can't do it.

[sdrapkin]

@CodesInChaos Interesting thoughts, thx. Personally, I don't trust preferences that infer trust based on slippery-slope of which team might hypothetically be maintaining what, and what hypothetically should happen in case of an issue.

The engineer in me prefers OrXor (same no-overflow-bit reasons).

The pragmatist in me prefers AndEq, which has huge .NET-framework deployment base compared to all other alternatives. It's also used in Protect/Unprotect calls (again, huge deployment base). If there is any concern with AndEq, MS would have to change the .NET-framework implementation asap.

OrSub I trust least of all. MS has switched their latest code to it, but did not alter the older widely-deployed code (which will continue to be widely deployed since .NET-full will continue to ship), and did not voice any concerns about the older implementations. This was a silent change-of-approach - nothing seems wrong with it, but nothing seems "more" right with it either. Very few other respected codebases use OrSub.

It is the inconsistency of MS approach that I personally find the least trustworthy (ie. if OrSub is indeed better - MS should've switched everywhere with detailed explanation of concerns/reasons).