International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
David Molnar
Matt Piotrowski
David Schultz
David Wagner
Download:
URL: http://eprint.iacr.org/2005/368
Search ePrint
Search Google
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
@misc{eprint-2005-12702,
  title={The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks},
  booktitle={IACR Eprint archive},
  keywords={implementation / side channels, countermeasures, PC-model},
  url={http://eprint.iacr.org/2005/368},
  note={Short version to appear in ICISC 2005. This is the long version. dmolnar@eecs.berkeley.edu 13130 received 18 Oct 2005, last revised 13 Dec 2005},
  author={David Molnar and Matt Piotrowski and David Schultz and David Wagner},
  year=2005
}