La confidencialidad de la información es un requisito crucial en muchas aplicaciones, donde los datos viajan a través de medios inseguros como el Internet. Hoy en día muchos esquemas de cifrado utilizados en estas aplicaciones, basan su seguridad en suposiciones no demostrables. Dichas suposiciones se refieren a la dificultad computacional de ciertos problemas matemáticos, para los cuales no se conocen algoritmos eficientes que los resuelvan; por tanto, son utilizadas para garantizar la seguridad de los esquemas de cifrado. Debido a que el nivel de conocimiento actual no nos permite aseverar la validez de tales suposiciones, no hay una razón sólida para creer que estos esquemas permanecerán seguros en el futuro. Además, la seguridad brindada por los esquemas actuales es llamada computacional, pues sólo se consideran adversarios con poder de cómputo "razonable" que pueden vulnerar su seguridad. Por tanto, la seguridad computacional no considera adversarios con capacidad de cómputo ilimitado. La alternativa a la seguridad computacional es la denominada seguridad teórica de la información. En sistemas de este tipo, la seguridad es garantizada sin suposiciones sobre la dificultad computacional de cualquier problema matemático o la capacidad de cómputo del adversario. Por tanto, son conocidos como sistemas perfectamente seguros. A pesar que estos esquemas proveen el nivel más alto de seguridad, no son prácticos. Esto se debe a que el tamaño de la llave en bits debe ser igual al tamaño en bits del mensaje, y además se debe utilizar una nueva llave por cada mensaje. El modelo de acceso limitado propuesto por Michael Rabin, describe un cripto-sistema demostrablemente seguro sin suposición alguna en la capacidad de cómputo del adversario. El objetivo del modelo es superar las limitantes de los esquemas perfectamente seguros. El modelo supone la existencia de una fuente de aleatoriedad distribuída la cual es una red de miles de computadoras dispersas alrededor del mundo, a la que el adversario posee un accesso limitado. Cada computadora genera, almacena y actualiza páginas aleatorias, las cuales son llamadas Page Server Nodes (PSNs). Así, dos usuarios que desean comunicarse, hacen uso de una llave inicial k y seleccionan aleatoriamente los mismos PSNs descargando el mismo conjunto de páginas de los servidores. Dado que algunas páginas descargadas pueden ser alteradas, los usuarios utilizan un mecanismo de reconciliación para determinar cuales páginas mantienen en común. Posteriormente, esta aleatoriedad es empleada para comunicarse mediante one-time pads. En esta tesis, describimos de manera pretesisgraduados/2010/resumenReneHenriquez.htmlcisa una implementación práctica de un esquema de cifrado en el modelo de acceso limitado. En ella mostramos modificaciones sobre una implementación previa de tal esquema, las cuales proveen mejoras en componentes del modelo como el protocolo de reconciliación de páginas y la construcción de la llave inicial k. Además, se sugieren los valores para varios parámetros a fin de lograr una implementación práctica y se discute la seguridad del esquema. Asimismo, presentamos el diseño de un generador de números aleatorios requerido por el modelo y finalmente presentamos los detalles de nuestra implementación.
Abstract
Secrecy of data is an important requirement in many application areas where data travels through insecure channels such as the Internet. Now-a-days, most of the existing encryption schemes used for practical applications rely on un-proven assumptions. These assumptions refer to the computational hardness of some mathematical problems for which there is no knowledge of efficient algorithms to solve them. These assumptions are used to derive security. But given our current state of knowledge nobody is able to prove the validity of these assumptions. Thus, there is no firm reason to believe that these encryption schemes which are based on un-proven assumptions will remain secure forever. Moreover, the security that modern encryption schemes guarantees is computational in nature, i.e., they only consider adversaries with "reasonable" computational power for breaking the security of these crypto-systems. Thus, computational security does not rule out the success of an adversary in breaking a system if (s)he is given unlimited computational ability. The alternative to computational security is what is known as information theoretic security. In an information theoretically secure system, security is guaranteed without any assumption regarding computational hardness of any mathematical problem or the computational power of an adversary. Thus, they are rightly called perfectly secret systems. Even though these schemes provide the highest level of security, they are not practical. This is because the number of necessary key bits is the same as the number of bits in the message, and also one needs to use a different key for each message. The limited access model proposed by Michael Rabin, describes a crypto-system which is provably unbreakable without any assumption on the computational power of an adversary. The aim of this model is to overcome the inherent drawbacks encountered in perfectly-secret schemes. But this model makes assumption on the inaccessibility of a distributed source of randomness which is a network of tens of thousands of computers distributed across the globe. Each of these computers generates, stores and updates randompages acting as Page ServerNodes (PSNs). Two communicating userswho initially shares a key k uses this key to randomly select the same PSNs downloading the same set of pages from them. Since some pages may be different between users, they also employ a reconciliation mechanism for assuring the pages they have in common. Then this randomness is used to communicate among themselves using one-time pads. In this thesis we precisely describe an encryption scheme in the limited access model for a practical prototypical implementation. We describe some modifications over a previous attempt, and provide improvements in some components of the model like the page reconciliation protocol and also in the construction of the initial key k. Moreover, we suggest various choices of parameters for a practical implementation and also argue about the security of the scheme. Furthermore, we describe the design of a physical random number generator required for the model and finally provide some implementational details of a prototype which we implemented.
