Constant-time code isn’t about making your code run at a consistent speed; it’s about making sure the time your code takes to execute is independent of the secret data it’s processing. This is crucial in cryptography because attackers can measure tiny variations in execution time to infer secrets, a class of attacks called timing attacks.
Let’s see this in action. Imagine we have a simple function that checks if a byte key_byte matches a byte in a secret secret_key array.
// WARNING: This is NOT constant-time and is VULNERABLE!
int compare_bytes_vulnerable(const unsigned char *secret_key, unsigned char key_byte, size_t len) {
int match = 0;
for (size_t i = 0; i < len; ++i) {
if (secret_key[i] == key_byte) {
match = 1;
// This 'break' is the vulnerability!
break;
}
}
return match;
}
The problem here is the break statement. If key_byte matches an early byte in secret_key, the loop terminates quickly. If it matches a later byte, or not at all, the loop runs longer. An attacker could repeatedly call this function with different key_byte values and measure the execution time. If they see consistently shorter execution times when key_byte is, say, 0x41, they might infer that 0x41 is part of the secret key.
To write constant-time code, we must ensure that every execution path within the critical section (where secrets are processed) takes the same amount of time, regardless of the secret’s value. This often means avoiding conditional branches that depend on secret data and performing operations that always execute.
Here’s how to fix the compare_bytes function:
// Constant-time comparison
int compare_bytes_constant_time(const unsigned char *secret_key, unsigned char key_byte, size_t len) {
int match = 0;
for (size_t i = 0; i < len; ++i) {
// Use a bitwise operation to avoid data-dependent branches
// (secret_key[i] ^ key_byte) is 0 if they match, non-zero otherwise.
// (~(secret_key[i] ^ key_byte)) + 1 will be 0 if they match, non-zero otherwise.
// The result of the '!' will be 1 if they match, 0 otherwise.
// We then OR this into 'match'. This ensures 'match' becomes 1
// if *any* byte matches, and stays 1.
match |= !(secret_key[i] ^ key_byte);
}
return match;
}
In this constant-time version, the loop always iterates len times. The comparison secret_key[i] ^ key_byte is performed for every byte. The ! operator converts the result to 0 or 1. The |= (bitwise OR assignment) ensures that match becomes 1 if any byte matches, and it stays 1. Crucially, there’s no break, so the loop always runs to completion. The operations inside the loop are simple bitwise operations and assignments, which are generally constant-time on most modern processors.
The primary problem constant-time code solves is preventing information leakage through execution timing. This is particularly relevant for cryptographic algorithms that handle sensitive data like private keys or passwords. Leaking even a single bit of information about a secret can, through repeated attacks, compromise the entire secret.
The core principle is to eliminate data-dependent control flow. This means avoiding if statements, for loops with early break or continue that depend on secrets, and switch statements where cases take different amounts of time. Instead, you use techniques like:
- Bitwise operations: As shown above, XORing and checking for zero is a common pattern.
- Lookup tables: When used carefully, lookup tables can be constant-time if memory access patterns don’t depend on secrets. However, cache timing attacks can still be a concern with lookup tables.
- Conditional moves (CMOV): Some architectures provide instructions that conditionally move data without branching. These can be leveraged to rewrite branches into data-independent operations.
- Arithmetic tricks: Performing calculations that always produce a result, even if intermediate values are not directly used, can mask secret-dependent behavior.
Consider a scenario where you need to select one of two values based on a secret bit. A vulnerable way would be:
// Vulnerable selection
if (secret_bit) {
result = value_if_set;
} else {
result = value_if_not_set;
}
A constant-time approach might look like this:
// Constant-time selection using bitwise operations
// Assume secret_bit is 0 or 1
// ((value_if_set - value_if_not_set) * secret_bit) + value_if_not_set
// If secret_bit is 0, result is value_if_not_set.
// If secret_bit is 1, result is value_if_set.
// This assumes arithmetic is constant-time.
int result = value_if_not_set + (value_if_set - value_if_not_set) * secret_bit;
Even better, on architectures that support it, you might use assembly for conditional moves. For example, on x86, CMOVcc instructions can conditionally move data without altering the instruction pointer, thus avoiding timing differences.
The most common mistake when trying to write constant-time code is assuming that standard library functions are safe. Many functions, especially those dealing with strings or memory comparisons (like memcmp, strcmp), are not constant-time. They often return early as soon as a mismatch is found, introducing timing vulnerabilities. Always check the documentation or, better yet, verify the implementation yourself.
Another pitfall is overlooking memory access patterns. Even if your CPU instructions are constant-time, the order in which you access memory can reveal information if the attacker can monitor cache behavior. For example, repeatedly accessing different parts of a large data structure based on a secret could leak information through cache hits and misses.
The next hurdle you’ll face after achieving constant-time execution for your core logic is dealing with side channels beyond just direct execution time.