Discussion :

[LE NEINDRE]

Bonjour à tous,

Dans le cadre d'un challenge, qui consiste à trouver un login, j'ai fait un script pour tester plusieurs combinaisons (26^5 combinaisons).
Novice, et constatant que ça prenait un temps fou je me pose les questions suivantes:

1) 26^5 combinaisons, ça fait beaucoup pour un processeur ? (désolé pour ma naïveté )
2) Le fait de faire des threads me permettra t'il de diviser le temps de calcul ?
3) Comment m'y prendre si je veux "partager les calculs" dans mes threads, ie: comment réservé un jeu de combinaison pour le thread1 et un autre jeu de combinaisons pour un thread2
4) Si je fais des threads, puis-je écrire dans le même fichiers mes résultats ?

Voilà le script, sans thread.
nb: j'avais commencé sur 26^6 combinaisons mais après une nuit, j'étais qu'à 0,2% d'avancement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#!c:\perl\bin\perl.exe
 
use String;
@charset;
 
$CHECKSUM="3696619";
my $Tab=new String("                   azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@");
$PASSWORD="souris";
 
while($i!=26)
{
      $charset[$i]=chr($i+97);
      $charset[$i+26]=chr($i+65);
      $i++;
}
$i=0;
#push(@charset,chr(95));
#push(@charset,chr(36));
#push(@charset,chr(38));
#push(@charset,chr(35));
#push(@charset,chr(64));
$total=($#charset+1)*($#charset+1)*($#charset+1)*($#charset+1)*($#charset+1);
#$total=($#charset+1)*($#charset+1);
$compteur=0;
$lastpourcent;
for(my $i=0;$i<=$#charset;$i++)
{
      for(my $j=0;$j<=$#charset;$j++)
      {
            for(my $k=0;$k<=$#charset;$k++)
            {
                    for(my $l=0;$l<=$#charset;$l++)
                    {
                            for(my $m=0;$m<=$#charset;$m++)
                            { 
                                    #for(my $n=0;$n<=$#charset;$n++)
                                    #{
                                            $login=$charset[$i].$charset[$j].$charset[$k].$charset[$l].$charset[$m];
                                            &Check($login);
                                            $pourcent=sprintf("%.2f",($compteur/$total*100));
                                            $compteur++;
                                            if($pourcent ne $lastpourcent)
                                            {
                                                  print "$pourcent %\n";
                                                  $lastpourcent=$pourcent;
                                            }
                                    #}
                            }
                    }
            }
      }
}
 
 
sub Check()
{
      my $login=shift;
      for($no=0;$no<length($CHECKSUM);$no++)
      {
            $nblog=length($login);
            $nbpass=length($PASSWORD);
            my $sum=1;
            if($nblog>$nbpass)
            {
                  $n=$nblog;
            }
            else
            {
                  $n=$nbpass;
            }
 
            for (my $i=0;$i<$n;$i++)
            {
                  my $pos1=$Tab->indexOf(substr($login,$i,1));
                  my $pos2=$Tab->indexOf(substr($PASSWORD,$i,1));
 
                  my $index1=$pos1+10;
                  my $index2=$pos2+10;
                  $sum=$sum+(($index1*$n*($i+1))*($index2*($i+1)*($i+1)));
            }
            if($sum==$CHECKSUM)
            {
                  open(fic,">>newbie_brutforce.txt");
                  print fic "$login : $sum\n";
                  close(fic);
 
            }
      }
 
}

Merci pour vos réponses !!

[2Eurocents]

1) 26^5 combinaisons, ça fait beaucoup pour un processeur ? (désolé pour ma naïveté )

Ca fait 11881376 possibilités.
Si tu es capable d'en traiter 1000 par seconde, il te faudra approximativement 12000 secondes pour trouver, dans le cas le plus défavorable (l'élément à trouver est le dernier de tous ceux testés).
A 1000 tests par secondes, on est donc déjà à 3h30 de recherche, environ.

Maintenant, si l'on ajoute la distinction majuscules/minuscules, des chiffres et quelques caractères non alphanumériques, ce n'est plus 26^5 possibilités pour cinq positions, mais quelque chose comme 65^5, soit 1160290625, presque cent fois plus ...

Et si l'on ne connait pas la longueur et qu'elle peut être inférieure à 5, il faut tester n + n^2 + n^3 + n^4 + n^5 combinaisons (n étant le nombre de caractères distincts valides dans la proposition). Ainsi, on teste toutes les possibilités à 1, puis à 2, puis à 3 ... et à 5 caractères.

Tout ça finit par rendre le brute-force très très très long ...

2) Le fait de faire des threads me permettra t'il de diviser le temps de calcul ?

Répartir le calcul sur plusieurs threads ne permet de gagner du temps de calcul QUE si chaque thread peut être exécuté sur une unité d'exécution distincte : processeur hyperthreadé, au minimum, voire dual-core, ou multi-processeur SMP, ou cluster et ferme de calcul ...

Sur un bête processeur mono-threadé, à la AMD Athlon, ou un P4 non-HT, cela ne raccourcira probablement pas le temps de calcul.

Tout au plus, on peut espérer qu'un des threads démarrant du milieu de l'ensemble de recherche trouve la solution, parce qu'elle est proche de son point de départ, dans un temps relativement bref par rapport au temps nécessaire pour atteindre cette combinaison en mono-thread. Pour quelquechose d'aléatoire, c'est très incertain ...

3) Comment m'y prendre si je veux "partager les calculs" dans mes threads, ie: comment réservé un jeu de combinaison pour le thread1 et un autre jeu de combinaisons pour un thread2

Question de design ... à toi de choisir.

Tu peux avoir un thread principal qui distribue des pools de valeurs à tester à une équipe de threads exécutants qui l'avertissent quand ils ont fini leurs tests et réclament de nouvelles valeurs : c'est une espèce de scheduler.

Tu peux aussi partager, à priori, toutes les valeurs à tester entre un certains nombre de threads (idée simpliste : le thread A teste toutes les valeurs commençant par "a", le B les valeurs commençant par "b", etc.

Et il y a bien d'autres possibilités ...

4) Si je fais des threads, puis-je écrire dans le même fichiers mes résultats ?

Certainement, mais gare à toi dans les accès concurrents !
A toi de blinder les accès simultanés. Un fichier partagé entre thread peut devenir une ressource critique !

[LE NEINDRE]

Bonjour 2eurocents,

merci beaucoup pour tes réponses complètes !!!

Je vais donc opter pour faire des threads répartis sur plusieurs machines (ça va être limité, je suis pas très riche ) qui recevront un pool de solutions à tester (je vais faire comme une des possibités que tu as énoncés à savoir
- thread 1 : machine 1 : solutions commençant de a à f
- thread 2 : machine 2 : solutions commençant de g à k
...
-thread n : machine n : solutions commençant de A à F

etc ...

En effet je me suis trompé, c'est 52^6 solutions que je dois tester.
En revanche, un petit indice non négligeable est parvenu à mes oreilles, c'est un login de 6 caractères ...

52^6 = 19770609664 combinaisons
à 1000 opérations par secondes ça fait 228 jours de calculs si je me trompe pas.
Si les calculs sont répartis sur 3 PC, ça fera 76 jours de calculs !!!!

J'ai un peu peur ...

deux petites questions pour finir:

1) Est-ce que 1000 opérations/secondes pour un processeur simple de 1ghz est réaliste ? Est-ce que c'est plus, beaucoup plus, beaucoup moins ?
2) Y a t'il une différence en terme de rapidité d'éxécution pour un même script écrit en perl ou en C.

Voilà les questions que je me pose.

Quoiqu'il en soit, merci encore pour tes réponses !!!!!

[vodevil]

C'est quoi ton proco ?

[2Eurocents]

En effet je me suis trompé, c'est 52^6 solutions que je dois tester.
En revanche, un petit indice non négligeable est parvenu à mes oreilles, c'est un login de 6 caractères ...

52, c'est donc une valeur purement alphabétique, avec distinction de casse. Il n'y a ni chiffres (+10 -> 62), ni caractères exotiques (+-*/#&|%$£µ ... soit au moins 10 de plus -> 72).

Et c'est pile 6 position, pas une longueur maximale de 6 ...

52^6 = 19770609664 combinaisons
à 1000 opérations par secondes ça fait 228 jours de calculs si je me trompe pas.
Si les calculs sont répartis sur 3 PC, ça fera 76 jours de calculs !!!!

J'ai un peu peur ...

Tu peux avoir peur ... le brute-force n'est pas un modèle d'efficacité ... C'est pour cela que c'est généralement le dernier moyen à mettre en oeuvre, après le social engineering, les attaques au dictionnaire et quelques autres analyses statistiques ... C'est par contre la méthode qui demande le moins de connaissances/compétences dans la mesure où c'est la plus simple à mettre en oeuvre.

Ceci dit, ce calcul de durée est basé sur une approche pessimiste ... c'est le nombre total de combinaison à vérifier et cette durée suppose que la bonne valeur est la dernière à passer ... dans ce cas, si on commence par la fin, ça va plus vite

Une durée raisonnable à prendre en compte est plutôt une durée moyenne, voire médiane : la moitié de cette durée maximale.

La durée maximale est cependant la seule qui soit garantie.

1) Est-ce que 1000 opérations/secondes pour un processeur simple de 1ghz est réaliste ? Est-ce que c'est plus, beaucoup plus, beaucoup moins ?

Ce ne sont pas véritablement d'opérations/secondes que l'on parle, ici. Il s'agit plus de vérifications/secondes.

A 1 GHz, ton processeur effectue déjà 1 000 000 000 (1 milliards) d'opérations élémentaires par seconde.

Par contre, une vérification va faire appel à de nombreuses opérations élémentaires ... Combien ? Je ne peux le savoir ...

Si la vérification consiste à générer/calculer une "clef" et à la comparer à une chaine mémorisée, cela peut tenir en quelques centaines d'opérations élémentaires - mettons 1000 - ce qui peut permettre jusqu'à 1 000 000 de vérifications par seconde. Correct ...

Si la vérification consiste à ouvrir une connexion, ou accéder à un fichier, une socket ou procéder à un calcul complexe, on peut tomber jusqu'à des valeurs telles que 2 ou 3 vérifications par secondes, même sur un processeur à 1 ou 2 GHz. Tu fais quoi ces 3 prochains siècles ?


Par contre, dans ce genre de challenge, il est intéressant de réfléchir soigneusement à la méthode de "codage" retenue. En effet, une faiblesse de conception peut donner des "raccourcis" dans le cassage par brute-force.

J'explique : si dans le codage final, tous les caractères sont indépendants les uns des autres et dépendants des caractères du message initial, par exemple, alors dès qu'un caractère est trouvé, le problème se restreint : plus que 5 positions à trouver, au lieu de 6, donc un intervalle de "brute-forçage" réduit, donc une plus grande chance de trouver un second caractère qui réduira encore notre problème ... effet boule de neige

Par contre, dans certains cas de fonction de hachage par exemple, l'ensemble du "codé" dépend de la totalité du message initial. Avoir 5 caractères de bons sur 6 ne donne rien, puisque la "signature" est totalement différente de celle de la solution ...


Plus on réfléchit à côté, meilleures sont les chances de trouver dans un temps humainement acceptable ... mais plus on s'éloigne de la force brute

Tans ton cas, une estimation du temps maximal de recherche peut être faite en testant sur 10 000 ou 100 000 valeurs pour savoir en combien de temps tu fais les vérifications ... On saura alors combien de vérifications tu fais par seconde, et quelle peut être la durée de la recherche exhaustive.

2) Y a t'il une différence en terme de rapidité d'éxécution pour un même script écrit en perl ou en C.

Tout dépend des opérations qui sont menées dans le script.

On a généralement tendance à estimer le C comme plus performant, mais il m'est déjà arrivé de ne mesurer qu'une différence de 2 à 3% de la vitesse d'exécution entre un programme C et un script Perl équivalent.

L'interprétation, par Perl, est souvent pointée comme l'élément pénalisant, en performance, mais c'est négliger que cette interprétation est plus proche de la "pré-compilation" que de l'interprétation pure et dure.

De plus, en Perl, on dispose nativement de mécanismes de cohérence de nos données qu'il faudra recréer en C pour avoir le même niveau de robustesse du code (sans parler de la gestion des entrées/sorties avec les contrôles idoines ...).

Pour un challenge de ce type, je partirais en Perl, quitte à faire mon script pour avoir une sauvegarde des plages traitées et ensuite le ré-écrire en C pour traiter les plages non traitées si ça semble prendre trop de temps ... En 76 jours, on a le temps de se rendre compte si le prototype est trop lent et de tenter de l'améliorer

Surtout si cela tourne en parallèle sur trois machine, on peut alors modifier le programme de l'une sans impacter le traitement des autres

Bon courage.

[LE NEINDRE]

Ok, très bien, je vais faire le script en perl pour lancer les calculs sur trois machines.
A côté, je vais essayer de réfléchir sur l'algorithme pour savoir si on peut pas limiter le nombre de combinaisons. Il doit y avoir moyen de faire quelque chose car on sait que c'est 6 lettres qui passéesdans une fonction doit nous donner un certains checksum. Donc il doit y avoir moyen de trouver des intervalles à exclure.

Merci grandement pour tes lumières !!
Bonn semaine !