Learning secrets and models from execution time

In this dissertation we study some of the problems arising on computer systems that leak information through execution time. We study several instances of how these leaks can be used to both learn secrets—of a confidential computation—and models—of an underlying component—, and we provide examples that violate previous assumptions about systems’ security or about the attackers’ capabilities. In particular, we study time leakage under three different scenarios, providing multiple independent contributions in each of them: • First, we show that event-driven software systems are susceptible to sidechannel attacks. The key observation is that event loops form a resource that can be shared between mutually distrusting programs. Hence, contention of this resource by one program can be observed by the others through variations in the time the latter processes take for dispatching their events. We exploit two different shared event loops in the Chrome web browser, and use the information obtained in three different attacks: for web page fingerprinting, for keystroke detection, and for a cross-origin covert channel. • Then, we show that our contributions are both theoretical and practical. On the theoretical side, we formalize the problem of finding minimal eviction sets, a key primitive for several microarchitectural attacks, and devise novel algorithms that improve the state-of-the-art from quadratic to linear. On the practical side, we perform a rigorous empirical analysis that exhibits the conditions under which our algorithms succeed or fail. • Finally, we present a practical end-to-end solution for inferring deterministic cache replacement policies using off-the-shelf techniques for automata learning and program synthesis. The enabling contribution is a chain of two abstractions: a clean interface to the hardware cache replacement policies based on timing measurements on a silicon CPU; and a mapper that exposes a membership oracle to the cache replacement policy abstracting away the details regarding cache content management. The results of this thesis constitute an evidence that better models and quantification methods, for both software and hardware systems, are required in order to reason about the soundness and trade-offs of security countermeasures; and provide a basis for principled countermeasures against, or paths for further improving the efficiency of, several side channel attacks. ----------RESUMEN---------- La presente disertación estudia los problemas surgidos en sistemas informáticos que filtran información a través del tiempo de ejecución. El trabajo se centra en cómo dichas fugas pueden ser utilizadas para aprender secretos—de computaciones confidenciales—o modelos—de los componentes subyacentes—, proporcionando ejemplos que violan suposiciones previas sobre la seguridad de los sistemas o sobre los límites de un atacante. El estudio se centra en la fuga de información a través del tiempo de ejecución en tres escenarios distintos, aportando múltiples contribuciones independientes en cada uno de ellos: • Primero, se muestra cómo los sistemas orientados a eventos son susceptibles a ataques laterales. La observación clave es que los bucles de eventos forman un recurso compartido entre varias partes desconfiadas. De este modo, la contención de este recurso por un programa puede ser observada por otros a través de variaciones en el tiempo de procesamiento del proceso de control. En concreto, se explotan dos bucles de eventos compartidos en el navegador Chrome, y se usa la información obtenida en tres ataques distintos para: identificar paginas web, detectar pulsaciones de teclado del usuario, y transmitir información entre páginas de distinto origen. • Después, se demuestra que las contribuciones de esta disertación son tanto teóricas como prácticas. En lo teórico, se formaliza el problema de encontrar conjuntos mínimos de desalojo en caches, un paso clave para varios ataques microarquitecturales; y se presenta un nuevo algoritmo que mejora el estado del arte desde coste cuadrático a lineal. En la práctica, llevamos a cabo un riguroso análisis empírico que exhibe las condiciones bajo las cuales el algoritmo tienen o no éxito. • Finalmente, se presenta una solución práctica y completa para aprender políticas de reemplazamiento de caches deterministas utilizando técnicas de aprendizaje de autómatas y síntesis de programas. La contribución clave es una cadena de dos abstracciones que expone un oráculo a la política de reemplazamiento de la caché, basándose únicamente en los tiempos de acceso a memoria de la CPU. Los resultados de esta tesis constituyen una evidencia de que se requieren mejores modelos y métodos para evaluar tanto la seguridad de los sistemas informáticos como la de las medidas contra ciberataques; y establecen una base para: definir contramedidas formales antes, y mejorar la eficiencia de, varios ataques laterales