Departamento de Computación

En estos días, la seguridad de la información contenida en dispositivos de almacenamiento masivo como discos duros, memorias flash, CDs y DVDs ha ganado mucha importancia. Dicha importancia se refleja en las recientes actividades de estandarización y la gran variedad de esquemas criptográficos propuestos para dar solución a este problema. En esta tesis tratamos varios temas relacionados con este problema. Nuestro principal interés está en los medios de almacenamiento tales como discos duros y memorias flash que están organizados en sectores. En los próximos párrafos se resumen los diferentes problemas que fueron abordados a lo largo de esta tesis. Hay un consenso entre los investigadores de que una clase de algoritmos criptográficos conocidos en inglés como Teakable Enciphering Schemes (TES), pueden ser usados para cifrar discos duros. Como primera contribución de esta tesis presentamos el primer reporte con evidencia experimental acerca de la eficiencia para casi todos los TES existentes. Dicho reporte está basado en implementaciones optimizadas en diversas familias de dispositivos de hardware reconfigurable. Mientras desarrollábamos las implementaciones encontramos algunos problemas algorítmicos y combinatorios muy interesantes. Presentamos soluciones a dichos problemas, que pueden ser de un interés más amplio en otros contextros. Así mismo proponemos algunos esquemas novedosos que resultan ser adecuados para la resolución de este problema. Entre otros, proponemos un nuevo TES llamado STES (por sus siglas en inglés provenientes de Small TES) el cual comparado con los TES existentes fue diseñado con una filosofía diferente. El objetivo de diseño de STES es de hacerlo apto para cifrar medios de almacenamiento disponibles en dispositivos restringidos en términos de área y consumo de potencia. STES está construido con primitivas criptográficas que al ser implementadas ocupan pocos recursos de hardware y consumen poca potencia. Además demostramos formalmente que STES provee la seguridad necesaria para la aplicación de cifrado de disco y también presentamos datos acerca del rendimiento usando dos familias diferentes de FPGAs que son apropiados para implementaciones orientadas al bajo consumo de potencia. El rendimiento de STES en términos de tasa de procesamiento de datos y consumo de potencia es muy alentador.

Abstract

Security of data stored in bulk storage devices like hard disks, flash memories, CDs and DVDs has gained a lot of importance in the current days. The importance of this topic is reflected in recent standardizing activities and a variety of cryptographic schemes proposed in the last decade as a solution to this problem. In this thesis we address several issues related to the problem of encryption of stored data. Our main focus is on block oriented storage medias like hard disks and flash memories. In the following paragraphs we summarize the different problems that we address in this thesis along with our contributions. There has been a consensus among researchers that a class of cryptographic algorithms called tweakable enciphering schemes (TES) can be used in the application of encrypting hard disks. In the last decade there have been many different proposals of TES each using different philosophies of construction. As a first contribution of this thesis we provide the first experimental performance data for (almost) all existing TES. The reported performance data is based on optimized implementations of the schemes on several families of reconfigurable hardware. While working towards efficient implementations of existing schemes we encountered some very interesting algorithmic and combinatorial problems. We present solutions to these problems also in this thesis, and they can be of a more broad interest. We also propose some new schemes suitable for the problem. Among others, we propose a new TES called STES (Small TES) which is designed using a different philosophy compared to the other existing TES. The design goal of STES is to make it suitable for encrypting storage provided in devices which are constrained in terms of power consumption and area. STES uses cryptographic primitives which when implemented would have a very low hardware and power footprint in a novel way. We formally prove that STES provides adequate security for the application and also provide performance data in two classes of FPGAs which are suitable for low-power implementations. The performance of STES both in terms of throughput per area and power consumption is very encouraging. In real life, all computations run in some physical device. When a physical device performs some computation it always emit or leak certain information. This leakage can be in the form of timing information, electromagnetic radiation, power consumption information or even sound. In the case of cryptographic computations, these leakages if measured properly can be used to gain important information regarding secret quantities handled by the computational process. Analyzing cryptographic implementations in the light of these leakages is collectively called side channel analysis. We provide some preliminary side channel analysis on some TES. To our knowledge no such analysis has been done before on TES. TES are length preserving schemes, in the sense that the length of the cipher text produced by a TES is same as that of the plain text. This property of length preservation has been considered very important for an encryption scheme to be suitable for encrypting hard disks. In this thesis we contest this well established notion, and argue why it may be possible to use encryption schemes which are not length preserving. We argue about this taking in consideration the structure of modern day hard disk. Finally we propose a new scheme called BRW-Counter mode (BCTR) which is not length preserving but provides the same security of that of a TES. We also present an optimal hardware architecture for BCTR and show that BCTR would outperform all other TES in terms of throughput. Finally, we address the problem of securing backups by use of a new cryptographic scheme. We propose a cryptographic primitive which we call as the double cipher text mode (DCM) and discuss the general syntax and security definition of a DCM. We provide two efficient constructions of DCM which we name as DCMG and DCM-BRW. We argue why DCM would be suitable for the application of secure backup.