Différence entre java.util.Random et java.security.SecureRandom

Question

Mon équipe a reçu un code côté serveur (en Java) qui génère des jetons aléatoires et j'ai une question à ce sujet.

L'objectif de ces jetons est assez sensible : ils sont utilisés pour l'identification de la session, les liens de réinitialisation du mot de passe, etc. Ils doivent donc être cryptographiquement aléatoires pour éviter que quelqu'un ne les devine ou ne les force brutalement. Le jeton est un "long", c'est-à-dire qu'il comporte 64 bits.

Le code utilise actuellement le java.util.Random pour générer ces jetons. Le site documentation para java.util.Random stipule clairement ce qui suit :

Les instances de java.util.Random ne sont pas sécurisées sur le plan cryptographique. Pensez plutôt à utiliser SecureRandom pour obtenir un générateur de nombres pseudo-aléatoires sécurisé sur le plan cryptographique pour les applications sensibles à la sécurité.

Cependant, la façon dont le code utilise actuellement java.util.Random est la suivante : elle instancie le java.security.SecureRandom et utilise ensuite la classe SecureRandom.nextLong() afin d'obtenir la graine utilisée pour l'instanciation de l'interface utilisateur. java.util.Random classe. Ensuite, il utilise java.util.Random.nextLong() pour générer le jeton.

Donc ma question maintenant - Est-il encore peu sûr étant donné que le java.util.Random est en cours d'ensemencement en utilisant java.security.SecureRandom ? Dois-je modifier le code de manière à ce qu'il utilise java.security.SecureRandom exclusivement pour générer les jetons ?

Actuellement, le code qui ensemence le Random une fois au démarrage

Answer 1

L'implémentation standard d'Oracle JDK 7 utilise ce que l'on appelle un générateur contructif linéaire pour produire des valeurs aléatoires dans les champs suivants java.util.Random .

Tiré de java.util.Random code source (JDK 7u2), à partir d'un commentaire sur la méthode protected int next(int bits) qui est celui qui génère les valeurs aléatoires :

Il s'agit d'un générateur de nombres pseudo-aléatoires linéaire congruent, tel que défini par D. H. Lehmer et décrit par Donald E. Knuth en L'art de la programmation informatique, Volume 3 : Algorithmes semi-numériques , section 3.2.1.

Prédictibilité des générateurs congruentiels linéaires

Hugo Krawczyk a écrit un très bon article sur la façon dont ces LCG peuvent être prédits ("How to predict congruential generators"). Si vous êtes chanceux et intéressé, vous pouvez encore en trouver une version gratuite et téléchargeable sur le Web. Et de nombreuses autres recherches montrent clairement que vous devriez jamais utiliser un LCG à des fins de sécurité. Cela signifie également que vos nombres aléatoires sont prévisible pour le moment, ce que vous ne voulez pas pour les identifiants de session et autres.

Comment casser un générateur congruentiel linéaire ?

L'hypothèse selon laquelle un attaquant devrait attendre que le LCG se répète après un cycle complet est fausse. Même avec un cycle optimal (le modulus m dans sa relation de récurrence), il est très facile de prédire les valeurs futures en beaucoup moins de temps qu'un cycle complet. Après tout, il ne s'agit que d'un ensemble d'équations modulaires à résoudre, ce qui devient facile dès que vous avez observé suffisamment de valeurs de sortie du LCG.

La sécurité ne s'améliore pas avec une "meilleure" graine. Il n'est tout simplement pas important de semer avec une valeur aléatoire générée par SecureRandom ou même produire la valeur en lançant un dé plusieurs fois.

Un attaquant calculera simplement la graine à partir des valeurs de sortie observées. Cela prend nettement moins temps que 2^48 dans le cas de java.util.Random . Les incrédules peuvent essayer ceci expérience où il est démontré que vous pouvez prédire le futur Random Les sorties observant seulement deux ( !) valeurs de sortie dans un temps approximativement 2^16. Il ne faut même pas une seconde à un ordinateur moderne pour prédire la sortie de vos nombres aléatoires en ce moment.

Conclusion

Remplacez votre code actuel. Utilisez SecureRandom exclusivement. Vous aurez alors au moins une petite garantie que le résultat sera difficile à prévoir. Si vous souhaitez bénéficier des propriétés d'un PRNG sécurisé sur le plan cryptographique (dans votre cas, c'est ce que vous voulez), vous devez opter pour SecureRandom seulement. Faire preuve d'ingéniosité pour changer la façon dont il était censé être utilisé aboutira presque toujours à quelque chose de moins sûr...

Answer 2

Un aléatoire n'a que 48 bits alors que SecureRandom peut avoir jusqu'à 128 bits. Les chances de répétition dans SecureRandom sont donc très faibles.

Random utilise le system clock comme graine ou pour générer la graine. Ils peuvent donc être reproduits facilement si l'attaquant connaît l'heure à laquelle la graine a été générée. Mais SecureRandom prend Random Data de votre os (il peut s'agir d'intervalles entre les frappes au clavier, etc. - la plupart des logiciels collectent ces données et les stockent dans des fichiers). /dev/random and /dev/urandom in case of linux/solaris ) et l'utilise comme semence.
Donc, si la petite taille du jeton est acceptable (dans le cas de Random), vous pouvez continuer à utiliser votre code sans aucune modification, puisque vous utilisez SecureRandom pour générer la graine. Mais si vous voulez des jetons de plus grande taille (qui ne peuvent pas être soumis à brute force attacks ) optez pour SecureRandom -
En cas d'aléatoire, il suffit de 2^48 Les tentatives sont nécessaires, avec les processeurs avancés d'aujourd'hui, il est possible de les briser en un temps record. Mais pour un aléa sécurisé 2^128 des tentatives seront nécessaires, ce qui prendra des années et des années pour atteindre le niveau des machines avancées d'aujourd'hui.

Voir ce pour plus de détails.
EDIT
Après avoir lu les liens fournis par @emboss, il est clair que la graine, aussi aléatoire soit-elle, ne doit pas être utilisée avec java.util.Random. Il est très facile de calculer la graine en observant la sortie.

Choisissez SecureRandom - Utilisation PRNG natif (comme indiqué dans le lien ci-dessus) parce qu'il prend des valeurs aléatoires à partir de la base de données des /dev/random pour chaque appel à nextBytes() . De cette façon, un attaquant qui observe la sortie ne pourra rien distinguer, à moins qu'il ne contrôle le contenu de l'interface. /dev/random (ce qui est très peu probable)
Le site sha1 prng L'algorithme ne calcule la graine qu'une seule fois et si votre VM fonctionne pendant des mois en utilisant la même graine, elle peut être craquée par un attaquant qui observe passivement la sortie.

NOTE - Si vous appelez le nextBytes() plus rapidement que votre système d'exploitation est capable d'écrire des octets aléatoires (entropie) dans le disque dur. /dev/random vous risquez d'avoir des problèmes en utilisant PRNG NATIF . Dans ce cas, utilisez une instance SHA1 PRNG de SecureRandom et toutes les quelques minutes (ou un certain intervalle), ensemencez cette instance avec la valeur de nextBytes() d'une instance NATIVE PRNG de SecureRandom. L'exécution de ces deux instances en parallèle vous permettra d'assurer un ensemencement régulier avec de véritables valeurs aléatoires, tout en n'épuisant pas l'entropie obtenue par le système d'exploitation.

Answer 3

Si tu cours deux fois java.util.Random.nextLong() avec la même graine, il produira le même nombre. Pour des raisons de sécurité, il est préférable de s'en tenir à java.security.SecureRandom parce que c'est beaucoup moins prévisible.

Les 2 Classes sont similaires, je pense que vous devez juste changer Random a SecureRandom avec un outil de refactoring et la plupart de votre code existant fonctionnera.

Answer 4

Si modifier votre code existant est une tâche abordable, je vous suggère d'utiliser la classe SecureRandom comme suggéré dans la Javadoc.

Même si vous constatez que l'implémentation de la classe Random utilise la classe SecureRandom en interne, vous ne devez pas considérer que cela va de soi :

1. D'autres implémentations de VM font la même chose.
2. Les implémentations de la classe Random dans les futures versions du JDK utilisent toujours la classe SecureRandom.

Il est donc préférable de suivre la suggestion de la documentation et d'utiliser directement SecureRandom.

Answer 5

L'implémentation de référence actuelle de java.util.Random.nextLong() fait deux appels à la méthode next(int) dont directement expose 32 bits de la graine actuelle :

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

Les 32 bits supérieurs du résultat de nextLong() sont les bits de la graine à ce moment-là. Puisque la largeur de la graine est de 48 bits (d'après la javadoc), il suffit* d'itérer sur les 16 bits restants (cela fait seulement 65.536 essais) pour déterminer la graine qui a produit le second 32 bits.

Une fois que la graine est connue, tous les jetons suivants peuvent être facilement calculés.

En utilisant la sortie de nextLong() directement, partiellement le secret du PNG à un degré tel que le secret entier peut être calculé avec très peu d'effort. Dangereux !

* Il faut faire un effort si les 32 derniers bits sont négatifs, mais on peut le découvrir.