Algoritmo de milenrama

El algoritmo Yarrow es un generador de números pseudoaleatorios criptográficamente seguro . Milenrama fue elegido como el nombre , cuyos tallos secos sirven como fuente de entropía en la adivinación [1] .

El algoritmo fue desarrollado en agosto de 1999 por Bruce Schneier , John Kelsey y Niels Ferguson de Counterpane Internet Security.[2] . El algoritmo no está patentado ni está libre de regalías , y no se requiere licencia para usarlo. Yarrow se incluye en febrero de2002 con FreeBSD , OpenBSD y Mac OS X comouna implementación del dispositivo /dev/random [3] .

El desarrollo posterior de Yarrow fue la creación por parte de Fergus y Schneier del algoritmo Fortuna , descrito en su libro "Criptografía práctica" [4] .

La necesidad de un algoritmo

La mayoría de las aplicaciones criptográficas modernas utilizan números aleatorios. Son necesarios para generar claves , obtener números aleatorios de una sola vez , crear un salt , etc. Si los números aleatorios no son seguros, esto conlleva la aparición de vulnerabilidades en las aplicaciones que no se pueden cerrar utilizando varios algoritmos y protocolos [5] .

En 1998, los creadores de Yarrow realizaron una investigación sobre otros PRNG e identificaron una serie de vulnerabilidades en ellos. Las secuencias de números aleatorios que producían no eran seguras para aplicaciones criptográficas [5] .

Actualmente, el algoritmo Yarrow es un generador de números pseudoaleatorios altamente seguro. Esto le permite utilizarlo para una amplia gama de tareas: encriptación , firma electrónica , integridad de la información , etc. [5] .

Principios de diseño

Durante el desarrollo del algoritmo, los creadores se centraron en los siguientes aspectos [6] :

Rapidez y eficacia . Ninguno de los desarrolladores utilizará un algoritmo que ralentice mucho la aplicación.
Simplicidad _ Cualquier programador sin mucho conocimiento de criptografía debería poder usarlo de forma segura.
optimización _ Siempre que sea posible, el algoritmo debe utilizar bloques de instrucciones preexistentes.

Estructura del algoritmo

Componentes

El algoritmo Yarrow consta de 4 partes independientes [7] :

Acumulador de entropía . Recoge muestras de fuentes de entropía y las coloca en dos grupos.
mecanismo de complicación . Complica periódicamente la clave del generador utilizando la entropía de las agrupaciones.
mecanismo de generación . Genera señales de salida PRNG desde el dongle.
Mecanismo de manejo de complicaciones . Especifica el tiempo de ejecución de la complicación.

Acumulador de entropía

La acumulación de entropía es un proceso en el que un PRNG adquiere un nuevo estado interno indescifrable [8] . En este algoritmo, la entropía se acumula en dos grupos : rápido y lento [9] . En este contexto, un grupo es un almacén de bits inicializados y listos para usar. La piscina rápida proporciona complicaciones clave frecuentes . Esto asegura que el compromiso clave tenga una duración corta. El grupo lento proporciona complicaciones clave raras pero significativas. Esto es necesario para garantizar que se obtenga una complicación segura incluso en los casos en que las estimaciones de entropía estén muy sobrestimadas. Las muestras de entrada se envían alternativamente a los grupos rápido y lento [10] .

Mecanismo de complicación

El mecanismo de complicación conecta el almacenamiento de entropía con el mecanismo de generación. Cuando el mecanismo de control de complejidad determina que se necesita complejidad, entonces el motor de complejidad, utilizando información de uno o ambos grupos, actualiza la clave que utiliza el mecanismo de generación. Por lo tanto, si el atacante no conoce la clave actual o los grupos, entonces la clave será desconocida para él después de la complicación. También es posible que la complejidad requiera una gran cantidad de recursos para minimizar el éxito de un ataque basado en adivinar los valores de entrada [11] .

Para generar una nueva clave , la complejidad del grupo rápido utiliza la clave actual y los valores hash de todas las entradas del grupo rápido desde la última complejidad de la clave. Una vez hecho esto, la entropía estimapara el grupo rápido se establecerá en cero [11] [12] .

La complicación del grupo lento usa la clave actual y los valores hash de las entradas del grupo rápido y lento. Después de generar una nueva clave, las estimaciones de entropía para ambos grupos se restablecen a cero [13] .

Mecanismo de generación

El mecanismo de generación da a la salida una secuencia de números pseudoaleatorios. Debe ser tal que un atacante que no conozca la clave del generador no pueda distinguirla de una secuencia de bits aleatoria .[14] .

El mecanismo de generación debe tener las siguientes propiedades [15] :

resistencia a ataques criptográficos ;
productividad ( inglés Efficiency );
la capacidad de generar una secuencia muy larga de señales sin complicaciones;
resistencia a ataques de fuerza bruta con backtracking ( Ing. Backtracking ) después de que la clave haya sido comprometida .

Mecanismo de gestión de complicaciones

Para elegir el tiempo de sofisticación, el mecanismo de control debe tener en cuenta varios factores. Por ejemplo, cambiar la clave con demasiada frecuencia hace que sea más probable un ataque de suposición iterativo [16] . Demasiado lento, por el contrario, da más información al atacante que comprometió la clave. Por lo tanto, el mecanismo de control debe ser capaz de encontrar un término medio entre estas dos condiciones [17] .

A medida que llegan las muestras en cada piscinase almacenan las estimaciones de entropía para cada fuente. Tan pronto como esta estimación para cualquier fuente alcanza el valor límite, hay una complicación del grupo rápido. En la gran mayoría de los sistemas, esto sucede muchas veces por hora. Una complicación del grupo lento ocurre cuando las puntuaciones de cualquiera de las fuentes en el grupo lento superan un umbral [17] . $k$ $norte$

En Yarrow-160, este límite es de 100 bits para el grupo rápido y de 160 bits para el lento. De forma predeterminada, al menos dos fuentes diferentes en el grupo lento deben tener más de 160 bits para que se produzcan complicaciones en el grupo lento [18] .

Milenrama 160

Una posible implementación del algoritmo Yarrow es Yarrow-160. La idea principal de este algoritmo es el uso de una función hash unidireccional y un cifrado de bloque [19] . Si ambos algoritmos son seguros y el PRNG recibe suficiente entropía inicial , el resultado será una fuerte secuencia de números pseudoaleatorios [20] . $h()$ ${\ estilo de visualización E_ {K} ()}$

La función hash debe tener las siguientes propiedades [21] :

ser irreversible, es decir, resistente a la restauración del prototipo ;
ser resistente a las colisiones ;
dar la salida -bit. $metro$

Yarrow-160 usa el algoritmo SHA-1 como [19] . $h()$

El cifrado de bloque debe tener las siguientes propiedades [22] :

tener una clave con una longitud de -bits y un bloque de datos con una longitud de -bits; $k$ $norte$
ser resistente a los ataques de texto sin formato y de texto elegido ;
tienen buenas propiedades estadísticas de las señales de salida, incluso con señales de entrada altamente moldeadas.

Yarrow-160 usa el algoritmo 3-KEY Triple DES como [19] . ${\ estilo de visualización E_ {K} ()}$

Generación

El generador se basa en el uso de un cifrado de bloque en modo contador (ver Fig. 2) [23] .

Hay un valor de contador de n bits . Para generar los siguientes bits de la secuencia pseudoaleatoria, el contador se incrementa en 1 y se cifra con un cifrado de bloque utilizando la clave [24] : $C$ $norte$ $C$ $k$

C\flecha izquierda (C+1){\bmod {2}}^{n}

R\leftarrow E_{K}(C)

donde es la salida del PRNG , y es el valor actual de la clave . $R$ $k$

Si en algún momento la clave se ve comprometida , entonces es necesario evitar la fuga de valores de salida anteriores que un atacante puede obtener. Este mecanismo de generación no tiene protección contra este tipo de ataques, por lo que adicionalmente se calcula el número de bloques de salida PRNG. Tan pronto como se alcanza un cierto límite ( la configuración de seguridad del sistema ${\ Displaystyle P_ {g}}$ , ), luego se genera una salida PRNG de bits, que luego se usa como una nueva clave [15] . ${\displaystyle 1\leq P_{g}\leq 2^{n/3))$ $k$

K\leftarrow {\text{siguientes k bits de salida PRNG))

En Yarrow-160 es 10. Este parámetro se establece deliberadamente en un valor bajo para minimizar el número de salidas que se pueden aprender mediante un ataque de retroceso [ 25 ] . ${\ Displaystyle P_ {g}}$

Complicación

El tiempo de ejecución del mecanismo de complicación depende del parámetro . Este parámetro se puede fijar o cambiar dinámicamente [26] . $P_{t}\geq 0$

Este mecanismo consta de los siguientes pasos [26] :

El acumulador de entropía calcula el hash de todas las entradas en el grupo rápido. El resultado de este cálculo se denota por . ${\ Displaystyle v_ {0}}$
deja _ $v_{i}:=h(v_{i-1}|v_{0}|i)~{\text{ para }}~i=1,\ldots,t$
$K\leftarrow h^{'}(h(v_{P_{t))|K),k)$ .
$C\leftarrow E_{K}(0)$ .
Restablece todos los contadores de entropía en las piscinas a 0.
Limpia la memoria que almacena valores intermedios.
Si se utiliza el archivo semilla , sobrescriba el contenido de este archivo con los siguientes bits de la salida de la secuencia pseudoaleatoria . $2k$

Una función se define en términos de una función de la siguiente manera [27] : ${\ estilo de visualización h ^ {'}}$ $h$

{\ estilo de visualización s_ {0}: = m}

s_{i}:=h(s_{0}|\ldots |s_{i-1}),\ \ {\text{dónde))\ \ i=1,\ldots

h^{'}(m,k):={\text{primeros))\ \ k\ \ {\text{bits))\;(s_{0}|s_{1}|\ldots)

De hecho, es una función de adaptación de tamaño, es decir, convierte una entrada de cualquier longitud en una salida de una longitud específica. Si la entrada recibió más datos de los esperados, la función toma los bits iniciales. Si los tamaños de la entrada y la salida son iguales, entonces la función es una función de identidad . Si el tamaño de los datos de entrada es inferior al esperado, se generan bits adicionales utilizando esta función hash . Este es un algoritmo PRNG bastante costoso en términos de cómputo, pero para tamaños pequeños se puede usar sin problemas [28] .

Establecer un nuevo valor para el contador no se hace por razones de seguridad, sino para proporcionar una mayor flexibilidad de implementación y mantener la compatibilidad entre diferentes implementaciones [26] . $C$

Cuestiones no resueltas y planes para el futuro

En la implementación actual del algoritmo Yarrow-160, el tamaño de los gruposla acumulación de entropía está limitada a 160 bits. Se sabe que los ataques al algoritmo 3-KEY Triple DES son más efectivos que la búsqueda exhaustiva . Sin embargo, incluso para los ataques de backtracking de fuerza bruta, las claves cambian con bastante frecuencia y 160 bits son suficientes para garantizar la seguridad en la práctica [29] .

El tema de investigación en curso es la mejora de los mecanismos de estimación de la entropía. Según los creadores de Yarrow-160, el algoritmo puede ser vulnerable precisamente debido a las malas estimaciones de entropía, y no desde el punto de vista del criptoanálisis [30] .

Los creadores tienen planes para el futuro para utilizar el nuevo estándar de cifrado de bloques AES . El nuevo cifrado de bloque puede encajar fácilmente en el diseño básico del algoritmo Yarrow. Sin embargo, como enfatizan los desarrolladores, será necesario cambiar la función hash de complejidad o crear una nueva función hash para garantizar que el grupo de entropía se llene con más de 160 bits. Para AES con 128 bits, esto no será un problema, pero para AES con 192 o 256 bits, este problema tendrá que resolverse. Cabe señalar que la estructura básica del algoritmo Yarrow es la combinación de un cifrado de bloque AES y una función hash de 256 bits [31] .

El conjunto de reglas para el mecanismo de manejo de complicaciones aún es provisional, sin embargo, un estudio adicional puede mejorarlo. Por esta razón, es objeto de investigación en curso [30] .

Notas

↑ Kelsey, Schneier, Ferguson, 2000 , pág. 29
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 13
↑ Murray, 2002 , pág. 47.
↑ Ferguson, Schneier, 2004 , pág. 183.
↑ 1 2 3 Schneier sobre seguridad. Preguntas y respuestas sobre Milenrama . Fecha de acceso: 1 de diciembre de 2016. Archivado desde el original el 11 de noviembre de 2016.
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 15-16.
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 18-21.
↑ Shcherbakov, Domashev, 2003 , pág. 232.
↑ Viega, 2003 , pág. 132.
↑ Ferguson, Schneier, 2004 , pág. 189-193.
↑ 1 2 Shcherbakov, Domashev, 2003 , p. 234-235.
↑ Ferguson, Schneier, 2004 , pág. 234-235.
↑ Shcherbakov, Domashev, 2003 , pág. 191-193.
↑ Ferguson, Schneier, 2004 , pág. 183-184.
↑ 1 2 Ferguson, Schneier, 2004 , pág. 183-185.
↑ Kelsey, Schneier, Wagner et al., 1998 , pág. 172.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , pág. 22
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 28
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , pág. 23
↑ Ferguson, Schneier, 2004 , pág. 202.
↑ Schneier, 1996 , pág. 55-57.
↑ Shcherbakov, Domashev, 2003 , pág. 236.
↑ Ferguson, Schneier, 2004 , pág. 95-96, 183-186.
↑ Ferguson, Schneier, 2004 , pág. 95-96, 183-188.
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 25
↑ 1 2 3 Kelsey, Schneier, Ferguson, 2000 , pág. 26-27.
↑ Kelsey, Schneier, Ferguson, 2000 , pág. 27
↑ Ferguson, Schneier, 2004 , pág. 188-189.
↑ Kelsey, Schneier, Wagner et al., 1998 , pág. 176-177.
↑ 1 2 Kelsey, Schneier, Ferguson, 2000 , pág. 28-29.
↑ Ferguson, Schneier, 2004 , pág. 109-111.

Literatura

en ruso

Shcherbakov, L. Yu. , Domashev, A. V. Criptografía aplicada. Uso y síntesis de interfaces criptográficas. - Edición rusa, 2003. - 416 p. — ISBN 5-7502-0215-1 .
Ferguson, N. , Schneier, B. Criptografía práctica. - Editorial Williams, 2004. - 432 p. — ISBN 5-8459-0733-0.

en inglés

Schneier, B. Criptografía aplicada. - John Wiley & Sons, 1996. - 784 p. - ISBN 978-1-119-09672-6 .
Agnew G. Random Sources for Cryptographic Systems // Advances in Cryptology - EUROCRYPT '87 :Workshop on the Theory and Application of Cryptographic Techniques Ámsterdam, Países Bajos, 13 al 15 de abril de 1987 Actas / D. Chaum , W. L. Price - Springer Science + Business Media , 1988. - P. 77-81. — 316 pág. — ISBN 978-3-540-19102-5 — doi:10.1007/3-540-39118-5_8
Kelsey J. , Schneier B. , Wagner D. A. , Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption :, FSE' 98 Paris, France, March 23–25, 1998 Proceedings / S Vaudenay - Berlin , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Berlin Heidelberg , 1998. - P. 168-188. - ( Lecture Notes in Computer Science ; Vol. 1372) - ISBN 978-3-540-64265-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-69710-1_12
Kelsey J. , Schneier B. , Ferguson N. Yarrow-160: Notas sobre el diseño y análisis del generador de números pseudoaleatorios criptográficos Yarrow // Áreas seleccionadas en criptografía :, SAC'99 Kingston, Ontario, Canadá, agosto 9-10, 1999 Proceedings / H. M. Heys , C. Adams - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 2000. - P. 13-33. - ( Lecture Notes in Computer Science ; Vol. 1758) - ISBN 978-3-540-67185-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-46513-8_2
Murray, Mark RV Una implementación de Yarrow PRNG para FreeBSD // BSDC'02 Actas de la Conferencia BSD 2002 sobre la Conferencia BSD. - USENIX, 2002. - S. 47-53 . - ISBN 1-880446-02-2 .
Viega J. Generación práctica de números aleatorios en software (inglés) // 19th Annual Computer Security Applications Conference (ACSAC) 2003, 8-12 de diciembre de 2003, Las Vegas, NV, (EE. UU.) - IEEE Computer Society , 2003. - P. 129 -140. - ISBN 978-0-7695-2041-4 - doi:10.1109/CSAC.2003.1254318

Enlaces

Yarrow - Página de algoritmos en el sitio web de B. Schneier (inglés)