2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ No solution at all? $\endgroup$ – kelalaka Feb 20 at 16:18
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Feb 20 at 17:17
  • $\begingroup$ Ok, I'll keep my answer as it is. $\endgroup$ – kelalaka Feb 20 at 17:48
  • 1
    $\begingroup$ It doesn't solve all the problems, but MethodImplOptions.NoOptimization can be used to keep the code from being optimized out. $\endgroup$ – bmm6o Feb 22 at 17:31
  • $\begingroup$ @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. $\endgroup$ – fgrieu Feb 22 at 18:23
0
$\begingroup$

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)
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Jeremy Feb 19 at 15:07
  • $\begingroup$ @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. $\endgroup$ – kelalaka Feb 19 at 15:28
  • $\begingroup$ 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. $\endgroup$ – fgrieu Feb 19 at 17:44
  • $\begingroup$ @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. $\endgroup$ – kelalaka Feb 19 at 17:54
  • $\begingroup$ @fgrieu could you write a better answer? Be aware it is C# $\endgroup$ – kelalaka Feb 19 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.