¿Cómo una función de hashing siempre devuelve la misma longitud de hash?

La mayoría de las funciones de hash criptográficas operan en un estado interno de tamaño fijo y procesan el mensaje para ser bloqueado bloque a bloque, donde un bloque es un número de bits. MD5, SHA-1 y SHA-2 siguen la construcción Merkle-Damgård que opera de la siguiente manera:

• Sea S una matriz de bits N , inicializada a un valor predefinido. N es el tamaño del estado interno y puede ser diferente del tamaño final del hash.
• Actualice el estado en función de cada bloque de mensajes sucesivamente. Más precisamente, para cada bloque de mensajes M _i , establezca S: = C (M _i , S). La función C se conoce como la función de compresión; toma un bloque de K -bit y un valor de estado de N -bit y genera un nuevo valor de N -bit state.
• Para los últimos bits de entrada, que pueden no formar un bloque completo (si la longitud del mensaje no es un múltiplo de la longitud del bloque), aplique una función de relleno a S que tome en cuenta la longitud del mensaje. (La construcción Merkle-Damgård requiere un método de relleno específico que no estoy describiendo aquí).
• Devuelva F (S) donde F se denomina función de finalización. F toma un estado de N -bit como entrada y devuelve un n -bit hash.

La función de compresión se llama así porque toma K + N bits de entrada y devuelve solo N bits de salida. Por supuesto, esto significa que hay muchas colisiones: pares distintos (M _i , S) que producen el mismo estado resultante. Sin embargo, si se hace correctamente, es decir, si es computacionalmente imposible encontrar colisiones para la función de compresión, entonces el hash en sí también es resistente a colisiones.

Hay funciones hash criptográficas no Merkle-Damgård, por ejemplo, SHA-3, que utiliza una construcción de esponja . El método operativo es un poco diferente, pero el principio básico es el mismo:

• Trabaja con un estado de tamaño fijo.
• Transforme el estado basado en un bloque de mensajes a la vez.
• Aplicar relleno al último bloque.
• Aplique una función de finalización al estado interno para devolver el valor de hash.

Los hash no criptográficos a menudo dependen de la aritmética (pero este enfoque no tiende a producir funciones hash criptográficas rápidas). Utilizan aritmética modular como función de compresión para mantener el estado actual en un tamaño fijo.

Las funciones de hash se definen para asignar entradas de longitud arbitraria a salidas de longitudes fijas. De esto queda claro que las funciones hash no son mapas biyectivos, es decir, debe haber colisiones de valores de entrada.

A partir de cómo una función hash logra producir una salida de longitud constante de forma algorítmica: la mayoría de las funciones hash modernas operan en forma de bloque en su entrada, rellenando el bloque final según sea necesario. Simplificando mucho las cosas, se puede decir que el diseño típico de una función hash es así: para una entrada que se puede dividir en n bloques, calcula una serie de valores de tamaño de bloque v_ {k + 1} = f (v_k, b_k) para k = 0, ..., n-1 donde b_k es el bloque k-th de la entrada, v_0 es un valor arbitrario, f es una función que para dos entradas de tamaño de bloque calcula una salida de tamaño de bloque y v_n es El resultado final.

Para darle una idea, suponga una función hash hipotética donde f es XOR. Hipotético, porque este diseño es inseguro. Una f realista sería un poco más compleja para lograr las propiedades típicas de la función hash.

Aquí está la referencia esencial a la descripción del algoritmo desde la cual se puede ver por qué un hash siempre tiene la misma longitud:

  

3.1 Paso 1. Añadir bits de relleno     El mensaje está "rellenado" (extendido) de modo que su longitud (en bits) es
  congruente con 448, módulo 512. Es decir, el mensaje se extiende así que
  eso es solo 64 bits tímidos de ser un múltiplo de 512 bits de largo.
  El relleno se realiza siempre, incluso si la longitud del mensaje es
  Ya congruente con 448, modulo 512.

     

El relleno se realiza de la siguiente manera: se agrega un solo "1" bit a   el mensaje, y luego se agregan "0" bits para que la longitud en   los bits del mensaje rellenado se hacen congruentes con 448, módulo 512. En   todos, al menos un bit y como máximo 512 bits se adjuntan.

De la descripción del algoritmo RFC 1321: más información sobre el algoritmo puede encontrar aquí

Como ejemplo rápido:

echo 1|md5sum
b026324c6904b2a9cb4b88d6d61c81d1 

echo 1234567890|md5sum
7c12772809c1c0c3deda6103b10fdfa0

El resultado de la función hash es un número rellenado a la cadena de una longitud fija. El número tiene un máximo (es diferente para diferentes funciones).

Las funciones hash, en términos generales, se calculan en un ciclo en el que cada ciclo modifica el número. Si el resultado de la operación es mayor que el máximo, entonces el número se desborda.

Puedes comenzar desde wikipedia: enlace