The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks

David Molnar, Matt Piotrowski, David Schultz, David A. Wagner

TL;DR

This paper introduces the "program counter security model" to formalize and defend against control-flow side-channel attacks, which exploit information leaked through the sequence of executed instructions. They present an automatic source-to-source transformation to make C code resistant to these attacks, along with a static checker to verify the security of the transformed assembly code, demonstrating practical performance overheads.

What Problem Does This Paper Address?

Side-channel attacks, such as timing and power analysis, pose a significant threat to the security of cryptographic implementations. These attacks exploit unintended information leakage from the physical execution of code, often revealing secret keys. While many ad-hoc defenses exist, they are often application-specific and lack formal security guarantees. This paper addresses the need for a principled, general, and automatic approach to defend against a specific class of side-channel attacks: those that leak information through the program's control flow, specifically by observing the sequence of program counter values.

Methods

The core of the paper is the program counter (PC) security model. This model defines a "transcript" that an adversary can observe, consisting solely of the sequence of program counter values during execution. A program is considered PC-secure if an adversary observing this transcript cannot deduce any information about secret inputs.

To achieve PC-security, the authors propose:

  • Dynamic Testing: A tool to find potential vulnerabilities by detecting key-dependent variations in program execution traces (specifically, line execution counts).
  • Source-to-Source Transformation: A generic algorithm that takes C code and transforms it into a PC-secure version. This transformation ensures that both branches of conditional statements are executed, but only the result of the "correct" branch is retained, effectively masking data-dependent control flow. Loops are handled by ensuring they always execute a fixed, known number of iterations, discarding results from iterations that wouldn't have occurred in the original program.
  • Static Checker: A tool that analyzes x86 assembly code generated by a compiler to verify that the PC-security property is preserved. This is crucial because compilers can introduce conditional branches that violate the transformed code's security.

Datasets

Not discussed in the paper. The paper focuses on theoretical models and applies its methods to existing implementations of cryptographic algorithms like IDEA, RC5, and modular exponentiation.

Key Insights and Ideas

  • Formalizing Control-Flow Leakage: The PC security model provides a clean, formal way to reason about a significant class of side-channel attacks that were previously addressed with ad-hoc methods.
  • "Always Execute Both Branches" Principle: The core idea of the transformation is to execute both branches of a conditional statement, masking the actual control flow. This is a powerful and general technique for eliminating PC-based side channels.
  • Hardware-Software Contract: The PC model can be viewed as a contract between hardware and software. The hardware guarantees to leak only PC values, and the software (via transformation) ensures that this leakage doesn't compromise security.
  • Practicality of Automatic Transformation: The paper demonstrates that automatic transformation can achieve PC-security with manageable performance and code size overheads, making it a viable option for many applications.
  • Compiler Challenges: The need for a static checker highlights that compiler optimizations can inadvertently reintroduce side-channel vulnerabilities, underscoring the importance of verification.

Key Results

  • The proposed PC security model captures timing attacks, simple power analysis, and error disclosure attacks.
  • The dynamic testing tool successfully identified vulnerabilities in implementations of IDEA, RC5, binary modular exponentiation, and the lsh implementation of the SSH protocol.
  • The automatic source-to-source transformation resulted in code with a performance overhead of at most 5x and a stack space overhead of at most 2x compared to optimized, untransformed code.
  • A hand-optimized transformation for IDEA's multiplication routine achieved a 2x slowdown.
  • The static checker successfully identified unsafe constructs introduced by a compiler (GCC) that violated PC-security, demonstrating its utility.

Limitations and Future Work

  • Scope of Attacks: The PC security model does not cover all side-channel attacks, particularly data-dependent ones like DPA or cache timing attacks.
  • Compiler Dependence: While the Intel compiler was used for performance tests due to its lack of conditional jumps for logical negation, other compilers might require modifications to the transformation or checker.
  • Performance Overhead: While manageable, the overhead might still be too high for extremely performance-sensitive applications.
  • More Transcript Models: The authors suggest exploring other transcript models to capture different types of leakage and applying their methods to these models.
  • "Right" Contract: Finding the optimal "contract" between hardware and software for side-channel security remains an open problem.
  • Handling Pointers: The current IncredibL model and transformation do not explicitly handle pointers, which can introduce data-dependent memory access patterns and cache behavior.
  • Error Handling: While the transformation can be applied to programs with potential runtime errors, the paper suggests that better error flagging and handling after execution would be beneficial.

Summary updated

Abstract

We introduce new methods for detecting control-flow side channel attacks, transforming C source code to eliminate such attacks, and checking that the transformed code is free of control-flow side channels. We model control-flow side channels with a program counter transcript, in which the value of the program counter at each step is leaked to an adversary. The program counter transcript model captures a class of side channel attacks that includes timing attacks and error disclosure attacks. We further show that the model formalizes previous ad hoc approaches to preventing side channel attacks. We then give a dynamic testing procedure for finding code fragments that may reveal sensitive information by key-dependent behavior, and we show our method finds side channel vulnerabilities in real implementations of IDEA and RC5, in binary modular exponentiation, and in the lsh implementation of the ssh protocol. Further, we propose a generic source-to-source transformation that produces programs provably secure against control-flow side channel attacks. We implemented this transform for C together with a static checker that conservatively checks x86 assembly for violations of program counter security; our checker allows us to compile with optimizations while retaining assurance the resulting code is secure. We then measured our technique's effect on the performance of binary modular exponentiation and real-world implementations in C of RC5 and IDEA: we found it has a performance overhead of at most 5X and a stack space overhead of at most 2X. Our approach to side channel security is practical, generally applicable, and provably secure against an interesting class of side channel attacks.
BibTeX
@article{molnar2005program,
  author = {David Molnar and Matt Piotrowski and David Schultz and David A. Wagner},
  title = {{The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2005},
}

Loading related content...

Figure