Provably fixing security problems can make a system unusable, while patching the system to protect from the latest security threat does not anticipate the vulnerabilities waiting around the corner. This statement is particularly true for side-channel attacks, which can be easily eliminated, however often with a prohibitively high performance penalty. For example, cache attacks can be prevented by disabling the cache, and timing attacks can be prevented by returning in constant time. Because of the high cost of eliminating side-channels, in practice some side-channel leakage is still tolerated, and one is faced with the problem of striking a balance between performance and security against such attacks.

In this talk, I will present a systematic approach for choosing a protection against timing attacks, on the example of cryptosystems based on discrete logarithms. Our model includes 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 fixed level of security. We obtain the optimal protection as an equilibrium in a game between the defender and the adversary. At the heart of the equilibrium computation are novel bounds for the probability of key recovery, which are expressed as a function of the applied protection and the attack strategy of a timing adversary.

We put our techniques to work in a case study in which we identify optimal protections for libgcrypt’s ElGamal implementation. We determine situations in which the optimal choice is to use a defensive, constant-time implementation and a small key, and situations in which the optimal choice is a more aggressively tuned (but leaky) implementation with a longer key.