GOST (función hash)

Función hash criptográfica rusa

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 .

Algoritmo

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.

Notación básica

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.
• ${\displaystyle +}$— 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.

Descripción

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. ${\displaystyle M}$ ${\displaystyle m_{n},\,m_{n-1},\,m_{n-2},\,\ldots ,\,m_{1}}$ ${\displaystyle m_{n}}$

Cada bloque es procesado por la función hash escalonada , donde , , son bloques de 256 bits. ${\displaystyle H_{\text{out}}=f(H_{\text{in}},\,m)}$ ${\displaystyle H_{\text{out}}}$ ${\displaystyle H_{\text{in}}}$ ${\displaystyle m}$

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

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

El valor puede elegirse arbitrariamente y normalmente es . ${\displaystyle H_{1}}$ ${\displaystyle 0^{256}}$

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

• ${\displaystyle H_{n+2}=f(H_{n+1},\,L)}$, donde L — es la longitud del mensaje M en bits módulo ${\displaystyle 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. ${\displaystyle h}$

Entonces el algoritmo funciona de la siguiente manera.

1. Inicialización:
   1. ${\displaystyle h:={\text{initial}}}$— Valor inicial de 256 bits de la función hash, determinado por el usuario.
   2. ${\displaystyle \Sigma :=0}$— Suma de control
   3. ${\displaystyle 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. ${\displaystyle 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 . ${\displaystyle h}$

Función hash escalonada

La función hash de paso asigna dos bloques de 256 bits en uno: . ${\displaystyle f}$ ${\displaystyle H_{\text{out}}=f(H_{\text{in}},\,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

Generación de claves

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)}$

Transformación cifrada

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}}$

Transformación aleatoria

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 }$

Valores iniciales

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}$

Cuadro S "Parámetros de prueba"

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.

Caja S de CryptoPro

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.

Criptoanálisis

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]

Vectores de prueba hash GOST

Hashes para "parámetros de prueba"

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") = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffaGOST("Suponga que el mensaje original tiene una longitud = 50 bytes") = 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

Más vectores de prueba:

GOST("") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dGOST("a") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddGOST("resumen del mensaje") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dGOST( 128 caracteres de 'U' ) = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4GOST(1000000 caracteres de 'a') = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

Hashes para los parámetros de CryptoPro

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

GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cGOST("resumen del mensaje") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0GOST("El rápido zorro marrón salta sobre el perro perezoso") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90GOST("Este es un mensaje, longitud=32 bytes") = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebGOST("Suponga que el mensaje original tiene una longitud = 50 bytes") = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011GOST(128 de "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8GOST(1000000 de "a") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

Véase también

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

Referencias

1. Mendel, Florian; Pramstaller, Norbert; Rechberger, Christian; Kontak, Marcin; Szmidt, Janusz (2008). "Criptoanálisis de la función hash GOST". En Wagner, David (ed.). Avances en criptología – CRYPTO 2008. Apuntes de clase en informática. Vol. 5157. Alemania : Springer Berlin Heidelberg . págs. 162–178. doi :10.1007/978-3-540-85174-5_10. ISBN 978-3-540-85173-8.
2. GOST R 34.11-2012: Función hash de Streebog
3. "Norma GOST R 34.11-94. Tecnología de la información. Seguridad de datos criptográficos. Función hash. Adición A." 1994. {{cite journal}}: Requiere citar revista |journal=( ayuda )

Lectura adicional

• 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).

Enlaces externos

• 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