Comment résoudre le lent Java `SecureRandom`?

Si vous voulez un nombre aléatoire cryptographiquement fort en Java, vous utilisez SecureRandom . Malheureusement, SecureRandom peut être très lent. S’il utilise /dev/random sous Linux, il peut bloquer l’attente d’une entropie suffisante. Comment évitez-vous la pénalité de performance?

Quelqu’un a-t-il utilisé les mathématiques inhabituelles pour résoudre ce problème?

Quelqu’un peut-il confirmer que ce problème de performance a été résolu dans JDK 6?

Si vous voulez de vraies données aléatoires, alors vous devez malheureusement les attendre. Cela inclut la graine pour un SecureRandom PRNG. Les maths SecureRandom ne peuvent pas collecter plus de données aléatoires plus rapidement que SecureRandom , bien qu’elles puissent se connecter à Internet pour télécharger des données de départ à partir d’un site Web particulier. Je suppose que cela ne sera probablement pas plus rapide que /dev/random là où il est disponible.

Si vous voulez un PRNG, faites quelque chose comme ceci:

 SecureRandom.getInstance("SHA1PRNG"); 

Les chaînes sockets en charge dépendent du fournisseur SecureRandom SPI, mais vous pouvez les énumérer à l’aide de Security.getProviders() et Provider.getService() .

Sun aime beaucoup SHA1PRNG, donc il est largement disponible. Ce n’est pas particulièrement rapide au fur et à mesure que les PRNG disparaissent, mais les PRNG ne feront que réduire les chiffres, ne bloquant pas la mesure physique de l’entropie.

La seule exception est que si vous n’appelez pas setSeed() avant d’obtenir des données, le PRNG s’enracine une fois la première fois que vous appelez next() ou nextBytes() . Cela se fera généralement en utilisant une quantité assez petite de données réellement aléatoires du système. Cet appel peut bloquer, mais rendra votre source de nombres aléatoires beaucoup plus sûre que n’importe quelle variante de “hash l’heure actuelle avec le PID, ajoutez 27 et espérez le meilleur”. Si tout ce dont vous avez besoin est des nombres aléatoires pour un jeu, ou si vous souhaitez que le stream soit reproductible à l’avenir en utilisant la même graine à des fins de test, une graine non sécurisée est toujours utile.

Vous devriez être capable de sélectionner / dev / urandom sous Linux plus rapide mais moins sécurisé en utilisant:

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

Cependant, cela ne fonctionne pas avec Java 5 et versions ultérieures ( bogue Java 6202721 ). La solution proposée consiste à utiliser:

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

(note le extra /./ )

Sous Linux, l’implémentation par défaut de SecureRandom est NativePRNG (le code source ici ), qui a tendance à être très lent. Sous Windows, la valeur par défaut est SHA1PRNG , que d’autres utilisateurs ont indiqué que vous pouvez également utiliser sous Linux si vous la spécifiez explicitement.

NativePRNG diffère de SHA1PRNG de SHA1PRNG et Uncommons Maths en ce sens qu’il reçoit continuellement l’entropie du système d’exploitation (en lisant /dev/urandom ). Les autres PRNG n’acquièrent aucune entropie supplémentaire après l’ensemencement.

AESCounterRNG est environ 10 fois plus rapide que SHA1PRNG , qui est lui-même deux ou trois fois plus rapide que NativePRNG .

Si vous avez besoin d’un PRNG plus rapide qui acquiert l’entropie après l’initialisation, voyez si vous pouvez trouver une implémentation Java de Fortuna . Le kernel PRNG d’une implémentation Fortuna est identique à celui utilisé par AESCounterRNG, mais il existe également un système sophistiqué de regroupement d’entropie et de réensemencement automatique.

J’ai eu un problème similaire avec les appels au blocage SecureRandom pendant environ 25 secondes à la fois sur un serveur Debian sans tête. J’ai installé le démon haveged pour s’assurer que /dev/random est maintenu plein, sur les serveurs sans tête, vous avez besoin de quelque chose comme ça pour générer l’entropie requirejse. Mes appels à SecureRandom prennent peut-être maintenant des millisecondes.

De nombreuses dissortingbutions Linux (principalement basées sur Debian) configurent OpenJDK pour utiliser /dev/random pour l’entropie.

/dev/random est par définition lent (et peut même bloquer).

De là, vous avez deux options pour le débloquer:

  1. Améliorer l’entropie, ou
  2. Réduire les exigences de caractère aléatoire.

Option 1, améliorer l’entropie

Pour obtenir plus d’entropie dans /dev/random , essayez le démon condensé . C’est un démon qui collecte continuellement l’entropie HAVEGE et fonctionne également dans un environnement virtualisé car il ne nécessite aucun matériel particulier, uniquement le processeur lui-même et une horloge.

Sur Ubuntu / Debian:

 apt-get install haveged update-rc.d haveged defaults service haveged start 

Sur RHEL / CentOS:

 yum install haveged systemctl enable haveged systemctl start haveged 

Option 2. Réduire les exigences de caractère aléatoire

Si pour une raison quelconque la solution ci-dessus ne vous aide pas ou si vous ne vous souciez pas du caractère aléatoire cryptographiquement fort, vous pouvez passer à /dev/urandom place, ce qui est garanti pour ne pas bloquer.

Pour le faire globalement, éditez le fichier jre/lib/security/java.security dans votre installation Java par défaut pour utiliser /dev/urandom (à cause d’un autre bogue, il doit être spécifié sous la forme /dev/./urandom ).

Comme ça:

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

Ensuite, vous ne devrez jamais le spécifier sur la ligne de commande.


Note: Si vous faites de la cryptographie, vous avez besoin d’une bonne entropie. Cas en question – problème Android Android PRNG réduit la sécurité des portefeuilles Bitcoin.

Si vous voulez vraiment un caractère aléatoire “cryptographiquement fort”, alors vous avez besoin d’une source d’entropie forte. /dev/random est lent car il doit attendre que les événements système recueillent l’entropie (lectures de disque, paquets réseau, mouvements de la souris, pressions sur les touches, etc.).

Une solution plus rapide est un générateur de nombres aléatoires matériel. Vous en avez peut-être déjà un intégré à votre carte mère; consultez la documentation de hw_random pour savoir comment déterminer si vous l’avez et comment l’utiliser. Le paquetage rng-tools inclut un démon qui alimentera l’entropie générée par le matériel dans /dev/random .

Si un HRNG n’est pas disponible sur votre système et que vous êtes prêt à sacrifier la force d’entropie pour les performances, vous voudrez créer un bon PRNG avec les données de /dev/random et laisser le PRNG faire le gros du travail. Plusieurs systèmes PRNG approuvés par le NIST sont répertoriés dans SP800-90 et sont simples à mettre en œuvre.

Utilisez l’aléatoire sécurisé comme source d’initialisation pour un algorithme récurrent. vous pourriez utiliser un twister de Mersenne pour le travail en vrac au lieu de celui de UncommonMath, qui existe depuis un certain temps et a fait ses preuves

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

Assurez-vous de rafraîchir le aléatoire sécurisé utilisé pour l’initialisation, par exemple, vous pourriez avoir un aléatoire sécurisé généré par client, en utilisant un seul générateur pseudo-aléatoire twister mersenne par client, obtenant un degré de randomisation suffisamment élevé

Le problème que vous avez mentionné à propos de /dev/random ne concerne pas l’algorithme SecureRandom , mais la source du caractère aléatoire qu’il utilise. Les deux sont orthogonaux. Vous devez savoir lequel des deux vous ralentit.

La page Maths inhabituelle que vous avez liée mentionne explicitement qu’ils ne traitent pas la source du caractère aléatoire.

Vous pouvez essayer différents fournisseurs JCE, tels que BouncyCastle, pour voir si leur implémentation de SecureRandom est plus rapide.

Une brève recherche révèle également les correctifs Linux qui remplacent l’implémentation par défaut avec Fortuna. Je ne sais pas beaucoup plus à ce sujet, mais vous êtes invités à enquêter.

Je devrais également mentionner que, bien qu’il soit très dangereux d’utiliser un algorithme SecureRandom et / ou une source d’aléatoire mal implémentés, vous pouvez déployer votre propre fournisseur JCE avec une implémentation personnalisée de SecureRandomSpi . Vous devrez suivre un processus avec Sun pour faire signer votre fournisseur, mais c’est en fait assez simple. il vous suffit de leur envoyer un formulaire par télécopie indiquant que vous êtes au courant des ressortingctions à l’exportation imposées par les États-Unis concernant les bibliothèques cryptographiques.

Mon expérience a été seulement avec une initialisation lente du PRNG, pas avec la génération de données aléatoires après cela. Essayez une stratégie d’initialisation plus rapide. Comme ils sont coûteux à créer, traitez-le comme un singleton et réutilisez la même instance. S’il y a trop de conflits de threads pour une instance, regroupez-les ou regroupez-les par thread.

Ne compromettez pas la génération de nombres aléatoires. Une faiblesse y compromet toute votre sécurité.

Je ne vois pas beaucoup de générateurs basés sur la désintégration atomique COTS, mais il existe plusieurs plans pour eux, si vous avez vraiment besoin de beaucoup de données aléatoires. Un site qui a toujours des choses intéressantes à regarder, y compris les HotBits, est le Fourmilab de John Walker.

J’ai fait face au même problème . Après quelques recherches sur Google avec les bons termes de recherche, je suis tombé sur cet article intéressant sur DigitalOcean .

hasged est une solution potentielle sans compromettre la sécurité.

Je ne fais que citer la partie pertinente de l’article ici.

Basé sur le principe HAVEGE, et précédemment basé sur sa bibliothèque associée, hasged permet de générer un caractère aléatoire en fonction des variations du temps d’exécution du code sur un processeur. Comme il est presque impossible qu’un morceau de code prenne le même temps pour s’exécuter, même dans le même environnement sur le même matériel, le moment de l’exécution d’un ou de plusieurs programmes devrait convenir pour créer une source aléatoire. L’implémentation créée génère la source aléatoire de votre système (généralement / dev / random) en utilisant les différences du compteur d’horodatage (TSC) de votre processeur après avoir exécuté une boucle de manière répétée

Comment installer a hasged

Suivez les étapes de cet article. https://www.digitalocean.com/community/tutorials/how-to-setup-additional-entropy-for-cloud-servers-using-haveged

Je l’ai posté ici

Il semble que vous devriez être plus clair sur vos exigences de RNG. L’exigence RNG cryptographique la plus forte (si je comprends bien) serait que, même si vous connaissez l’algorithme utilisé pour les générer, et que vous connaissez tous les nombres aléatoires générés précédemment, vous ne pourriez obtenir aucune information utile sur les nombres aléatoires générés dans avenir, sans dépenser une quantité de puissance de calcul impraticable.

Si vous n’avez pas besoin de cette garantie complète de caractère aléatoire, il y a probablement des compromis de performance appropriés. J’aurais tendance à être d’accord avec la réponse de Dan Dyer à propos de AESCounterRNG d’Uncommons-Maths ou de Fortuna (un de ses auteurs est Bruce Schneier, un expert en cryptographie). Je n’ai jamais utilisé non plus mais les idées semblent fiables à première vue.

Je pense que si vous pouviez générer une graine aléatoire initiale de manière périodique (par exemple une fois par jour ou par heure), vous pourriez utiliser un chiffrement rapide pour générer des nombres aléatoires à partir de morceaux successifs du stream (si le chiffrement de stream utilise XOR passer un stream de nulls ou saisir directement les bits XOR). Le projet eStream d’ECRYPT contient de nombreuses informations utiles, notamment des tests de performance. Cela ne maintiendrait pas l’entropie entre les moments où vous le reconstituiez, donc si quelqu’un connaissait l’un des nombres aléatoires et l’algorithme que vous utilisiez, techniquement, il pourrait être possible, avec une grande puissance de calcul, de casser le chiffrement du stream et devinez son état interne pour pouvoir prédire les nombres aléatoires futurs. Mais vous devrez décider si ce risque et ses conséquences sont suffisants pour justifier le coût du maintien de l’entropie.

Edit: voici quelques notes de cours cryptographiques sur RNG que j’ai trouvées sur le net et qui sont très pertinentes pour ce sujet.

Il y a un outil (sur Ubuntu au moins) qui alimentera votre système de manière aléatoire. La commande est simplement:

 rngd -r /dev/urandom 

et vous pourriez avoir besoin d’un sudo à l’avant. Si vous n’avez pas de package rng-tools, vous devrez l’installer. J’ai essayé ceci et ça m’a vraiment aidé!

Source: mat vs monde

En utilisant Java 8, j’ai trouvé que sous Linux, l’appel de SecureRandom.getInstanceStrong() me donnerait l’algorithme NativePRNGBlocking . Cela bloquait souvent pendant plusieurs secondes pour générer quelques octets de sel.

Je suis passé à demander explicitement NativePRNGNonBlocking place, et comme prévu du nom, il n’est plus bloqué. Je n’ai aucune idée de ce que cela implique pour la sécurité. La version non bloquante ne peut probablement pas garantir la quantité d’entropie utilisée.

Mise à jour : Ok, j’ai trouvé cette excellente explication .

En résumé, pour éviter le blocage, utilisez le new SecureRandom() . Ceci utilise /dev/urandom , qui ne bloque pas et est fondamentalement aussi sécurisé que /dev/random . A partir du post: “La seule fois où vous voudriez appeler / dev / random, c’est quand la machine démarre pour la première fois et que l’entropie ne s’est pas encore accumulée”.

SecureRandom.getInstanceStrong() vous donne le RNG le plus puissant, mais vous ne pouvez l’utiliser que dans des situations où un blocage ne vous affectera pas.

Je n’ai pas rencontré ce problème moi-même, mais j’aurais créé un thread au démarrage du programme qui essaie immédiatement de générer une graine, puis meurt. La méthode que vous appelez pour les aléas se joindra à ce thread si elle est active, donc le premier appel ne bloque que s’il se produit très tôt dans l’exécution du programme.

Quelque chose d’autre à regarder est la propriété securerandom.source dans le fichier lib / security / java.security

L’utilisation de / dev / urandom plutôt que / dev / random peut présenter un avantage en termes de performances. Rappelez-vous que si la qualité des nombres aléatoires est importante, ne faites pas de compromis qui rompt la sécurité.

Si votre matériel le prend en charge, essayez d’utiliser Java RdRand Utility à l’ adresse suivante : http://code.google.com/p/lizalab-rdrand-util/

Il est basé sur l’instruction RDRAND d’Intel et est environ 10 fois plus rapide que SecureRandom et aucun problème de bande passante pour l’implémentation de gros volumes.

Divulgation complète, je suis l’auteur de l’utilitaire.

Vous pouvez essayer le projet mathématique Apache commons, qui comporte des implémentations d’algorithmes bien connus:

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

Cependant, soyez prudent avec la performance. Le constructeur par défaut de RandomDataGenerator crée une instance dédiée de Well19937c , une opération très coûteuse.

Selon la documentation, cette classe n’est pas thread-safe, mais si vous pouvez garantir qu’un seul thread accédera à cette classe, vous ne pourrez initialiser qu’une seule instance par thread.

Énoncé du problème

Cette bibliothèque msprandom illustre une technique de génération de nombres aléatoires à des fins cryptographiques sans générateurs de matériel. Le chiffrement et la signature nécessitent un nombre aléatoire de bonne qualité. Générer des nombres aléatoires (ou des séquences d’octets aléatoires) sans générateurs de matériel n’est pas une tâche banale. En particulier, ce problème est réel pour un petit appareil où les sources de données aléatoires sont absentes ou limitées. La solution consiste à avoir de véritables semences aléatoires enregistrées dans un fichier sécurisé (coffre-fort) et un chiffrement pouvant produire des séquences générées pseudo-aléatoires chiffrées (PRNG) basées sur des semences aléatoires avec de bonnes caractéristiques aléatoires.

De nombreuses bibliothèques cryptographiques (par exemple, BouncyCastle) utilisent la classe SecureRandom pour le chiffrement et la signature pour obtenir des nombres aléatoires. SecureRandom dépend de la mise en œuvre du système d’exploitation. Un autre mot, la réalisation de moteur aléatoire est en dehors de votre application que vous ne pouvez pas contrôler. Pour éviter d’utiliser des nombres aléatoires médiocres, vous DEVEZ semer le générateur SecureRandom avec de bonnes données aléatoires chaque fois que vous appelez des fonctions cryptographiques nécessitant des données aléatoires. Ou vous pouvez étendre la classe SecureRandom avec votre réalisation qui produit des nombres aléatoires dont vous pouvez contrôler la qualité.

Idée

Nous devons utiliser de vraies données aléatoires stockées dans un coffre de données sécurisé.

Quelques étapes sur la façon de msprandom dans votre application:

  1. Générez sur votre ordinateur ou cahier une véritable graine aléatoire et placez-la dans un coffre-fort en utilisant cette bibliothèque.
  2. Placez un coffre-fort (fichier) avec une graine aléatoire sur votre appareil, ordinateur ou serveur où vous devez crypter et signer les données.
  3. Chargez le coffre-fort une fois au début du programme lorsque vous avez besoin de chiffrer ou de signer des données.
  4. Appelez la fonction gen-rand à partir de la bibliothèque msprandom pour obtenir des octets aléatoires autant de fois que nécessaire.

La voûte avec des graines aléatoires est cryptée et sécurisée avec HMAC. La semence aléatoire dans un coffre-fort est mise à jour chaque fois que vous chargez le coffre-fort de manière imprévisible, de sorte que HMAC change également. Changer un coffre-fort se fait intentionnellement contre une situation si un attaquant peut enrichir une copie de votre coffre-fort par le passé.

Véritable générateur de données aléatoires

Pour générer une véritable graine aléatoire, une entrée humaine est utilisée dans msprandom . Voici l’algorithme de collecte de données aléatoires:

  1. Nous exécutons un thread séparé où le compteur atomique incrémente chaque tic de 0..255 avec une vitesse très élevée.
  2. Attendez que l’utilisateur appuie sur une touche sans tampon et obtenez un code de numérisation du bouton enfoncé.
  3. Prenez la valeur actuelle de nanosecondes à partir du début d’Epoch et prenez le mod 256 pour convertir sa valeur en un octet aléatoire.
  4. Valeurs Xor entre elles: scan-code-byte ^ current-counter-value ^ nanosecondes pour produire un octet aléatoire.
  5. Ajouter un octet aléatoire au vecteur de sortie. Nous supposons que seulement 3 bits ont un caractère aléatoire réel dans cet octet aléatoire. Donc, pour obtenir 32 octets au hasard, nous avons besoin d’appuyer sur un bouton d’environ 32 * 3 à partir de l’entrée utilisateur.
  6. Répétez les étapes 2 à 5 jusqu’à ce que vous obteniez la quantité requirejse d’octets aléatoires. Si nous avons collecté la quantité requirejse de données aléatoires, nous effectuons l’étape finale -> vecteur de sortie de hachage avec une fonction de hachage cryptographiquement forte pour garantir que la probabilité de 1 et 0 bits dans le vecteur de sortie sera de 0,5. Notez que cette fonction de hachage est utilisée ici uniquement pour mélanger des bits aléatoires et n’influence pas la qualité des données aléatoires. So hash (données aléatoires) = données aléatoires. En utilisant cet algorithme, le msprandom collecte 512 bits aléatoires comme graine qui sera sauvegardée dans un coffre.

Pourquoi 512 bits aléatoires sont suffisants?

Eh bien, chaque PRNG a besoin d’une vraie graine aléatoire. Si un attaquant connaît une graine, il peut prédire la génération de clés, etc. 256 bits de semences aléatoires initiales sont suffisamment éloignés pour garder des secrets de qualité militaire. J’ai fait 512 pour être sûr que personne ne peut brutaliser ou deviner la graine initiale. Ainsi, vous pouvez utiliser librement msprandom pour créer des générateurs PRNG ou SecureRandom.