Recherche de probabilité

[hubeert]

coucou;
tout d'abord j’espère avoir posté dans la bonne section..
Je fabrique un générateur de code "aléatoire" de 4 a 32 caractères qu'on appellera code.
Ce code est généré a l'aide de 92 glyphes comportant minuscules, majuscules, chiffres et autre glyphe spéciaux
Le nombre de combinaisons possibles est donc égal au code ^{nombre de glyphe}.
je décide de tester le temps qu'il me faudrait en force brute pour être sur de trouver la bonne combinaison..
Donc je divise le nombre de combinaisons possibles par le nombre d'essais de code par seconde sur un ordinateur de bureau par exemple et je le converti en minute ou jour ou année voire siècle..
Ce que je cherche c'est a pondérer cette formule simpliste par une probabilité que je ne connais pas et que je ne sais pas calculer.
A savoir que l'ordi qu'il recherche la combinaison de manière linéaire ou aléatoire a certaine chance de tomber sur le bon code sans avoir a explorer toutes les combinaisons..
En clair je cherche la probabilité si j'ai 1 chance sur cent de tomber bonne combinaison au bout de 20 ou 15 essais par exemple sans explorer les cent possibilités.
Est ce que des recherches ont été faites la dessus ou mieux existerait-il une formule assez simple donnant une réponse approchant la réalité.

Merci de vos lumières
-----

[gg0]

Bonjour.

Si j'ai bien compris, tu cherches à évaluer la probabilité de trouver un nombre au hasard parmi n par une répétition de p choix équiprobables (genre : probabilité d'avoir obtenu un 6 en lançant un dé au plus 4 fois).
On a deux cas :
1) On ne tient pas compte des tirages précédents s'ils n'ont pas réussi (donc on peut tirer plusieurs fois un nombre incorrect) :
La probabilité de réussir au premier coup est 1/n, celle de rater est 1-1/n; la probabilité de réussir au deuxième coup (en n'ayant pas encore réussi) est (1-1/n)*1/n=1/n-1/n², celle de n'avoir pas encore réussi est (1-1/n)²; etc. En généralisant, on voit que la probabilité de ne pas avoir encore réussi au k-ième coup est (1-1/n)^k et la probabilité de réussir pour la première fois au k-ième coup est (1-1/n)^k-1*1/n.
Je te laisse finir, puisque la probabilité d'avoir eu le bon tirage en au plus p coups est la somme des probabilités de l'avoir eu au premier, ou au deuxième, ou ... ou au p-ième.
Et ça donne une formule très simple, puisque tu connais la probabilité contraire, celle de ne pas l'avoir encore eu au p-ième coup !!!

[gg0]

Le deuxième cas, maintenant :
2) on élimine les valeurs testées pour ne pas avoir à les reprendre. Le calcul est plus complexe, car la proba fixe 1/n devient variable. Mais l'idée est la même : regarder la probabilité contraire (probabilité de ne pas trouver en p coups). elle vaut (1-1/n)(1-1/(n-1))(1-1/(n-2))...(1-1/(n-p+1)).

Cette deuxième solution donne évidemment une probabilité plus grande, et c'est ce qu'on fait quand on essaie un code "au hasard" à la main. Mais si c'est un logiciel qui le fait, la complexité de l'implémentation rend cette méthode inefficace en génral.

Reste le cas d'une recherche exhaustive : on prend les nombres dans l'ordre (quel qu'il soit). Alors, si on a testé la moitié des nombres, comme il y a une chance sur 2 que le bon soit dans cette première moitié, on a une chance sur 2 de l'avoir trouvé. Généralisation : En p essais (au maximum) on a p/n comme probabilité de réussite.

Cordialement.

[hubeert]

coucou;
merci de la peine prise a me répondre. Mais c'est pas tout a fait ce que je cherche ( en admettant que cela existe )et je me suis surement mal exprimé; je cherche a partir de quel nombre de combinaison en fonction du nombre de combinaisons possibles j'ai une chance optimum d'avoir la bonne combinaison. Un peu comme dans les sondages ou a partir d'un échantillon on arrive a être "presque sûr" que ca représente la réalité.Je cherche le seuil de cette "chance raisonnable" d'avoir la bonne combinaison en fonction
-du nombre de combinaisons possibles. (ou d'autres paramètres que je ne connais pas)
on élimine de facto les cas ou la recherche exhaustive est très courte ( genre code de 4 chiffres)
Cela est proche de la loi des grands nombres qui permet au casino d'etre sur de gagner de l'argent par exemple ou pour les assurances.
Dans mon cas je cherche en fonction de la longueur du code (nombre de glyphe) puissance (le nombre de glyphe prévu pour générer le code)une formule qui assurerait la probabilité maximum d'avoir ce code. ( et qui donc me permettrait d’alléger les calculs )
Je sais que je demande la lune.. et merci a vous

[A voir en vidéo sur Futura]

[gg0]

Ben ...

ça dépend de ce que tu acceptes comme "optimum", de ce que tu appelles être "presque sûr". Si comme les statisticiens tu veux une probabilité de 95%, tu utilises la formule que je t'ai laissé calculer pour définir ton p optimum. Mais j'ai peur que tu sois un peu déçu !!!

Cordialement.

[hubeert]

coucou;
tout d'abord merci de la peine que tu prends a la fois a me comprendre et me répondre.;
Beh si je poste c'est que je ne connais pas la chance optimum ni le presque etre sur..
je sais deux ou trois truc..
ceux qui veulent cracker un code( de manière exhaustive) éliminent certaines possibilités.. ( les quelles et sur quelle probabilités; je ne sais pas et cest le sens de ma question)
ceux qui gèrent les sondages s'appuient sur des notions qui leur permettent d’après un échantillon de penser qu'ils ont de grandes chance d'avoir une réalité proche aussi bien que s'ils avaient sondé la totalité de l'ensemble
je veux juste savoir quel est le nombre (ou le pourcentage) représentatif de combinaison que je dois tester pour etre " presque sur " d'avoir la bonne solution.
Je demande donc quelles probabilités je dois éliminer ( ou accepter) pour réduire mes calculs .. pour qu'ils soient néanmoins a peu près fiables..
Et merci a toi .( et a ceux qui lisent)

[gg0]

Allez,

je te livre le secret : Pour n grand, et une confiance de 95%, il faut environ 3n essais pour avoir cette probabilité de 95% ! Autrement dit une exploration systématique est plus de trois fois plus efficace qu'une exploration au hasard ! C'est normal, dans l'exploration au hasard, on refait par hasard des essais déjà tentés. En fait, à chaque nouvel essai, on a autant de chance de reprendre la combinaison fausse précédente que de trouver !

Donc soit il faut ne pas reprendre les cas déjà rencontrés (délicat !), soit ne pas faire au hasard.

D'ailleurs, les chercheurs d'or le savent : Ils ne cherchent pas au hasard.

Cordialement.

[zoonel]

comme le dit gg0 :

Autrement dit une exploration systématique est plus de trois fois plus efficace qu'une exploration au hasard !

et encore, dans le cas de l'exploration systématique on est sûr de trouver le code alors que dans l'autre on n'a que 95%.

maintenant il y à quand même un problème, c'est que 92^32 ça fait 6.9*10^62 et donc on ne peut pas retenir ce qu'on a déjà testé.
On peut générer les codes et les tester dans l'ordre de génération, c'est (je suppose) ce que tu fais et ça demande beaucoup de puissance de calcul. On pourrait générer les codes dans un autre ordre en suivant une heuristique dans l'optique de favoriser les code les plus probables, par exemple on exclut tout ce qui n'est pas alphanumérique dans un premier temps, mais ça sert à rien si le code choisit l'a été de manière aléatoire avec équiprobabilité des glyphes; l'exemple serait pertinent si c'était un humain qui choisit le code.

Si c'est un humain qui choisit le code (ou mot de passe), on pourrait se dire qu'il a choisit un mot qu'il connaît ou une date ou une légère variation des deux. C'est là qu’entre en jeu l'attaque par dictionnaire. On dispose donc d'un fichier remplis de mots du dictionnaire et de chiffres représentant toutes les dates possibles ainsi que leur variations les plus courantes, par exemple on trouve y trouvera superman et sup3rman. On peut alors tester juste ceux là, mais ce qui se passe plutôt en réalité c’est que l'attaquant dispose d'un fichier contenant les mots de passes codés, il va donc coder les mots du dictionnaire avec le même codage que le fichier (sans doute volé) et comparer les mots ainsi codés avec ceux du fichier. Ça demande aussi pas mal de calcul mais on peut réutiliser le dictionnaire codé pour d'autres fichiers etc...

les rainbow tables sont un peu comme les dictionnaires mais on y trouve (presque) toutes les possibilités, c’est juste une astuce de représentation. Mettre toutes les possibilités dans un fichiers serait beaucoup trop volumineux, on sacrifie donc du temps de calcul pour gagner de la place. Par contre on y perd également certaines possibilités (elles ne se trouvent plus dans la table), au plus on en perd au plus la taille(ou le temps de calcul) de la table est petite et inversement.

Maintenant s'ajoute à cela la technique de salage des mots de passe, qui rend les techniques autre que force brute obsolète. Avec salage, on est obligé de créer un dictionnaire par personne ou une rainbow table par personne, dans le premier cas ça revient au même que de tester chaque mot du dictionnaire et dans le deuxième cas ça revient au même que de tester de manière exhaustive chaque possibilité (= force brute).

À noter que c'est une bonne chose si le codage des mots de passe est gourmand en temps de calcul, ça ralentit considérablement la force brute. Sans compter sur l'allongement de temps nécessaire entre chaque tentative que peut proposer un vérificateur (site web ou autre), et même faire un test de Turing au bout de trop de tentatives ratées (exemple: captcha).


Tout ça pour dire que derrière le crackage de mots de passe se trouve en fait le crackage de mots de passe faciles (mots du dictionnaires, mots de passe petits comme 4 chiffres). L'attaquant va se focaliser sur les vulnérabilités: mots de passe trop faciles, ingénierie sociale, base de données en clair, mauvais codage des mot de passe, liaison non sécurisée, postes de travail vérolé, ...
Si le mot de passe est vraiment aléatoire alors on ne sait pas faire plus efficace qu'une recherche exhaustive et l'ordre ne changera rien.

ps: je me permet de répondre un peu à côté de la question mais la réponse à déjà été donnée par gg0.

[hubeert]

coucou;
Et bien merci donc il y a pas vraiment de combinaison a ne pas tester qu'on pourrait éliminer d'une recherche exhaustive ( tout en préservant un maximum les chances de trouver la bonne).
Je vais essayer d’expliquer mon idée différemment.
Avec un code généré aléatoirement.
En supposant que j'ai généré un code de longueur n caractères choisis aléatoirement parmi 92 glyphes .Est ce que le hacker dans sa recherche exhaustive peut éliminer raisonnablement certaine combinaisons peu probables ?
du genre mon code a un longueur de 10 mon code tiré aux hasard donnerait = aaaaaaaaa?
Donc éliminer des combinaisons selon une formule a trouver..par exemple pour un code de longueur 10
toutes les combinaisons ou 4 glyphe semblables se suivent
Donc faire un modèle fiable qui éliminerait un grand nombres de combinaisons peut probable et ainsi réduire le temps de recherche.
j’espère ne pas vous ennuyer; est ce que ce genre de recherche a été faite et auriez vous des pistes?

Merci encore a vous deux.

[gg0]

Bonjour.

Si la combinaison a été choisie aléatoirement, toutes les combinaisons sont équiprobables, et si n est grand, aussi peu probables les unes que les autres.
Par exemple je choisis un chiffre au hasard. Quels sont les chiffres improbables ?

Ou dans ton exemple, la combinaison 2*-l'ds=p0 est aussi improbable que aaaaaaaaaa.

Ne pas confondre improbable et surprenant (parce que le cerveau humain y voit une structure).

Cordialement.

[toothpick-charlie]

si le code a été engendré à l'aide d'un algorithme qu'on connaît (avec une initialisation inconnue bien sûr) il est possible de trouver un raccourci. Sinon le plus simple est de tester toutes les combinaisons dans l'ordre lexicographique.

[hubeert]

coucou;
deja merci de votre patience.. J' attends bien que d'un point de vu mathématique aaaaaaaaaa a autant de chance de sortir que 8~R\&{g-z=
mais il faudrait que mon tirage aléatoire tombe 10 fois sur le même hasard..
pour répondre a toothpick-charlie l'algorithme c'est un tirage au hasard des glyphes; ce tirage pseudo aléatoire étant lui même basé sur l'algorithme de monte carlo.
Donc d'un point de vue strictement statistique ( j'ai imaginé sans aucune certitude) que javais plus de chance de générer un code de ce type I?680oTEI< que aaaaaaaaaa
Si vous me dite que non; ma question n'a plus de sens.
j'ai purement fonctionner a l'intuition comme au poker j'ai 5 cartes jai autant de chance d'avoir une suite que d'avoir rien et pourtant on a plus souvent rien qu'une suite.
donc ici je me disais ( et je vous embeterai plus ) est til possible d’éliminer certaine combinaison avec une formule fiable et si cette formule est découverte trouver combien de combinaisons elle concerne.
Exemple je découvre que des codes aléatoires de 10 glyphes ont peu de chance d'avoir 4 glyphes identiques.; donc combien de combinaison possible possibles sont affectées?
En gros faire un mix entre combinaison possible d'un coté et le calcul des chances de gagner au loto de lautre.(ou tous les chiffres et nombres ne sont utilisés qu'une fois)
faire un mixage des deux calculs est ce que cela est possible?

faire un mix entre ca combinaisons possibles =longueurCode^{nombre de glyphe}

et nombre de chance au loto = C⁶49
soit calculer le nombre de combinaisons en tenant compte qu'on exclu par exemple les codes comportant plus de 4 glyphes identiques.

Et en tous les cas merci..

[toothpick-charlie]

un générateur de nombres aléatoires, c'est en fait une formule de récurrence qui permet de calculer les termes successifs d'une suite de nombres, parfaitement déterministe. Pour éviter d'avoir toujours la même suite à chaque fois qu'on relance un calcul, on initialise la suite avec un certain nombre de valeurs tirées du contexte (par exemple la valeur de l'horloge du système, ou bien le numéro du processus, etc). Cette initialisation ne peut pas être connue du craqueur potentiel. Mais s'il connaît l'algorithme, il peut relativement facilement prédire la suite de nombres aléatoires. En tout cas toutes les suites possibles de 32 symboles ne sont pas équiprobables (je suppose que l'algorithme de codage consiste à tirer 32 valeurs successives de la suite de nombres pseudo-aléatoires).

[hubeert]

coucou;
merci de ta réponse. en fait c'est pas la position du craqueur qui m’intéresse mais de celui qui génère le code( afin de pouvoir indiquer le temps qu'il faudrait pour craquer le code en force brute en éliminant certaine combinaison soumise a la force brute)(mais pour cela je dois aussi me mettre a sa place..).Je pense aussi que les suites ne sont pas équiprobables.(mais comment le déterminer ?) j'ai une piste..
je sais comment on calcule toutes les possibilités ( les chances aux loto) si tous les éléments(chiffre et nombres) ne sont utilsés qu'une seule fois. je pense et c'est purement intuitif que sur un code de 10 glyphe il y en ai pas plus de 4 qui soit similaires.
voila donc ma règle; j’estime quil y a peu de chance qu'un code de 10 glyphe comporte plus de 4 glyphes similaires..donc jene vais pas les tester( si je suis un craqueur)
donc pour un code de 10 chiffre au moment ou j'arrive a 4 glyphe identiques je ne teste plus..
mais j'arrive pas a mettre le calcul en place
ca donne un peu ca si on considere que 4 glyphe sont les memes; il ne reste plus que
C⁶(92-1) chance si les six autres élément sont différent; mais eux aussi peuvent etre en double ou triple..
Brèf j'y arrive pas.;
mais est ce que mon raisonnement est possible?

[Tryss]

mais est ce que mon raisonnement est possible?

Les chaines à 4 caractères identiques forment une toute petite partie de l'ensemble des chaines de 10 caractères : ça ne changera donc pas l'ordre de grandeur.

Même si tu élimine 99% des chaines, selon la puissance dont dispose la personne qui tente le brute-force, ça ne change pas forcément grand chose (si l'attaquant à un réseau d'un millier de botnet à disposition par exemple)

[zoonel]

coucou;
merci de ta réponse. en fait c'est pas la position du craqueur qui m’intéresse mais de celui qui génère le code( afin de pouvoir indiquer le temps qu'il faudrait pour craquer le code en force brute en éliminant certaine combinaison soumise a la force brute)(mais pour cela je dois aussi me mettre a sa place..).Je pense aussi que les suites ne sont pas équiprobables.(mais comment le déterminer ?) j'ai une piste..
je sais comment on calcule toutes les possibilités ( les chances aux loto) si tous les éléments(chiffre et nombres) ne sont utilsés qu'une seule fois. je pense et c'est purement intuitif que sur un code de 10 glyphe il y en ai pas plus de 4 qui soit similaires.
voila donc ma règle; j’estime quil y a peu de chance qu'un code de 10 glyphe comporte plus de 4 glyphes similaires..donc jene vais pas les tester( si je suis un craqueur)
donc pour un code de 10 chiffre au moment ou j'arrive a 4 glyphe identiques je ne teste plus..
mais j'arrive pas a mettre le calcul en place
ca donne un peu ca si on considere que 4 glyphe sont les memes; il ne reste plus que
C⁶(92-1) chance si les six autres élément sont différent; mais eux aussi peuvent etre en double ou triple..
Brèf j'y arrive pas.;
mais est ce que mon raisonnement est possible?

On va se placer dans un contexte théorique; on lance un dé à 6 faces ou autrement dit on génère un nombre aléatoire entre 1 et 6 où chaque possibilité à la même probabilité (équiprobable).
Il y a une plus grande probabilité de tomber sur un nombre plus grand que 1 que de tomber sur 1, 5/6 contre 1/6. Mais éliminer le 1 est totalement arbitraire, chaque valeur de 2 à 6 a autant de chance de tomber que le 1.
C'est exactement la mềme chose dans ton cas, éliminer les codes avec plus de 4 glyphes similaires ou éliminer au hasard le même nombre de code c'est pareil. Maintenant dénombrer les codes avec plus de 4 glyphes est peut être pas évident, mais c'est un choix arbitraire qui est aussi valable que le hasard.

Parler du générateur aléatoire revient à se demander si le dé n'est pas pipé. En gros certains générateurs pseudo aléatoire sont pipés et privilégient certains nombres plus que d'autres, d'autres permettent de trouver la suite connaissant un certain nombre de nombres sorti précédemment, ou encore le fait d'utiliser un seed petit permet de tous les tester et de retrouver la suite (un seed petit restreint également l'espace des possibilités).
Mais bon, si on a un bon seed (grand et assez aléatoire) et un générateur cryptographiques sûr tu peux te considérer dans le cas théorique.