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