Un nombre véritablement aléatoire pourrait-il être généré en utilisant des pings pour des adresses IP sélectionnées de manière pseudo-aléatoire?

La question posée a été soulevée lors d’une conférence de deuxième année en sciences comp lors de la discussion sur l’impossibilité de générer des nombres dans un dispositif de calcul déterministe.

C’était la seule suggestion qui ne dépendait pas d’un matériel de classe autre que les produits de base.

Par la suite, personne ne mettrait sa réputation en jeu pour argumenter définitivement pour ou contre.

Tout le monde veut prendre position pour ou contre. Si oui, que diriez-vous d’une mention sur une éventuelle mise en œuvre?

Je mettrai mon représentant en ligne (au moins, 2 points par défrichement).

Non.

Une machine malveillante sur votre réseau pourrait utiliser l’usurpation ARP (ou un certain nombre d’autres techniques) pour intercepter vos pings et y répondre après certaines périodes. Ils ne sauraient alors non seulement savoir quels sont vos nombres aléatoires, ils les contrôleraient.

Bien sûr, la question de savoir si votre réseau local est déterministe rest posée, de sorte qu’il ne sera peut-être pas aussi simple que tout cela dans la pratique. Mais comme vous ne tirez aucun avantage du ping sur des adresses IP aléatoires sur Internet, vous pourriez tout aussi bien tirer une entropie du trafic Ethernet.

Le dessin d’entropie à partir de périphériques connectés à votre machine est un principe bien étudié, et les avantages et inconvénients de divers types de périphériques et de méthodes de mesure peuvent être volés, par exemple, dans l’implémentation de / dev / random.

[ Edit : comme principe général, lorsque vous travaillez dans les principes fondamentaux de la sécurité (et que les seuls besoins pratiques pour des quantités significatives de données vraiment aléatoires sont liées à la sécurité), vous devez présumer qu’un attaquant doté de pouvoir briser votre système.

Pour une sécurité pratique, vous pouvez supposer que personne ne veut que votre clé PGP soit défectueuse, et opter pour un compromis entre la sécurité et le coût. Mais lorsque vous inventez des algorithmes et des techniques, vous devez leur donner les meilleures garanties de sécurité auxquelles ils pourraient être confrontés. Étant donné que je peux croire que quelqu’un, quelque part, voudrait que la clé privée de quelqu’un d’autre le fasse assez bien pour construire ce petit kit pour faire échouer votre proposition, je ne peux pas l’accepter comme une avancée par rapport aux meilleures pratiques actuelles. AFAIK / dev / random suit assez près des meilleures pratiques pour générer des données vraiment aléatoires sur un PC domestique bon marché]

[ Une autre édition : dans les commentaires, il a suggéré (1) qu’il est vrai pour tout RGTR que le processus physique pourrait être influencé, et (2) que les problèmes de sécurité ne s’appliquent pas ici de toute façon.

La réponse à (1) est qu’il est possible sur n’importe quel matériel réaliste de faire beaucoup mieux que les temps de réponse de ping, et de collecter plus d’entropie plus rapidement, que cette proposition est une non-solution. En termes de CS, vous ne pouvez évidemment pas générer de nombres aléatoires sur une machine déterministe, ce qui a provoqué la question. Mais en termes de CS, une machine avec n’importe quel stream d’entrée externe n’est pas déterministe par définition, donc si nous parlons de ping, nous ne parlons pas de machines déterministes. Il est donc logique d’examiner les entrées réelles des machines réelles et de les considérer comme des sources d’aléa. Quelle que soit votre machine, les temps de ping bruts ne figurent pas au haut de la liste des sources disponibles, de sorte qu’ils peuvent être exclus avant de vous soucier des meilleurs. En supposant qu’un réseau ne soit pas corrompu, c’est une hypothèse beaucoup plus importante (et inutile) que de supposer que votre propre matériel n’est pas altéré.

La réponse à (2) est philosophique. Si cela ne vous dérange pas que vos nombres aléatoires aient la propriété de pouvoir être choisis au hasard plutôt que par hasard, alors cette proposition est correcte. Mais ce n’est pas ce que je comprends par le terme «aléatoire». Ce n’est pas parce que quelque chose est incohérent que c’est nécessairement aléatoire.

Enfin, pour traiter les détails d’implémentation de la proposition comme demandé: en supposant que vous acceptiez les temps ping comme aléatoires, vous ne pouvez toujours pas utiliser les temps de ping non traités comme sortie RNG. Vous ne connaissez pas leur dissortingbution de probabilités, et elles ne sont certainement pas uniformément dissortingbuées (ce qui est normalement ce que les gens veulent d’un RNG).

Vous devez donc décider du nombre de bits d’entropie par ping sur lesquels vous souhaitez vous appuyer. L’entropie est une propriété mathématique définie avec précision d’une variable aléatoire qui peut raisonnablement être considérée comme une mesure de son caractère «aléatoire». En pratique, vous trouvez une limite inférieure avec laquelle vous êtes satisfait. Ensuite, hachez ensemble un certain nombre d’entrées et convertissez-le en un nombre de bits de sortie inférieur ou égal au nombre total d’entropie des entrées. «Total» ne signifie pas nécessairement sum: si les entrées sont statistiquement indépendantes, alors c’est la sum, mais il est peu probable que ce soit le cas pour les pings, une partie de votre estimation d’entropie sera donc responsable de la corrélation. La grande soeur sophistiquée de cette opération de hachage s’appelle un «collecteur d’entropie», et tous les bons systèmes d’exploitation en ont un.

Si vous utilisez les données pour créer un PRNG et que le PRNG peut utiliser des données de départ arbitrairement grandes, alors vous n’avez pas à hacher car cela le fera pour vous. Vous devez toujours estimer l’entropie si vous voulez savoir à quel point votre valeur de graine était «aléatoire» – vous pouvez utiliser le meilleur PRNG au monde, mais son entropie est toujours limitée par l’entropie de la graine.]

Les nombres aléatoires sont trop importants pour être laissés au hasard.

Ou influence / manipulation externe.

Réponse courte

Utiliser les données de synchronisation de ping par lui-même ne serait pas vraiment aléatoire, mais il peut être utilisé comme source d’ entropie qui peut ensuite être utilisée pour générer des données vraiment aléatoires.

Version plus longue

A quel point les temps de ping sont-ils aléatoires?

En soi, les données temporelles provenant des opérations réseau (telles que ping) ne seraient pas dissortingbuées de manière uniforme. (Et l’idée de sélectionner des hôtes aléatoires n’est pas pratique – beaucoup ne répondront pas du tout, et les différences entre les hôtes peuvent être énormes, avec des écarts entre les plages de temps de réponse – pensez aux connexions par satellite).

Cependant, même si le calendrier ne sera pas bien dissortingbué, les données présenteront un certain degré d’aléa. Autrement dit, un niveau d’ entropie de l’ information est présent. C’est une bonne idée d’alimenter les données de synchronisation dans un générateur de nombres aléatoires. Alors, quel niveau d’entropie est présent?

Pour les données de synchronisation réseau, par exemple autour de 50 ms, mesurées à 0,1 ms près, avec un étalement de valeurs de 2 ms, vous avez environ 20 valeurs. En arrondissant à la puissance la plus proche de 2 (16 = 2 ^ 4), vous avez 4 bits d’entropie par valeur de synchronisation. Si c’est pour n’importe quel type d’application sécurisée (telle que la génération de clés cryptographiques), alors je serais prudent et dirais que c’était seulement 2 ou 3 bits d’entropie par lecture. (Notez que j’ai fait une estimation très approximative ici et ignoré la possibilité d’une attaque).

Comment générer des données vraiment aléatoires

Pour les vrais nombres aléatoires, vous devez envoyer les données dans quelque chose conçu selon / dev / random qui collectera l’entropie, en la dissortingbuant dans un magasin de données (en utilisant une sorte de fonction de hachage , généralement sécurisée ). En même temps, l’estimation de l’entropie est augmentée. Donc, pour une clé AES à 128 bits, 64 timings de ping seraient nécessaires avant que le pool d’entropie ait assez d’entropie.

Pour être plus robuste, vous pouvez ensuite append des données de synchronisation à partir de l’utilisation du clavier et de la souris, des temps de réponse du disque dur, des données de capteur de la carte mère (par exemple la température), etc. de l’entropie. Et en effet, c’est ce qui se fait avec les systèmes modernes. La liste complète des sources d’entropie MS Windows est répertoriée dans le deuxième commentaire de cet article .

Plus de lecture

Pour discuter des attaques (de sécurité informatique) sur des générateurs de nombres aléatoires et de la conception d’un générateur de nombres aléatoires sécurisé sur le plan cryptographique, vous pourriez faire pire que de lire le papier parachute de Bruce Schneier et John Kelsey. (Yarrow est utilisé par les systèmes BSD et Mac OS X).

Non.

Détwigz le câble réseau (ou /etc/init.d/networking stop ) et l’entropie tombe à zéro.

Effectuez une attaque par déni de service sur la machine en cours de ping et vous obtenez également des résultats prévisibles (la valeur ping-timeout)

Je suppose que tu pourrais. Quelques points à surveiller:

  • Même si le ping des adresses IP aléatoires, les premiers sauts (de vous au premier routeur L3 réel sur le réseau ISP) seront les mêmes pour chaque paquet. Cela met une limite inférieure sur le temps d’aller-retour, même si vous faites un ping sur quelque chose dans un centre de données dans ce premier sharepoint présence. Donc, il faut faire attention à la normalisation du timing, il y a une limite inférieure pour l’aller-retour.
  • Vous devez également faire attention à la mise en forme du trafic dans le réseau. Une implémentation typique d’un seau dans un routeur libère N octets toutes les M microsecondes, ce qui perturbe efficacement votre synchronisation dans des intervalles de temps spécifiques plutôt que dans une plage de temps continue. Vous devrez donc peut-être ignorer les bits de poids faible de votre horodatage.

Cependant, je ne suis pas d’accord avec la prémisse selon laquelle il n’y a pas de bonnes sources d’entropie dans le matériel de base. Au cours des dernières années, de nombreux chipsets x86 ont inclus des générateurs de nombres aléatoires. Ceux que je connais utilisent des ADC relativement sensibles pour mesurer la température à deux endroits différents de la masortingce et les soustraire. Les bits de poids faible de cette différence de température peuvent être montrés (via une parsing du chi carré) comme fortement aléatoires. Lorsque vous augmentez la charge de traitement sur le système, la température globale augmente, mais le différentiel entre deux zones de la masortingce rest non corrélé et imprévisible.

La meilleure source d’aléa sur le matériel de base que j’ai vue était un gars qui retirait un filtre ou quelque chose de sa webcam, mettait de la colle opaque sur la lentille et était capable de détecter facilement les pixels blancs des rayons cosmiques frappant le CCD. Celles-ci sont aussi proches du hasard que possible et sont protégées de la surveillance externe par des effets quantiques.

Une partie d’un bon générateur de nombres aléatoires correspond à des probabilités égales de tous les nombres comme n -> infini.

Donc, si vous prévoyez de générer des octets aléatoires, puis avec suffisamment de données d’un bon rng, chaque octet devrait avoir la même probabilité d’être renvoyé. De plus, il ne devrait y avoir aucun modèle ou prédictibilité (pointes de probabilité pendant certaines périodes) de certains nombres renvoyés.

Je ne suis pas sûr d’utiliser ping ce que vous mesureriez pour obtenir la variable aléatoire, est-ce le temps de réponse? Si c’est le cas, vous pouvez être certain que certains temps de réponse, ou plages de temps de réponse, seront plus fréquents que d’autres et créeront donc un générateur de nombres aléatoires potentiellement non sécurisé.

Si vous voulez du matériel de base, votre carte son devrait le faire. Augmentez simplement le volume sur une entrée analogique et vous obtenez une source de bruit blanc bon marché. Aléatoire bon marché sans besoin d’un réseau.

L’approche consistant à mesurer quelque chose pour générer une graine aléatoire semble être assez bonne. Le livre de O’Reilly Practical Unix et Internet Security donne quelques méthodes supplémentaires similaires pour déterminer une graine aléatoire, par exemple demander à l’utilisateur de taper quelques touches, puis mesurer le temps écoulé entre les frappes. (Le livre note que cette technique est utilisée par PGP comme source de son caractère aléatoire.)

Je me demande si la température actuelle du processeur d’un système (mesurée à plusieurs décimales) pourrait être un composant viable d’une graine aléatoire. Cette approche aurait l’avantage de ne pas avoir besoin d’accéder au réseau (de sorte que le générateur aléatoire ne devienne pas indisponible lorsque la connexion réseau tombe en panne).

Cependant, il est probable que le capteur interne d’un processeur ne puisse mesurer avec précision la température du processeur à des décimales suffisantes pour rendre la valeur réellement viable en tant que valeur de départ aléatoire. au moins, pas avec du “matériel de classe marchandise”, comme mentionné dans la question!

Ce n’est pas aussi bon que d’utiliser le bruit atmosphérique, mais il rest vraiment aléatoire car cela dépend des caractéristiques du réseau qui est connu pour son comportement aléatoire non reproductible.

Voir Random.org pour plus d’informations sur le caractère aléatoire.

Voici une tentative d’implémentation:

 @ips : list = getIpAddresses(); @rnd = PseudorandomNumberGenerator(0 to (ips.count - 1)); @getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime } 

J’utiliserais plus tôt quelque chose comme ISAAC comme un PRNG plus fort avant de faire confiance aux pings aller-retour comme entropie. Comme d’autres l’ont dit, il serait trop facile pour une personne non seulement de deviner vos chiffres, mais aussi de les contrôler à des degrés divers.

D’autres grandes sources d’entropie existent, que d’autres ont mentionnées. Ce qui n’a pas été mentionné (ce qui pourrait ne pas être pratique) consiste à échantillonner le bruit de l’appareil audio embarqué. Ce qui sera généralement un peu bruyant même si aucun microphone n’est connecté.

Je suis allé 9 tours en essayant de trouver un PRNG fort (et rapide) pour un mécanisme RPC client / serveur que j’écrivais. Les deux parties avaient une clé identique composée de 1024 lignes de 32 caractères. Le client enverrait AUTH xx, le serveur retournerait AUTH yy .. et les deux parties savaient quelles étaient les deux lignes de la clé à utiliser pour produire le secret blowfish (+ salt). Le serveur envoyait alors un résumé SHA-256 de la clé entière (chiffrée), le client savait qu’il parlait à quelque chose qui avait la clé correcte .. la session continuait. Ouais, protection très faible pour l’homme au centre, mais une clé publique était hors de question pour savoir comment l’appareil était utilisé.

Donc, vous aviez un serveur non bloquant qui devait gérer jusqu’à 256 connexions. Non seulement le PRNG devait être puissant, il devait être rapide. Ce n’était pas si difficile d’utiliser des méthodes plus lentes pour rassembler l’entropie dans le client, mais cela n’était pas possible sur le serveur.

Donc, je dois vous demander votre idée. Comment serait-ce pratique?

Aucun calcul mathématique ne peut produire un résultat aléatoire, mais dans le «monde réel», les ordinateurs ne font pas que créer des nombres. Avec un peu de créativité, il devrait être possible de produire des résultats aléatoires. reproduire ou prédire des résultats exacts.

L’une des idées les plus faciles à mettre en œuvre que j’ai vues et qui fonctionne universellement sur tous les systèmes consiste à utiliser des lignes statiques à partir du port ligne / carte son de l’ordinateur.

D’autres idées incluent le bruit thermique et la synchronisation de bas niveau des lignes de cache. De nombreux PC modernes dotés de puces TPM disposent déjà de générateurs de nombres aléatoires matériels de qualité de cryptage.

Ma réaction la plus rapide au ping (surtout si vous utilisez ICMP) est que votre sortingche est trop flagrante. À ce stade, vous pourriez aussi bien sortir un compteur giger et utiliser le rayonnement de fond comme source aléatoire.

Oui, c’est possible, mais … le diable est dans les détails.

Si vous voulez générer un nombre entier de 32 bits, vous devez collecter> 32 bits d’entropie (et utiliser une fonction de mixage suffisante pour que cette entropie soit diffusée, mais cela est possible et réalisable). La grande question qui est:

combien d’entropie les temps de ping ont-ils?

La réponse à cette question dépend de toutes sortes d’hypothèses concernant le réseau et votre modèle d’attaque, et les réponses sont différentes selon les circonstances.

Si les attaquants sont capables de contrôler totalement les temps de ping, vous obtenez 0 bit d’entropie par ping, et vous ne pouvez jamais totaliser 32 bits d’entropie, peu importe combien vous mélangez. S’ils ont un contrôle moins que parfait sur les temps de ping, vous obtiendrez une certaine entropie et (si vous ne surestimez pas la quantité d’entropie que vous collectez), vous obtiendrez des nombres 32 bits parfaitement aléatoires.

Vous pouvez utiliser la méthode XKCD:

Générateur de nombres aléatoires

YouTube affiche un périphérique en action: http://www.youtube.com/watch?v=7n8LNxGbZbs

Au hasard, si personne ne peut prédire le prochain état.

Bien que je ne puisse pas trouver de site pour ou contre, cette mise en œuvre a ses problèmes.

D’où proviennent ces adresses IP, si elles sont sélectionnées de manière aléatoire, que se passe-t-il lorsqu’elles ne répondent pas ou sont en retard dans la réponse, cela signifie-t-il que le nombre aléatoire sera plus lent à apparaître.

De plus, même si vous faites un graphique visuel de 100 000 résultats et que vous calculez qu’il n’ya pas ou peu de corrélations entre les nombres, cela ne signifie pas qu’il est vraiment aléatoire. Comme expliqué par dilbert 🙂

Cela ne me semble pas une bonne source de hasard.

Quelle mésortingque utiliseriez-vous – la plus évidente est le temps de réponse, mais la gamme de valeurs auxquelles vous pouvez raisonnablement vous attendre est petite: quelques dizaines de millisecondes à quelques milliers. Les temps de réponse eux-mêmes suivront une courbe en cloche et ne seront pas dissortingbués aléatoirement sur un intervalle quelconque (comment choisir l’intervalle?), Vous devrez donc sélectionner quelques bits «aléatoires» parmi les nombres.

Le LSB peut vous donner un stream binary aléatoire, mais vous devriez considérer les problèmes de granularité d’horloge – peut-être en raison du fonctionnement des interruptions, vous obtiendrez toujours des multiples de 2 ms sur certains systèmes.

Il y a probablement de meilleures façons «intéressantes» d’obtenir des bits aléatoires – peut-être google pour un mot aléatoire, prenez la première page et choisissez le Nième bit de la page.

Eh, je trouve que ce genre de question mène à des discussions sur la signification de «vraiment aléatoire» assez rapidement.

Je pense que la mesure des pings produirait des bits aléatoires de qualité décente, mais à un taux insuffisant pour être très utile (à moins que vous ne soyez prêt à effectuer des DDOS sérieux).

Et je ne vois pas que ce serait plus aléatoire que de mesurer les propriétés analogiques / mécaniques de l’ordinateur, ou le comportement du sac à viande qui l’exploite.

(edit) Sur une note pratique, cette approche vous ouvre la possibilité que quelqu’un de votre réseau manipule votre générateur de nombres «aléatoires».

Il me semble que le vrai hasard est ineffable – il n’y a aucun moyen de savoir si une séquence est aléatoire, car par définition, elle peut contenir quelque chose d’improbable. Garantir un modèle de dissortingbution particulier réduit le caractère aléatoire. Le mot “modèle” est un peu un cadeau.

  I MADE UA RANDOM NUMBER BUT I EATED IT 

Le hasard n’est pas une propriété binary – c’est une valeur comprise entre 0 et 1 qui décrit la difficulté de prédire la valeur suivante dans un stream.

Demander “comment mes valeurs peuvent-elles être aléatoires si je les base sur des pings?” est en train de demander “comment les pings sont-ils aléatoires?”. Vous pouvez estimer cela en rassemblant un dataset suffisamment important (1 million de pings par exemple) et en cartographiant leur courbe de dissortingbution et leur comportement dans le temps. Si la dissortingbution est plate et que le comportement est difficile à prévoir, les données semblent plus aléatoires. La dissortingbution plus cahoteuse ou le comportement prévisible suggèrent un caractère aléatoire plus faible.

Vous devriez également considérer la résolution de l’échantillon. Je peux imaginer que les résultats ont été arrondis d’une manière quelconque à une milliseconde, donc avec les pings, vous pouvez avoir des valeurs entières comsockets entre 0 et 500. Ce n’est pas beaucoup de résolution.

Sur le plan pratique, je déconseillerais cela, car les pings peuvent être prédits et manipulés, réduisant encore leur caractère aléatoire.

En règle générale, je suggère de ne pas “rouler vos propres” générateurs de caractère aléatoire, les méthodes de chiffrement et les algorithmes de hachage. Aussi amusant que cela puisse paraître, c’est surtout beaucoup de mathématiques très intimidantes.

En ce qui concerne la façon de construire un très bon générateur d’entropie – je pense que cela devra probablement être une boîte scellée qui produira une sorte de résultat d’interactions au niveau atomique ou sous-atomique. Je veux dire, si vous utilisez une source d’entropie que l’ennemi peut facilement lire, il lui suffit de trouver votre algorithme. Toute forme de connexion est un vecteur d’attaque possible, vous devez donc placer la source d’entropie au plus près du service qui la consum le plus possible.

J’ai un code qui crée des nombres aléatoires avec traceroute. J’ai aussi un programme qui le fait en utilisant ping. Je l’ai fait il y a plus d’un an pour un projet de classe. Tout ce qu’il fait est de lancer traceroute on et address et il prend le chiffre minimum des ms. Cela fonctionne assez bien pour obtenir des nombres aléatoires mais je ne sais vraiment pas à quel point il est proche du vrai hasard.

Voici une liste de 8 numéros que j’ai eu quand je l’ai couru.

455298558263758292242406192

506117668905625112192115962

805206848215780261837105742

095116658289968138760389050

465024754117025737211084163

995116659108459780006127281

814216734206691405380713492

124216749135482109975241865

 #include  #include  #include  #include  #include  #include  #include  using namespace std; int main() { system("traceroute -w 5 www.google.com >> trace.txt"); ssortingng fname = "trace.txt"; ifstream in; ssortingng temp; vector tracer; vector numbers; in.open(fname.c_str()); while(in>>temp) tracer.push_back(temp); system("rm trace.txt"); unsigned index = 0; ssortingng a = "ms"; while(index 

Très simplement, les réseaux obéissant à des règles prescrites, les résultats ne sont pas aléatoires.

L’idée de la webcam semble (légèrement) raisonnable. Les utilisateurs de Linux recommandent souvent d’utiliser simplement le bruit aléatoire d’une carte son sans micro.

voici ma suggestion:

1- Choisissez un coup de poing de sites Web aussi éloignés que possible de votre emplacement. Par exemple, si vous êtes aux États-Unis, essayez certains sites Web qui ont leurs adresses IP de serveur en malasia, en chine, en russie, en inde ..etc. les serveurs à fort trafic sont meilleurs.

2- pendant les périodes de trafic Internet élevé dans votre pays (dans mon pays, il est environ 19h-23h), envoyez un ping à ces sites plusieurs fois, prenez chaque résultat de ping (utilisez uniquement la valeur entière) et calculez le module 2 (c.-à-d. à partir de chaque opération ping, vous obtenez un bit: 0 ou 1).

3- répéter le processus pendant plusieurs jours, en enregistrant les résultats.

4- collecter tous les bits que vous avez obtenus à partir de tous vos pings (vous obtiendrez probablement des centaines de milliers de bits) et choisir parmi eux vos bits. (peut-être que vous voulez choisir vos bits en utilisant des données de la même méthode mentionnée ci-dessus :))

ATTENTION: dans votre code, vous devriez vérifier le timeout ..etc