Unidad 1 - Función Hash
Unidad 1 - Función Hash
Unidad 1 - Función Hash
INDICE
A las funciones resumen también se les llama funciones hash o funciones digest . Una función
hash H es una función computable mediante un algoritmo tal que:
H: U → M
x → h(x)
Tiene como entrada un conjunto de elementos, que suelen ser cadenas, y los convierte en un
rango de salida finito, normalmente cadenas de longitud fija. Es decir, la función actúa como una
proyección del conjunto U sobre el conjunto M.
La idea básica de un valor hash es que sirva como una representación compacta de la cadena de
entrada. Por esta razón decimos que estas funciones resumen datos del conjunto dominio.
Se dice que se produce una colisión cuando dos entradas distintas de la función de hash producen
la misma salida. De la definición de función hash podemos decir que U, el dominio de la función,
puede tener infinitos elementos. Sin embargo M, el rango de la función, tiene un número finito
de elementos debido a que el tamaño de sus cadenas es fijo. Por tanto la posibilidad de existencia
de colisiones es intrínseca a la definición de función hash. Una buena función de hash es una que
1
Servicios de Red e Internet
tiene pocas colisiones en el conjunto esperado de entrada. Es decir, se desea que la probabilidad
de colisión sea muy baja.
Una función hash con clave HK (en inglés keyed hash function) es una función hash H que tiene
un parámetro secreto K que pertenece al conjunto posible de claves K y en la que para una
entrada x, hK(x) es el valor hash de x. Al resto de funciones hash se dice que son sin clave (en
inglés unkeyed hash function).
Se dice que la función hash es inyectiva cuando cada dato de entrada se mapea a un valor hash
diferente. En este caso se dice que la función hash es perfecta. Para que se dé, es necesario que
la cardinalidad del conjunto dominio sea inferior o igual a la cardinalidad del conjunto imagen.
Normalmente solo se dan funciones hash perfectas cuando las entradas están preestablecidas.
Ejemplo: Mapear los días del año en números del 1 al 366 según el orden de aparición.
Formalización:
k 1 ≠ k 2 implica h ( k 1 ) ≠ h ( k 2 )
Cuando no se cumple la propiedad de inyectividad se dice que hay colisiones. Hay una colisión
cuando k 1 ≠ k 2 y h ( k 1 ) = h ( k 2 )
Una función hash se dice que es determinista cuando dada una cadena de entrada siempre
devuelve el mismo valor hash. Es decir, el valor hash es el resultado de aplicar un algoritmo que
opera solo sobre la cadena de entrada. Ejemplos de funciones hash no-deterministas son aquellas
funciones hash que dependen de parámetros externos, tales como generadores de números
pseudoaleatorios o la fecha. Tampoco son deterministas aquellas funciones hash que dependen
de la dirección de memoria en la que está almacenada la cadena de entrada. Esa dirección es
accidental y no se considera un cambio de la cadena entrada en sí. De hecho puede cambiar
dinámicamente durante la propia ejecución del algoritmo de la función hash
El algoritmo de hash más utilizado en estos momentos es el MD5 . Este algoritmo fue desarrollado
por Ronald Rivest en 1995 y está basado en dos algoritmos anteriores MD2 y MD4. Todos estos
protocolos producen un número de 128 bits a partir de un texto de cualquier longitud.
MD4 fue desarrollado para mejorar el rendimiento de MD2 , sin embargo, varios problemas
fueron detectados y en 1996 fueron publicados elementos que hacen hoy en día inservible el
algoritmo. MD5 sustituyó a MD4 y aunque no tiene el rendimiento de su antecesor, hasta el
momento no han sido publicados elementos que comprometan su integridad y funcionamiento.
MD5 comienza rellenando el mensaje a una longitud congruente en módulo 448 mod 512. Es
decir la longitud del mensaje es 64 bits menos que un entero múltiplo de 512. El relleno consiste
en un bit en 1 seguido por cuentos bits en 0 sean necesarios. La longitud original del mensaje es
almacenada en los últimos 64 bits del relleno.
2
Servicios de Red e Internet
Adicionalmente se inicializa, con un valor fijo, un buffer de 128 bits. Este buffer puede verse como
4 registros de 32 bits (A,B,C,D) y son inicializados con los siguientes valores hexadecimales:
Durante varias rondas de procesamiento el algoritmo toma bloques de 512 bits de la entrada y
los mezcla con los 128 bits del buffer. Este proceso es repetido hasta que todos los bloques de
entrada han sido consumidos. El valor resultante en el buffer es el hash del mensaje.
9A659FE04DB6E4FEB497B9CF7731BB07
AE3CCB55457C53BECF8C20546031C019
Que se corresponden con dos cadenas que varían sólo en un carácter. Esto demuestra que una
pequeña variación en la cadena de entrada provoca una gran variación en la cadena de salida.
NIST presentó en 1993 un algoritmo basado en las mismas técnicas que MD5 y denominado SHA
(Secure Hash Algorithm).
El primer miembro de la familia fue publicado en 1993 es oficialmente llamado SHA. Sin embargo,
hoy día, no oficialmente se le llama SHA‐0 para evitar confusiones con sus sucesores. Dos años
más tarde el primer sucesor de SHA fue publicado con el nombre de SHA‐1.
Este algoritmo en 1995 la Agencia de Seguridad Nacional (NSA) lo sustituyó por una versión
mejorada que actualmente se conoce como SHA-1 y que se considera más seguro que MD5.
Produce un código hash de 160 bits para mensajes de longitud máxima 264 bits, aunque existen
otras variantes poco utilizadas todavía que producen códigos de mayor longitud.
SHA1(“”) = da39a3ee5e6b4b0d3255bfef95601890afd80709
3
Servicios de Red e Internet
Características:
SHA‐0 y SHA‐1 producen una salida resumen de 160 bits (20 bytes) de un mensaje que puede
tener un tamaño máximo de 264 bits, y se basa en principios similares a los usados por el profesor
Ronald L. Rivest del MIT en el diseño de los algoritmos de resumen de mensaje MD4 y MD5.
El relleno consiste en un uno seguido de los ceros que sean necesarios. Aunque el mensaje ya
tenga la longitud deseada, se debe efectuar el relleno, por lo que el número de bits de dicho
relleno está en el rango de 1 a 512 bits.
A la salida del paso 1, se le añade un bloque de 64 bits que represente la longitud del
mensaje original antes de ser rellenado.
Se inicializa la memoria temporal MD, la cual consta de 160 bits y su finalidad es
almacenar los resultados intermedios y finales de la función de dispersión. La MD
consta de 5 registros (A,B,C,D,E) de 32 bits cada uno, los valores con los que se
inicializan son los siguientes (valores hexadecimales):
Se procesa el mensaje por bloques de 512 bits, cada uno pasa por un módulo que consta
de 4 rondas de procesamiento de 20 pasos cada una. Las rondas tienen una estructura
similar, con la excepción de que cada una ocupa una función lógica primitiva diferente
(f1, f2, f3 y f4).
La entrada a cada ronda consta del bloque de 512 bits que se esté procesando (Yq) y los 160 bits
de la memoria MD, nótese que cada bloque de 512 bits actualizará el valor de la memoria
temporal. Cada ronda también hace uso de la constante aditiva Kt, donde 0<= t <= 79 indica
uno de los 80 pasos a lo largo de las cuatro rondas.
Una vez que se procesan los L bloques de 512 bits, el resumen del mensaje son los 160
bits de salida del último bloque.
Aplicaciones de SHA‐1
4
Servicios de Red e Internet
2. E‐mail
4. Distribución de software
5. Almacenamiento de datos
Tiene tres versiones: LM, NTLMv1 y NTLMv2. El flujo de mensajes para los tres es el mismo; Las
únicas diferencias son la función utilizada para calcular varios campos de respuesta del desafío, y
qué campos de respuesta se establecen
LAN Manager utiliza una clave de hash para transformar un código de tamaño variable en un
código fijo. Para ello aplica una función matemática en la contraseña. La contraseña puede tener
hasta 14 caracteres. Si la contraseña es más corta, LM añade ceros para llegar hasta los 15
caracteres. A continuación, pasa la contraseña a mayúsculas y la divide en dos partes de 7
caracteres.
Se construye una clave DES (Data Encryption Standard) de 56 bits a partir de cada una de las dos
mitades de 7 bytes y se concatenan para obtener una clave hash de 16 bytes.
NT LAN Manager conocido como NTLM fue el primero en Windows NT y es una mejora respecto
al protocolo LM. A diferencia de las contraseñas LM, que usan el conjunto de caracteres ASCII, las
de NTLM están basadas en el conjunto de caracteres Unicode, se reconocen las minúsculas y las
mayúsculas, la longitud aumenta hasta 128 caracteres. Como con LM, el sistema no almacena la
contraseña sino que almacena una representación de la misma mediante el NTLM OWF. OWF se
combina con el algoritmo MD4 Hash, que implementa una función de cifrado denominada digest
(resumen)-un hash de 16 bytes- de una cadena de texto de longitud variable, que en este caso es
la contraseña del usuario.
Otra de las diferencias entre NTLM y LM es que las contraseñas del primero no se dividen en
partes más pequeñas antes de combinar su algoritmo de hash. NTLM usa el mismo proceso
Desafío/Respuesta para autenticarse como LM. NTLM es el proveedor predeterminado de
autenticación e Windows NT, Windows 2000 y Windows Server 2003 mientras no sean miembros
5
Servicios de Red e Internet
de un dominio de Active Directory, y aun así se utiliza por diversas funciones. Para respetar
compatibilidad hacia atrás, el hash LM se envía junto al Hash NT. Si eliminamos los hashes LM de
la BD al crear contraseñas mayores de 14 caracteres o modificando la llave NoLMHash del
registro, el sistema crea un valor nulo para el hash LM. Aunque este valor nulo no sirve para
autenticar al usuario se sigue enviando junto al hash NT.
NTLMv2
Segunda versión del protocolo NTLM, apareció con el SP4 de Windows NT 4.0 y se incluye en
Windows 2000 y posteriores. Sigue las mismas reglas que NTLM, sin embargo usa un proceso de
autenticación ligeramente distinto. NTLMv2 necesita además que la posible diferencia horaria
entre clientes y servidores no supere los 30 minutos.
Si el cliente y el servidor son compatibles con NTLMv2, se consigue una sesión de seguridad
mejorada. Esta seguridad mejorada proporciona claves separadas para confidencialidad e
integridad del mensaje, proporciona una entrada al cliente al desafío para impedir ataques
específicos de texto plano, y usa un hash basado en el algoritmo MD5 y el código de autenticación
de mensaje (HMAC) para la comprobación de la integridad del mensaje.
Como parte de una arquitectura extensible, los sistemas operativos Windows Server
implementan un conjunto predeterminado de proveedores de compatibilidad de seguridad de
autenticación, que incluyen Negotiate, el protocolo de Kerberos, NTLM, Schannel (canal seguro)
y Digest. Los protocolos utilizados por estos proveedores permiten la autenticación de usuarios,
equipos y servicios, y permite que el proceso de autenticación de usuarios y servicios autorizados
tener acceso a recursos de forma segura.
La autoridad de seguridad Local (LSA) es un subsistema protegido que autentica e inicia sesión en
el equipo local a los usuarios. Además, LSA mantiene información sobre todos los aspectos de
seguridad local en un equipo (estos aspectos se conocen colectivamente como la directiva de
seguridad local). También proporciona diversos servicios para la traducción entre nombres e
identificadores de seguridad (SID).
El Administrador de cuentas de seguridad (SAM, por sus siglas en inglés) de Windows Server 2012
es una base de datos que almacena cuentas de usuario e información de seguridad para los
usuarios que acceden al sistema. La base de datos se ejecuta automáticamente como un proceso
cuando se inicia el sistema. SAM está en la carpeta Windows dentro de la carpeta System 32 y
trabaja en conjunto con otros procesos del sistema.
6
Servicios de Red e Internet
Administrador: 500::c691a4e531c95817ca88e6fe67bff2f6:::
*disabled* Invitado:501::31d6cfe0d16ae931b73c59d7e0c089c0:::
usuario: 1000::f2ab082fa1b21c772eea4193d454d7b0:::
profesor: 1001::31d6cfe0d16ae931b73c59d7e0c089c0:::
ASPNET: 1010::1edb3ed5e858a8e1065c41d2bff5a686:::
pepe: 1013::c780c78872a102256e946b3ad238f661:::
C:\Windows\System32\lsass.exe
C:\Windows\System32\SAM
7
Servicios de Red e Internet
La base de datos SAM está siendo utilizada por el proceso lsass y por tanto no se puede abrir
directamente. Para ver su contenido debemos utilizar el comando samdump2 o pwdump6.
Puestos que las contraseñas de los usuarios están almacenadas en formato Hash, no es posible
recontruir la clave original ya que estos algoritmos son irreversibles. Los posibles métodos para
obtener la clave en texto plano son:
a) Fuerza bruta.
Consiste en construir todas las combinaciones posibles de caracteres e ir calculando su
hash hasta encontrar una combinación cuyo hash coincida con el almacenado en SAM.
Este método requiere mucho tiempo ya que el número de combinaciones es elevado.
b) Tablas Rainbow.
Es importante saber que las tablas rainbow son creadas a partir de una función de hash
específica, por ejemplo, para romper los hashes de MD5 necesitaremos unas tablas
rainbow basadas en hashes de MD5 y para SHA, tablas rainbow SHA.
Usuario root
También llamado superusuario o administrador. Su UID (User ID) es 0 (cero). Es la única cuenta
de usuario con privilegios sobre todo el sistema. Acceso total a todos los archivos y directorios
con independencia de propietarios y permisos. Controla la administración de cuentas de usuarios.
Ejecuta tareas de mantenimiento del sistema.
8
Servicios de Red e Internet
Usuarios especiales
Ejemplos: bin, daemon, adm, lp, sync, shutdown, mail, operator, squid, apache, etc. Se les llama
también cuentas del sistema. No tiene todos los privilegios del usuario root, pero dependiendo
de la cuenta asumen distintos privilegios de root.
Usuarios normales
Se usan para usuarios individuales. Cada usuario dispone de un directorio de trabajo, ubicado
generalmente en /home. Cada usuario puede personalizar su entorno de trabajo.
En las distribuciones actuales de Linux se les asigna generalmente un UID superior a 500.
El archivo /etc/passwd contiene una línea para cada usuario, similar a las siguientes:
root:x:0:0:root:/root:/bin/bash
sergio:x:501:500:Sergio Pere<:/home/sergio:/bin/bash
La información de cada usuario está dividida en 7 campos delimitados cada uno por ':' dos puntos.
<password> Una “x” indica que el password está almacenado en /etc/shadow, en el caso de ser
una “!” es que el usuario está bloqueado. Si tiene “!!” es que no tiene.
<uid> Cada usuario lleva un no identificador (uid) entre 0(root) y 65535. Se reservan algunos para
usuario root( el cero siempre), y para usuarios de servicios varios del sistema.
9
Servicios de Red e Internet
<gid> – grupo id, cada usuario tiene un id de grupo principal, pero puede pertenecer a más
grupos.
<carpeta> La usará como la carpeta de inicio del usuario, al iniciar sesión con él será la que cargue
por defecto.
<shell> Los usuarios de servicios y usuarios con permisos limitados no deben tener shell, es decir
iniciar sesión en consola, normalmente se les deja con /usr/bin/nologin o /bin/false
En este archivo se almacena la información de las contraseñas cifradas para cada una de las
cuentas de usuarios. Además de la contraseña cifrada, en el archivo /etc/shadow también se
almacena la información opcional acerca del envejecimiento de la contraseña o expiración. La
introducción del archivo sombra ocurrió debido a la necesidad de separar las contraseñas cifradas
del archivo /etc/passwd. Esto se hizo necesario en virtud de que fue creciendo la facilidad con la
cual las contraseñas cifradas podían ser descifradas con el aumento en el poder de procesamiento
de las computadoras de consumo. La idea fue mantener el archivo /etc/passwd de manera que
pudiera ser leído por todos los usuarios, sin almacenar las contraseñas cifradas en él, y a
continuación, hacer que el archivo /etc/shadow sólo pudiera ser leído por el raíz u otros
programas privilegiados que requieren el acceso a esa información. Un ejemplo de ese tipo de
programas sería el programa login (de concesión de acceso).
Se podría uno preguntar: “¿por qué no sólo hacer que el archivo /etc/passwd pudiera ser leído
sólo por el raíz u otros programas privilegiados?” Bien, eso no es tan sencillo. Al tener el archivo
de contraseñas abierto durante tantos años, el resto del software del sistema que creció en torno
a él dependió del hecho de que ese archivo siempre podía ser leído por todos los usuarios.
Cambiar esto sencillamente haría que el software fallara.
• Contraseña cifrada.
• Dias transcurridos a partir del 1 de Enero de 1970 en que la contraseña se cambió por
última vez.
10
Servicios de Red e Internet
• Días transcurridos a partir del 1 Enero de 1970 en que se desactiva esa cuenta.
• Un campo reservado.
Enseguida, se presenta una entrada muestra del archivo /etc/shadow para la cuenta del usuario
postgres:
postgres:$1$lYWUMpDn$flx4reZc7F8Pxr9eHV6/9/:15139:0:99999:7::22279:
El archivo /etc/shadow contiene una línea para cada usuario, similar a las siguientes:
root:ghy675gjuXCc12r5gt78uuu6R:10568:0:99999:7:7:-1::
sergio:rfgf886DG778sDFFDRRu78asd:10568:0:-1:9:-1:-1::
En este fichero almacenamos las contraseñas cifradas y nos da información sobre caducidad y
validez de la cuenta.
$6$OrqRmooe$2XSkIJNgd3Te/xPUd6S1wdysNgPhFrT7UFHkbhvjECkt/L9Z3rmqBUbRDBcfLf4sz/Z
775X.WgJTaijVG7mhn1
En términos de cifrado hay varios algoritmos (de cifrado seguro) hash usados. el número
destacado en rojo $6$ indica en qué tipo de hash está mi contraseña cifrada, en este caso se trata
de SHA-512, (Secure Hash Algorithm) y por lo tanto tiene 86 caracteres en total.
Este es un resumen de los más conocidos cuando os los encontréis en este fichero, dependiendo
del primer número entre símbolos $ será una codificación u otra.
Al poner una contraseña a un usuario, una función hash la cifra con el algoritmo determinado
según sea el cifrado. Toma un bloque arbitrario de datos y devuelve una cadena con una
determinada longitud (valor hash). Los datos para ser codificados son denominados “el mensaje”
y el valor hash se le denomina “message digest” o simplemente “digest”
Pero no es todo… pues si dos contraseñas fueran iguales o supieramos el algoritmo usado quizás
podríamos descifrarlo sabiendo unas cuantas contraseñas básicas y comparando el digest hasta
sacar unas equivalencias.
11
Servicios de Red e Internet
Para evitar esto y cerrar completamente el cerco de seguridad de la contraseña, se le añaden los
bit salt, que son datos al azar añadidos a la contraseña para posteriormente cifrar con el hash.
Digamos que lo enmascaramos en más datos y así no sabremos si qué parte es la contraseña real
y cuales son los datos sin valor.
$6$OrqRmooe$2XSkIJNgd3Te/xPUd6S1wdysNgPhFrT7UFHkbhvjECkt/L9Z3rmqBUbRDBcfLf4sz/Z
775X.WgJTaijVG7mhn1
Todo lo marcado en azul serían los salt bits, desde el segundo “$” hasta el siguiente.
Los cifrado con bits salt se usan en muchos sistemas modernos, desde seguridad de credenciales
a Seguridad en Internet. Hacen mucho más lentos los ataque por diccionario y fuerta bruta para
el crackeo. Sin estos como introducimos anteriormente un atacante que descifra una contraseña,
sólo necesita adivinarla uno vez y con ella tiene la llave para aligerar la velocidad de crackeo de
las demás.
En la autenticacion pam se pueden definir el tipo de algoritmo usado en particular para servicios
12