3 ms·
Constant time operations in the context of cryptography means that the runtime of the operation is not dependent on the data being manipulated. As an example,
by nightcracker 6y ago
Constant time operations in the context of cryptography means that the runtime of the operation is not dependent on the data being manipulated.
As an example, suppose you were checking a 256-bit number for equality. This would be unacceptable:
bool eq256(uint32_t a[8], uint32_t b[8]) {
for (int i = 0; i < 8; ++i) {
if (a[i] != b[i]) return false;
}
return true;
}
Why? Because depending on the data this function takes longer or shorter, and timing attacks might be used to figure out secret data. Instead you need an implementation like this:
bool eq256(uint32_t a[8], uint32_t b[8]) {
uint32_t diff = 0;
for (int i = 0; i < 8; ++i) {
diff |= a[i] ^ b[i];
}
return diff == 0;
}
This implementation always takes the same amount of time regardless of the contents of a and b.
It goes further than this as well, you're not supposed to take branches based on secret data nor access memory locations based on secret data as those can be recovered through the branch predictor and cache respectively.
- leni536 6y agoThere is no reason that an optimizing compiler doesn't "optimize" your function to non-constant time.
- saagarjha 6y agoWhile downvoted at the time of my response, this answer is correct. The optimizing compiler makes no timing guarantees, so it's not required to use any of the constructs in your second answer at all. If you need guaranteed timing, you cannot use standard C (instead use assembly or compiler extensions).
- cyphar 6y agoA proper implementation uses the correct compiler intrinsics and hints to cause such operations to be constant-time. Timing problems are a fairly well-known problem in cryptography and constant-time implementations are often required for safe cryptography.
- leni536 6y agoFair enough. I just wanted to point out that standard C is inadequate on its own. I'm pretty sure that cryptographers are aware of this.
- mratsim 6y agoOften that hints boils down to use assembly though. Constant-time is a pain to achieve and new compiler optimizations might make your code not constant-time anymore: https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf Given that I'm writing such a cryptographic library, I am very interesting on the compiler hints you use.
- contravariant 6y agoOh right, that's what's being meant. I confused it with constant time as in O(1). Wouldn't most implementations of fixed length integers have constant time though? It barely seems worth optimizing unless your integers vary massively in size, at which point using fixed size integers is clearly suboptimal.