Étant donné que le garbage collection n'est pas déterministe, pourquoi n'est-il pas utilisé pour la génération sécurisée de nombres aléatoires?

13

J'obtiens que / dev / random est une bonne source d'entropie, et c'est ce qui est généralement utilisé - C'est juste que je lis sur GC, au moins en Java, il semble accepté que le démon de récupération de place s'exécute de manière non déterministe . Si c'est vrai, pourquoi ne pas utiliser le timing de la collecte des ordures comme source d'entropie au lieu de la variable / dev / random?

edthethird
la source
7
jetez un oeil à certains des documents pour les fonctions rand () dans la bibliothèque C standard. Ils appellent spécifiquement à ce que, bien qu'ils vous donnent ce qui semble être des nombres aléatoires, ils ne peuvent pas être utilisés pour des raisons de sécurité. Votre garbage collector typique tomberait probablement dans la même catégorie. Si vous allez en utiliser un pour la sécurité, vous devez vous assurer que vous utilisez un ramasse-miettes cryptographiquement sécurisé.
DXM
15
quelque chose de non déterministe peut encore être hautement prévisible
ratchet freak
7
Dans ce cas, «non déterministe» est une mauvaise description. Un garbage collector est un système complètement déterministe et si vous avez une connaissance complète de son état et de l'état du programme qui l'utilise, vous pouvez prédire de manière déterministe les résultats.
Gort the Robot
4
@DXM connaissez-vous une bonne implémentation pour un garbage collector cryptographiquement sécurisé? ;)
AJMansfield
7
"Quiconque considère les méthodes arithmétiques de production de chiffres aléatoires est, bien sûr, dans un état de péché." - John von Neumann
Mark Adler

Réponses:

58

"Non spécifié" et "aléatoire" sont deux concepts entièrement différents.

Le fonctionnement exact d'un garbage collector n'est pas spécifié et dépend du garbage collector (généralement implémenté par une machine virtuelle en quelque sorte, mais pas nécessairement).

Par conséquent, vous n'avez aucune heure spécifiée (c'est-à-dire déterministe) à laquelle les déchets seront collectés.

Cependant, toute implémentation donnée suivra certaines règles et il y a de fortes chances que deux exécutions ultérieures du même programme aient des modèles de récupération de place très similaires.

Par conséquent , la réelle entropie fournie par un collecteur de déchets serait très faible (et savoir qui les pièces que vous pouvez réellement utiliser comme l' entropie sera difficile).

A titre de comparaison: A HashMapen Java ne garantit aucun ordre de récupération pour ses membres (essentiellement parce que le garantir ajouterait des frais généraux qui ne valent pas la peine d'être payés, la plupart du temps). Cependant, pour une implémentation donnée et un ensemble donné d'insertions / suppressions, vous pouvez certainement calculer l'ordre résultant. Ce n'est pas parce qu'il n'y a aucune garantie pour une commande donnée que la commande est aléatoire.

Joachim Sauer
la source
20
Je pense qu'il serait juste de dire que si un ordinateur fait quelque chose qui n'est en fait pas déterministe, cet ordinateur est en panne.
Schilcote
Non déterministe pourrait également signifier qu'il s'appuie sur un état extérieur au programme en question, qui peut lui-même être déterministe, mais sera complètement indépendant du programme lui-même et peut donc être différent à chaque exécution du programme.
asmeurer
@asmeurer Je ne pense pas avoir entendu ces termes dans un tel contexte. En fait, je ne suis même pas sûr de ce que vous voulez dire: chaque programme qui prend une entrée externe (c'est-à-dire la plupart des programmes utiles) "s'appuie sur un état externe", mais cela ne le rend pas non déterministe.
us2012
2
@Schilcote: Certains processeurs modernes ont des RNG non déterministes (vrais) implémentés dans le matériel. Ce sont vraiment non déterministes jusqu'à la physique au niveau quantique.
MSalters
2
@Schilcote Même sans instructions RNG spécialisées (RDRAND et RDSEED d'Intel), un ordinateur n'est pas complètement déterministe. Certains horaires ne sont pas complètement spécifiés et peuvent dépendre de facteurs externes comme la température.
CodesInChaos
8

Premièrement, nous devons veiller à ne pas tomber dans le piège du raisonnement en manipulant de simples mots. Par exemple, nous pourrions demander, puisqu'un NFA est un "automate fini non déterministe", pourquoi ne l'utilisons-nous pas pour obtenir des nombres aléatoires? Dans ce cas, ce serait parce que ce n'est pas ce que signifie «non déterministe» dans un NFA; en fait, lorsque nous simulons un NFA, sur une entrée donnée, le comportement de la simulation est parfaitement déterministe.

"Déterministe" est une phrase chargée. Pour un programmeur informatique ou un informaticien, un comportement non déterministe signifie simplement "déterminer le comportement exact est compliqué à penser" et dépend de trop de facteurs, y compris l'entrée du programme.

Cependant, cela ne signifie pas que ce n'est pas déterministe pour quelqu'un motivé pour attaquer un cryptosystème. Parfois, les facteurs environnementaux et les intrants peuvent être identifiés, et des schémas reproductibles émergent d'un comportement "non déterministe".

Kaz
la source