GOST (función hash)

La función hash GOST , definida en las normas GOST R 34.11-94 y GOST 34.311-95, es una función hash criptográfica de 256 bits . Fue definida inicialmente en la norma nacional rusa GOST R 34.11-94 Tecnología de la información – Seguridad de la información criptográfica – Función hash . La norma equivalente utilizada por otros estados miembros de la CEI es GOST 34.311-95.

Esta función no debe confundirse con una función hash de Streebog diferente , que se define en la nueva revisión de la norma GOST R 34.11-2012 . ^[2]

La función hash GOST se basa en el cifrado de bloque GOST .

GOST procesa un mensaje de longitud variable y lo convierte en una salida de longitud fija de 256 bits. El mensaje de entrada se divide en fragmentos de bloques de 256 bits (ocho enteros little endian de 32 bits); el mensaje se rellena añadiendo tantos ceros como sean necesarios para que la longitud del mensaje alcance los 256 bits. Los bits restantes se completan con una suma aritmética de enteros de 256 bits de todos los bloques previamente codificados y, a continuación, un entero de 256 bits que representa la longitud del mensaje original, en bits.

Las descripciones del algoritmo utilizan la siguiente notación:

• ${\displaystyle {\mathcal {f}}0{\mathcal {g}}^{j}}$— bloque j-bit lleno de ceros.
• ${\displaystyle {\mathcal {j}}M{\mathcal {j}}}$— longitud del bloque M en bits módulo 2 ²⁵⁶ .
• ${\displaystyle {\mathcal {k}}}$— concatenación de dos bloques.
• ${\estilo de visualización +}$— suma aritmética de dos bloques módulo 2 ²⁵⁶ .
• ${\displaystyle \oplus}$— xor lógico de dos bloques.

Además, consideramos que el bit de orden pequeño se ubica a la izquierda de un bloque y el bit de orden alto a la derecha.

El mensaje de entrada se divide en bloques de 256 bits . En caso de que el último bloque contenga menos de 256 bits, se antepone a la izquierda un bit cero para lograr la longitud deseada. ${\estilo de visualización M}$${\displaystyle m_{n},\,m_{n-1},\,m_{n-2},\,\ldots ,\,m_{1}}$$Estilo de visualización m_{n}$

Cada bloque es procesado por la función hash escalonada , donde , , son bloques de 256 bits. ${\displaystyle H_{\text{salida}}=f(H_{\text{entrada}},\,m)}$${\displaystyle H_{\text{fuera}}}$${\displaystyle H_{\text{en}}}$${\estilo de visualización m}$

Cada bloque de mensaje, comenzando por el primero, es procesado por la función hash escalonada para calcular el valor hash intermedio. ${\estilo de visualización f}$

${\displaystyle \!H_{i+1}=f(H_{i},\,m_{i})}$

El valor puede elegirse arbitrariamente y normalmente es . $Estilo de visualización H_{1}$${\estilo de visualización 0^{256}}$

Luego de calculado, el valor hash final se obtiene de la siguiente manera $Estilo de visualización H_{n+1}$

• ${\displaystyle H_{n+2}=f(H_{n+1},\,L)}$, donde L — es la longitud del mensaje M en bits módulo${\estilo de visualización 2^{256}}$
• ${\displaystyle h=f(H_{n+2},\,K)}$, donde K es la suma de control de 256 bits de M:${\displaystyle m_{1}+m_{2}+m_{3}+\ldots +m_{n}}$

El es el valor deseado de la función hash del mensaje M. ${\estilo de visualización h}$

Entonces el algoritmo funciona de la siguiente manera.

1. Inicialización:
   1. ${\displaystyle h:={\text{inicial}}}$— Valor inicial de 256 bits de la función hash, determinado por el usuario.
   2. ${\displaystyle \Sigma :=0}$— Suma de control
   3. ${\estilo de visualización L:=0}$— Longitud del mensaje
2. Función de compresión de iteraciones internas: para i = 1 … n — 1 haga lo siguiente (while ): ${\displaystyle |M|>256}$
   1. ${\displaystyle h:=f(h,\,m_{i})}$ – aplicar función hash escalonada
   2. ${\estilo de visualización L:=L+256}$ – recalcular la longitud del mensaje
   3. ${\displaystyle \Sigma :=\Sigma +m_{i}}$ – calcular la suma de control
3. Función de compresión de la iteración final:
   1. ${\displaystyle L:=L+{\mathcal {j}}\,m_{n}\,{\mathcal {j}}}$ – Calcular la longitud completa del mensaje en bits
   2. ${\displaystyle m_{n}:={0}^{256-{\mathcal {j}}m_{n}{\mathcal {j}}}{\mathcal {k}}m_{n}}$– rellena el último mensaje con ceros
   3. ${\displaystyle \Sigma :=\Sigma +m_{n}}$ – actualizar suma de control
   4. ${\displaystyle h:=f(h,\,m_{n})}$ – procesar el último bloque de mensajes
   5. ${\displaystyle h:=f(h,\,L)}$ – MD – Fortalecimiento mediante hash de la longitud del mensaje
   6. ${\displaystyle h:=f(h,\,\Sigma )}$– suma de control de hash
4. El valor de salida es .${\estilo de visualización h}$

La función hash de paso asigna dos bloques de 256 bits en uno: . ${\estilo de visualización f}$${\displaystyle H_{\text{salida}}=f(H_{\text{entrada}},\,m)}$

Consta de tres partes:

• Generación de claves${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$
• Transformación de cifrado mediante claves${\displaystyle H_{\text{in}}}$${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$
• Transformación aleatoria

El algoritmo de generación de claves utiliza:

• Dos transformaciones de bloques de 256 bits:
  • Transformación , donde son subbloques de 64 bits de Y.${\displaystyle A(Y)=A(y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}\ {\mathcal {k}}\ y_{1})=(y_{1}\oplus y_{2})\ {\mathcal {k}}\ y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}}$${\displaystyle y_{1},\,y_{2},\,y_{3},\,y_{4}}$
  • Transformación , donde , y son subbloques de 8 bits de Y .${\displaystyle P(Y)=P(y_{32}{\mathcal {k}}y_{31}{\mathcal {k}}\dots {\mathcal {k}}y_{1})=y_{\varphi (32)}{\mathcal {k}}y_{\varphi (31)}{\mathcal {k}}\dots {\mathcal {k}}y_{\varphi (1)}}$${\displaystyle \varphi (i+1+4(k-1))=8i+k,\quad i=0,\,\dots ,\,3,\quad k=1,\,\dots ,\,8}$${\displaystyle y_{32},\,y_{31},\,\dots ,\,y_{1}}$
• Tres constantes:
  • C2 = 0_​
  • C ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ff00ff00ff00ff00ff00
  • C4 = 0_​

El algoritmo:

1. ${\displaystyle U:=H_{\text{in}},\quad V:=m,\quad W:=U\ \oplus \ V,\quad K_{1}=P(W)}$
2. Para j = 2, 3, 4 haga lo siguiente:

   ${\displaystyle U:=A(U)\oplus C_{j},\quad V:=A(A(V)),\quad W:=U\oplus V,\quad K_{j}=P(W)}$

Después de la generación de claves, el cifrado de se realiza utilizando GOST 28147-89 en el modo de sustitución simple en claves . Denotemos la transformación de cifrado como E (cifrado de datos de 64 bits utilizando una clave de 256 bits). Para el cifrado, el se divide en cuatro bloques de 64 bits: , y cada uno de estos bloques se cifra como: ${\displaystyle H_{\text{in}}}$${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$${\displaystyle H_{\text{in}}}$${\displaystyle H_{\text{in}}=h_{4}{\mathcal {k}}h_{3}{\mathcal {k}}h_{2}{\mathcal {k}}h_{1}}$

• ${\displaystyle s_{1}=E(h_{1},\,K_{1})}$
• ${\displaystyle s_{2}=E(h_{2},\,K_{2})}$
• ${\displaystyle s_{3}=E(h_{3},\,K_{3})}$
• ${\displaystyle s_{4}=E(h_{4},\,K_{4})}$

Después de esto, los bloques de resultados se concatenan en un bloque de 256 bits: . ${\displaystyle S=s_{4}{\mathcal {k}}s_{3}{\mathcal {k}}s_{2}{\mathcal {k}}s_{1}}$

En el último paso, se aplica la transformación aleatoria a , S y m mediante un registro de desplazamiento con retroalimentación lineal . Como resultado, se obtiene el valor hash intermedio. ${\displaystyle H_{\text{in}}}$${\displaystyle H_{\text{out}}}$

Primero definimos la función ψ, realizando LFSR en un bloque de 256 bits:

${\displaystyle \psi (Y)=\psi (y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\mathcal {k}}y_{2}{\mathcal {k}}y_{1})=(y_{1}\oplus y_{2}\oplus y_{3}\oplus y_{4}\oplus y_{13}\oplus y_{16}){\mathcal {k}}y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\mathcal {k}}y_{3}{\mathcal {k}}y_{2}}$,

¿Dónde están los subbloques de 16 bits de Y ? ${\displaystyle y_{16},y_{15},\ldots ,y_{2},y_{1}}$

La transformación aleatoria es , donde denota una potencia i-ésima de la función. ${\displaystyle H_{\text{out}}=\psi ^{61}{\mathord {\left(H_{\text{in}}\oplus \psi \left(m\oplus \psi ^{12}(S)\right)\right)}}}$${\displaystyle \psi ^{i}}$${\displaystyle \psi }$

Hay dos conjuntos de parámetros iniciales que se utilizan comúnmente para GOST R 34.11 94. El vector de inicio para ambos conjuntos es

${\displaystyle H_{1}}$= 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 .

Aunque la norma GOST R 34.11 94 en sí no especifica el valor inicial del algoritmo y el S-box de la transformación de cifrado , pero utiliza los siguientes "parámetros de prueba" en las secciones de muestras. ^[3]${\displaystyle H_{1}}$${\displaystyle E}$

RFC 5831 especifica sólo estos parámetros, pero RFC 4357 los denomina "parámetros de prueba" y no recomienda su uso en aplicaciones de producción.

La S-box de CryptoPro proviene del conjunto de parámetros "listo para producción" desarrollado por la compañía CryptoPro, también se especifica como parte de RFC 4357, sección 11.2.

En 2008 se publicó un ataque que rompe la función hash GOST de ronda completa. El artículo presenta un ataque de colisión en 2 ¹⁰⁵ veces, y ataques de primera y segunda preimagen en 2 ¹⁹² veces (2 ⁿ veces se refiere al número aproximado de veces que se calculó el algoritmo en el ataque). ^[1]

Los hashes GOST de 256 bits (32 bytes) normalmente se representan como números hexadecimales de 64 dígitos.

Aquí se muestran los vectores de prueba para el hash GOST con "parámetros de prueba"

GOST("El rápido zorro marrón salta sobre el perro perezoso " ) =
 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

Incluso un pequeño cambio en el mensaje tendrá como resultado, con una probabilidad abrumadora, un hash completamente diferente debido al efecto avalancha . Por ejemplo, cambiar d por c :

GOST("El rápido zorro marrón salta sobre el perezoso engranaje ") =
 a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Dos muestras procedentes de la norma GOST R 34.11-94: ^[3]

GOST("Este es un mensaje, longitud=32 bytes") =
 b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa

GOST("Suponga que el mensaje original tiene una longitud = 50 bytes") =
 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

Más vectores de prueba:

GOST("") =
 ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d

GOST("a") =
 d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd

GOST("resumen del mensaje") =
 ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d

GOST( 128 caracteres de 'U' ) =
 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4

GOST(1000000 caracteres de 'a') =
 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

El algoritmo GOST con CryptoPro S-box genera diferentes conjuntos de valores hash.

GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011

GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42c

GOST("resumen del mensaje") =
  bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0

GOST("El rápido zorro marrón salta sobre el perro perezoso") =
  9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76

GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
  73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61

GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") =
  6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90

GOST("Este es un mensaje, longitud=32 bytes") =
  2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48eb

GOST("Suponga que el mensaje original tiene una longitud = 50 bytes") =
  c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011

GOST(128 de "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8

GOST(1000000 de "a") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

• Kupyna
• Resumen de seguridad de la función hash
• Normas GOST
• Lista de funciones hash

• Dolmatov, V. (marzo de 2010). Dolmatov, V (ed.). "GOST R 34.11-94: Algoritmo de función hash". IETF. doi : 10.17487/RFC5831 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
• "Tecnología de la información. Seguridad de datos criptográficos. Función hash". 20 de febrero de 2010.El texto completo de la norma GOST R 34.11-94 (en ruso).

• Implementación en C y vectores de prueba para la función hash GOST de Markku-Juhani Saarinen. También contiene traducciones preliminares al inglés de las normas GOST 28147-89 y GOST R 34.11-94. Versión con errores corregidos, consulte [1].
• Implementación de C++ con flujos STL ^{[ enlace muerto permanente ]} .
• RHash, una herramienta de línea de comandos de código abierto , que puede calcular y verificar el hash GOST (admite ambos conjuntos de parámetros).
• Implementación de GOST R 34.11-94 en JavaScript (parámetros de CryptoPro)
• Página de cifrado de la función hash de GOST
• Calculadora GOST en línea Archivado el 6 de noviembre de 2014 en Wayback Machine