Tesis:
On the Security of Cache Algorithms
- Autor: CAÑONES MARTÍN, Pablo
- Título: On the Security of Cache Algorithms
- Fecha: 2019
- Materia: Sin materia definida
- Escuela: E.T.S DE INGENIEROS INFORMÁTICOS
- Departamentos: LENGUAJES Y SISTEMAS INFORMATICOS E INGENIERIA DE SOFTWARE
- Acceso electrónico: http://oa.upm.es/56259/
- Director/a 1º: KÖPF, Boris Alexander
- Resumen: Las memorias cachés son una componente importante de los ordenadores modernos ya que reducen la latencia al obtener datos de la memoria principal. Sin embargo, también son muy susceptibles a los ataques de canal lateral dado que un atacante que pueda medir el tiempo de ejecución de un programa que utiliza la caché puede obtener información acerca del patrón de acceso del programa a la memoria. En esta tesis nos centramos en los aspectos de seguridad de la caché, concretamente en el algoritmo de caché; la componente lógica que organiza la memoria almacenada en la caché y decide qué partes de la caché hay que vaciar cuando se debe almacenar nueva información. Nuestro objetivo es obtener resultados que den una idea de cómo de seguros son los algoritmos de caché actuales frente a los ataques de canal lateral y si existe un algoritmo de caché (o una clase de ellos) que sea predominantemente mejor en términos de seguridad. Proponemos dos medidas de seguridad orientadas a diferentes aspectos de la seguridad de los algoritmos de caché frente a tres tipos comunes de atacantes de caché, tiempo, traza y acceso, y obtenemos resultados sobre diversos algoritmos de caché. Las cotas superiores de seguridad de los algoritmos de caché se obtienen al centrarse en la ejecución en la que el algoritmo de caché filtra la mayor cantidad de información. Este análisis ofrece garantías de seguridad que son independientes de la ejecuición y por tanto da información sólo sobre el algoritmo de caché. Sin embargo, el uso de cotas superiores no es apropiado para comparar algoritmos de caché ya que no se puede garantizar que ambos algoritmos sean comparados en igualdad de condiciones. Obtenemos cotas superiores de la filtración para los tres tipos de atacantes y diferentes clases de algoritmos de caché. Una propiedad interesante de estos resultados es que son independientes de la porción concreta de memoria que usa un programa, únicamente dependen de la cantidad de memoria que debe ser almacenada en la caché. Para los atacantes de tiempo y traza obtenemos cotas superiores de filtración para una clase muy amplia de algoritmos de caché, los algoritmos basados en autómata. Incidentalmente demostramos que, para este análisis y para los atacantes de tiempo y traza, todos los algoritmos de caché filtran la misma cantidad de información. Para el atacante de acceso proponemos un nuevo modelo que captura mejor cómo este atacante obtiene información de la caché. El atacante de acceso no puede ver el contenido de la caché y debe sondarla, esto es, debe acceder partes de la memoria y comprobar si están o no almacenadas en la caché, con lo que modifica la configuración de la caché. Entonces, la seguridad de la caché frente al atacante de acceso se caracteriza por dos aspectos: (1) la cantidad de información sobre la víctima que puede ser absorbida por la caché y (2) la cantidad de información que puede ser en efectivamente extraída de la caché por el atacante. Definimos estas dos nociones y proponemos un algoritmo que calcula la extracción de información para cualquier algoritmo de caché. Utilizando este modelo para el atacante de acceso estudiamos una clase más pequeña de algoritmos de caché, los algoritmos de caché basados en permutaciones. Para estos algoritmos, obtenemos cotas superiores de filtración que varían dependiendo del algoritmo de caché en cuestión, contrariamente a lo que pasaba para los atacantes de tiempo y traza. Si además consideramos cachés con varios conjuntos independientes, comprobamos que la idea intuitiva de que varios conjuntos de caché deberían reducir la filtración no es necesariamente cierta. Aplicando nuestro algoritmo de extracción de información, mejoramos las cotas de seguridad del analizador estático CacheAudit para el atacante de acceso y analizamos la seguridad de diversos algoritmos criptográficos. El análisis de competitividad compara la filtración de dos algoritmos de caché para cualquier programa posible. Esto permite cuantificar cómo de diferentes dos algoritmos de caché son en términos de seguridad. Sin embargo, el análisis de competitividad siempre requiere comparar un algoritmo de caché con otro y no es apropiado para analizar individualmente la seguridad de los algoritmos de caché. Para el atacante de tiempo demostramos que la relación de competitividad para filtración es simétrica en los algoritmos de caché para cualquier pareja de algoritmos de caché basados en autómata. Esto implica que ningún algoritmo de caché domina a otro en términos de filtración de tiempo, lo cual es sorprendente dado que sí existen resultados de dominación en el caso de la eficiencia. Además, si nos restringimos a algoritmos de caché con control finito (comunes en implementaciones basadas en hardware) la relación de competitividad para filtración entre dos algoritmos de caché es o bien asintóticamente lineal o bien constante, no son posibles otros comportamientos. Para el atacante de acceso mostramos ejemplos de algoritmos de caché (concretamente LRU, FIFO y PLRU) que muestran que, para este atacante, sí existen relaciones de dominación, contrastando con el atacante de tiempo. ----------ABSTRACT---------- Cache memories are an important component of modern computers as they reduce the latency gap when retrieving data from main memory. However, they are also very susceptible to side channel attacks as an attacker who can measure the execution time of a program using the cache can obtain information about the memory access pattern of the program. In this thesis we address the security aspects of the cache, specifically the cache algorithm; the logical component that organizes memory stored the cache and decides which parts of the cache to empty when new data has to be stored. We aim to obtain results that give an idea of how secure current cache algorithms are against side channel attacks and if there is a cache algorithm (or a class of them) that is predominantly better in terms of security. We propose two measures of security aimed at different aspects of the security of cache algorithms under three common types of cache attackers, time, trace and accessbased attackers, and obtain results on several cache algorithms. Upper bounds on the security of cache algorithms are obtained by focusing on the execution where the cache algorithm leaks the most information. This analysis provides security guaranties that are independent of the execution and therefore gives information only about the cache algorithm. However, the use of upper bounds is not suited for comparing cache algorithms as it does not guaranty that both algorithms are fairly compared. We obtain upper bounds on the leakage for the three types of attackers and different classes of cache algorithms. An interesting property of all these results is that they are independent of the actual data a program uses, they only depend on the amount of memory that has to be stored in the cache. For the time and trace-based attackers we obtain upper bounds for the leakage for a large class of cache algorithms, automata-based cache algorithms. Incidentally we show that, under this analysis and for the time and trace-based attackers, all cache algorithms leak the same amount of information. For the access-based attacker we propose a new model that better captures how this attacker retrieves information from the cache. The access-based attacker can not see the actual content of the cache but has to probe it, that is, has to access data and check whether or not it is stored in the cache, thus modifying the configuration of the cache. Then, the security of the cache against an access-based attacker is characterized by two aspects: (1) the amount of information about the victim that can be absorbed by the cache and (2) the amount of information that can effectively be extracted from the cache by the attacker. We define these two notions and propose an algorithm to compute the information extraction for any cache algorithm. Using this model for the access-based attacker we study an smaller class of cache algorithms, permutation-based cache algorithms. For those algorithms, we obtain upper bounds on the leakage that vary depending on the cache algorithm in question, contrary to what happened for the time and trace-based attacker. When considering set-associative caches we show that the intuitive idea that several cache sets should reduce the leakage is not necessarily true. Additionally, we apply our algorithm of information extraction to improve the security bounds of the CacheAudit static analyzer for the case of the accessbased attacker and analyze the security of several cryptographic algorithms. Competitive analysis compares the leakage of two cache algorithms on every possible program. This allows to quantify how different two cache algorithms are in terms of security. However, competitive analysis always requires to compare one cache algorithm with respect to another and it is not suited to analyze the security of cache algorithms individually. For the time-based attacker we show that the leak competitiveness relationship is symmetric in the cache algorithms for every pair of automata-based cache algorithms. This implies that no cache algorithm dominates another in terms of timing leakage, which is surprising since dominance results do exist in the case of performance. Moreover, when restricted to cache algorithms with finite control (common in hardware-based implementations) the leak competitiveness relationship between two cache algorithms is either asymptotically linear or constant, no other shapes are possible. For the access-based attacker, we show examples of cache algorithms (LRU, FIFO and PLRU) that show that, for this attacker, dominance relationships do exist, in contrast to the time-based attacker.