¿Cómo resolver Java `SecureRandom` lento?

performance security (18)

Si desea un número aleatorio criptográficamente fuerte en Java, use SecureRandom . Desafortunadamente, SecureRandom puede ser muy lento. Si usa /dev/random en Linux, puede bloquear esperando a que se acumule suficiente entropía. ¿Cómo se evita la penalización de rendimiento?

¿Alguien ha usado Uncommon Maths como solución a este problema?

¿Alguien puede confirmar que este problema de rendimiento se ha resuelto en JDK 6?

Debería poder seleccionar el / dev / urandom más rápido / pero menos seguro en Linux usando:

-Djava.security.egd=file:/dev/urandom

Sin embargo, esto no funciona con Java 5 y posterior ( Java Bug 6202721 ). El trabajo sugerido es usar:

-Djava.security.egd=file:/dev/./urandom

(tenga en cuenta el extra /./ )

El problema al que hizo referencia sobre /dev/random no es con el algoritmo SecureRandom , sino con la fuente de aleatoriedad que utiliza. Los dos son ortogonales. Debes averiguar cuál de los dos te está ralentizando.

La página Uncommon Maths que usted ha vinculado menciona explícitamente que no están abordando el origen de la aleatoriedad.

Puede probar diferentes proveedores de JCE, como BouncyCastle, para ver si su implementación de SecureRandom es más rápida.

Una breve search también revela parches de Linux que reemplazan la implementación predeterminada con Fortuna. No sé mucho más sobre esto, pero puedes investigar.

También debo mencionar que si bien es muy peligroso usar un algoritmo SecureRandom mal implementado y / o una fuente de aleatoriedad, puede hacer que su propio proveedor de JCE implemente una aplicación personalizada de SecureRandomSpi . Tendrá que pasar por un proceso con Sun para firmar a su proveedor, pero en realidad es bastante sencillo; solo necesitan que les envíe por fax un formulario que indique que conoce las restricciones de exportación de los Estados Unidos a las bibliotecas de cifrado.

En Linux, la implementación predeterminada para SecureRandom es NativePRNG (código fuente here ), que tiende a ser muy lento. En Windows, el valor predeterminado es SHA1PRNG , que, como otros señalaron, también se puede usar en Linux si se especifica explícitamente.

NativePRNG difiere de SHA1PRNG y Uncommons Maths '' AESCounterRNG en que continuamente recibe entropía del sistema operativo (leyendo de /dev/urandom ). Los otros PRNG no adquieren ninguna entropía adicional después de la siembra.

AESCounterRNG es aproximadamente 10 veces más rápido que SHA1PRNG , que IIRC es en sí mismo dos o tres veces más rápido que NativePRNG .

Si necesita un PRNG más rápido que adquiera entropía después de la inicialización, consulte si puede encontrar una implementación Java de Fortuna . El PRNG central de una implementación de Fortuna es idéntico al utilizado por AESCounterRNG, pero también hay un sistema sofisticado de agrupamiento de entropía y resiembra automática.

Enfrenté el mismo issue . Después de buscar en Google con los términos de búsqueda correctos, me encontré con este buen artículo en DigitalOcean .

haveged es una solución potencial sin comprometer la seguridad.

Simplemente estoy citando la parte relevante del artículo aquí.

Basado en el principio HAVEGE, y previamente basado en su biblioteca asociada, haveged permite generar aleatoriedad según las variaciones en el tiempo de ejecución del código en un procesador. Dado que es casi imposible que una parte del código tome el mismo tiempo para ejecutarse, incluso en el mismo entorno en el mismo hardware, el tiempo de ejecución de uno o varios programas debería ser adecuado para generar una fuente aleatoria. La implementación de hasged genera la fuente aleatoria de su sistema (generalmente / dev / random) usando diferencias en el contador de marca de tiempo de su procesador (TSC) después de ejecutar un bucle repetidamente

Cómo instalar haveged

Sigue los pasos en este artículo. DigitalOcean

Lo he publicado here

Hay una herramienta (al menos en Ubuntu) que alimentará la aleatoriedad artificial en su sistema. El comando es simplemente:

rngd -r /dev/urandom

y es posible que necesite un sudo en el frente. Si no tiene el paquete de herramientas rng, tendrá que instalarlo. Intenté esto, ¡y definitivamente me ayudó!

Fuente: mate vs mundo

Mi experiencia ha sido solo con la inicialización lenta del PRNG, no con la generación de datos aleatorios después de eso. Pruebe una estrategia de inicialización más entusiasta. Dado que son caros de crear, trátelo como un singleton y reutilice la misma instancia. Si hay demasiada contención de subprocesos para una instancia, agréguelos o conviértalos en subprocesos locales.

No comprometa la generación de números aleatorios. Una debilidad allí compromete toda su seguridad.

No veo muchos generadores basados en decaimiento atómico de COTS, pero existen varios planes para ellos, si realmente se necesitan muchos datos aleatorios. Un sitio que siempre tiene cosas interesantes para mirar, incluyendo HotBits, es el Fourmilab de John Walker.

Muchas distribuciones de Linux (mayormente basadas en Debian) configuran incorrectamente OpenJDK para usar /dev/random para entropy.

/dev/random es por definición lento (e incluso puede bloquear). Hubiera sido prudente usar /dev/urandom lugar (que es lo que el JDK usa en Solaris, por ejemplo).

Para solucionarlo globalmente, edite el archivo jre/lib/security/java.security en su instalación Java predeterminada para usar /dev/urandom (debido a otro error , debe especificarse como /dev/./urandom ).

Me gusta esto:

#securerandom.source=file:/dev/random securerandom.source=file:/dev/./urandom

Entonces nunca tendrás que especificarlo en la línea de comando.

No he atacado este problema yo mismo, pero generaría un hilo en el inicio del programa que de inmediato intenta generar una semilla, luego muere. El método que usted llame para randoms se unirá a ese hilo si está activo, por lo que la primera llamada solo se bloquea si se produce muy temprano en la ejecución del programa.

Otra cosa a mirar es la propiedad securerandom.source en el archivo lib / security / java.security

Puede haber un beneficio de rendimiento al usar / dev / urandom en lugar de / dev / random. Recuerde que si la calidad de los números aleatorios es importante, no haga concesiones que rompan la seguridad.

Parece que deberías ser más claro acerca de tus requisitos de RNG. El requisito de RNG criptográfico más fuerte (según tengo entendido) sería que, incluso si conoce el algoritmo utilizado para generarlos, y conoce todos los números aleatorios generados previamente, no podría obtener ninguna información útil sobre ninguno de los números aleatorios generados en el futuro, sin gastar una cantidad poco práctica de poder de cómputo.

Si no necesita esta garantía completa de aleatoriedad, entonces probablemente haya compensaciones de rendimiento apropiadas. Tiendo a estar de acuerdo con la respuesta de Dan Dyer sobre AESCounterRNG de Uncommons-Maths, o Fortuna (uno de sus autores es Bruce Schneier, un experto en criptografía). Nunca he usado ninguno pero las ideas parecen acreditadas a primera vista.

Creo que si pudieras generar una semilla aleatoria inicial periódicamente (por ejemplo, una vez por día, hora o lo que sea), podrías usar un cifrado de flujo rápido para generar números aleatorios a partir de fragmentos sucesivos de la secuencia (si el cifrado de flujo usa XOR entonces solo pasar una secuencia de nulos o tomar los bits XOR directamente). El proyecto eStream de ECRYPT tiene mucha información buena, incluyendo puntos de referencia de rendimiento. Esto no mantendría la entropía entre los puntos en el tiempo que usted reponga, por lo que si alguien supiera uno de los números aleatorios y el algoritmo que utilizó, técnicamente podría ser posible, con una gran cantidad de poder de cómputo, descifrar el cifrado de flujo y adivinar su estado interno para poder predecir números aleatorios futuros. Pero tendría que decidir si ese riesgo y sus consecuencias son suficientes para justificar el costo de mantener la entropía.

Editar: aquí hay algunas notas del curso criptográfico sobre RNG que encontré en la red que parecen muy relevantes para este tema.

Puede probar el proyecto Apache commons Math, que tiene algunas implementaciones de algoritmos conocidos:

https://commons.apache.org/proper/commons-math/userguide/random.html

Sin embargo, ten cuidado con el rendimiento. El constructor predeterminado de RandomDataGenerator crea una instancia dedicada de Well19937c , que es una operación muy costosa.

Según la documentación, esta clase no es segura para subprocesos, pero si puede garantizar que solo un subproceso tendrá acceso a esta clase, puede inicializar solo una instancia por subproceso.

Si quieres aleatoriedad verdaderamente "criptográficamente fuerte", entonces necesitas una fuente de entropía fuerte. /dev/random es lento porque tiene que esperar a que los eventos del sistema recopilen entropía (lecturas de disco, paquetes de red, movimiento del mouse, pulsación de teclas, etc.).

Una solución más rápida es un generador de números aleatorios de hardware. Es posible que ya tenga uno integrado en su placa base; revise la documentación hw_random para obtener instrucciones sobre cómo averiguar si la tiene y cómo usarla. El paquete rng-tools incluye un daemon que alimentará la entropía generada por hardware en /dev/random .

Si un HRNG no está disponible en su sistema, y está dispuesto a sacrificar la fuerza de entropía por el rendimiento, querrá sembrar un buen PRNG con datos de /dev/random , y dejar que el PRNG haga la mayor parte del trabajo. Hay varios PRNG aprobados por NIST enumerados en SP800-90 que son fáciles de implementar.

Si quieres datos aleatorios verdaderos, desafortunadamente tienes que esperarlos. Esto incluye la semilla para un SecureRandom PRNG. Uncommon Maths no puede recopilar datos aleatorios verdaderos más rápido que SecureRandom , aunque puede conectarse a Internet para descargar datos iniciales de un sitio web en particular. Supongo que es poco probable que sea más rápido que /dev/random cuando esté disponible.

Si quieres un PRNG, haz algo como esto:

SecureRandom.getInstance("SHA1PRNG");

Las cadenas soportadas dependen del proveedor SecureRandom SPI, pero puede enumerarlas usando Security.getProviders() y Provider.getService() .

Sun es aficionado a SHA1PRNG, por lo que está ampliamente disponible. No es especialmente rápido a medida que avanzan los PRNG, pero los PRNG simplemente estarán crujiendo los números, no bloqueando la medición física de la entropía.

La excepción es que si no llama a setSeed() antes de obtener datos, entonces el PRNG se iniciará una vez la primera vez que llame a next() o nextBytes() . Normalmente lo hará utilizando una cantidad bastante pequeña de datos aleatorios verdaderos del sistema. Esta llamada puede bloquear, pero hará que su fuente de números aleatorios sea mucho más segura que cualquier variante de "hash la hora actual junto con el PID, agregue 27 y espere lo mejor". Sin embargo, si todo lo que necesitas son números aleatorios para un juego, o si quieres que la transmisión sea repetible en el futuro utilizando la misma semilla para fines de prueba, una semilla insegura sigue siendo útil.

Si su hardware lo admite, intente usar Java RdRand Utility disponible en: http://code.google.com/p/lizalab-rdrand-util/

Está basado en la instrucción RDRAND de Intel y es aproximadamente 10 veces más rápido que SecureRandom y no tiene problemas de ancho de banda para la implementación de grandes volúmenes.

Divulgación completa, soy el autor de la utilidad.

Tuve un problema similar con las llamadas al bloqueo de SecureRandom durante unos 25 segundos a la vez en un servidor Debian sin cabeza. Instalé el daemon con haveged para asegurar que /dev/random se mantenga actualizado, en servidores sin cabeza necesitas algo como esto para generar la entropía requerida. Mis llamadas a SecureRandom ahora tal vez tomen milisegundos.

Usando Java 8, encontré que en Linux llamar a SecureRandom.getInstanceStrong() me daría el algoritmo NativePRNGBlocking . Esto a menudo bloqueará durante muchos segundos para generar unos pocos bytes de sal.

Pasé a pedir explícitamente NativePRNGNonBlocking y, como esperaba del nombre, ya no está bloqueado. No tengo idea de cuáles son las implicaciones de seguridad de esto. Presumiblemente, la versión sin bloqueo no puede garantizar la cantidad de entropía que se utiliza.

Actualización : Ok, encontré esta excelente explicación .

En pocas palabras, para evitar el bloqueo, use el new SecureRandom() . Esto usa /dev/urandom , que no bloquea y es básicamente tan seguro como /dev/random . Desde la publicación: "La única vez que desea llamar a / dev / random es cuando la máquina arranca por primera vez y la entropía aún no se ha acumulado".

SecureRandom.getInstanceStrong() te ofrece el RNG más potente, pero solo es seguro para usar en situaciones donde un montón de bloqueo no te afectará.

Use la fuente aleatoria segura como fuente de inicialización para un algoritmo recurrente; podría usar entonces un tornado Mersenne para el trabajo a granel en lugar de uno en UncommonMath, que ha existido por un tiempo y ha demostrado ser mejor que otros procesos.

http://en.wikipedia.org/wiki/Mersenne_twister

Asegúrese de actualizar de vez en cuando el azar seguro utilizado para la inicialización; por ejemplo, podría generar un seguro aleatorio generado por cliente, utilizando un generador seudoaleatorio mersenne twister por cliente, obteniendo un grado suficientemente alto de aleatorización

Planteamiento del problema

Esta biblioteca msprandom demuestra una técnica de generación de números aleatorios para propósitos criptográficos sin generadores de hardware. El cifrado y la firma requieren números aleatorios de buena calidad. Generar números aleatorios (o secuencias de bytes aleatorios) sin generadores de hardware no es una tarea trivial. Especialmente este problema es real para dispositivos pequeños donde las fuentes de datos aleatorios están ausentes o limitadas. La solución es tener semilla aleatoria verdadera guardada en un archivo protegido (bóveda) y cifrado que puede producir secuencias encriptadas generadas pseudoaleatorias (PRNG) basadas en semilla aleatoria con buenas características aleatorias.

Muchas bibliotecas criptográficas (por ejemplo, BouncyCastle) usan la clase SecureRandom para el cifrado y la firma para obtener números aleatorios. SecureRandom depende de la implementación del sistema operativo. Otra de las palabras, la realización de motor aleatorio está fuera de su aplicación, que no puede controlar. Para evitar el uso de números aleatorios pobres, DEBE sembrar el generador SecureRandom con buenos datos aleatorios cada vez que llame a funciones criptográficas que requieran datos aleatorios. O puede extender la clase SecureRandom con su realización que produce un número aleatorio cuya calidad puede controlar.

Idea

Necesitamos usar datos aleatorios verdaderos almacenados en una bóveda de datos segura.

Algunos pasos de cómo msprandom dentro de su aplicación:

Genere en su computadora o computadora portátil una semilla aleatoria verdadera y póngala en una bóveda usando esta biblioteca.
Coloque una bóveda (archivo) con una semilla aleatoria en su dispositivo, computadora o servidor donde necesita encriptar y firmar datos.
Cargue la bóveda una vez al inicio del programa cuando necesite encriptar o firmar datos.
Llame a la función gen-rand de la biblioteca msprandom para obtener bytes aleatorios tantas veces como lo necesite.

La bóveda con semilla aleatoria está encriptada y asegurada con HMAC. La semilla aleatoria en una bóveda se actualiza cada vez que carga la bóveda de manera impredecible, por lo que HMAC también está cambiando. Cambiar una bóveda se hace intencionalmente en contra de la situación si el atacante puede enriquecer alguna copia de tu bóveda en el pasado.

Verdadero generador de datos aleatorios

Para generar una verdadera semilla aleatoria se usa una entrada humana en msprandom . Aquí está el algoritmo de recopilación de datos aleatorios:

Ejecutamos hilo separado donde el contador atómico incrementa cada tic desde 0..255 con una velocidad muy alta.
Espere a que el humano presione la tecla sin búfer y obtenga un código de exploración del botón presionado.
Tome el valor actual de nanosegundos desde el inicio de Epoch y tome el mod 256 para convertir su valor a un byte aleatorio.
Xor valores entre sí: scan-code-byte ^ current-counter-value ^ nanoseconds para producir byte aleatorio.
Agregue un byte aleatorio al vector de salida. Suponemos que solo 3 bits tienen aleatoriedad verdadera en este byte aleatorio. Por lo tanto, para obtener 32 bytes aleatorios verdaderos, necesitamos presionar 32 ~ 3 botones desde la entrada del usuario.
Repita los pasos 2 a 5 hasta que obtengamos la cantidad requerida de bytes aleatorios. Si recogimos la cantidad requerida de datos aleatorios, hagamos el paso final -> hash vector de salida con función hash criptográficamente fuerte para garantizar que la probabilidad 1 y 0 bits en el vector de salida será 0.5. Tenga en cuenta que la función hash utilizada aquí solo para mezclar bits aleatorios y no influye en la calidad de los datos aleatorios. Entonces hash (datos aleatorios) = datos aleatorios. Usando este algoritmo, el msprandom recoge un verdadero 512 bits aleatorios como una semilla que se guardará en una bóveda.

¿Por qué 512 bits aleatorios es suficiente?

Bueno, cada PRNG necesita una verdadera semilla aleatoria. Si un atacante conoce una semilla, entonces puede predecir la generación de claves, etc. 256 bits de semilla aleatoria inicial es lo suficientemente lejos como para mantener secretos de grado millitary. Hice 512 para asegurarme de que nadie puede usar la fuerza bruta ni adivinar la semilla aleatoria inicial. Entonces, puedes usar libremente msprandom para sembrar tus generadores PRNG o SecureRandom.