Hashing

Salt (sal)

Para hacer más difícil la utilización de las tablas arcoiris, se le suele agregar a la contraseña un conjunto de bits aleatorios llamado “sal” (salt en inglés) antes de hashearla. Esto asegura de que el hash de tu contraseña siempre va a ser único en comparación con usuarios con la misma contraseña.

Digamos que Juan y Pepe se crean una cuenta en un servicio y, sin que el otro lo sepa, sus contraseñas son goku123. Usando el algoritmo SHA-256, el hash se ve de esta manera:

18B722E185EEBF0A6533826DEFD86456DCF47C7329FBA0E3ECB59DC91B3D0887

Si decidimos agregar salt (debe ser única para cada uno), obtendremos lo siguiente:

Juan: Hash(goku123 + VtJVjfGzq6 )

Pepe: Hash(goku123 + 5bLhd6ahHO)

Los nuevos hashes resultantes van a ser:

Juan: B57D7497DD5368FE8EF1E4C7461ED9DE23C8222AB50FA6BA2C37A75213E8EB81

Pepe: EA81ACD2DE7EEF525DF002CB8B403C78C67B466E501E8FC66C5DBE0F3B735CC6

Podemos notar como ahora son completamente distintos.

Pepper (pimienta)

Ya que la salt suele guardarse dentro del sistema, algunas implementaciones deciden agregar una cadena pequeña o carácter al final de la contraseña. Esta cadena se llama pimienta (pepper). La pimienta también se genera aleatoriamente y se puede decidir si generarla en el momento, o guardarla por separado.

Por ejemplo, tomaremos como pepper la letra E. Esto es transparente para el usuario, pero la contraseña va a ser hasheada junto a la pimienta (la E). Esto provee una capa más de protección a las tablas arcoiris. Al servidor no le cuesta nada porque sólo tiene que ir probando y hasheando con cada carácter hasta llegar a la E, pero al atacante le va a tomar muchas veces (52 en este caso, ya que se tiene en cuenta min. y mayús.) más tiempo de crackear.

Hash de goku123: 18B722E185EEBF0A6533826DEFD86456DCF47C7329FBA0E3ECB59DC91B3D0887

Hash de goku123E: F1949DE9ADCCB566403962C0E00D60D251D011D91364F2EBE6F117EC823AC072

Costo en algoritmos

Usar sal y/o pimienta hace los ataques de fuerza bruta más lentos, pero aún posibles. Para resolver esto, se suele usar una variante en la función hash, que ralentice el proceso intencionalmente. Ejemplos: bcrypt, scrypt, argon2.

Estos algoritmos toman la contraseña, una sal y un costo. Este último es un parámetro que incrementa la cantidad de trabajo necesario para computar un hash de manera exponencial con cada iteración. Esto no incrementa el costo de verificar contraseñas cuando el usuario se loguea normalmente de manera significativa, pero penaliza gravemente a aquel que intenta adivinar y se equivoca todas las veces.

Referencias

https://www.tarsnap.com/scrypt/scrypt.pdf

El hashing permite generar un string de longitud fija dado otro string de cualquier longitud. Por ejemplo: Sea F una función de hashing que genera hashes de 32 caracteres, entonces, dada una entrada de N caracteres, siendo N cualquier entero positivo, el resultado siempre tendrá 32 caracteres (es decir, 128 bits).

Lo anterior se puede representar así:

Entrada de N caracteres => Función Hash => Resultado de 32 caracteres.

A su vez teniendo el resultado generado por el hash es realmente muy difícil obtener la entrada con el cual se generó. Notar que la cantidad de entradas es superior a la cantidad de resultados posibles, pues un resultado podría haber sido generada por más de una entrada.

Algoritmos para generar hashes

Ejemplos para generar hashes en Linux

$ date +%s%N | md5sum

70f4533cdf78cb958270cb61e6c22c8f

$ echo -n hola | md5sum # Sin el retorno de carro.

4d186321c1a7f0f354b297e8914ab240

$ echo hola | md5sum # Con el retorno de carro.

916f4c31aaa35d6b867dae9a7f54270d

Ejemplos para generar hashes en Python 3

>>> import hashlib
>>> m = hashlib.md5()
>>> m.update("hola")
>>> m.hexdigest()
'4d186321c1a7f0f354b297e8914ab240'

Para generar un bcrypt usando la librería bcrypt [https://pypi.org/project/bcrypt/]

>>> import bcrypt
>>> password = b"super secret password"
>>> hashed = bcrypt.hashpw(password, bcrypt.gensalt())
>>> hashed

Referencias:

https://academy.bit2me.com/que-es-hash/

¿En un MD5 existen combinaciones de 32 caracteres que no pueden ser nunca generadas?

A responder...

¿En MD5, se puede cambiar el vector de inicialización sin problemas?

En el algoritmo MD5 existe un vector de inicialización (básicamente son 4 variables) que cambiando al menos un bit de una de ellas, tendremos otra instancia de este algoritmo. A continuación se presentan estas variables:

A: 01 23 45 67

B: 89 ab cd ef

C: fe dc ba 98

D: 76 54 32 10

O bien, escrito de otra forma:

A = 0x67452301

B = 0xEFCDAB89

C = 0x98BADCFE

D = 0x10325476

Referencias útiles

https://github.com/timvandermeij/md5.py

https://tools.ietf.org/html/rfc1321

Los algoritmos que generan hashes reciben como entrada un string (de longitud variable) y generan un string de longitud fija. A estos algoritmos, se le suelen llamar funciones hashes. Una de las características más importantes de una función hash es que un cambio mínimo en la entrada produce una salida totalmente diferente. Por ejemplo, usando el algoritmo SHA-256 para entradas similares:

labsis:      910FA8C73764DC9DDC46810D873624843C520B085C71C3AF30F1C2C4065D1987

Labsis:      F7440C74D3A3CFE6FC6AC1537E873FE90E42DA66202DAFD0FD20C9605FAB47F2

LABSIS:      8877A447873EE3E417244BE2A4F2D596D086CD230810E91ED28F6BB66F36E1BF

labsissssss: 05D29F443C6FD6C2D5FD95BA85A57D42DC771935A2F49E421C0B9EE87112E380

lab:         A51146D38077FF992EBA84CF1D5E9B249073503EB74868699016153B031A38F7

labsir:      D42EE5817CB91BA9AEACEFFB0A0B63B5C9BDC91D465FBF7547576F34F862043B

Como se puede notar de los ejemplos anteriores, un hash es bueno para detectar cambios en la información. Por ejemplo, si hubo un cambio de al menos un bit en la entrada, su hash va a ser totalmente diferente. Por esta razón, algunas descargas de archivos se complementan con el hash, para que al descargar se calcule el hash del archivo descargado y se compare con el ofrecido. En caso que sean iguales se puede asumir que el archivo no se modificó ni se dañó durante la descarga. En caso que sean diferentes, podemos asegurar que al menos un bit cambió.

Otro uso común de los hashes, es guardar las contraseñas hasheadas en la base de datos. Esto se usa en muchos sitios web pero también en el sistema operativo Linux (archivo /etc/shadow).

Una colisión de hashes es una situación que se produce cuando dos entradas distintas producen la misma salida. En término matemáticos:

F(X1) = S

F(X2) = S

Dónde:

F es una función hash.

X1, X2 son dos entradas diferentes.

S es el hash.

Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número potencial de posibles entradas es mucho mayor que el número de salidas que puede producir una función hash. Por supuesto, se podría crear una función hash perfecta, reduciendo en número de entradas posibles.

Existen al menos 3 maneras de almacenar claves:

• En texto plano (plain text).

• Cifrada con una clave (puede ser simétrica o asimétrica).

• Hasheada.

Guardar las contraseñas como texto plano es una estrategia muy riesgosa. Si un atacante accede de alguna manera a una base de datos, y las contraseñas estaban guardadas en texto plano, éste no tiene que hacer ningún tipo de esfuerzo para usarlas.

Por otro lado, se pueden cifrar. Esto impedirá que el atacante obtenga las contraseñas directamente como en el caso anterior.

La tercer alternativa es hashearlas, que evidentemente no podremos recuperarla nunca más, pues hemos guardado el hash de la contraseña y no hay un proceso reversible para eso.

Ejemplo

En Linux se guardan las claves hasheadas en el archivo /etc/shadow. Están formadas por una terna: $ ID $ SALT $ HASH. El ID indica la función hash que se utiliza (normalmente es el número 6 que indica a la función SHA-512).

En caso que quieras generar una clave tal cual como está en el archivo /etc/shadow podés usar:

$ openssl passwd -6 -salt SALT clave

La función hash MD5 recibe como parámetro un string de N caracteres que se compone de T bits dónde T < 2 ^ 64. Ya veremos porqué este límite.

Pasos que ejecuta el algoritmo

PASO 1: Adición de bits

1. Convierte el string recibido a una representación ASCII.
2. La representación en ASCII es dividida en bloques de 512 bits. Evidentemente, el último bloque puede no tener los 512 bits completos y habrá que completarlos con un padding. Pero este padding no debe completarse hasta los 512 bits sino que hasta los 448 bits, ya que los últimos 64 bits se reservan para especificar el tamaño original del mensaje en bits (es decir, sin el padding). Es por eso, que como se reservan 64 bits para el tamaño, en principio, el string máximo de entrada debería tener 2 ^ 64 bits.

Ahora bien, pasemos a completar el padding en el último bloque. Acá hay dos opciones que pueden ocurrir:

CASO 1: El último bloque tiene menos de 448 bits: Se debe aplicar un padding hasta completar los 448 bits (un 1 y el resto 0).

CASO 2: El último bloque tiene 448 bits o más: Se debe aplicar un padding hasta completar los 512 bits de este último bloque y los primeros 448 bits de un bloque extra que se debe agregar después del último.

PASO 2: Longitud del mensaje

Tanto en el último bloque del caso 1 como en el bloque añadido del caso 2, se debe establecer el tamaño del mensaje original (sin el padding) en los últimos 64 bits.

En los pasos 1 y 2, se asegura que el tamaño del mensaje de T bytes será extendido hasta que sea congruente con 448, módulo 512.

Para entender mejor estos 2 primeros pasos, se puede hacer uso del simulador:: https://fthb321.github.io/MD5-Hash/MD5OurVersion2.html

PASO 3: Inicializar el búfer MD

Se inicializan 4 variables (también llamado vector de inicialización). Los valores más comunes en hexadecimal son (aunque podrían ser otros):

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

PASO 4: Procesado de mensaje en bloques de 16 palabras

PASO 5: Salida

Referencias: https://es.wikipedia.org/wiki/MD5#Algoritmo

https://www.tarsnap.com/scrypt/scrypt.pdf

https://academy.bit2me.com/que-es-funcion-hash-scrypt/