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] :
- la nueva función hash no debe tener propiedades que permitan aplicar ataques conocidos;
- la función hash debe usar construcciones y transformaciones aprendidas;
- el cálculo de la función hash debe ser eficiente, llevar poco tiempo;
- no debe haber transformaciones innecesarias que compliquen el diseño de la función hash. Además, cada transformación utilizada en la función hash debe ser responsable de ciertas propiedades criptográficas.
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
- En GOST R 34.11-2012, el tamaño de los bloques de mensajes y el estado interno de la función hash es de 512 bits frente a los 256 bits de GOST R 34.11-94.
- El nuevo estándar define dos funciones hash con longitudes de código hash de 256 y 512 bits, mientras que en el estándar anterior la longitud del código hash solo puede ser de 256 bits. La capacidad de variar el hash de salida puede ser útil en el caso de implementaciones integradas con recursos limitados o algunos requisitos adicionales en el campo de la criptografía.
- La principal diferencia entre la función hash moderna y la antigua es la función de compresión . GOST R 34.11-2012 utiliza funciones de compresión basadas en tres transformaciones: transformación biyectiva no lineal (indicada como S), permutación de bytes (indicada como P), transformación lineal (indicada como L). GOST R 34.11-94 usa una función de compresión basada en el cifrado de bloque simétrico GOST R 28147-89 , y esta función también usa operaciones de mezcla.
- Al calcular una nueva función hash, si el tamaño del mensaje no es un múltiplo del tamaño del bloque procesado (para el estándar moderno - 512 bits, para el estándar antiguo - 256 bits), dicho bloque se complementa con un vector ( 00 ... 01). Al calcular la función hash anterior, el bloque incompleto se rellena con el valor (00 ... 0). El relleno (00...01) se considera mejor que (00...0) desde un punto de vista criptográfico, ya que el relleno con el valor (00...0) conduce a ataques del oráculo de relleno [3] . En el caso de complemento distinto de cero, se ha demostrado la resistencia a este tipo de ataques [4] .
- Otra diferencia es que el estándar GOST R 34.11-94 no definió el valor del vector de inicialización, mientras que en el estándar GOST R 34.11-2012 el valor del vector de inicialización está fijo y definido en el estándar: para una función hash con un tamaño hash de salida de 512 bits este es un vector (00 ... 0), para una función hash con un tamaño de código hash de salida de 256 bits - (000000010 ... 100000001) (todos los bytes son 1).
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:
- suma módulo 2;
- sustitución o transformación por sustitución. Denotado S-transformada;
- transformación de permutación. Denotado transformada P;
- transformación lineal. Se denota la transformada L.
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:
- la transformación final, que es que la función de compresión se aplica a la suma de verificación de todos los bloques del mensaje módulo 2 512 ;
- al calcular el código hash, se aplican diferentes funciones de compresión en cada iteración. Podemos decir que la función de compresión depende del número de iteraciones.
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:
- procesamiento por la función de compresión de un bloque con la longitud total del mensaje.
- procesamiento por la función de compresión de bloques con una suma de comprobación.
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 la sección "Descripción", se puede ver en el diagrama que todos los bloques del mensaje se suman módulo 2 512 y el resultado de la suma de todos los bloques ya se envía a la entrada de la etapa final (etapa 3). Debido al hecho de que aquí la suma no es una suma bit a bit, obtenemos protección contra los siguientes ataques:
- construcción de multicolisiones;
- alargamiento del prototipo;
- criptoanálisis diferencial;
- la función de compresión utiliza la construcción Miaguchi-Prenelly, esto brinda protección contra un ataque basado en puntos fijos, ya que no se han encontrado formas fáciles de encontrar puntos fijos para la construcción Miaguchi-Prenelly;
- en cada iteración, se utilizan diferentes constantes para calcular el código hash. Esto hace que los ataques basados en claves vinculadas y diferenciales vinculadas, los ataques de deslizamiento y reflexión sean más difíciles.
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:
- 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;
- 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;
- implementación de GOST R 34.11-2012, escrito por A. Kazimirov [17] ;
- 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
- ↑ 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.
- ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. Un algoritmo hash prometedor // Informe en la conferencia RusCrypto'2010, 2010.
- ↑ 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.
- ↑ 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.
- ↑ Fuente . Consultado el 1 de diciembre de 2013. Archivado desde el original el 3 de diciembre de 2013.
- ↑ f. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
- ↑ 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.
- ↑ 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.
- ↑ http://www.streebog.info/ Archivado el 3 de diciembre de 2013 en el Concurso abierto de investigación de funciones de Wayback Machine .
- ↑ 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
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ GitHub-okazymyrov/stribog . Consultado el 3 de diciembre de 2013. Archivado desde el original el 11 de junio de 2018.
- ↑ 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.
- ↑ 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.
- ↑ 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
- El texto de la norma GOST R 34.11-2012 “Tecnología de la información. Protección criptográfica de la información. Función hash"
- El texto del estándar GOST 34.11-2018 “Tecnología de la información. Protección criptográfica de la información. Función hash"
- El texto del estándar GOST R 34.11-2012 en Wikisource
- RFC 6986 GOST R 34-11-2012: función hash
- Aspectos algebraicos del estándar hash ruso GOST R 34.11-2012 , 2013
- Ingeniería inversa del S-Box de Streebog, Kuznyechik y STRIBOBr1 (versión completa) , 2016
| Funciones hash | |
|---|---|
| propósito general | |
| Criptográfico | |
| Funciones de generación de claves | |
| Número de cheque ( comparación ) | |
| Hachís |
|