IMDEA Software Institute Madrid
Title : Rational Protection Against Timing Attacks
Building: E1 5 (MPI-SWS), Room 0.02
Timing attacks can effectively recover keys from cryptosystems. While
they can be defeated using constant-time implementations, this defensive
approach comes at the price of a performance penalty. One is hence
faced with the problem of striking a balance between performance and
security against timing attacks.
This talk presents a game-theoretic approach to the problem, for the case of
cryptosystems based on discrete logarithms. Namely, we identify the
optimal countermeasure configuration as an equilibrium in a game between
a resource-bounded timing adversary who strives to maximize the
probability of key recovery, and a defender who strives to reduce the
cost while maintaining a certain degree of security. The key novelty in
our approach are bounds for the probability of key recovery, which are
expressed as a function of the countermeasure configuration and the
attack strategy of the adversary.
We put our techniques to work for a library implementation of ElGamal.
A highlight of our results is that we can formally justify the use of an
aggressively tuned but (slightly) leaky implementation over a defensive
constant-time implementation, for some parameter ranges. The talk
concludes with an outlook on how similar analyses can be performed
automatically and for more general classes of systems.