PDF de programación - APLICACIÓN DE METODOLOGÍAS DE PARALELIZACIÓN PARA LA GENERACIÓN DE TABLAS RAINBOW MEDIANTE LA UTILIZACIÓN DE SERVIDORES DE ALTAS PRESTACIONES EN GNU/LINUX

UNIVERSIDAD DE ALMERÍA
ESCUELA POLITECNICA SUPERIOR

TITULACIÓN DE INGENIERO EN INFORMÁTICA

APLICACIÓN DE METODOLOGÍAS DE PARALELIZACIÓN

PARA LA GENERACIÓN DE TABLAS RAINBOW

MEDIANTE LA UTILIZACIÓN DE SERVIDORES DE ALTAS

PRESTACIONES EN GNU/LINUX



AUTOR:

Rafael Francisco Benedicto Tovar



DIRECTORES:



Dr. D. Julio Gómez López
Dr. Dña. Consolación Gil Montoya



ALMERÍA, MAYO DE 2010.







Tanto la memoria de este trabajo como el software desarrollado se distribuyen bajo

la licencia GNU GPL v3.

La Licencia Pública General GNU (GNU GPL) es una licencia libre, sin derechos para

software y otro tipo de trabajos.

Las licencias para la mayoría del software y otros trabajos prácticos están
destinadas a suprimir la libertad de compartir y modificar esos trabajos. Por el contrario, la
Licencia

Pública General GNU persigue garantizar su libertad para compartir y modificar
todas las versiones de un programa--y asegurar que permanecerá como software libre para
todos sus usuarios.

Cuando hablamos de software libre, nos referimos a libertad, no a precio. Las

Licencias Públicas Generales están destinadas a garantizar la libertad de distribuir
copias de software libre (y cobrar por ello si quiere), a recibir el código fuente o poder
conseguirlo si así lo desea, a modificar el software o usar parte del mismo en nuevos
programas libres, y a saber que puede hacer estas cosas.

Para obtener más información sobre las licencias y sus términos puede consultar:

• http://www.gnu.org/licenses/gpl.html (Licencia original en inglés)

• http://www.viti.es/gnu/licenses/gpl.html (Traducción de la licencia al castellano)







Dar gracias
a mi padre por estar siempre ahí,
a Maricarmen por aguantarme,
a Alberto por ser un buen amigo,
a todos porque sin vosotros jamás
se hubiera hecho este proyecto.







Índice



 

Índice 

 
Introducción .................................................................................................................................. 1 

Capítulo 1 ‐ Introducción a las funciones hash ............................................................................. 5 

1.1  Seguridad Informática ................................................................................................... 5 

1.1.1 Conceptos básicos de la Seguridad Informática ..................................................... 5 

1.1.2 Las amenazas informáticas ..................................................................................... 6 

1.1.3 Ataques informáticos .............................................................................................. 9 

1.2 Criptografía .................................................................................................................. 11 

1.2.1 Historia y evolución de la criptografía .................................................................. 12 

1.2.2 Criptosistemas ....................................................................................................... 15 

1.3 Las funciones hash ....................................................................................................... 19 

1.3.1 Descripción de las funciones hash ........................................................................ 19 

1.3.2 Características de las funciones hash .................................................................... 20 

1.3.3 Paradoja del cumpleaños ...................................................................................... 21 

1.3.4 Algoritmos hash .................................................................................................... 22 

1.3.5 Criptoanálisis de las funciones hash ..................................................................... 24 

1.3.6 Aplicaciones de las funciones hash ....................................................................... 28 

 

  
 

I 

 
 

APLICACIÓN DE METODOLOGÍAS DE PARALELIZACIÓN PARA LA GENERACIÓN DE TABLAS RAINBOW 

MEDIANTE LA UTILIZACIÓN DE SERVIDORES DE ALTAS PRESTACIONES EN GNU/LINUX 

 
Capítulo 2 ‐ Técnicas de programación paralela ......................................................................... 30 

       

2.1 Hebras .......................................................................................................................... 34 

2.1.1 Hebras en C++ ....................................................................................................... 37 

2.1.2 Ejemplo Hebras ..................................................................................................... 39 

2.1.3 Compilación y ejecución hebras ............................................................................ 39 

2.2 MPI ............................................................................................................................... 40 

2.2.1 Open MPI .............................................................................................................. 42 

2.2.2 Ejemplo MPI .......................................................................................................... 44 

2.2.3 Compilación y ejecución MPI ................................................................................ 44 

2.3 CUDA ............................................................................................................................ 45 

2.3.1 Modelo de programación ..................................................................................... 45 

2.3.2 Calificadores .......................................................................................................... 50 

2.3.3 Ejemplo CUDA ....................................................................................................... 52 

3.3.4 Compilación y ejecución ....................................................................................... 54 

Capítulo 3 ‐ Implementación de funciones hash basadas en el multiprocesamiento ................ 55 

3. 1 MD4 ............................................................................................................................. 55 

3.1 .1 Descripción ........................................................................................................... 55 

3.1.2 Implementación multiprocesada .......................................................................... 57 

3.2 MD5 .............................................................................................................................. 58 

3.2.1 Descripción ............................................................................................................ 58 

3.2.2 Implementación multiprocesada .......................................................................... 61 

3.3 SHA1 ............................................................................................................................. 62 

3.3.1 Descripción ............................................................................................................ 62 

3.3.2 Implementación multiprocesada .......................................................................... 64 

3.4 LM ................................................................................................................................. 65 

3.4.1 Descripción LM ...................................................................................................... 65 

3.4.2 Descripción DES ..................................................................................................... 66 

II 

 
 

  
 

APLICACIÓN DE METODOLOGÍAS DE PARALELIZACIÓN PARA LA GENERACIÓN DE TABLAS RAINBOW 

MEDIANTE LA UTILIZACIÓN DE SERVIDORES DE ALTAS PRESTACIONES EN GNU/LINUX 

 

       

3.4.3 Implementación multiprocesada .......................................................................... 69 

3.5 NTLM ............................................................................................................................ 70 

3.5.1 Descripción ............................................................................................................ 70 

3.5.2 Implementación multiprocesada .......................................................................... 71 

3.6 Conclusiones ................................................................................................................ 72 

Capítulo 4 ‐ Tablas Rainbow ........................................................................................................ 74 

4.1 Esquema general .......................................................................................................... 76 

4.2 Estructura y funcionamiento ........................................................................................ 80 

4.3 Generación de Tablas Rainbow  (rtGen) ...................................................................... 88 

4.4 Ordenación de Tablas Rainbow  (rtSort) ...................................................................... 93 

4.5 Ruptura de Hash  (rCrack) ............................................................................................ 96 

4.6 Posibles mejoras ........................................................................................................ 102 

Capítulo 5 ‐ Generación de Tablas Rainbow  mediante técnicas multiprocesadas .................. 105 

5.1 Algoritmo rtGen Hebras ............................................................................................. 106 

5.2 Algoritmo rtGen MPI .................................................................................................. 112 

5.3 Algoritmo rtGen CUDA ............................................................................................... 118 

5.4 Comparativa rtGen ..................................................