PDF de programación - Consultas Eficientes y Seguras a Bases de Datos Utilizando Fragmentación y Cifrado de Datos

CENTRO DE INVESTIGACI ´ON Y DE ESTUDIOS

AVANZADOS DEL INSTITUTO POLIT´ECNICO NACIONAL

DEPARTAMENTO DE COMPUTACI ´ON

Consultas Eficientes y Seguras a Bases de

Datos Utilizando Fragmentaci´on y Cifrado de

Datos

Tesis que presenta:

Jazm´ın Beatrz Trejo Gatica

Para obtener el grado de

Maestro en Ciencias

en Computaci´on

Director de la Tesis:

Dr. Debrup Chakraborty

M´exico, D. F.

Noviembre 2009

3

Agradecimientos

A mis padres por su apoyo incondicional y por ser mi motor a seguir.

Porque juntos hemos logrado cada una de mis metas.

A mis hermanos, Hugo y Deyanira por confiar ci´egamente en m´ı.
A Edgar, por su compa˜n´ıa, su sinceridad, su amistad, paciencia y preocu-
paci´on. Por su apoyo en cada momento dificil y por compartir grandes cosas
juntos.

A mis sobrinos Andrea y Rodrigo, por verme como ejemplo a seguir y por

motivarme cada d´ıa m´as a ser una mejor persona.

Al Dr. Debrup Chakraborty, por su gran paciencia y preocupaci´on a lo
largo de mi trabajo. Por ser una persona admirable y sabia, que siempre me
regal´o el tiempo necesario sin escatimar en ´el.

Al Dr. Luis Gerardo de la Fraga, por su motivaci´on y por su buena actitud
ante cualquier duda, por tomarse el tiempo de auxiliarme y ayudarme con
su gran conocimiento.

Al Dr. Guillermo Morales por su gran paciencia y por el tiempo que le

dedico a esta tesis en la revisi´on y correcci´on.

Al CINVESTAV por permitirme formar parte de esta reconocida institu-

ci´on.

A CONACyT por el apoyo, brindado a lo largo de mi estancia en el

cinvestav.

Al proyecto de investigaci´on SEP-CONACyT titulado “VISION POR
COMPUTADORA EVOLUTIVA” (Ref. 80965), cuyo responsable es el Dr.
Luis Gerardo de la Fraga.

Resumen

Mantener la privacidad en la informaci´on ha cobrado mayor importancia
en las ´ultimas d´ecadas. Con el surgimiento de Internet y la centralizaci´on
de los datos, es cada vez m´as necesario dotar de seguridad a nuestra infor-
maci´on para protegerla contra robos, plagios, extorsiones, etc. Gracias a este
gran avance tecnol´ogico en la comunicaci´on global naci´o DaaS (Database as a
Service), una arquitectura que ofrece el servicio de hosting de bases de datos
brindando la comodidad de administrar las bases de datos y permitir con-
sultas desde cualquier terminal que pueda conectarse a Internet. A pesar de
que estas empresas que prestan el servicio de hosting de datos ofrecen cierto
nivel de seguridad para que solamente el poseedor de la misma pueda con-
sultarla, el prestatario del servicio tiene acceso total a nuestra informaci´on.
Para cubrir este aspecto se ha hecho uso de las bondades de seguridad que la
Criptograf´ıa ofrece. Han surgido diversos esquemas que cifran por completo
la base de datos con el fin de que el prestatario del servicio no pueda ser
capaz de interpretar la informaci´on; lo malo es que para realizar consultas a
la base de datos cifrada el tiempo de espera del cliente es bastante significa-
tivo ya que para realizar la consulta se deben realizar diversas funciones de
descifrado y as´ı obtener la informaci´on en claro.

Es por esta raz´on que nos sentimos motivados a dise˜nar un modelo que
permita satisfacer consultas eficientes y seguras en una base de datos bajo el
contexto DaaS. Este trabajo de tesis presenta un esquema que en vez de ci-

i

ii

frar por completo la base de datos, fragmenta la informaci´on y gracias a esto,
gran parte de la informaci´on puede permanecer en texto claro. Fragmentar
la base de datos implica separar aquellos atributos que juntos nos denotan
informaci´on valiosa, como puede ser el nombre de un empleado y su sueldo,
y cifrar la relaci´on existente entre estos datos. As´ı, fragmentar los datos trae
grandes beneficios tanto en t´opicos de seguridad como en eficiencia; debido
a que las consultas se realizan a los datos en texto claro, ´estas son realizadas
en tiempo real y generadas por el motor de b´usqueda del Sistema Manejador
de Bases de Datos. Adem´as, nuestro esquema no s´olo se preocupa por la
seguridad de la informaci´on, sino tambi´en de la autenticidad de la misma; si
un dato no ha sido autenticado, no podemos saber si ´este ha sido modificado
de forma intencional o accidental. Es por este motivo que los datos cifrados
en nuestro esquema son autenticados mediante un cifrado con autenticaci´on.

Por otra parte, y ya que la fragmentaci´on de la base de datos es un pro-
blema NP-dif´ıcil debido a que corresponde al mismo problema de coloraci´on
de hipergrafos, se dise˜n´o e implement´o una heur´ıstica que permitiera resolver
este problema y minimizar el n´umero de fragmentos. Se dise˜n´o un algoritmo
gen´etico que permitiera realizar la fragmentaci´on y se compar´o directamen-
te contra otra heur´ıstica mostrada en la literatura; los resultados obtenidos
fueron bastante satisfactorios, nuestro algoritmo gen´etico obtuvo significati-
vamente menos fragmentos de los obtenidos con la otra heur´ıstica.

Abstract

During the last decade privacy of information has gained a lot of atten-
tion. With the rapid expansion of the internet and centralized data storage
mechanisms it has become very important to protect the stored information
against non-authorized access and processing. Rapid technological develop-
ment has brought many new data storage solutions, one of them is Database
as a Service (Daas). DaaS is a specific architecture providing database hos-
ting services. In the DaaS model, the owner of the data delegates the duty of
maintaining his/her data to a third party (called the server) which hosts the
database and process his/her queries. These kind of service providers which
provides the service of data hosting may add some security mechanism on
the stored data, but the service provider has full access to it. It is undesira-
ble as the owner may not want to reveal the data to the server. Numerous
cryptographic techniques can be used by the owner to protect the data. But
such an encryption applied to the whole data brings in a new problem: the
server needs to process queries on the encrypted data. Last said would be
very inefficient, as a good encryption scheme would destroy all the structure
which exists in the original data, hence indexing and other techniques ge-
nerally applied for efficient query processing can no longer be applied. Thus
specialized cryptographic schemes are required.

In this thesis we deal with the problem of secure storage in the DaaS
model which is friendly to efficient query processing. We present a scheme

iii

iv

in which instead of encrypting the total database, we fragment the infor-
mation and encrypt only parts of it. By using this strategy the majority of
the information stays un-encrypted, and thusquery processing can also be
done efficiently. Fragmenting a database implies to separate those attributes
which have a sensitive association between them. For example, in an emplo-
yees database the individual attributes employee name and salary are not
themselves sensitive, but the association between them is not revealed.

Fragmentation of a database provides some security to the data without
hampering the ease of query processing, and they can be done by the da-
tabase management system without much extra overhead. Our scheme also
adds an additional security service of authentication along with encryption.
Authentication allows detection of accidental or intentional changes made
within a database. We obtain authentication by using a primitive called aut-
henticated encryption.

The other part which the thesis deals with is the problem of creating
fragments. The problem of creating minimum fragments is the same as the
minimum hyper-graph coloring problem which is known to be NP hard. We
developed a heuristic based on genetic algorithm to create the minimum
number of fragments given a database. Our scheme gives significantly lesser
number of fragments compared to other heuristics reported in the literature.

´Indice general

Contenido

Lista de Figuras

1. Introducci´on

1.1. Bases de datos relacionales . . . . . . . . . . . . . . . . . . . .
1.2. Lograr la seguridad . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Propuesta y contribuciones . . . . . . . . . . . . . . . . . . . .
1.4. Estructura de la Tesis
. . . . . . . . . . . . . . . . . . . . . .

V

VII

1
2
4
6
7

2. Preliminares

9
2.1. Modelo relacional de bases de datos y procesamiento de consultas 10
2.2. Esquemas sim´etricos de cifrado . . . . . . . . . . . . . . . . . 12
2.2.1. El est´andar de cifrado avanzado . . . . . . . . . . . . . 13
2.2.2. Cifrado con autenticaci´on . . . . . . . . . . . . . . . . 18
2.2.2.1. OCB1 . . . . . . . . . . . . . . . . . . . . . . 19
2.3. Algoritmos gen´eticos . . . . . . . . . . . . . . . . . . . . . . . 22

3. Estado del Arte

4. Procesamiento Eficiente de Consultas y Autenticaci´on en Ba-

ses de Datos

27

45

v

vi

´INDICE GENERAL

4.1. Restricciones de confidencialidad . . . . . . . . . . . . . . . . 46
4.2. Esquema de cifrado y fragmentaci´on . . . . . . . . . . . . . . 48
4.3. Protocolo de consultas . . . . . . . . . . . . . . . . . . . . . . 53

5. Un Mejor Algoritmo para la Fragmentaci´on

59
5.1. Algoritmo de Fragmentaciones M´ınimas . . . . . . . . . . . . . 60
5.2. Algoritmo Gen´etico . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3. Comparaci´on entre heur´ısticas y resultados obtenidos . 66

6. Acerca de la implementaci´on

7. Conclusiones y Trabajo a Futuro

71

77

´Indice de figuras

2.1. Tabla de ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2. En la consulta 1 deseamos conocer la edad de Fabi´an. En la
2 se desea saber el nombre y el salario de las mujeres. En la
tercer consulta buscamos toda la informaci´on de las mujeres
menores de 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3. Algoritmo de cifrado AES . . . . . . . . . . . . . . . . . . . . 15
2.4. La caja S para AES
. . . . . . . . . . . . . . . . . . . . . . . 15
2.5. La caja auxiliar RCon para la expansi´on de llaves . . . . . . . . 16
2.6. Algori