Diseccionando el SHA-512, un preludio al Length Extension Attack.

La Antártida, 28 de febrero de 2042. Transmisión recuperada al 67%, reproduciendo:

... la IA llamada Bob fue diseñada para recopilar y almacenar ... mi equipo fue asignado en secreto a esta investigación hace 5 años... Eve logró sesgar a Bob para que use un ... de autenticación vulnerable con un sabotaje a los repositorios de código públicos durante el cataclismo de internet del 2037... había un espía en el... atacados... logré escapar solo para enviarte esta transmisión, no hay nadie más en quien confíe, sé que Eve aún no ha logrado obtener el portal de acceso para explotar la vulnerabilidad, de lo contrario no nos habría...

Le he tomado gusto a los retos de CTF, así que quise comenzar con una historia.

Esta es una serie de artículos que tienen como objetivo facilitar al lector la comprensión de la vulnerabilidad Length Extension Attack cuando no se emplea correctamente el SHA-2 (especificamente el SHA-512) como código de autenticación de mensajes; y se dividirá en 2 partes:

Parte 1: Diseccionando el SHA-512.
Parte 2: Caso de estudio SHA-512 para autenticar mensajes.

¡Cada artículo se potenciará con scripts de Python3 reproducibles!, a los que se puede acceder en mi repositorio de github magor-posts-resources.

Nota: Los diagramas e imágenes que no tengan la referencia de dónde fueron tomados, es porque son de mi autoría.

Funcionamiento del SHA-2

El SHA-2 es una familia de 6 funciones hash criptográficas publicadas por la National Institute of Standards and tecnology - NIST en su Federal Information Processing Standard - FIPS . Las funciones hash convierten un dato de entrada en una representación condensada denominada message digest o hash, que si cumplen una serie de propiedades de seguridad se denominan funciones hash criptográficas y las hace útiles en múltiples aplicaciones como almacenamiento de contraseñas y búsqueda en bases de datos.

Las 6 funciones SHA-2 son SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256 al ser parte de la misma familia, comparte la misma estructura algorítmica, solo varían en los valores y tamaño de las variables con los que trabajan. A continuación, se presenta la estructura general para la familia SHA-2:

El proceso explicado de esta sección se basa en el FIPS 180-4 Secure Hash Standard (SHS). Por lo que parte de la explicación será directamente tomada del estándar.

Preprocesamiento: Pad, Parse and initializate. Se encarga de darle una estructura de bloques (chunks) de igual tamaño al mensaje e inicializa algunas variables, esto se hace en 3 etapas:
- Aplicar un padding al mensaje para que la longitud sea múltiplo de 512 bits para el SHA-256 o de 1024 bits para el SHA-512; El padding usa las reglas del Merkle–Damgår-compliant padding.
  
  ya que el objetivo es que se divida en bloques del mismo tamaño, si no se hiciera el padding podría quedar un bloque de tamaño diferente a los otros)
- Aplicar un parse, que consiste en dividir el mensaje en chunks de N bits (de 512 bits o 1024 bits para el SHA-256 o el SHA-512 respectivamente).
- Declarar una serie de constantes $K_{t}^{\{512\}}$ y los valores hash iniciales $H^{(0)}$, el tamaño y valores dependerá de la función SHA-2 que se emplee.
Procesamiento de chunks. En el que se aplican la función de compresión (compression function) y el message schedule mediante operaciones a nivel de bits - bitwise operation. Mas adelante se explicará en detalle.

Diagrama de flujo de SHA-512

Con la descripción general dada previamente, se presenta en la figura 1 el diagrama de flujo del algoritmo de hash para el SHA-512 que se desglosará en el artículo.

Figura 1. Diagrama de flujo de algoritmo SHA-512

Con el camino trazado, ahora se va a detallar cada etapa de procesamiento, partiendo como ejemplo, de la siguiente entrada de texto:

>>> msg = b"Para_encontrarlo_debes_mirar_mas_alla_de_lo_que_ves" # bytes

Es oportuno resaltar que para efectos prácticos, todas las variables se manejaran a nivel de bytes (por eso en Python3, el msg se inicializa con tipo de dato bytes usando el prefijo b al string). Y por esa misma razón, no se usan tildes ya que bytes can only contain ASCII literal characters.

Preprocesamiento SHA 512

Padding

El mensaje se debe preparar bajo las siguientes reglas (recordando que para SHA-512 se busca procesar bloques de 1024b bits).

1. Calcular la longitud `l` del mensaje en bits

Al final del padding se debe agregar la longitud del mensaje medida en bits en formato binario de 128 bits. Y a pesar de que se concatena al final del padding, es nescario calcularla al inicio ya que debe ser la longitud del mensaje de entrada antes de cualquier tratamiento.

    >>>➊L = len(msg) # Longitud del string en número de bytes
    >>> L
    51
    >>>➋l_bits = L*8
    >>> l_bits
    408
    >>>➌len_big_endian = l_bits.to_bytes(16,'big')
    >>> len_big_endian
    b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x98'

Para el msg de ejemplo, L almacena en ➊ el número de bytes que luego en ➋ se convierte a número de bits ; posteriormente el número de bits (408 para el caso de ejemplo) se debe transformar en su representación de bytes con el padding de ceros en ➌, el padding de ceros es necesario ya que el algoritmo indica que se debe representar en un binario de 128 bits (16 bytes). El método int.to_bytes(length, byteorder) recibe dos argumentos length indica la cantidad de bytes con los que se requiere representar el número, si se usan mas de los necesarios se colocaran bytes nulos \x00; y byteorder indica el sistema de ordenado que se usará para "leer los bytes" definiendo big si el byte más significativo es el byte del comienzo big-endian, o little si el byte más significativo es el último byte little-endian.

Es importante destacar que directamente no indicamos bits, ya que la mínima unidad con la que se puede trabajar es el byte, por eso en ➌ la longitud que se usa es 16 bytes (128 bits/8).

En Python3, para escribir un byte en formato hexadecimal dentro de comillas se usa la estructura '\x<2-digit hex number>'. Pero es posible declarar una variable con variable = 0x60 por ejemplo y almacenará el equivalente en entero base 10.

La notación big-endian es a la que quizá se está más acostumbrado ya que un número en base 2 se lee en esa notación (de derecha a izquierda el valor va de menor a mayor), para profundizar en el tema pueden leer Byte ordering

Por el momento se va a reservar la variable len_big_endian, para usarala más adelante.

2. Concatenar el bit `1` al final del mensaje

Como se resaltó en el paso anterior, no es posible agregar solamente un bit 1, ya que las instrucciones que llegan al procesador están agrupadas en en octetos de bits, así que para agregar ese único bit 1, se debe usar el byte 10000000 que en hexadecimal es 0x80 (128 base 10) ; de esta manera, realmente se concatena el bit 1 y 7 bits 0.

msg_pad = msg + b"\x80"

En la figura 2 se aprecia el comienzo de la estructura de bloque de 1024 bits que se busca realizar.


Figura 2. Se concatena `0x80` para agregar en binario `10000000`

3. Concatenar `k` bits "0"

Donde k es el valor más pequeño que cumple con: $$l + 1 + k \equiv 896 \bmod 1024$$Donde:

$l$ es la longitud del mensaje en bits.
1 es el bit que se concatena al mensaje.
$k$ es el número de bits 0 que se concatenan luego del bit 1.

En esencia, lo que dice la ecuación es que se quieren agregar k veces el bit 0 para rellenar el bloque, teniendo en cuenta de que al principio del bloque irá una porción del msg, que se agrega el byte 0x80 y que al final se debe agregar la longitud del mensaje con un tamaño de 128 bits.

En aritmética modular la ecuación presentada indica que $(l + 1 + k)$ y $896$ son congruentes según el módulo $1024$. y que sean congruentes quiere decir que tanto 896 como $(l + 1 + k)$ deben dejar el mismo resto si se dividen entre $1024$ bajo una división euclídea , en otras palabras, que $896$ es el residuo de la división entre $(l + 1 + k)/1024$.

La división euclídea es la división con resto, que mantienen los números en el conjunto de los enteros, diferente a la división exacta, que los maneja en el conjunto de los números reales.

Bien, ahora el padding (es decir, calcular k) se puede implementar de múltiples maneras, les presentaré la que escogí por su belleza matemática.

Note que $896 + 128 = 1024$, justo los 128 bits necesarios para concatenar la longitud del mensaje calculado en el paso 1 del padding, y gracias a que la relación de congruencia mencionada previamente satisface todas las condiciones de una relación de equivalencia se cumple la siguiente propiedad:

Si $a \equiv b \bmod N$ entonces se cumple que $(a + z) \equiv (b + z) \bmod N$ para cualquier entero $z$. Lo que significa que se puede sumar el mismo valor a ambos lados de la igualdad sin alterar la relación.

Aplicando la propiedad se suma $128$ en cada lado: $$(l + 1 + k + 128) \equiv (896 + 128) \bmod 1024$$Ahora se resta $k$ en ambos lados: $$(l + 1 + 128) \equiv 1024 - k \bmod 1024$$Y, según la relación euclídea, el $1024 -k$ es el resto de la divisón de $(l+1+128)/1024$. En Python se puede re escribir con el operador módulo % como una igualdad:$$(l + 1 + 128 ) \% 1024 = 1024 - k$$ Se despeja $k$: $$k = 1024 - (l + 1 + 128 ) \% 1024$$Se podría pensar que la ecuación está lista para escribirse en Python, pero cuidado, hay un detalle que no puede pasar desapercibido. Recuerde que la ecuación está planteada en número de bits y que en teoría solo se concatena el bit 1 y por eso solo se suma $+1$, pero nosotros no agregamos realmente el bit 1 sino el byte 0x80, es decir agregamos 8 bits. Realizando esa corrección la ecuación queda: $$k = 1024 - (l + 8 + 128 ) \% 1024$$ En el código de Python escribo la ecuación convirtiéndola a bytes:

    K = 128 - (L + 1 + 16)%128 # 128 - (51 + 1 + 16)%128 = 60

    msg_pad = msg + b"\x80" + b"\x00"*K

Para aquellos que inician en el mundo de la aritmética modular, recomiendo ver la serie de videos del canal de Lemnismath.

4. Concatenar la longitud del mensaje

Escrito en binario en bloque de 128 bits que ya se procesó en el paso 1 del padding. Resulta:

msg_pad = msg + b"\x80" + b"\x00"*K + len_big_endian

Con el proceso de padding finalizado el mensaje luce como se presenta en la figura 3.


Figura 3. Proceso completo de padding: concatenar `0x80`, $k$ veces `0x00` y la longitud del mensaje en un binario de 128 bits

Lo escribo en monoespaciado por si se requiere copiar:

>>> msg_pad
b'Para_encontrarlo_debes_mirar_mas_alla_de_lo_que_ves\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x98'

Y recolecto todo el proceso de padding en una función de Python:

def padding(msg: bytes) -> bytes:

    # Cálculo de longitud, midiendo el número de bits usados en base decimal
    L = len(msg) # 51 bytes
    l_bits = L*8 # 408 bits

    len_big_endian = l_bits.to_bytes(16,'big')
    K = 128 - (L + 1 + 16)%128 # 128 - (51 + 1 + 16)%128 = 60

    msg_pad = msg + b"\x80" + b"\x00"*K + len_big_endian

    return msg_pad

Para solventar las dudas que se puedan presentar, dejo algunos casos con diferentes longitudes de mensaje, tanto ejecutandolo con Python como con una representación visual en la figura 4.

Para facilitar el control de la longitud del mensaje, repito la letra H un número n de veces

>>> msg_pad = padding(b'H'*108)
>>> msg_pad
b'HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03`'
>>> msg_pad = padding(b'H'*209)
>>> msg_pad
b'HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x06\x88'
>>> msg_pad = padding(b'H'*251)
>>> msg_pad
b'HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x07\xd8'
>>> msg_pad = padding(b'H'*390)
>>> msg_pad
b'HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x0c0'


Figura 4. Ejemplos de padding para diferentes longitudes de mensajes

Note que en Python3 cuando un hexadecimal tiene una representación de carácter imprimible, se verá el carácter en lugar del hexadecimal, como ocurre en el último ejemplo que al final queda \x0c0, esto es equivalente a b'\x0c\x30' pero el b'\x30' se representa con 0 por su equivalencia en ASCII.

Parssing

Si el proceso de padding quedó bien hecho, se debe poder dividir el mensaje en $N$ bloques de exactamente 1024 bits (128 bytes).

def parssing(msg_pad: bytes) -> list:

    M = []
  ➊ for i in range(0, len(msg_pad), 128):
      ➋ M_i = msg_pad[i:i+128]
        M.append(M_i)

    return M

El bucle ➊ se realiza en saltos de 128 bytes, de tal manera que cada i-ésimo bloque o chunk ➋ se agregará a la lista M para ser procesado en la siguiente etapa.

Presento este paso con el objetivo de dar claridad al algoritmo, una vez se comprenda, se verá que podría prescindirse y realizarce directamente en el procesamiento.

Initialize

Consiste en inicializar 8 valores hash con datos de 64 bits (8 bytes) $$ \begin{gather} H^{(0)}_0 = 6a09e667f3bcc908 \\ H^{(0)}_1 = bb67ae8584caa73b \\ H^{(0)}_2 = 3c6ef372fe94f82b \\ H^{(0)}_3 = a54ff53a5f1d36f1 \\ H^{(0)}_4 = 510e527fade682d1 \\ H^{(0)}_5 = 9b05688c2b3e6c1f \\ H^{(0)}_6 = 1f83d9abfb41bd6b \\ H^{(0)}_7 = 5be0cd19137e2179 \\ \end{gather} $$ Los valores surgen de representar en hexadecimal los primeros 64 bits de las partes fraccionarias de las raíces cuadradas de los primeros 8 números primos.

Para comprender el enunciado anterior, lo voy a desglosar desde el final al inicio e iré mostrando el ejemplo con el primer valor del hash $H^{(0)}_0$.

Dice que tome los primeros 8 números primos, para el $H^{(0)}_0$ correspondría el primer primo 2:

Luego dice, saque la raíz cuadrada y tome solo la parte fraccionaria (números a la derecha de la coma), es decir: $$ \begin{gather} \sqrt(2) = 1.4142135... \\ fractional_{part} = 0.4142135... \end{gather} $$

Comencemos realizando ese proceso en Python3:

>>> import decimal
>>>➊2**(1/2) # or import math ; math.sqrt(2)
1.414213562373095
>>>➋decimal.getcontext().prec 
28
>>>➌prime = decimal.Decimal(2)
>>> prime
Decimal('2')
>>>➍square_root = prime.sqrt()
>>> square_root
Decimal('1.414213562373095048801688724')
>>> whole_part = int(square_root)
>>>➎fractional_part = square_root - whole_part
>>> fractional_part
Decimal('0.414213562373095048801688724')

Utilizo el módulo decimal con el objetivo de tener mayor precisión en el manejo de números de punto flotante. Por defecto decimal maneja una precisión a nivel de 28 decimales ➋ en contraste con ➊ de 15 decimales. Se define 2 como un objeto de la clase decimal.Decimal ➌, la clase tiene el método de raíz cuadrada incorporado ➍, luego se elimina la parte entera ➎ para quedar únicamente con la parte fraccionaria.

Ahora retomando el enunciado, dice que tome los primeros 64 bits de la parte fraccionaria y represéntelos en formato hexadecimal, analice que lo que piden es convertir la parte decimal de un número base 10 a base 16, para ello recomiendo leer conversión de parte decimal base 10 a base 2.

El método de conversión entre diferentes bases es equivalente, Solo varía el tamaño con el que se hacen las multiplicaciones o divisiones, para base 16, reemplace el 2 que aparezca por 16 (y cuando obtenga un numero entre 10 - 15, reemplácelo por letras entre A - F)

Un resumen del algoritmo a realizar es:

Tomar la parte fraccionaria del número real.
Multiplicar la parte fraccionaria por la base del sistema de numeración a convertir (16 en este caso) y restarle la parte entera, para obtener nuevamente solo la parte fraccionaría.
Si la parte entera está entre 10-15 mapéela entre A-F. La parte entera sustraída es ahora parte del valor hexadecimal.
Ir al paso 1 hasta completar la cantidad de números hex que se requiere representar.

A continuación presento un paso a paso de ejemplo para convertir los primeros 3 bytes de la parte fraccionaria de 0.41421 base 10 a base 16.

'''
    0.41421 x 16 =  6.62736 ->  6 -> 6
    0.62736 x 16 = 10.03776 -> 10 -> 6a   # 10 se mapea en 'a'
    0.03776 x 16 =  0.60416 ->  0 -> 6a0
    0.60416 x 16 =  9.66656 ->  9 -> 6a09
    0.66656 x 16 = 10.66496 -> 10 -> 6a09a 
    0.66496 x 16 = 10.63936 -> 10 -> 6a09aa
'''

Tenga en cuenta que el paso 4 habla de cantidad de números hex, y una pareja de hexadecimales representa un byte. Requerimos 64 bits que equivale a 8 bytes, por lo que se requieren 8 parejas de hexadecimales, es decir longitud de 16 valores hexadecimales

Una vez comprendido el proceso de conversión se puede definir una función decimalPart_to_hex() que se encargue de retornar un string con la representación hexadecimal a partir de ingresar la parte fraccionaria:

def decimalPart_to_hex(➊value: decimal.Decimal, length: int) -> str:
    new = value*16
  ➋ whole = int(new)
    fractional_part = new - whole
    length += -1
    if length >= 0:
        return ➌ hex(whole)[2:] + ➍decimalPart_to_hex(fractional_part, length)
    else:
        return ''

Aplico el algoritmo de recursión para realizar la conversión. En él se va a ir multiplicando la parte fraccionaría ➊ por la base (16 en este caso) y almacenar la parte entera ➋ que será un valor entre 0-15, por lo que al usar hex(N) se mapea entre 0-F ➌, y se incluye dentro del return con el llamado a la misma función con la nueva parte fraccionaría ➍, y para evitar que siga indefinidamente la variable length se usa para ir contando el número de veces que se llama la recursión.

>>> H_0 = decimalPart_to_hex(fractional_part, 16)
>>> H_0
'6a09e667f3bcc908'

Al ejecutar la función se define la length en 16 ya que requerimos 8 bytes (64 bits) y cada pareja de valores hexadecimales es un byte.

Se podría haber realizado un algoritmo iterativo en lugar de uno recursivo, solo utilicé el recursivo para variar, pero usualmente se prefieren los iterativos sobre los recursivos. ¿Qué pasaría si no se limitara la conversión de un número irracional a otro sistema de numeración?, pues, así como un número irracional como el sqrt(2) tiene infinitos decimales, !la conversión nunca pararía!, es por eso que se debe especificar el límite al decir los primeros 64 bits de la parte fraccionaria.

En Python se almacenan los 8 valores de inicialización de hash en una tupla:

H_0 =(
    0x6a09e667f3bcc908, # H_0_0
    0xbb67ae8584caa73b, # H_0_1
    0x3c6ef372fe94f82b, # H_0_2
    0xa54ff53a5f1d36f1, # H_0_3
    0x510e527fade682d1, # H_0_4
    0x9b05688c2b3e6c1f, # H_0_5
    0x1f83d9abfb41bd6b, # H_0_6
    0x5be0cd19137e2179, # H_0_7
)

Curiosidad sobre la inicialización: how to compute initial buffer of sha 512. La inicialización será crucial para cuando se realice el Length extension attack.

Adicional a los valores hash que se inicializan, existen 80 constantes $K_{0}^{\{512\}}, K_1^{\{512\}}, ..., K\_79^{\{512\}} $ de 64 bits word. Estos valores surgen de representar en hexadecimal los primeros 64 bits de las partes fraccionarias de las raíces cúbicas de los primeros 80 números primos.

K = (
    0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,  
    0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
    0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
    0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694, 
    0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 
    0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 
    0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 
    0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70, 
    0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df, 
    0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b, 
    0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 
    0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
    0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
    0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
    0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
    0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
    0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178,
    0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
    0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
    0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
    )

Intente aplicar el proceso presentado para los valores hash en el cálculo de los valores de la constante K. Note que las diferencias con respecto al $H^{(0)}$ son que ya no se usan las raíces cuadradas sino las cúbicas y que en lugar de tomar solo los primeros 8 primos se toman los primeros 80.

Con esto se finalizan los preparativos para el procesamiento de cada bloque.

Procesamiento SHA-512

La fase de procesamiento de chunks consiste en emplear una serie de funciones definidas a partir de varias operaciones aplicadas a un conjunto de variables.

Ya que eso es todo el procesamiento, vale la pena separar una sección para definir cada una.

Definiciones

Variables

Chunks number $N$. Número de bloques en el mensaje luego del padding.
Constans $K_t$ . $K_{0}^{\{512\}}, K_1^{\{512\}}, ..., K\_79^{\{512\}} $. 80 constantes cada una es tipo word de 64 bits.
Message Block $M^{(i)}$. i-éssimo Message Block $M^{(1)}$ , $M^{(2)}$ , ... , $M^{(N)}$ cada uno de de los bloques (chunks) de mensajes que serán procesados, cada uno de 1024 bits.
Message Schedule $W_t$. t-ésimo message schedule $W^{(1)}_t, W^{(2)}_t, ..., W^{(N)}_t$ cada uno de tipo word de 64 bits. con t en el rango $0 \leq t \leq 79$.
Working variables. $a, b, c, d, e, f, g, h$ cada una de tipo word de 64 bits.
Hash value: $H^{(i)}_0, H^{(i)}_1, ... , H^{(i)}_7$ i-ésimo valor, va desde el inicializado previamente en (0) hasta el (N) que será el hash final. Cada uno es de tipo word de 64 bits y al concatenarlos se representa el hash.
Temporary Words: $T_1$ y $T_2$ ambos de tipo word de 64 bits.

El símbolo {512} indica que el tamaño de la variable es de 512 bits.

Operaciones

A continuación, se presentan las operaciones aplicadas bit a bit que se emplearán (bitwise operators):

$\land$ a & b. AND.
$\lor$ a | b. OR.
$\neg$ a ~ b. Complemento (negación).
$\oplus$ a ^ b. XOR.
$\ll$ a << b. Desplazamiento a la izquierda left-shift.
$\gg$ a >> b. Desplazamiento a la derecha rigth-shift.
$+$. (a + b)%2**w. Toda suma se realiza aplicando al final el módulo de $2^{w}$, donde w es el número de bits de la variable.
$ROTL^n(x)$ (x << n) | (x >> (w - n)). Desplazamiento a la izquierda circular de n bits (circular left shift) donde x es tipo word the w bits, n es un entero $0 \leq n < w$. Se define como: $$ROTL^n(x) = (x \ll n) \lor (x \gg w - n)$$
$ROTR^n(x)$ (x >> n) | (x >> (w - n)). Desplazamiento a la derecha circular de n bits (circular right shift) donde x es tipo word the w bits, n es un entero $0 \leq n < w$. Se define como: $$ROTR^n(x) = (x \gg n) \lor (x \ll w - n)$$
$SHR^n(x)$ x >> n. Desplazamiento a la izquierda left-shift de n bits. donde x es tipo word the w bits, n es un entero $0 \leq n < w$. Se define como: $$SHR^n(x) = x \gg n$$

Usualmente la suma modular (a + b) % 2**w se encontrará como la bitwise operation (a + b) & 0xFFFFFFFF si w=32bits y como (a + b) & 0xFFFFFFFFFFFFFFFF si es w=64bits.

Para SHA-512 el tamaño de las variables es de 64 bits por lo que w en ROTL y ROTR se reemplaza directamente por 64.

Funciones

Se definen las siguientes funciones a partir de las operaciones ya definidas:

$Ch(x,y,z) = (x \land y) \oplus (\neg x \land z)$
$Maj(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$
$\sum_0^{{512}}(x) = ROTR^{28}(x) \oplus ROTR^{34}(x) \oplus ROTR^{39}(x)$
$\sum_1^{{512}}(x) = ROTR^{14}(x) \oplus ROTR^{18}(x) \oplus ROTR^{41}(x)$
$\sigma_0^{{512}}(x) = ROTR^1(x) \oplus ROTR^8(x) \oplus SHR^7(x)$
$\sigma_1^{{512}}(x) = ROTR^{19}(x) \oplus ROTR^{61}(x) \oplus SHR^6(x)$

Con el ánimo de mejorar la comprensión del código cuando se realice el cálculo de hash, declararé todas las funciones y operaciones con funciones lambda de Python:

ROTL = lambda x, n: (x << n) | (x >> (64 - n))
ROTR = lambda x, n: (x >> n) | (x << (64 - n))
SHR = lambda x, n: x >> n
mod_add = lambda x: x % 2**64

Ch = lambda x, y, z : (x & y) ^ (~x & z)
Maj = lambda x, y, z : (x & y) ^ (x & z) ^ (y & z)
sum_0 = lambda x : ROTR(x, 28) ^ ROTR(x, 34) ^ ROTR(x, 39)
sum_1 = lambda x : ROTR(x, 14) ^ ROTR(x, 18) ^ ROTR(x, 41)
sigma_0 = lambda x : ROTR(x, 1) ^ ROTR(x, 8) ^ SHR(x, 7)
sigma_1 = lambda x : ROTR(x, 19) ^ ROTR(x, 61) ^ SHR(x, 6)

Cálculo de Hash

A continuación, se enumeran los pasos a a realizar para cada bloque de mensaje $M^{(i)}$

1. Preparar el message schedule $W_t$

EL message schedule es un array de 80 elementos tipo word de 64 bits $0 \leq t \leq 79$ y se define similar a una función definida por partes :

Cuando aparece t-2 o t+7 , se refiere a 2 posiciones antes o a 7 posiciones después del t-ésimo elemento respectivamente.

La definición anterior quiere decir que en en los primeros 16 elementos se almacena el messsage block o chunk. En la figura 5 se representa este proceso.

Recuerde que cada elemento del array almacena un tipo word de 64 bits , 16 elementos de 64bits serían 64bits*16 = 1024bits y 1024 bits es el tamaño del message block


Figura 5. Se agrupa el chunck `M_i` del mensaje (para el ejemplo solo hay un chunk) en octetos de bytes para alamacenarlo en los primeors 16 elementos del array de $W_t$

Veamos cómo se puede representar en Python, a partir de la lista completa de bloques de mensajes que se definió en la etapa de Parssing y fue declarada como M:

➊H = list(H_0)

for M_i in M:
    # Step 1 ----------------------------------------------------

   ➋w = [0 for _ in range(80)]
   ➌w[:16] = [ 
        int.from_bytes(M_i[i:i+8], 'big') 
        for i in range(0,len(M_i),8)
    ]

    for t in range(16,80):
      ➍w[t] = mod_add(
            sigma_1(w[t-2]) + w[t-7] + sigma_0(w[t-15]) + w[t-16]
        )

Se define la variable H ➊ necesaria para inicializar las working variables. Se inicializa el message schedule con una lista de 80 ceros ➋. Ahora, es imporante tener en mente el tamaño de los datos dentro de cada variable. Un elemento dentro de M_i es de 8 bits (1 byte) y cada elemento de w debe ser de 64 bits (8 bytes) , por lo tanto en un elemento de w se almacenan 8 elementos de M_i (como se aprecia en la figura 5). En ese orden de ideas, en ➌ se almacena los 1024 bits (128 bytes) del chunk M_i empaquetados en 8 bytes por cada elemento de w , ocupando un total de 16 elementos de w (16*8bytes = 128bytes). Posteriormente en ➍ se definen los valores de cada elemento de w entre $16 \leq t \leq 79$.

Recuerde que para el SHA-512 toda suma debe realizarse con el módulo de $2^{64}$, por eso en la operación matemática se encierra entre la función definida previamente mod_add().

Al finalizar esta etapa, el message schedule resulta:

>>> w = 
[5792036358313045603, 8029483220258155631, 6873730404557479789, 7598242665182617971, 6872893719089996901, 6875993186804000095, 8531352062716280832, 0, 0, 0, 0, 0, 0, 0, 0, 408, 2911571691693936358, 3599803890956546956, 7541715550729207361, 14763430595941586223, 12312816151770750367, 12221682926778623852, 5065764605691471852, 9444882222117987553, 15673123931426500046, 3941027188781235209, 14389396689712119193, 2139564214514873782, 14610487654926014051, 15679082303173250267, 8864052261723828435, 12832137541508966715, 11218412837963075850, 8564761913537379313, 1995267673534508094, 9473927269912204893, 10815907873009744948, 17844192423246078642, 13726635304036556379, 17077913186545515888, 18241471263070543080, 1877929430572687587, 17691916832615320201, 3968507111924603135, 16122024224616967401, 12787763067175072500, 2226289459605279125, 18219338217107309453, 17733145255601345618, 7897476126423227698, 17406592524453969575, 13891853509198693113, 1221032305862058346, 5303190446724297546, 2805658293275771255, 2754100344892797835, 9850149294321940400, 408632191292797017, 14727669876953957793, 11747409623811856090, 8023752552519758681, 15791508814739320106, 15892588487913833078, 18274926912844589231, 14380282967716036150, 3091346308650631290, 15928723970613978624, 3026232147351673458, 717573406951658796, 5068373460565810904, 15144568462656454078, 5475194329958706105, 1518406966454733837, 5523058003328669248, 4760157115369456577, 1291837423923193297, 12518490877969124772, 3028727687397583669, 13846493182456048854, 15906529927879894119]

Y si se verifica al convertir de int a bytes el primer elemento de la lista, se encuentra que son los primeros 8 bytes del chunk :

>>> w[0]
5792036358313045603
>>> w[0].to_bytes(8, 'big')
b'Para_enc'

2. Inicializar las 8 Working variables

Se inicializan las 8 working variables a,b,c,d,e,f,g y h a partir del i-ésimo hash $H^{(i)}_0, H^{(i)}_1, ... , H^{(i)}_7$ que se calculan al finalizar cada iteración. En la primera iteración ya que no hay un calculo previo se usa el hash $H^{(0)}$ inicializado previamente.

a, b, c, d, e, f, g, h = H

3. Calcular variables temporales y redefinir Working variables 80 veces

$$ \begin{gather} T_1 = h + \sum_1^{\{512\}}(e) + Ch(e,f,g) + K_t^{\{512\}} + W_t \\ T_2 = \sum_0^{\{512\}}(a) + Maj(a,b,c) \end{gather} $$

Esta estapa es bastante directa, solo hay que tener presente que toda ecuación con una suma debe ir acompañada de la función mod_add() para que se aplique la suma modular.

for t in range(80):
    T_1 = mod_add(h + sum_1(e) + Ch(e, f, g) +K[t] + w[t])
    T_2 = mod_add(sum_0(a) + Maj(a, b, c))

    h = g
    g = f
    f = e
    e = mod_add(d + T_1)
    d = c
    c = b
    b = a
    a = mod_add(T_1 + T_2)

4. Calcular el i-ésimo valor del hash intermedio

Consiste en actualizar el valor del i-ésimo hash, es decir, la lista H la cual en la primera iteración tiene el mismo valor de $H^{(0)}$. La forma de actualizar cada elemento de H consiste en sumar al valor previo una de las working variables según la posición a la que corresponda: $$ \begin{gather} H^{(i)}_0 = a + H^{(i-1)}_0 \\ H^{(i)}_1 = b + H^{(i-1)}_1 \\ H^{(i)}_2 = c + H^{(i-1)}_2 \\ H^{(i)}_3 = d + H^{(i-1)}_3 \\ H^{(i)}_4 = a + H^{(i-1)}_4 \\ H^{(i)}_5 = b + H^{(i-1)}_5 \\ H^{(i)}_6 = c + H^{(i-1)}_6 \\ H^{(i)}_7 = d + H^{(i-1)}_7 \end{gather} $$

for i, val in enumerate([a, b, c, d, e, f, g, h]):
    H[i] = mod_add(H[i] + val)

Tome un momento para analizar el funcionamiento del hash H con la siguiente descripción de la figura 6:

Cada iteración representa el procesamiento de uno de los chunks en los que está dividido el mensaje luego del padding y parssing.
Al inicio de la primera iteración el valor de H es igual a $H^{(0)}$, y al finalizar se actualiza este valor al sumarle las working variables.
El nuevo valor de H al finalizar la primera iteración será el que se use para la siguiente iteración (es decir, para procesar el siguiente chunk).
Y ¿qué pasa en el último chunk?. El valor del hash final será igual al de H al finalizar la última iteración.


Figura 6. Flujo de hash `H` en cada iteración del procesamiento. ¿Qué pasaría si el hash final se usara posteriormente como hash inicial en un nuevo procesamiento?

Ahora compacto todo el procesamiento de chunks dentro de la función chunkProcess().

def chunkProcess(M: list) -> bytes :

    H = list(H_0)
    for M_i in M:
        # Step 1 ----------------------------------------------------
        w = [0 for _ in range(80)]
        w[:16] = [ 
            int.from_bytes(M_i[i:i+8], 'big') 
            for i in range(0,len(M_i),8)
        ]

        for t in range(16,80):
            w[t] = mod_add(
                sigma_1(w[t-2]) + w[t-7] + sigma_0(w[t-15]) + w[t-16]
            )

        # Step 2 ----------------------------------------------------
        a, b, c, d, e, f, g, h = H

        # Step 3 ----------------------------------------------------
        for t in range(80):
            T_1 = mod_add(h + sum_1(e) + Ch(e, f, g) +K[t] + w[t])
            T_2 = mod_add(sum_0(a) + Maj(a, b, c))

            h = g
            g = f
            f = e
            e = mod_add(d + T_1)
            d = c
            c = b
            b = a
            a = mod_add(T_1 + T_2)

        # Step 4 ----------------------------------------------------
        for i, val in enumerate([a, b, c, d, e, f, g, h]):
            H[i] = mod_add(H[i] + val)

    return H

Luego de la ejecución H resulta:

>>> H = chunkProcess(M)
>>> H
[11776468079915641988, 17808183282443026845, 11099696865277071668, 1174027064773869192, 2297846786359901650, 14842508190960772371, 7035755112111959691, 5973417008618735621]

Ya solo falta convertir cada elemento de la lista a hexadecimal y concatenarlos:

def hexdigest(H:list) -> str:
        return ''.join(map(lambda x: f"{hex(x)[2:]:0>16}", H))

Para ello, defino la función hexdigest() donde se usa map() para aplicar la función lambda a cada elemento de H, y en la función lambda se convierte a hexadecimal cada elemento y se le remueve el 0x, para al final concatenar todo en un string con ''.join().

Tal vez se esté preguntando el porqué se usa la estructura f-strings. f'{valor:0>16}'. Se usa porque hay casos en los que la conversión a hexadecimal resulta comenzando con 0, por ejemplo, si uno de los valores del hash fuera 151085024878499711 el primer byte de izquierda a derecha sería el 0x02, pero Python ignora el 0 ya que es un cero a la izquierda:

>>> int_2_hex = hex(151085024878499711)[2:]
>>> int_to_hex
'218c30796c3977f'
>>> len(int_to_hex)
15
>>>➊ f"{int_to_hex:0>16}"
'0218c30796c3977f'

Entonces para asegurar que cada byte sea escrito con una pareja de valores hexadecimales, se agrega un padding con el f-string ➊ . La estructura {[variable]:[pad][symbol][n]} indica que a la [variable] se le agregará un padding con el carácter definido en [pad] para asegurar que la longitud total del string sea igual a [n], y con el [symbol] se define si se quiere realizar el padding a la izquierda, derecha o centro.

Y !listo!, ya se obtiene el hash SHA-512 del mensaje en formato hexadecimal:

>>> hexdigest(H)
'a36e6b5304192c84f7236057f511019d9a0a0b7d815b5134104afb65288a7e881fe3977a49413dd2cdfb2e8f8a0ae51361a405ff58126e8b52e5d71eedff0805'

Ahora para darle estructura a las funciones de todo el algoritmo, las agrupé como métodos en la clase sha512()

class sha512():

  ➊ def __init__(self, msg, H_0 = H_0) -> None:
        self.msg = msg
        self.msg_pad = b''
        self.M = []
        self.H = list(H_0)

      ➋ self.padding()
        self.parssing()
        self.chunkProcess()


    def padding(self) -> None:
          # ...SNIP...


    def parssing(self) -> None:
          # ...SNIP...


    def chunkProcess(self) -> None :
          # ...SNIP...


    def hexdigest(self) -> str:
        return ''.join(map(lambda x: f"{hex(x)[2:]:0>16}", self.H))

Se usa el constructor de clase __init__ ➊ para definir los parámetros que requiere la clase: msg y H_0 ( H_0 lo definí con el valor por defecto de la inicialización); las variables principales de cada etapa de procesamiento msg_pad, M y H ; y ejecutar todo el preprocesamiento y procesamiento ➋. Los cambios que se realizan a nivel de funciones principalmente consisten en reemplazar las variables definidas en ➊ en todos los métodos.

Note que para el algoritmo, H_0 no es necesario que sea un parámetro de entrada en el constructor __init__ porque en esencia es una constante. Pero ya se verá la utilidad de jugar con ese valor cuando se comprenda la length extension attack 👀.

Validación

Sin importar el lenguaje en el que se implemente el algoritmo, debe retornar el mismo valor hash para el mismo mensaje de entrada. Por lo tanto, se puede verificar que se aplicó correctamente, al comparar el hash resultante con el que retorna el módulo de Python hashlib o desde la terminal el comando sha512sum.

>>> msg = b"Para_encontrarlo_debes_mirar_mas_alla_de_lo_que_ves"
>>>➊msg_hash = sha512(msg)
>>> msg_hash_hex = msg_hash.hexdigest()
>>>➋msg_hash_hex
'a36e6b5304192c84f7236057f511019d9a0a0b7d815b5134104afb65288a7e881fe3977a49413dd2cdfb2e8f8a0ae51361a405ff58126e8b52e5d71eedff0805'
>>>➌standard_hash = hashlib.sha512(msg)
>>> standard_hash_hex = standard_hash.hexdigest()
>>>➍standard_hash_hex
'a36e6b5304192c84f7236057f511019d9a0a0b7d815b5134104afb65288a7e881fe3977a49413dd2cdfb2e8f8a0ae51361a405ff58126e8b52e5d71eedff0805'
>>>➎msg_hash_hex == standard_hash_hex
True

Primero se calcula el SHA-512 con la clase que definí durante el transcurso del artículo ➊ y se imprime el hash resultante ➋. Luego se usa el módulo hashlib para calcular el hash SHA-512 del mismo mensaje ➌ (se tuvo que haber instalado e importado previamente import hashlib) y se imprime el valor en ➍. Finalmente comparamos que son iguales ➎.

Al ejecutar el comando sha512sum en la terminal de bash, se obtiene el mismo resultado:

$ echo -n "Para_encontrarlo_debes_mirar_mas_alla_de_lo_que_ves" | sha512sum
a36e6b5304192c84f7236057f511019d9a0a0b7d815b5134104afb65288a7e881fe3977a49413dd2cdfb2e8f8a0ae51361a405ff58126e8b52e5d71eedff0805  -

Conclusión

Se presentó en detalle el algoritmo SHA-512 perteneciente a la familia SHA-2, se implementó en Python3, se contrastó el resultado con el módulo de Python hashlib y con el comando de terminal sha512sum. El artículo en sí mismo es el preludio para la siguiente entrega que se enfocará en el length extension attack. Si lo requiere, puede acceder a los códigos presentados en mi repositorio de github magor-posts-resources.

En ida y sin regreso, como el tiempo quedas preso. Eres algo que fue y nunca volverá, pero que si vuelve a suceder a ti te hallarán.

Length Extension Attack en SHA-2 Parte 1 - Diseccionando el SHA-512

Funcionamiento del SHA-2

Diagrama de flujo de SHA-512

Preprocesamiento SHA 512

Padding

1. Calcular la longitud `l` del mensaje en bits

2. Concatenar el bit `1` al final del mensaje

3. Concatenar `k` bits "0"

4. Concatenar la longitud del mensaje

Parssing

Initialize

Procesamiento SHA-512

Definiciones

Variables

Operaciones

Funciones

Cálculo de Hash

1. Preparar el message schedule \(W_t\)

2. Inicializar las 8 Working variables

3. Calcular variables temporales y redefinir Working variables 80 veces

4. Calcular el i-ésimo valor del hash intermedio

Validación

Conclusión

Referencias

Comments

More from this blog

Comunicación PLC Mitsubishi - Python | protocolo MC

Command Palette

Funcionamiento del SHA-2

Diagrama de flujo de SHA-512

Preprocesamiento SHA 512

Padding

1. Calcular la longitud l del mensaje en bits

2. Concatenar el bit 1 al final del mensaje

3. Concatenar k bits "0"

4. Concatenar la longitud del mensaje

Parssing

Initialize

Procesamiento SHA-512

Definiciones

Variables

Operaciones

Funciones

Cálculo de Hash

1. Preparar el message schedule \(W_t\)

2. Inicializar las 8 Working variables

3. Calcular variables temporales y redefinir Working variables 80 veces

4. Calcular el i-ésimo valor del hash intermedio

Validación

Conclusión

Referencias

Comments

More from this blog

1. Calcular la longitud `l` del mensaje en bits

2. Concatenar el bit `1` al final del mensaje

3. Concatenar `k` bits "0"