# Constant time comparison for arrays of different lengths

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)?

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…).

• No solution at all? Commented Feb 20, 2021 at 16:18
• @kelalaka: that's it, no solution at all from a high-level language as we know them, even if we assume a compiler that makes no optimization and a standard execution environment. And it does not matter, for under these assumptions, there's no way to setup an array in time independent of it's size.
– fgrieu
Commented Feb 20, 2021 at 17:17
• Ok, I'll keep my answer as it is. Commented Feb 20, 2021 at 17:48
• It doesn't solve all the problems, but MethodImplOptions.NoOptimization can be used to keep the code from being optimized out. Commented Feb 22, 2021 at 17:31
• @bmm6o: thanks for pointing that. When recognized and handled correctly by the compiler and runtime environment, MethodImplOptions.NoOptimization indeed should insure that the code has no data-dependent timing dependency, and solve the second bullet, on all hardware I know currently. The first bullet can also be solved. But there is no solution to the last two bullets, nor to the general problem that there's no portable way to setup an array in time independent of it's size.
– fgrieu
Commented Feb 22, 2021 at 18:23

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)


• To be clear, this wasn't my code. Are you saying the Bouncy Castle code isn't in constant time? If so, then that should probably be reported. Commented Feb 19, 2021 at 15:07
• @Jeremy That depends on what you don't want to leak. If the length leak is not a problem then no issues as commented on the link you provided No. The intent of this function is to not leak the contents of the slices, not their length. However, non-constant time min may leak information to distinguish the inputs to the attacker. That really depends where it is used. Commented Feb 19, 2021 at 15:28
• I don't think this answer is correct. Specifically, even with the improved constantTimeMin, there remains a probable timing dependency. In particular, an optimizing compiler is likely to optimize out a lot of the second loop, since (b[i] ^ ~b[i]) is always ~0. If it does not, or is prevented from doing so by compilation options, the cache is likely to make the second loop run faster than the first, because each loops actually hits a single memory location. And even if cache is disabled, it's likely the case of equal length runs faster, for less code is fetched.
– fgrieu
Commented Feb 19, 2021 at 17:44
• @fgrieu you are right about (b[i] ^ ~b[i]), also it assumes $b$ has a larger size so that part even may not run at all. Commented Feb 19, 2021 at 17:54
• @fgrieu could you write a better answer? Be aware it is C# Commented Feb 19, 2021 at 17:56

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.