  Constant-time programming is a widely deployed approach to harden
cryptographic programs against side channel attacks. However, modern processors
violate the underlying assumptions of constant-time policies by speculatively
executing unintended paths of the program.
  In this work, we propose Cassandra, a novel hardware-software mechanism to
protect constant-time cryptographic code against speculative control flow based
attacks. Cassandra explores the radical design point of disabling the branch
predictor and recording-and-replaying sequential control flow of the program.
Two key insights that enable our design are that (1) the sequential control
flow of a constant-time program is constant over different runs, and (2)
cryptographic programs are highly looped and their control flow patterns repeat
in a highly compressible way. These insights allow us to perform an offline
branch analysis that significantly compresses control flow traces. We add a
small component to a typical processor design, the Branch Trace Unit, to store
compressed traces and determine fetch redirections according to the sequential
model of the program. Moreover, we provide a formal security analysis and prove
that our methodology adheres to a strong security contract by design. Despite
providing a higher security guarantee, Cassandra counter-intuitively improves
performance by 1.77% by eliminating branch misprediction penalties.
