Constant time comparison for arrays of different lengths

Question

I found the following code snippet from the Bouncy Castle C# library, which seems to claim that it's constant time, even when the arrays have different lengths.

/// <summary>
/// A constant time equals comparison - does not terminate early if
/// test will fail.
/// </summary>
/// <param name="a">first array</param>
/// <param name="b">second array</param>
/// <returns>true if arrays equal, false otherwise.</returns>
public static bool ConstantTimeAreEqual(byte[] a, byte[] b)
{
    if (null == a || null == b)
        return false;
    if (a == b)
        return true;

    int len = System.Math.Min(a.Length, b.Length);
    int nonEqual = a.Length ^ b.Length;
    for (int i = 0; i < len; ++i)
    {
        nonEqual |= (a[i] ^ b[i]);
    }
    for (int i = len; i < b.Length; ++i)
    {
        nonEqual |= (b[i] ^ ~b[i]);
    }
    return 0 == nonEqual;
}

However, I've heard that it's not possible to compare arrays of different sizes in constant time. For instance, the Go crypto ConstantTimeCompare() function checks the length of the arrays before the comparison. Some people have complained that this leaks the length of the secret.

func ConstantTimeCompare(x, y []byte) int {
    if len(x) != len(y) { // <--- here
        return 0
    }

    var v byte

    for i := 0; i < len(x); i++ {
        v |= x[i] ^ y[i]
    }

    return ConstantTimeByteEq(v, 0)
}

Which approach should be taken when comparing arrays of different lengths? Or should you just hash the data and then perform the comparison (since the lengths will be the same)?

Answer 1

Assuming the first code extract is translated straightforwardly to machine code (perhaps by blocking some compiler optimizations, or using a relatively dumb compiler) and executed on a CPU that performs no groundbreaking runtime optimization, it it is plausible that execution time has no dependency on the data in the arrays, except perhaps in the final 0 == nonEqual (and that residual timing dependency is a non-issue if the function result is to be used as argument of a conditional operator, as seems likely in the context). It's possible to ascertain this by looking at the generated code and at the characteristics of the CPU, and/or confirm it by careful instrumentation.

But execution time almost certainly depends on the length of the arrays, in several ways:

• As noted in another answer, System.Math.Min likely does.
• An optimizing compiler is likely to crunch out a lot of the second for loop, since (b[i] ^ ~b[i]) is always ~0. The whole nonEqual |= (b[i] ^ ~b[i]); could be replaced by nonEqual = ~0. It's entirely possible that the full loop is reduced to a test that it runs at least once and a conditional nonEqual = ~0.
• Even if somehow the above is made to not occur, there's no reason to believe each execution of the second loop lasts the same time as the first: the code is not the same; on some architecture the code alignment matters; a data cache or some other CPU optimization is likely to make the two references to b[i] faster than the references to a[i] and b[i]; on some architectures, the ~ has a cost...
• When the second loop does not run at all, it's possible the code is not fetched and that it saves some time when the two arrays are exactly the same length.

Can we fix it? Not portably, in C# or in any language I know that targets multiple CPUs.

Does it matter? Perhaps, but only if that's among the smallest timing dependencies on the length of the arrays. Which is unlikely, and hard to assess: there's no portable way to setup an array in time independent of it's size!

Which approach should be taken when comparing arrays of different lengths?

Try to reformulate the problem/method so that the need to perform such comparison in constant time vanishes. E.g. if we want to hide the length of a password, we can turn the password into a hash once in a context where adversaries can't time the hashing operation, then hash the string to be compared and compare the equal-length hashes in constant time. If even that is difficult (a compiler, JIT, or even CPU architecture optimization can optimize the loop in a ConstantTimeCompare into something with a data timing dependency), we can perhaps compare (H)MACs of the hashes computed using the same secret random key.

More generally, demonstrable absence of timing dependency is hard to obtain. It's impossible to obtain from a high level language without exquisite control on the compiler and runtime environment. The best line of action is to reduce to an absolute minimum where in the code that's necessary. Or offload the problem to an environment dedicated to that, like a security CPU, which is designed to prevent timing side channels (including using a CPU having carefully designed and specified timing characteristics making execution time precisely predictable), and other side channels (power analysis, fault injection…).

Answer 2

Your problem is the min. Here is one way to make a constant time min if you have a constant time subtractor and adder,

• Let $Sub(x,y)$ be a constant time subtractor.
• Let $Add(x,y)$ be a constant time adder.
• Let $MSB(x)$ returns the sign bit.

//Inputs x and y are arrays with length property
//Returns the min of x and y in constant time
constantTimeMin(x,y)
  
    A = Sub(x.length, y.length)
    
    return Add(MSB(A)*x,~MSB(A)*y)

Answer 3

I don’t think there is a point in doing that. Usually, constant-time equality comparisons compare two cryptograms with by-design identical length (e.g. hashes). And where not, I’d expect the expected length to be more or less public (e.g. length of a generated OTP).

However, if you really want to do that, you cannot do that as a generic comparison function with symmetrical inputs.

In your solution, you are trying to force time proportional to max(len(A), len(B)), but why do that? Why not just compare the common part, i.e. min(len(A), len(B)), and drop the complicated (and broken) rest? Sure, the attacker can start with a zero-length string, and incrementally increase its length, until the execution time gets constant, learning the length of the secret. But your solution has the same problem, only in reverse: the attacker observes when the execution time stops being constant. There is no way to have constant-time execution in this aspect (unless you want to force a constant large execution time regardless of both input sizes).

What you’d need to have is two asymmetrical inputs: compare a “secret” against an “possibly-attacker-provided” attempt. In that case, always run the loop based on the length of the attempt, so that the secret length does not have any effect on the execution length.

I’d try something like:

public static bool ConstantTimeAreEqual(byte[] secret, byte[] attempt)
{
    int secretLen = secret.Length;
    int attemptLen = attempt.Length;
    if (attemptLen == 0 || secretLen == 0) return secretLen == attemptLen;

    var diff = 0;
    for (int i = 0; i < attemptLen; ++i)
    {
        var a = secret[i % secretLen];
        var b = attempt[i];
        diff |= a ^ b;
    }
    diff |= secretLen ^ attemptLen;
    return diff == 0;
}

However, even this is not completely safe from hypothetical/future optimizing compilers, I’d guess.