Firmware Security and the Importance of Constant-Time Programming (Part - 2)

Reproduced from - https://2wisebit.wordpress.com/2025/03/13/701/

Understanding Constant-Time String Comparison: A Deep Dive

Constant-time comparison of strings is an important security measure that helps maintain the consistent execution time for a string comparison operation, no matter what strings are being input. This supposedly minor detail goes a long way in avoiding timing attacks, which are a side-channel attack group that takes advantage of differences in execution time in order to glean sensitive information.

Why Constant-Time Comparison?

In typical string comparison, the operation tends to end as soon as a difference is encountered. The optimization, although effective in common usage, turns into a weakness in security-related situations. The duration for comparing two strings is directly proportional to the count of identical characters prior to the occurrence of the first difference. When the strings are equal, comparison takes the maximum time. When they have differences at the first character, it takes the least.

Constant-time comparison avoids this dependency. It ensures that the algorithm for comparison will always take the same amount of steps, irrespective of whether the strings are equal or not. It does this by comparing all the characters and adding up the results instead of short-circuiting at the first mismatch.

Importance of Constant-Time Comparison in Security

The major reason for constant-time comparison is to prevent timing attacks. Such attacks take advantage of the observation that various operations require different time periods to process on a computer. By monitoring these differences accurately, an attacker can deduce information about data being processed.

Following is an explanation of why this is essential in security:

Password Verification:

Consider a system that hashes a user-input password and compares it to a stored hash. In a non-constant-time comparison, an attacker can repeatedly try passwords, measuring the responses.

If the response time grows longer with each correctly input character, the attacker can guess the password character by character.

Constant-time comparison prevents this weakness by making the comparison take the same time every time, no matter what the input is.

Cryptographic Operations:

Cryptographic primitives typically consist of sensitive data comparisons, e.g., keys.

Information about the keys can be revealed through timing attacks, rendering the whole system insecure.

Implementations of constant time for cryptographic functions are therefore a must for avoidance of these types of attacks.

Other Sensitive Data:

All applications processing sensitive data like private keys, encryption keys, or authentication tokens should use constant-time comparison.

This serves to protect the attackers from deriving information regarding such secrets through timing attacks.

Example - Consider a non-constant-time string comparison

for (size_t i = 0; i < length; i++)
{
    if (a[i] != b[i]) {
        return 0; // Exit early if a difference is found
    }
}        

Variable Execution Time

• Data-Dependent Branching: The?if?statement introduces a branch that depends on the data. If a difference is found, the function exits early, leading to a shorter execution time for strings that differ early in their sequence.
• Variable Execution Time: The execution time varies based on where the first difference occurs, making it susceptible to timing attacks.

What Happens with Early Exit in String Comparison?

Timing attacks exploit variations in the execution time of a program to infer sensitive information, such as passwords or cryptographic keys. An attacker can measure the time taken by the comparison function to infer information about the strings being compared.

Example: Password Verification

Suppose an attacker is trying to guess a password by comparing their guesses to a stored hash. The comparison function exits early if a mismatch is found. The attacker can use the following steps to deduce the password:

1. Send a Guess: The attacker sends a guess (e.g., "passw") to the system.
2. Measure Execution Time: The attacker measures the time taken for the comparison function to return.
3. Analyze Timing Information: If the function returns quickly, the attacker knows that the guess differs from the actual password early on (e.g., at the first byte). If the function takes longer, the attacker knows that more bytes match before a mismatch is found.
4. Refine the Guess: Based on the timing information, the attacker refines their guess (e.g., "passwo", "passwor") and repeats the process.

Example Scenario

• Guess 1: "passw" (returns quickly) The function exits after the first byte, indicating that the first character is incorrect.
• Guess 2: "passwo" (takes slightly longer) The function exits after the sixth byte, indicating that the first five characters match.
• Guess 3: "passwor" (takes even longer) The function exits after the seventh byte, indicating that the first six characters match.

By observing the timing differences, the attacker can deduce that "passwor" is closer to the correct password than "passw" or "passwo". Over multiple attempts, the attacker can reconstruct the entire password.

How Constant-Time Comparison Works (Conceptual)

The secret to constant-time comparison is to prevent any conditional branching or premature termination based on the result of comparison. This can normally be done by:

Comparing all characters: Rather than terminating at the first mismatch, all characters of the strings are compared.

With bitwise operations: Bitwise operations like XOR can be employed to add the result of comparison without exposing the intermediate results.

Conditional statements avoidance: Conditional statements that would control the flow of execution depending on comparison outcomes are not used.

By following these conventions, constant-time comparison makes the execution time constant in effect, essentially foiling timing attacks.

int constant_time_compare(const char * a, const char * b, size_t length)
{
    volatile unsigned char result = 0;

    for (size_t i = 0; i < length; i++) {
        result |= a[i] ^ b[i];
    }

    // If result is 0, the strings are equal;
    // otherwise, they are not.
    return result == 0;
}        

Why is it Constant Time?

Fixed Number of Operations

The loop iterates over every byte of the input strings, from the first to the last, without any possibility of exiting early. The loop always executes?length?iterations, performing the same operations (XOR and OR) for each byte. This ensures that the number of operations is constant for a given input length.

No Data-Dependent Branching

There are no conditional branches within the loop that depend on the input data. This prevents variations in execution time based on the content of the strings.

Consistent Memory Access Patterns

The memory access pattern (reading each byte of the strings) is consistent and does not depend on the data, minimizing the risk of timing variations due to cache effects.

Improving the Implementation of constant time execution

Prefetching

Prefetching can be done using compiler-specific intrinsics or pragmas. This is architecture and compiler-dependent, so the implementation may vary.

for (size_t i = 0; i < length; i++)
{
        // Prefetch the next cache line
        if (i % 64 == 0) { // Assuming a cache line size of 64 bytes
            __builtin_prefetch( & a[i + 64], 0, 1);
            __builtin_prefetch( & b[i + 64], 0, 1);
        }

        result |= a[i] ^ b[i];
}        

Alignment

Ensuring alignment is typically done at the data allocation level. If you control the allocation of?a?and?b, you can use aligned memory allocation functions.

// Example of aligned allocation (outside the compare function)
char *aligned_alloc(size_t alignment, size_t size);
char *a = aligned_alloc(64, length); // Align to 64-byte boundary
char *b = aligned_alloc(64, length);        

Batch Processing

Process data in chunks that fit into the cache. This requires careful handling to maintain constant-time properties.

int constant_time_compare(const char *a, const char *b, size_t length) {
    volatile unsigned char result = 0;
    size_t chunk_size = 64; // Process in chunks of 64 bytes

    for (size_t i = 0; i < length; i += chunk_size) {
        for (size_t j = 0; j < chunk_size && (i + j) < length; j++) {
            result |= a[i + j] ^ b[i + j];
        }
    }

    return result == 0;
}        

Compiler Optimizations

Use compiler flags to control optimizations. This is done outside the code, typically in the build system or makefile.

gcc -fno-tree-vectorize -o compare compare.c        

-fno-tree-vectorize:

• Vectorization is a compiler optimization that attempts to execute multiple operations in parallel using vector instructions (e.g., SIMD instructions).
• -fno-tree-vectorize disables this optimization. Vectorization can lead to timing variations because the execution time of vector instructions can depend on the alignment and size of the data being processed.
• In a compare function, if the compiler was allowed to vectorize, and the input strings were of different sizes, or memory alignments, the timing would be different. This is very bad for secure compare.

Limitations and Challenges of Constant-Time Programming

Constant-time programming is a step in the right direction towards defense against timing attacks but also comes with some limitations and challenges. Constant-time implementations of algorithms need to consider performance, complexity, verification, and the compiler. These have been explained in detail below.

1. Overhead in Performance

Why Does Performance Overhead Arise

Constant-time programming tends to incur additional operations to prevent input data dependency on execution time. Some of them are:

• Early Exits Avoiding: The constant-time comparison operation must process all the input bytes even upon an early mismatch, which incurs more operations than non-constant-time algorithms.
• Uniform Memory Access: Constant-time algorithms uniformly access memory in order to evade cache-based timing attacks, which might reduce their efficiency.
• Elimination of Data-Dependent Branches: Data-dependent conditional branches are replaced with slower arithmetic or logical operations.

Trade-Off Between Performance and Security

• Security-Critical Applications: Constant-time programming performance overhead is usually acceptable in security-critical applications (e.g., password verification, cryptographic libraries).
• Performance-Critical Applications: The performance overhead can be prohibitively costly in performance-critical applications (e.g., high-frequency trading, real-time).

Minimizing Performance Overhead

• Selective Use: Use constant-time programming selectively on security-critical sections of code.
• Optimized Algorithms: Use algorithms with small performance overhead but constant-time execution.
• Hardware Acceleration: Leverage hardware capabilities (e.g., cryptographic accelerators) to reduce performance overhead.

2. Complexity

Why Constant-Time Code is Challenging

• Low-Level Programming: Constant-time programming might need low-level access to the code frequently, as with the help of bitwise operations, inline assembly, or compiler-specific attributes.
• Hidden Timing Variabilities: The variability in timing could be due to parameters such as the use of caches, instruction timing, or compiler optimizations, so it would not be easy to identify and remove.
• Fault-Prone: Constant-time code is harder to write than normal code. A benign bug (e.g., a data-dependent branch) still presents timing vulnerabilities.

Simplifying Complexity

• Code Reviews: Conduct formal code reviews to prevent any potential timing vulnerabilities.
• Best Practices: Code in constant-time with best coding principles, like avoiding data-dependent branches and constant memory access.
• Automated Tools: Employ automated tools to confirm constant-time properties in the code.

3. Verification

Why Verification is Difficult

• Hidden Timing Variabilities: Hardware components (e.g., branch prediction, cache) or compiler optimizations could cause timing variation and thus would be difficult to find.
• Manual Inspection: It is typically performed manually by inspecting machine or assembly code, and it is tedious and error-prone.

Bypassing Verification Issues

• Automated Tools: Employ tools to check for constant-time properties of the code.
• Testing: Run the program on the intended platform to check that it responds as needed in various situations.
• Formal Verification: Employ formal verification methods to prove that the program is constant-time.

4. Compiler Optimizations

Impact of Compiler Optimizations on Constant-Time Code

• Branch Elimination: Compilers may eliminate redundant branches, disturbing constant-time behavior.
• Loop Unrolling: Compiler loop unrolling may introduce timing variability.
• Instruction Reordering: Compilers may reorder instructions for performance enhancement, disturbing time consistency.
• Short-Circuiting: Compilers may short-circuit operations in advance under certain conditions, breaching constant-time constraints.

Preventing Compiler Optimizations

• Volatile Keyword: Use the volatile keyword to prevent the compiler from removing useful operations.
• Compiler Flags: Employ compiler flags to control optimizations (e.g., -O0 to disable optimizations or -fno-tree-vectorize to disable vectorization).
• Intrinsics: Employ intrinsics to compel specific instructions to be run.
• Inline Assembly: Employ inline assembly to compel target instructions to be run.
• Manual Inspection: Manually inspect the generated assembly or machine code to ensure constant-time properties are preserved.

Previously -

https://www.dhirubhai.net/pulse/firmware-security-importance-constant-time-part-1-anupam-datta-hpnwe