El algoritmo Yarrow es una familia de generadores de números pseudoaleatorios criptográficos (CSPRNG) ideados por John Kelsey , Bruce Schneier y Niels Ferguson y publicados en 1999. El algoritmo Yarrow no está patentado, no tiene derechos de autor y es de código abierto; no se requiere licencia para usarlo. Un diseño mejorado de Ferguson y Schneier, Fortuna , se describe en su libro, Practical Cryptography.
Yarrow se utilizó en FreeBSD , pero ahora Fortuna lo ha reemplazado. [1] Yarrow también se incorporó en iOS [2] y macOS para sus dispositivos /dev/random , pero Apple cambió a Fortuna desde el primer trimestre de 2020. [3]
Nombre
El nombre Milenrama alude al uso de la planta de milenrama en el proceso de generación aleatoria de la adivinación del I Ching . Desde la dinastía Xia ( c. 2070 a c. 1600 a. C. ), los chinos han utilizado tallos de milenrama para la adivinación. Los adivinos dividen un conjunto de 50 tallos de milenrama en montones y utilizan aritmética modular de forma recursiva para generar dos bits de información aleatoria [4] que tienen una distribución
no uniforme .
Principios
Los principios de diseño principales de Yarrow son: resistencia a ataques, facilidad de uso por parte de programadores sin conocimientos de criptografía y reutilización de los bloques de construcción existentes. Los diseños anteriores ampliamente utilizados, como ANSI X9.17 y RSAREF 2.0 PRNG, tienen lagunas que brindan oportunidades de ataque en algunas circunstancias. Algunos de ellos no están diseñados teniendo en cuenta los ataques del mundo real. Yarrow también tiene como objetivo proporcionar una integración sencilla, para permitir a los diseñadores de sistemas con poco conocimiento de la funcionalidad PRNG. [5]
Diseño
Componentes
El diseño de Yarrow consta de cuatro componentes principales: un acumulador de entropía , un mecanismo de resiembra , un mecanismo de generación y un control de resiembra.
Yarrow acumula entropía en dos grupos: el grupo rápido, que proporciona resiembras frecuentes de la clave para mantener la duración de los compromisos de la clave lo más breve posible; el grupo lento, que proporciona resiembras de la clave poco frecuentes pero conservadoras. Esto garantiza que la resiembra sea segura incluso cuando las estimaciones de entropía sean muy optimistas.
El mecanismo de resembrado conecta el acumulador de entropía con el mecanismo de generación. El resembrado desde el grupo rápido utiliza la clave actual y el hash de todas las entradas al grupo rápido desde el inicio para generar una nueva clave; el resembrado desde el grupo lento se comporta de manera similar, excepto que también utiliza el hash de todas las entradas al grupo lento para generar una nueva clave. Ambos resembrados restablecen la estimación de entropía del grupo rápido a cero, pero el último también establece la estimación del grupo lento a cero. El mecanismo de resembrado actualiza la clave constantemente, de modo que incluso si el atacante conoce la clave de la información del grupo antes del resembrado, será desconocida para el atacante después del resembrado.
El componente de control de resiembra está haciendo un uso equilibrado entre la resiembra frecuente, que es deseable pero podría permitir ataques de adivinación iterativos, y la resiembra poco frecuente, que compromete más información para un atacante que tiene la clave. Yarrow utiliza el grupo rápido para resiembra cada vez que la fuente supera ciertos valores de umbral, y utiliza el grupo lento para resiembra cada vez que al menos dos de sus fuentes superan algún otro valor de umbral. Los valores de umbral específicos se mencionan en la sección Yarrow-160.
Filosofía de diseño
Yarrow supone que se puede acumular suficiente entropía para garantizar que el PRNG se encuentre en un estado impredecible. Los diseñadores acumulan entropía con el fin de mantener la capacidad de recuperar el PRNG incluso cuando la clave se ve comprometida. Los PRNG RSAREF, DSA y ANSI X9.17 adoptan una filosofía de diseño similar.
Milenrama-160
Yarrow utiliza dos algoritmos importantes: una función hash unidireccional y un cifrado de bloques . La descripción y las propiedades específicas se enumeran en la siguiente tabla.
Generación
Funciones para el mecanismo de generación
Yarrow-160 utiliza el Triple DES de tres teclas en modo contador para generar salidas. C es un valor de contador de n bits; K es la clave. Para generar el siguiente bloque de salida, Yarrow sigue las funciones que se muestran aquí.
Yarrow lleva la cuenta del bloque de salida, porque una vez que la clave se ve comprometida, la fuga de la salida anterior a la comprometida se puede detener de inmediato. Una vez que se alcanza algún parámetro de seguridad del sistema P g , el algoritmo generará k bits de salida PRNG y los usará como la nueva clave. En Yarrow-160, el parámetro de seguridad del sistema se establece en 10 , lo que significa que P g = 10. El parámetro se establece intencionalmente en un valor bajo para minimizar la cantidad de salidas que se pueden rastrear.
Resembrar
El mecanismo de resembrado de Yarrow-160 utiliza SHA-1 y Triple DES como función hash y cifrado de bloque. Los pasos detallados se encuentran en el artículo original.
Implementación de Yarrow-160
Yarrow-160 se ha implementado en Java y para FreeBSD . Los ejemplos se pueden encontrar en "Una implementación del PRNG de Yarrow para FreeBSD" [6] de Mark RV Murray.
Pros y contras de la milenrama
Ventajas
Yarrow reutiliza bloques de construcción existentes.
En comparación con los PRNG anteriores, Yarrow es razonablemente eficiente.
Yarrow puede ser utilizado por programadores sin conocimientos previos de criptografía de forma razonablemente segura. Yarrow es portátil y está definido con precisión. La interfaz es sencilla y clara. Estas características reducen un poco las posibilidades de errores de implementación.
Yarrow se creó utilizando un proceso de diseño orientado a ataques.
La estimación de entropía de Yarrow es muy conservadora, lo que evita ataques de búsqueda exhaustiva . Es muy común que los PRNG fallen en aplicaciones del mundo real debido a la sobreestimación de la entropía y a puntos de partida adivinables.
El proceso de resiembra de Yarrow es relativamente costoso en términos computacionales, por lo que el costo de intentar adivinar la clave del PRNG es mayor.
Yarrow utiliza funciones para simplificar la gestión de los archivos de semillas, por lo que los archivos se actualizan constantemente.
Para hacer frente a los ataques criptoanalíticos , Yarrow está diseñado para basarse en un cifrado de bloques seguro. El nivel de seguridad del mecanismo de generación depende del cifrado de bloques.
Yarrow intenta evitar rutas de ejecución dependientes de los datos. Esto se hace para evitar ataques de canal lateral , como ataques de sincronización y análisis de potencia . Esto es una mejora en comparación con PRNG anteriores, por ejemplo, RSAREF 2.0 PRNG, que se desmoronará por completo una vez que la información adicional sobre las operaciones internas ya no esté protegida.
Yarrow utiliza funciones hash criptográficas para procesar muestras de entrada y luego utiliza una función de actualización segura para combinar las muestras con la clave existente. Esto garantiza que el atacante no pueda manipular fácilmente las muestras de entrada. Los PRNG como RSAREF 2.0 PRNG no tienen la capacidad de resistir este tipo de ataque de entrada elegida.
A diferencia de ANSI X9.17 PRNG, Yarrow tiene la capacidad de recuperarse de una vulnerabilidad de clave. Esto significa que incluso cuando la clave está comprometida, el atacante no podrá predecir resultados futuros para siempre. Esto se debe al mecanismo de resiembra de Yarrow. [5] : 5
Yarrow tiene el grupo de muestras de entropía separado de la clave y solo vuelve a sembrar la clave cuando el contenido del grupo de entropía es completamente impredecible.Este diseño evita ataques de adivinación iterativos, donde un atacante con la clave adivina la siguiente muestra y verifica el resultado observando la siguiente salida.
Contras
Yarrow depende de SHA-1, un hash que se ha roto (en términos de resistencia a colisiones) desde la publicación de Yarrow y ya no se considera seguro. [7] Sin embargo, no hay ningún ataque publicado que utilice colisiones SHA-1 para socavar la aleatoriedad de Yarrow.
Dado que los resultados de Yarrow se derivan criptográficamente, los sistemas que utilizan esos resultados solo pueden ser tan seguros como el propio mecanismo de generación. Eso significa que el atacante que puede romper el mecanismo de generación romperá fácilmente un sistema que depende de los resultados de Yarrow. Este problema no se puede resolver aumentando la acumulación de entropía.
Yarrow requiere una estimación de entropía, lo que supone un gran desafío para las implementaciones. [8] Es difícil estar seguro de cuánta entropía se debe recolectar antes de usarla para volver a sembrar el PRNG. [9] Este problema se resuelve con Fortuna , una mejora de Yarrow. Fortuna tiene 32 grupos para recolectar entropía y eliminó por completo el estimador de entropía.
La potencia de Yarrow está limitada por el tamaño de la clave. Por ejemplo, Yarrow-160 tiene un tamaño de clave efectivo de 160 bits. Si la seguridad requiere 256 bits, Yarrow-160 no es capaz de realizar el trabajo.
Referencias
^ "[base] Revisión 284959". Svnweb.freebsd.org . Consultado el 18 de octubre de 2016 .
^ "Seguridad de iOS" (PDF) . Apple.com . Octubre de 2012 . Consultado el 21 de octubre de 2016 .
^ "Generación de números aleatorios". Soporte técnico de Apple . Consultado el 26 de octubre de 2020 .
^ Schneier, Bruce . "Preguntas y respuestas sobre la milenrama". Schneier sobre seguridad . Consultado el 15 de febrero de 2016. El adivino dividiría un conjunto de 50 tallos en montones y luego usaría repetidamente la aritmética modular para generar dos bits aleatorios.
^ ab Kelsey, John; Schneier, Bruce; Ferguson, Niels (agosto de 1999). "Yarrow-160: Notas sobre el diseño y análisis del generador de números pseudoaleatorios criptográficos Yarrow" (PDF) . Sexto taller anual sobre áreas seleccionadas en criptografía . 1758 : 13–33. doi :10.1007/3-540-46513-8_2.
^ "Una implementación del PRNG de Yarrow para FreeBSD" . Consultado el 18 de octubre de 2016 .
^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (23 de febrero de 2017). "SHAttered". SHAttered . Consultado el 27 de abril de 2017 .
^ "PRNG criptográficamente seguro de Fortuna: AN0806 - Nota de aplicación" (PDF) . Silabs.com . Consultado el 21 de octubre de 2016 .
^ Citadel (4 de marzo de 2004). «Fortuna: un generador de números pseudoaleatorios criptográficamente seguro – CodeProject» . Consultado el 18 de octubre de 2016 .
Enlaces externos
Página del algoritmo de Yarrow
Implementación de Yarrow en Java
Implementación de Yarrow en FreeBSD
"Una implementación del PRNG de Yarrow para FreeBSD"
