stringtranslate.com

Algoritmo de milenrama

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 resiembra conecta el acumulador de entropía con el mecanismo de generación. La resiembra 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; la resiembra 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. Ambas resiembras restablecen la estimación de entropía del grupo rápido a cero, pero la última también establece la estimación del grupo lento a cero. El mecanismo de resiembra actualiza la clave constantemente, de modo que incluso si el atacante conoce la clave de la información del grupo antes de la resiembra, será desconocida para el atacante después de la resiembra.

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

Contras

Referencias

  1. ^ "[base] Revisión 284959". Svnweb.freebsd.org . Consultado el 18 de octubre de 2016 .
  2. ^ "Seguridad de iOS" (PDF) . Apple.com . Octubre de 2012 . Consultado el 21 de octubre de 2016 .
  3. ^ "Generación de números aleatorios". Soporte técnico de Apple . Consultado el 26 de octubre de 2020 .
  4. ^ 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.
  5. ^ 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.
  6. ^ "Una implementación del PRNG de Yarrow para FreeBSD" . Consultado el 18 de octubre de 2016 .
  7. ^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (23 de febrero de 2017). "SHAttered". SHAttered . Consultado el 27 de abril de 2017 .
  8. ^ "PRNG criptográficamente seguro de Fortuna: AN0806 - Nota de aplicación" (PDF) . Silabs.com . Consultado el 21 de octubre de 2016 .
  9. ^ 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