Ensayo HASH
INSTITUTO POLITÉCNICO NACIONAL
CENTRO DE ESTUDIOS CIENTIFICOS Y TECNOLOGICOS
“JUAN DE DIOS BATIZ PAREDES”
GRUPO: 5IM6
MATERIA: SEGURIDAD WEB
PROFESOR: JUAN MANUEL
FECHA DE ENTREGA: 12 DE NOVIEMBRE DEL 2017
ENSAYO HASH
FUNCIONES Y TABLAS HASH
Introducción
Una de las aplicaciones más interesantes de la actual criptografía es la posibilidad real de añadir en un mensaje una firma digital: La autenticación completa.
Todo esto comienza en el año 1976 cuando Diffie y Hellman presentan un modelo de cifrado asimétrico con clave pública, con los antiguos sistemas de cifra de clave simétrica esto era inviable o bien muy complejo. No obstante dado que los sistemas de clave pública son muy lentos en vez de firmar digitalmente el mensaje completo, en un sistema criptográfico se incluirá como firma digital una operación de cifra con la clave privada del emisor sobre un resumen o hash de dicho mensaje representado por sólo una centena de bits.
Funciones HASH
Definicion
Los hash o funciones de resumen son algoritmos que consiguen crear a partir de una entrada (ya sea un texto, una contraseña o un archivo, por ejemplo) una salida alfanumérica de longitud normalmente fija que representa un resumen de toda la información que se le ha dado (es decir, a partir de los datos de la entrada crea una cadena que solo puede volverse a crear con esos mismos datos).
Estas funciones no tienen el mismo propósito que la criptografía simétrica y asimétrica, tiene varios cometidos, entre ellos está asegurar que no se ha modificado un archivo en una transmisión, hacer ilegible una contraseña o firmar digitalmente un documento.
Estas funciones no tienen el mismo propósito que la criptografía simétrica y asimétrica, tiene varios cometidos, entre ellos está asegurar que no se ha modificado un archivo en una transmisión, hacer ilegible una contraseña o firmar digitalmente un documento.
En otras palabras, una función hash es método para generar claves o llaves que representen de manera unívoca a un documento o conjunto de datos. Es una operación matemática que se realiza sobre este conjunto de datos de cualquier longitud, y su salida es una huella digital, de tamaño fijo e independiente de la dimensión del documento original. El contenido es ilegible.
Características
En definitiva las funciones hash se encargan de representar de forma compacta un archivo o conjunto de datos que normalmente es de mayor tamaño que el hash independientemente del propósito de su uso.
Este sistema de criptografía usa algoritmos que aseguran que con la respuesta (o hash) nunca se podrá saber cuáles han sido los datos insertados, lo que indica que es una función unidireccional. Sabiendo que se puede generar cualquier resumen a partir de cualquier dato nos podemos preguntar si se podrían repetir estos resúmenes (hash) y la respuesta es que teóricamente si, podría haber colisiones, ya que no es fácil tener una función hash perfecta (que consiga que no se repita la respuesta), pero esto no supone un problema, ya que si se consiguiera (con un buen algoritmo) dos hash iguales los contenidos serían totalmente distintos.
En definitiva las funciones hash se encargan de representar de forma compacta un archivo o conjunto de datos que normalmente es de mayor tamaño que el hash independientemente del propósito de su uso.
Este sistema de criptografía usa algoritmos que aseguran que con la respuesta (o hash) nunca se podrá saber cuáles han sido los datos insertados, lo que indica que es una función unidireccional. Sabiendo que se puede generar cualquier resumen a partir de cualquier dato nos podemos preguntar si se podrían repetir estos resúmenes (hash) y la respuesta es que teóricamente si, podría haber colisiones, ya que no es fácil tener una función hash perfecta (que consiga que no se repita la respuesta), pero esto no supone un problema, ya que si se consiguiera (con un buen algoritmo) dos hash iguales los contenidos serían totalmente distintos.
Ejemplos de funciones Hash
- MD5
Es una función hash de 128 bits. Como todas las funciones hash, toma unos determinados tamaños a la entrada, y salen con una longitud fija (128bits). El algoritmo MD5 no sirve para cifrar un mensaje. La información original no se puede recuperar, ya que está específicamente diseñado para que a partir de una huella hash no se pueda recuperar la información. Actualmente esta función hash no es segura utilizarla, nunca se debe usar. - SHA-1
Es parecido al famoso MD5, pero tiene un bloque de 160bits en lugar de los 128bits del MD5. La función de compresión es más compleja que la función de MD5, por tanto, SHA-1 es más lento que MD5 porque el número de pasos son de 80 (64 en MD5) y porque tiene mayor longitud que MD5 (160bits contra 128bits).
SHA-1 es más robusto y seguro que MD5, pero ya se han encontrado colisiones, por tanto, actualmente esta función hash no es segura utilizarla, nunca se debe usar. - SHA-2
Las principales diferencias con SHA-1 radica en en su diseño y que los rangos de salida han sido incrementados. Dentro de SHA-2 encontramos varios tipos, el SHA-224, SHA-256, SHA-384 y SHA-512. El más seguro, es el que mayor salida de bits tiene, el SHA-512, que tiene 80 rondas (pasos), como el SHA-1 pero se diferencia de éste en:
Tamaño de salida 512 por los 160 de SHA-1.
Tamaño del bloque, tamaño de la palabra y tamaño interno que es el doble que SHA-1.
Como ocurre con todos los cifrados y hash, cuanto más seguro, más lento su procesamiento y uso, debemos encontrar un equilibrio entre seguridad y velocidad.
Tablas HASH
Definicion
Las tablas hash son estructuras de datos que se utilizan para almacenar un número elevado de datos sobre los que se necesitan operaciones de búsqueda e inserción muy eficientes. Una tabla hash almacena un conjunto de pares “(clave, valor)”. La clave es única para cada elemento de la tabla y es el dato que se utiliza para buscar un determinado valor.
Un diccionario es un ejemplo de estructura que se puede implementar mediante una tabla hash. Para cada par, la clave es la palabra a buscar, y el valor contiene su significado. El uso de esta estructura de datos es tan común en el desarrollo de aplicaciones que algunos lenguajes las incluyen como tipos básicos.
Un diccionario es un ejemplo de estructura que se puede implementar mediante una tabla hash. Para cada par, la clave es la palabra a buscar, y el valor contiene su significado. El uso de esta estructura de datos es tan común en el desarrollo de aplicaciones que algunos lenguajes las incluyen como tipos básicos.
Contexto de uso de una tabla hash
Supongamos que en una aplicación se deben manipular un número muy elevado de pares (clave, valor). Estos pares son creados bajo demanda por la aplicación, se manipulan, y se destruyen. La manipulación consiste principalmente en buscar si la aplicación contiene ya un par (clave, valor) dado, y si no es así, se añade a la tabla.
Por ejemplo, se dispone de una aplicación un teléfono móvil que es capaz de reconocer mediante la cámara los números de un pasaporte. Para cada pasaporte se almacena un mensaje de texto con un comentario. La aplicación debe realizar las siguientes operaciones:
Crear una tabla de pasaportes vacía.
Dado un número de pasaporte, buscar si está almacenado ya en la tabla.
Dado un número de pasaporte y un comentario, almacenar este par (clave, valor) en la tabla. Se asume que no hay información previa sobre este número de pasaporte.
Posibles implementaciones
Como el número de pares a manipular es indeterminado, se necesita una estructura de datos dinámica. Como primera solución podemos considerar una lista encadenada de pares. La operación de inserción es sencilla. Dado un número de pasaporte y una cadena, se crea un elemento nuevo en la tabla y se inserta. La operación de búsqueda necesita atravesar la lista hasta que, o se encuentra la clave dada (número de pasaporte), o se llega al final (la clave no está en la tabla). Cuando el número de pares es muy elevado, esta búsqueda es muy ineficiente, pues hay que procesar un gran número de elementos.
Una segunda opción para tener una búsqueda muy rápida podría ser almacenar todos los datos en una tabla y utilizar el número de pasaporte como su índice. En este caso, ver si un número está en la tabla consiste simplemente en ver si tiene una cadena asociada. El insertar un nuevo par (pasaporte, mensaje) también sería muy rápido pues consistiría en guardar el mensaje dado en la posición correspondiente al número. Pero el problema con esta solución es que el número de pasaportes puede ser un entero muy largo y por tanto la tabla que se necesita definir está más allá de lo aceptable.
La tabla hash ofrece un compromiso para esta situación. Los pares (clave, valor) se guardan en una tabla, pero con un tamaño menor del ideal. Para nuestro ejemplo, se utiliza una tabla, pero no tiene como tamaño el número máximo de pasaportes posibles, sino un número más pequeño.
Tablas hash
Las tablas hash son uno de los mecanismos más utilizados en el desarrollo de aplicaciones (haz una búsqueda en internet del término hash table y mira número de enlaces que se devuelven). Existen múltiples librerías en casi todos los lenguajes de programación que proporcionan implementaciones muy eficientes de estas tablas (por ejemplo la clase java.util.Hashtable de las librerías del lenguaje Java).
La implementación de una tabla hash está basada en los siguientes elementos:
Supongamos que en una aplicación se deben manipular un número muy elevado de pares (clave, valor). Estos pares son creados bajo demanda por la aplicación, se manipulan, y se destruyen. La manipulación consiste principalmente en buscar si la aplicación contiene ya un par (clave, valor) dado, y si no es así, se añade a la tabla.
Por ejemplo, se dispone de una aplicación un teléfono móvil que es capaz de reconocer mediante la cámara los números de un pasaporte. Para cada pasaporte se almacena un mensaje de texto con un comentario. La aplicación debe realizar las siguientes operaciones:
Crear una tabla de pasaportes vacía.
Dado un número de pasaporte, buscar si está almacenado ya en la tabla.
Dado un número de pasaporte y un comentario, almacenar este par (clave, valor) en la tabla. Se asume que no hay información previa sobre este número de pasaporte.
Posibles implementaciones
Como el número de pares a manipular es indeterminado, se necesita una estructura de datos dinámica. Como primera solución podemos considerar una lista encadenada de pares. La operación de inserción es sencilla. Dado un número de pasaporte y una cadena, se crea un elemento nuevo en la tabla y se inserta. La operación de búsqueda necesita atravesar la lista hasta que, o se encuentra la clave dada (número de pasaporte), o se llega al final (la clave no está en la tabla). Cuando el número de pares es muy elevado, esta búsqueda es muy ineficiente, pues hay que procesar un gran número de elementos.
Una segunda opción para tener una búsqueda muy rápida podría ser almacenar todos los datos en una tabla y utilizar el número de pasaporte como su índice. En este caso, ver si un número está en la tabla consiste simplemente en ver si tiene una cadena asociada. El insertar un nuevo par (pasaporte, mensaje) también sería muy rápido pues consistiría en guardar el mensaje dado en la posición correspondiente al número. Pero el problema con esta solución es que el número de pasaportes puede ser un entero muy largo y por tanto la tabla que se necesita definir está más allá de lo aceptable.
La tabla hash ofrece un compromiso para esta situación. Los pares (clave, valor) se guardan en una tabla, pero con un tamaño menor del ideal. Para nuestro ejemplo, se utiliza una tabla, pero no tiene como tamaño el número máximo de pasaportes posibles, sino un número más pequeño.
Tablas hash
Las tablas hash son uno de los mecanismos más utilizados en el desarrollo de aplicaciones (haz una búsqueda en internet del término hash table y mira número de enlaces que se devuelven). Existen múltiples librerías en casi todos los lenguajes de programación que proporcionan implementaciones muy eficientes de estas tablas (por ejemplo la clase java.util.Hashtable de las librerías del lenguaje Java).
La implementación de una tabla hash está basada en los siguientes elementos:
- Una tabla de un tamaño razonable para almacenar los pares (clave, valor).
- Una función “hash” que recibe la clave y devuelve un índice para acceder a una posición de la tabla.
- Un procedimiento para tratar los casos en los que la función anterior devuelve el mismo índice para dos claves distintas. Esta situación se conoce con el nombre de colisión.
- Las posibles implementaciones de cada uno de estos tres elementos se traducen en una infinidad de formas de implementar una tabla hash. A continuación se detalla una solución concreta para el problema de las colisiones.
Referencias:
- De Luz Sergio (2009) Algoritmos de autenticación (hash), Criptográfia. Recuperado el 22 de Noviembre de 2017 de: https://www.redeszone.net/2010/11/09/criptografia-algoritmos-de-autenticacion-hash/
- Zuaznabar Mazorra, López Catalá (2008) Monogafìa Funciones HASH, Criptografía. Recuperado el 23 de Noviembre de 2017 de: http://www.monografias.com/trabajos76/funciones-hash-criptografia/funciones-hash-criptografia2.shtml
- Universidad Carlos III de Madrid (2011) Tablas Hash, Tablas Hash. Recuperado el 23 de Noviembre del 2017 de: http://www.it.uc3m.es/abel/as/MMC/M2/HashTable_es.html
- Gutierrez Pedro (2013) Funciones de resumen y firmas digitales, ¿Qué son y para qué sirven los hash?. Recuperado el 24 de Noviembre de 2017 de: https://www.genbetadev.com/seguridad-informatica/que-son-y-para-que-sirven-los-hash-funciones-de-resumen-y-firmas-digitales
Comentarios
Publicar un comentario