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

Reproduced from - https://2wisebit.wordpress.com/2025/03/11/firmware-security-and-the-importance-of-constant-time-programming-part-1/

Introduction

Low-level software that communicates with hardware directly in the form of firmware is a critical element of modern computing platforms. Firmware initializes hardware, handles system resources, and delivers a secure environment for operating systems and applications. Firmware is the attack point of first contact, however, as it sits on a privileged plane within system design. Malicious firmware causes havoc in the guise of unauthorized access, data exfiltration, and complete system compromise.

The most dangerous firmware security attack would be a timing attack. Timing attacks utilize timing differences between actions to steal sensitive information like cryptographic keys or passwords. Timing attacks are more dangerous for firmware because they can evade normal security actions and attack the system core.

Constant-Time Programming Principles

Secret-Independent Resource Usage:

The secret to coding constant-time is that secret information should not impact the program's resource usage. This involves avoiding data-dependent branches, memory access, and variable-time instructions.

Avoiding Data-Dependent Branches:

Secret values should not be placed in conditional statements since this will cause different execution paths and varying timing.

Consistent Memory Access:

Secret values should not dictate memory addresses since this will result in cache timing attacks.

Avoiding Variable-Time Instructions:

Instructions such as division, whose execution time can vary depending on the input, must not employ secret values.

Challenges in Firmware Contexts

Hardware-Specific Leakage

Timing variations from microarchitectural features (e.g., interrupts, DMA) may not be captured at the LLVM level.

Legacy Code & Efficiency

Older firmware codebases may use non-constant-time algorithms for speed.

A program is constant-time if the product program is safe - no missed vulnerabilities.

Considerations for Constant-Time Implementations

Compiler Optimizations

Compiler optimizations may introduce shortcuts or branches that destroy constant-time behavior. Volatile or inline assembly can reduce this, but assembly coding offers more control.

Cache Effects

Even with a constant-time algorithm, cache effects can introduce timing differences. Access patterns must be regular to reduce these effects.

Architecture-Specific Behavior

Instruction timings can differ between architectures, so testing on the target architecture is important.

Security Audits

Any implementation to be used for security reasons should be audited and tested rigorously to confirm that it has the desired security properties.

Importance of Evading Data-Dependent Conditionals

Deterministic Execution Path

In constant-time implementation, the control flow should be identical for every possible input data. This means that the sequence of instructions being executed should be the same regardless of the input values.

Preventing Timing Attacks

Timing attacks exploit the variations in the execution time in order to learn something about data being processed. Constant-time implementations make the execution time independent for all inputs with the same size, making it impossible for an attacker to acquire useful information via timing analysis.

Compiler Optimizations and How They Affect Constant-Time Execution

1. Branch Elimination

Impact of Branch Elimination on Constant-Time Execution

Definition: Compilers tend to optimize code by removing branches that they identify as unnecessary. For instance, if a compiler can conclude that a particular condition is always false or always true, the branch can be removed entirely.

Effect: In constant-time code, this can cause removal of operations that are meant to be performed unconditionally, and therefore violate the constant-time property. For example, a branch that tests for equality and exits early may be optimized away, producing variable running times.

Preventing Branch Elimination

Volatile Usage: Using variable declarations as volatile tells the compiler that the value of the variable may change at any time, which prevents optimizations like branch elimination.

Inline Assembly: Inline assembly allows programmers to embed special assembly instructions in C code, providing greater control over the exact instructions executed and preventing unwanted optimizations from occurring.

2. Loop Unrolling

How Loop Unrolling Affects Constant-Time Execution

Definition: Loop unrolling is an optimization technique where the compiler unrolls the loop body multiple times to reduce the overhead of loop control instructions.

Effect: Although this is helpful in increasing performance, it also causes variations in the run time if the loop being unrolled has operations or branches that are data-dependent. As an example, unrolling a loop handling sensitive data may provide different execution paths depending on the data, and this violates the constant-time property.

Mitigating Loop Unrolling

Compiler Flags: Utilize compiler flags to manage levels of optimization. For instance, using GCC, you can use -O2 to allow optimizations without out-of-control loop unrolling.

Manual Unrolling: Unroll loops manually so that each iteration executes identical operations irrespective of the data.

3. Short-Circuiting

How Short-Circuiting Affects Constant-Time Execution

Definition: Short-circuiting optimizations are done by compilers, where certain operations are skipped if the result can be established in advance. This is acceptable with logical operators && and ||.

Effect: These optimizations result in early exit or bypassing operations, which have variable timings. For instance, a short-circuited logical AND could bypass the second operand in case the first one is false, which yields timing variations.

Mitigating Short-Circuiting

Avoid Logical Operators: Instead of using logical operators, use bitwise operations to force all operands to be evaluated.

Volatile Usage: Use the volatile keyword for variable declarations to avoid the compiler optimizing away required operations.

4. Instruction Selection

How Instruction Selection Affects Constant-Time Execution

Definition: Compilers select a sequence of machine instructions depending on target architecture and optimization level. Instructions take different amounts of time to execute, which may influence the uniformity of execution time of code.

Impact: For example, a compiler would select a quicker but nonuniform-time instruction for a calculation involving varying execution times which could be potentially utilized by timing attacks.

Prevention through Instruction Selection

Inline Assembly: Employ inline assembly to be able to control explicitly executed instructions and make sure that they have known execution times.

Compiler Flags: Employ compiler flags to manage instruction selection and rule out variable-time instructions. As an example, employing GCC, you can utilize -fno-tree-vectorize to turn off vectorization, which provides timing variability.

5. Compiler Optimizations Mitigation

Volatile Usage

Definition: Making variables volatile informs the compiler that the value of the variable may change at any instant and hence avoids certain optimizations such as storing the value of the variable in a register.

Application: Use volatile to hold secret data in variables or carry out sensitive operations so that operations are carried out as planned.

Inline Assembly

Definition: Inline assembly enables programmers to insert special assembly instructions directly into C code.

Application: Utilize inline assembly on critical pieces of code to provide explicit control of the instructions as well as how they are being executed, and minimize the chance of unintended optimizations.

Compiler Flags

Definition: Compilers provide flags that tend to control the levels of optimizations.

Application: Utilize flags such as -O0 to disable most optimizations or special flags to disable specific types of optimizations, like branch prediction or loop unrolling.

Assembly Coding

Definition: To write most important segments of code in assembly allows for maximum control over running.

Use: For the most important segments of code, try writing in assembly to guarantee that the specific sequence of instructions runs with no input from the compiler.

Cache Impact on Constant-Time Algorithms

• Data Access Pattern: A constant-time algorithm accesses data in a consistent and anticipatory pattern in order to limit cache misses as well as fluctuations in timing.
• Spatial and Temporal Locality: Spatial locality is the proximity of accessing the nearby locations in memory. Temporal locality is the repetition over a short timeframe of accessing similar locations in the data.
• Cache Contention: Cache contention arises when several processes or threads vie for cache space, resulting in cache evictions and higher cache misses.

Mitigating Cache Effects

• Consistent Access Patterns: Structure algorithms to access memory in a consistent pattern, irrespective of the input data.
• Data Alignment: Align data structures to the boundaries of cache lines to minimize the number of cache lines accessed and enhance cache efficiency.
• Prefetching: Employ hardware or software prefetching to preload the data into the cache ahead of time.
• Cache-Aware Programming: Consider the cache structure and design data structures and algorithms for optimal utilization of the cache hierarchy.
• Testing and Profiling: Employ profiling software to examine the cache behavior and determine regions in which cache influence can introduce temporal variations.

Architecture-Specific Factors Influencing Timing

• Instruction Timing Variability: Different execution time for the same instruction on a different architecture.
• Pipeline and Superscalar Execution: Pipelining and superscalar are utilized by next-generation CPUs to execute multiple instructions in parallel.
• Branch Prediction and Speculative Execution: Branch prediction is widely utilized to predict the branch target with multiple paths by CPUs.
• Cache Architecture: The cache memory size, structure, and policies can differ between architectures.
• Patterns of Memory Access: The architecture's memory hierarchy, i.e., RAM and cache, can affect the timing of memory access.

Influence on Constant-Time Attacks

• Instruction Timing Exploitation: Attackers use variations in instruction timing to make assumptions about data being processed.
• Branch Prediction Side Channels: When a constant-time algorithm has, even by chance, data-dependent branches, the attackers use the branch prediction behavior to make guesses.
• Cache Timing Attacks: Cache timing attacks attack the time of reading memory data.
• Architecture-Specific Vulnerabilities: There are architectures that have some side effects or weaknesses and could be vulnerable in the case of timing attacks.

Minimizing Architecture-Specific Timing Variations

• Target Architecture Testing: To ensure if a constant-time algorithm actually executes in constant time, it needs to be tested on the target architecture.
• Portable Libraries: Use portable and thoroughly tested cryptographic and security libraries to produce constant-time behavior across different architectures.
• Architecture-Specific Optimizations: Use architecture-specific optimizations for balanced performance.
• Profiling and Analysis: Use profiling tools to profile your code's run time on the target architecture.
• Assembly Writing: In the most important parts of your code, use assembly writing to have explicit control of the instructions and how they get executed.

Maximizing Spatial and Temporal Locality

Spatial Locality

• Definition: Spatial locality refers to the property of a program to access neighboring data locations in memory which are close in physical location.
• Maximizing Spatial Locality:
• Reuse Data: Structure algorithms to reuse data that has already been loaded into the cache.
• Loop Nesting: Organize nested loops to maximize the reuse of data in the innermost loop.
• Cache-Friendly Algorithms: Design algorithms that naturally exhibit high temporal locality.

Temporal Locality

• Definition: Temporal locality is the property of a program in reusing the same memory locations over and over again within a small time interval.
• How to Optimize Temporal Locality:

Applying These Principles with Constant-Time Algorithms

• Periodic Access Patterns: Make the access pattern periodic and input-data independent.
• Exclude Data-Dependent Branching: Avoid data-dependent branching because it creates non-periodic access patterns.
• Profiling and Optimization: Profiling can be used to track cache performance and determine where spatial locality and temporal locality must be improved.
• Algorithm Design: Select algorithms whose good locality is inherent.

Next - Deep dive with constant time programming with example