Paper 2005/368

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

David Molnar, Matt Piotrowski, David Schultz, and David Wagner

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.

Note: Current posting is a preliminary draft. Comments welcomed.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Short version to appear in ICISC 2005. This is the long version.
Keywords
side channelscountermeasuresPC-model
Contact author(s)
dmolnar @ eecs berkeley edu
History
2005-12-13: revised
2005-10-19: received
See all versions
Short URL
https://ia.cr/2005/368
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/368,
      author = {David Molnar and Matt Piotrowski and David Schultz and David Wagner},
      title = {The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2005/368},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/368}},
      url = {https://eprint.iacr.org/2005/368}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.