Stribog (función hash)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de julio de 2021; las comprobaciones requieren 6 ediciones .
Stribog
Desarrolladores FSB de Rusia ,
OJSC "InfoTeKS"
publicado 2012
Estándares GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
tamaño de hash 256 o 512 bits
Número de rondas 12
Tipo de función hash

Stribog  ( STREEBOG  [ 1] ) es un algoritmo criptográfico para calcular una función hash con un tamaño de bloque de datos de entrada de 512 bits y un tamaño de código hash de 256 o 512 bits .

Descrito en GOST 34.11-2018 “Tecnología de la información. Protección criptográfica de la información . La función hash "- el estándar criptográfico interestatal actual .

Desarrollado por el Centro de Seguridad de la Información y Comunicaciones Especiales del Servicio Federal de Seguridad de Rusia con la participación de JSC InfoTeKS basado en el estándar nacional de la Federación Rusa GOST R 34.11-2012 y puesto en vigencia el 1 de junio de 2019 por orden de Rosstandart N° 1060-st de fecha 4 de diciembre de 2018 .

El estándar GOST R 34.11-2012 se desarrolló e introdujo como reemplazo del estándar obsoleto GOST R 34.11-94 :

La necesidad de desarrollar <...> se debe a la necesidad de crear una función hash que cumpla con los requisitos modernos de fortaleza criptográfica y los requisitos del estándar GOST R 34.10-2012 para firma digital electrónica .

— El texto de la norma. Introducción.

El nombre de la función hash - " Stribog ", después del nombre de la deidad eslava - se usa a menudo en lugar del nombre oficial del estándar, aunque no se menciona explícitamente en su texto (ver más abajo ).

Conceptos para construir la función hash de Stribog

De acuerdo con los requisitos expresados ​​en la conferencia RusCrypto-2010, en el trabajo sobre la nueva función hash [2] :

En el mismo trabajo, se introducen requisitos "universales" en cuanto a la complejidad de los ataques a la función hash:

Una tarea Complejidad
construyendo un prototipo 2n_ _
construyendo una colisión 2n/ 2
construcción del segundo prototipo 2 n /(longitud del mensaje)
alargamiento del prototipo 2n_ _

Comparación de GOST R 34.11-2012 y GOST R 34.11-94

Función de compresión

En una función hash, un elemento importante es la función de compresión. En GOST R 34.11-2012, la función de compresión se basa en el diseño de Miaguchi-Prenel . Esquema del diseño de Miaguchi-Prenel: h, m - entrada de vectores a la función de compresión; g(h, m) es el resultado de la función de compresión; E es un cifrado de bloque con una longitud de bloque y clave de 512 bits. El cifrado XSPL se toma como un cifrado de bloque en la función hash GOST R 34.11-2012. Este cifrado consta de las siguientes transformaciones:

Las transformaciones utilizadas en la nueva función hash deben entenderse bien. Por lo tanto, el cifrado de bloques E utiliza las transformaciones X, S, P, L, que están bien estudiadas.

Un parámetro importante de un cifrado de bloque es cómo se elige la clave que se utilizará en cada ronda. En el cifrado de bloque utilizado en GOST R 34.11-2012, las claves , , ... , para cada una de las 13 rondas se generan mediante la propia función de cifrado.

, , ... ,  son constantes iterativas que son vectores de 512 bits. Sus significados se especifican en la sección correspondiente de la norma.

Descripción

La función hash se basa en la construcción iterativa Merkle-Damgor usando amplificación MD. Se entiende por amplificación MD la adición de un bloque incompleto al calcular la función hash a uno completo sumando un vector (0...01) de tal longitud que se obtiene un bloque completo. Entre los elementos adicionales, cabe señalar lo siguiente:

Las soluciones descritas anteriormente le permiten contrarrestar muchos ataques conocidos.

A continuación se puede presentar una breve descripción de la función hash GOST R 34.11-2012 . La entrada de la función hash es un mensaje de tamaño arbitrario. Además, el mensaje se divide en bloques de 512 bits, si el tamaño del mensaje no es un múltiplo de 512, entonces se complementa con el número de bits requerido. Luego, la función de compresión se usa de forma iterativa, como resultado de lo cual se actualiza el estado interno de la función hash . También se calculan la suma de comprobación del bloque y el número de bits procesados . Cuando se han procesado todos los bloques del mensaje original, se realizan dos cálculos más que completan el cálculo de la función hash:

En el trabajo de Alexander Kazimirov y Valentina Kazimirova [5] , se da una ilustración gráfica del cálculo de la función hash.

Análisis

Seguridad

El criptoanálisis del antiguo estándar reveló algunas de sus debilidades desde un punto de vista teórico. Así, en uno de los artículos [6] dedicados al criptoanálisis de GOST R 34.11-94, se encontró que la complejidad del algoritmo de construcción de pre-imagen se estima en 2192 cálculos de funciones de compresión, colisión 2105 , que es menor que el estimaciones "universales", que para GOST R 34.11-94 es igual a 2256 y 2128 . Aunque a partir de 2013 no hay una gran cantidad de trabajos dedicados a la fortaleza criptográfica de la nueva función hash, en base al diseño de la nueva función hash, podemos sacar algunas conclusiones sobre su fortaleza criptográfica y asumir que su resistencia criptográfica será mayor que la de GOST R 34.11-94:

En 2013, el sitio "Cryptology ePrint Archive: Listing for 2013" publicó dos artículos sobre el criptoanálisis de una nueva función hash. El artículo "Ataque de rebote en Stribog" [7] explora la robustez de la función hash contra un ataque llamado "El ataque de rebote"; este ataque se basa en el "criptoanálisis de rotación" y el criptoanálisis diferencial . Los criptoanalistas utilizaron un método llamado "inicio libre" cuando buscaban vulnerabilidades. Esto significa que al calcular el código hash, se fija un cierto estado de la función hash, y los cálculos posteriores pueden ir tanto hacia el cálculo del código hash como hacia el cálculo del mensaje. Los criptoanalistas pudieron lograr una colisión en 5 rondas y se obtuvo la llamada "casi colisión" (lo que significa que se encontraron dos mensajes cuyos códigos hash son diferentes en una pequeña cantidad de bits) utilizando 7,75 rondas. También se encontró que el esquema por el cual se eligen las teclas para cada ronda agrega estabilidad a la función de compresión. Sin embargo, se ha demostrado que es posible una colisión en 7,75 rondas y "casi colisión" en 8,75 y 9,75, respectivamente.

El artículo "Distintivos integrales para Stribog de ronda reducida" [8] analiza la seguridad de una función hash (con un número reducido de rondas) frente al criptoanálisis integral . Los autores, al estudiar la función de compresión, lograron encontrar el diferencial en 4 vueltas al calcular en la dirección de avance y en 3,5 vueltas al calcular en la dirección opuesta. También se encontró que un ataque diferencial a una función hash con rondas de 6 y 7 requiere 264 y 2120 rondas promedio , respectivamente.

Para estudiar la fuerza criptográfica de una nueva función hash, la empresa InfoTeKS anunció el inicio de una competencia en noviembre de 2013 [9] ; terminó en mayo de 2015 [10] . El ganador fue The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, en el que los autores presentaron un ataque para encontrar la segunda preimagen para la función hash Stribog-512, que requirió 2266 llamadas a la función de compresión para mensajes más largos. de 2 259 bloques [11] .

En la conferencia Crypto-2015, Alex Biryukov , Leo Perrin y Alexey Udovenko presentaron un informe que indica que los valores del bloque S del cifrado Grasshopper y la función hash Stribog no son (pseudo) números aleatorios, sino que se generan en base a en un algoritmo oculto, que los oradores lograron restaurar utilizando métodos de ingeniería inversa [12] [13] .

El 29 de enero de 2019 se publicó el estudio “Partitions in the S-Box of Streebog and Kuznyechik” [14] , que refuta la afirmación de los autores sobre la elección aleatoria de parámetros para las tablas de reemplazo en los algoritmos de Stribog y Kuznyechik [15] .

Rendimiento

El sitio dedicado a la VI Conferencia Internacional "Problemas de Control y Cómputo Paralelo" (PACO'2012) presenta un artículo de P. A. Lebedev "Comparación de los estándares rusos antiguos y nuevos para la función hash criptográfica en CPU y GPU NVIDIA", en el que compara del desempeño de la familia de funciones hash criptográficas GOST R 34.11-94 y GOST R 34.11-2012 en procesadores de arquitectura x86_64 y tarjetas de video NVIDIA que soportan tecnología CUDA [16] .

Para comparar el rendimiento en un procesador x86_64, se tomaron 4 implementaciones diferentes de funciones hash:

  1. implementación de GOST R 34.11-1994 del paquete criptográfico OpenSSL (versión 1.0.1c) con código fuente abierto. No hay optimizaciones algorítmicas o de software en esta implementación;
  2. implementación de GOST R 34.11-1994 en el programa RHash (versión 1.2.9). Esta implementación tiene optimizaciones algorítmicas y de software, incluidas optimizaciones de ensamblador;
  3. implementación de GOST R 34.11-2012, escrito por A. Kazimirov [17] ;
  4. implementación de GOST R 34.11-1994 y GOST R 34.11-2012 escrito por P. A. Lebedev.

Se utilizó una CPU Intel Core i7-920 a una frecuencia base de 2,67 GHz. Resultados de rendimiento:

GOST R 34.11-1994 GOST R 34.11-2012
Número de implementación MB/s Relojes/byte MB/s Relojes/byte
una Dieciocho 143 - -
2 49 52 - -
3 - - 38 67
cuatro 64 40 94 27

La comparación de la velocidad de los estándares antiguos y nuevos de funciones hash en la GPU se llevó a cabo entre las implementaciones de P. A. Lebedev. Se utilizó la tarjeta gráfica NVIDIA GTX 580. Resultados de rendimiento (8192 flujos de datos de 16 KB):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Relojes/byte MB/s Relojes/byte
1697 - 608 -

Con base en estos resultados, se concluye que la función hash GOST R 34.11-2012 puede ser el doble de rápida que la función hash GOST R 34.11-94 en procesadores modernos, pero más lenta en tarjetas gráficas y sistemas con recursos limitados.

Estos resultados de rendimiento pueden explicarse por el hecho de que el cálculo de la nueva función hash utiliza solo adiciones de módulo 2 e instrucciones de transferencia de datos. La antigua función hash contiene muchas instrucciones aleatorias que no se asignan bien al conjunto de instrucciones de la CPU. Pero el mayor tamaño de los estados y las tablas de sustitución de la función hash GOST R 34.11-2012 la hace más lenta en instalaciones de computación altamente paralelas, como las GPU.

Además, sus desarrolladores realizaron un estudio del rendimiento de la nueva función hash en un procesador Intel Xeon E5335 de 64 bits y 2 GHz. Se utilizó un núcleo. El rendimiento de la función hash GOST R 34.11-2012 fue de 51 ciclos de procesador por 1 byte de datos hash (aproximadamente 40 MB/s). El resultado obtenido es un 20% mejor que la antigua función hash GOST R 34.11-94.

Datos interesantes

Al final del texto del estándar, se dan ejemplos de cálculo de hash paso a paso para varios valores iniciales. Uno de estos valores es el número hexadecimal M 2 de longitud 576 bits (72 bytes) del ejemplo 2:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220e8e6eee1e8f0f2d1202ce8f0f2e5e220e5d1

En una computadora x86 , el orden de los bytes es de menor a mayor , y un número similar en la memoria se representará en forma "invertida". Si convierte esta matriz de bytes en texto en codificación Windows-1251 , obtendrá una línea ligeramente modificada de Word about Igor's Campaign :

Estos vientos, los nietos de Stribozh, soplan desde el mar con flechas sobre los valientes desplumados de Igor.

En respuesta al artículo crítico "Watch your Constants: Malicious Streebog" [18] , el comité TK26 emitió una nota "Sobre el algoritmo para generar constantes para la función hash de Stribog" [19] [20] , que explica que las constantes clave redondas se construyeron como una transformación de cadenas de entrada utilizando la función hash similar a Stribog. Si estas cadenas de entrada se convierten en texto en codificación Windows-1251 , se obtendrán los nombres de los autores del estándar:

C i = H inicial (M) M (en notación hexadecimal) M cp1251 (cadena en Windows-1251 )
C1 _ e2e5ede1e5f0c3 Grebnev
C2 _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 sergey vladimirovich
C3 _ f5f3ecc4 Dmuh
C4 _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrei Alexandrovich
C5 _ ede8e3fbc4 Dygin
C6 _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Mijáilovich
C7 _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitri Viktorovich
C9 _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladímir Igorevich
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 vasily alekseevich

Notas

  1. 17. Función hash dedicada 11 (STREEBOG-512) Archivado el 22 de enero de 2020 en Wayback Machine // ISO/IEC 10118-3:2018 Técnicas de seguridad de TI - Funciones hash - Parte 3: Funciones hash dedicadas.
  2. Matyukhin D.V., Shishkin V.A., Rudsky V.I. Un algoritmo hash prometedor // Informe en la conferencia RusCrypto'2010, 2010.
  3. Serge Vaudenay (2002). "Fallos de seguridad inducidos por aplicaciones de relleno de CBC para SSL, IPSEC, WTLS...". Avances en Criptología - EUROCRYPT 2002, Proc. Congreso Internacional de Teoría y Aplicaciones de Técnicas Criptográficas. Springer Verlag (2332): 534-545.
  4. Kenneth G. Paterson; Gaven J. Watson (2008). "Modo CBC inmunizante contra los ataques de oráculo de relleno: un tratamiento de seguridad formal". Seguridad y Criptografía para Redes - SCN 2008, Lecture Notes in Computer Science. Springer Verlag (5229): 340-357.
  5. Fuente . Consultado el 1 de diciembre de 2013. Archivado desde el original el 3 de diciembre de 2013.
  6. f. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. Riham AlTawy, Aleksandar Kircanski y Amr M. Youssef. Ataques de rebote en Stribog  (inglés) (27 de agosto de 2013). Consultado el 1 de diciembre de 2013. Archivado desde el original el 3 de diciembre de 2013.
  8. Riham AlTawy y Amr M. Youssef. Distinguidores integrales para Stribog de ronda reducida  (inglés) (8 de octubre de 2013). Consultado el 3 de noviembre de 2015. Archivado desde el original el 4 de marzo de 2016.
  9. http://www.streebog.info/ Archivado el 3 de diciembre de 2013 en el Concurso abierto de investigación de funciones de Wayback Machine .
  10. http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Archivado el 10 de septiembre de 2015 en Wayback Machine Se han determinado los ganadores del concurso de investigación de la función hash de Stribog
  11. Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function  (inglés) (29 de agosto de 2014). Consultado el 3 de noviembre de 2015. Archivado desde el original el 4 de marzo de 2016.
  12. Alex Biryukov, Leo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob  (inglés) (14 de agosto de 2015). Consultado el 3 de noviembre de 2015. Archivado desde el original el 8 de septiembre de 2015.
  13. Alex Biryukov, Leo Perrin, Aleksei Udovenko. Ingeniería inversa del S-Box de Streebog, Kuznyechik y STRIBOBr1 (versión completa)  (inglés) (26 de enero de 2016). Consultado el 22 de febrero de 2017. Archivado desde el original el 16 de julio de 2017.
  14. Leo Perrin. Particiones en el S-Box de Streebog y Kuznyechik (29 de enero de 2019). Consultado el 25 de agosto de 2020. Archivado desde el original el 14 de noviembre de 2020.
  15. Virgilio Security Inc. Otra rareza en los algoritmos GOST Grasshopper y Stribog . habr.com . Consultado el 25 de agosto de 2020. Archivado desde el original el 7 de noviembre de 2020.
  16. P. A. Lebedev. Comparación de los estándares RF antiguos y nuevos para la función hash criptográfica en las CPU y GPU de NVIDIA . Instituto de Electrónica y Matemáticas de Moscú, Escuela Superior de Economía de la Universidad Nacional de Investigación (2012). Consultado el 25 de agosto de 2020. Archivado desde el original el 18 de abril de 2021.
  17. GitHub-okazymyrov/stribog . Consultado el 3 de diciembre de 2013. Archivado desde el original el 11 de junio de 2018.
  18. Riham AlTawy y Amr M. Youssef. Watch your Constants: Malicious Streebog  (inglés) (8 de octubre de 2013). Consultado el 3 de noviembre de 2015. Archivado desde el original el 4 de marzo de 2016.
  19. VI Rudskoy. Sobre el algoritmo para generar las constantes de la función hash de Stribog . Consultado el 26 de diciembre de 2019. Archivado desde el original el 26 de diciembre de 2019.
  20. V. Rudskoy. Nota sobre el origen de las constantes de Streebog  . Consultado el 26 de diciembre de 2019. Archivado desde el original el 2 de marzo de 2021.

Enlaces