The most surprising thing about constant-time code is that it’s not about making your code faster, but about making its execution time unpredictable to an attacker.
Let’s see this in action. Imagine we’re comparing a secret password with a user-provided guess. A naive comparison might look like this:
def compare_passwords_vulnerable(secret, guess):
if len(secret) != len(guess):
return False
for i in range(len(secret)):
if secret[i] != guess[i]:
return False
return True
This code is vulnerable. If the secret is "password" and the guess is "passwosd", the loop will run until the 7th character. The attacker, by measuring how long the function takes to return False, can infer how many characters matched. A faster return means fewer characters matched. Over many guesses, this can leak the secret.
To build a constant-time version, we need to ensure the comparison always takes the same amount of time, regardless of where the mismatch occurs. This means the loop must always run to completion, and we can’t use early exits.
Here’s a constant-time comparison using bitwise operations, which are generally executed in a fixed number of clock cycles by the CPU:
def compare_passwords_constant_time(secret, guess):
if len(secret) != len(guess):
return False
result = 0
for i in range(len(secret)):
# XORing bytes: result is 0 if bytes match, non-zero otherwise.
# Bitwise OR accumulates the non-zero results.
result |= ord(secret[i]) ^ ord(guess[i])
# If result is 0, all bytes matched. Otherwise, at least one mismatch.
# This comparison itself must also be constant time.
return result == 0
This revised function iterates through the entire length of both strings, performing a bitwise XOR operation for each pair of characters. The result variable accumulates any differences. Crucially, the loop always runs for len(secret) iterations, and the final result == 0 check also takes a fixed amount of time. An attacker measuring the execution time of compare_passwords_constant_time would get a consistent duration, regardless of whether the first character mismatches or the last.
The core problem constant-time code solves is information leakage through execution time. Many cryptographic operations, like key generation, decryption, or signature verification, involve comparing secrets. If an attacker can precisely measure the time it takes for these operations to complete, they can often deduce information about the secret key. This is the essence of a timing attack. For example, in RSA decryption, if the modular exponentiation implementation has branches that depend on the bits of the private key, an attacker measuring the time for many decryptions can infer the key bits.
The mental model for constant-time code is to eliminate any control flow or data-dependent operations that could alter the execution path or the number of operations performed. This includes:
- Branching (
if/else): Avoid conditional jumps that depend on secret data. - Loop Termination: Ensure loops always run for a fixed number of iterations, even if a match or mismatch is found early.
- Memory Access Patterns: Variable memory accesses (e.g., cache hits vs. misses) can also leak timing information.
- Arithmetic Operations: Some operations might take slightly longer depending on the operand values.
When implementing constant-time operations, especially for byte-by-byte comparisons, you need to be careful about the comparison itself. Directly returning secret[i] == guess[i] inside a loop that then returns False is the naive, vulnerable approach. Instead, you accumulate a "difference" value. For example, result |= (byte1 ^ byte2) ensures that result becomes non-zero if any byte pair differs, and the loop continues to the end. The final check return result == 0 is a single, constant-time operation.
Consider the memcmp function in C. A naive implementation might look like:
int memcmp_vulnerable(const void *s1, const void *s2, size_t n) {
const unsigned char *p1 = s1;
const unsigned char *p2 = s2;
while (n--) {
if (*p1 != *p2) {
return *p1 - *p2; // Early exit on mismatch
}
p1++;
p2++;
}
return 0; // All bytes matched
}
The vulnerable part is the if (*p1 != *p2) condition causing an early exit. A constant-time equivalent would ensure the loop always runs n times and accumulates differences. Many standard library implementations of memcmp are not constant-time for security reasons. Secure implementations often use bitwise tricks to achieve this. For instance, a common pattern is to compute a difference mask and then use bitwise operations to determine if any differences exist without branching.
int memcmp_constant_time(const void *s1, const void *s2, size_t n) {
const unsigned char *p1 = s1;
const unsigned char *p2 = s2;
int diff = 0;
while (n--) {
// XOR bytes and OR into diff. diff will be non-zero if any byte differs.
diff |= (*p1++ ^ *p2++);
}
// Convert diff to 0 if all bytes matched, or 1 if any byte differed.
// This transformation must also be constant time.
// For example, if diff is 0, (diff | -diff) is 0.
// If diff is non-zero, (diff | -diff) is non-zero and has the highest bit set.
// Shifting right by (sizeof(int)*8 - 1) isolates the sign bit, turning
// non-zero into 1 and zero into 0.
return (diff | -diff) >> (sizeof(int) * 8 - 1);
}
The (diff | -diff) >> (sizeof(int) * 8 - 1) part is a common trick to turn any non-zero diff into 1 and 0 into 0 in a constant-time manner, without branching. This ensures that the return value (0 for match, 1 for mismatch) is also determined in fixed time.
The most subtle way timing attacks can occur isn’t just in direct comparisons, but in how data structures are accessed. For example, a hash table lookup that iterates through a linked list of collisions will have a time dependent on the number of collisions, which can be influenced by an attacker’s input. Using a fixed-size array or a structure with guaranteed constant-time lookups (like a perfect hash function, though these are rare and complex) is crucial.