On the security of cache algorithms

Resumen

Las memorias cachés son una componente importante de los ordenadores modernos ya que reducen la latencia al obtener datos de la memoria principalSin 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 deprograma 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 acentrarse 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 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. 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. Además, 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 canti dad 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é. 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.