Discussion :

[sloshy]

Hello,
Voilà j'aimerai bien avoir une idée de comment faire un algorithme de bruteforce.

Mettons que je veux tester toutes les possibilités d'un mots de passe qui fait X caractère et chaque caractère peut prendre N valeur.
Bien sur avec les boucles imbriquée ca va bien, mais je ne connais pas à l'avance la valeur de X.

[pacificator]

Salut,

tu peux regarder le module itertools, certaines fonctions ne sont disponibles qu'à partir de la version 2.6.

[sloshy]

Merci c'est exactement ce que je cherchais, sauf que je travaille toujours sous python 2.5.4

C'est exactement ca que je recherche:

Code :

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

product('ABCD', repeat=2)

Soit le code fourni:

Code :

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

1
2
3
4
5
6
7
8
9
def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

mais non seulement je n'arrive pas a la comprendre, mais je n'arrive pas non plus à l'utiliser ...

EDIT://
Bon ca commence à plus ou moins s'utiliser et à se comprendre mais de là à arriver à modifier la fonction à ma sauce :/
L'idée est de pouvoir appeler une fonction avec en paramètre chaque entrée crée par la fonction (au lieu de les mettre dans un tableau).

EDIT://
Ok, donc si j'ai bien compris (ce qui est pas du tout sur), ca crée un tableau qui est modifié au fur et à mesure afin de prévoir toutes les possibilités, ce qui est pas vraiment bon pour moi, si le mdp fait 6 caractère et qu'il y a des minuscule (26 possibilités) + des majuscules (26 possibilités) + des chiffres (10 possibilités) + des caractères spéciaux (une 10aine de possibilité) ca va me faire 72**6 entrées, soit 139314069504L entrée, la ram va morfler non? (EDIT:// effectivement c'est beaucoup trop lent)

[sopsag]

En effet, cette fonction n'est codée pour une utilisation à la combinatoire aussi explosive !
(c'est un peu dommage...)
Je dois avoir un truc qui fait ça dans mes archives...
Je te retrouve ça et je reviens...

[sopsag]

Je ne retrouve pas mon petit bout de code qui va bien
Mais voici, écrite sur le pouce, une version dédiée à ton problème :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
def all_6_combi ( alphabet ):
    for c0 in alphabet :
        for c1 in alphabet :
            for c2 in alphabet :
                for c3 in alphabet :
                    for c4 in alphabet :
                        for c5 in alphabet :
                            yield ( c0,c1,c2,c3,c4,c5 )
 
for i in all_6_combi('abc'):
    print i

Ouiiii je sais, c'est moche ! Le 6 est en dur au lieu d'être un paramètre...
Si je retombe sur ma version super élégante je te la poste.

[sloshy]

Hello,
Merci de ta réponses mais heuu effectivement, je me vois mal faire une fonction par argument
Si tu retrouves ta fonction ce serait sympa (et si tu avais le temps d'en commenté un peu l'algo aussi c'est la que j'ai beaucoup de mal).

[tyrtamos]

Bonjour,

Sincèrement, je suis ravi - pour nous tous - que ce soit aussi difficile de faire ça .

Sinon, même si je suis souvent impressionné par la vitesse de Python, je crois qu'un tel projet mériterait d'être exécuté directement en code machine (C, C++, ...) sans l'écran d'une machine virtuelle, voire même en assembleur.

Si tu continues avec Python, essaye d'accélérer avec psyco.

Tyrtamos

[sopsag]

Bon allez, comme je ne retrouvais pas ma fonction, je l'ai recodée rien que pour toi :

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
def all_words ( alphabet,nb ):
    max = len( alphabet )-1 # max = dernier indice autorisé
    res = [0]*nb # tableau d'indices [0,0,0], [1,0,0], [2,0,0], ... [max,0,0], [0,1,0] ... [max,max,max]
    yield ''.join( [alphabet[i] for i in res] )
    while 1:
        for i in range( nb ):
            res[i] += 1 # incrémente le + à gauche
            if res[i] <= max: # si on n'a pas dépassé max,
                break         # on peut sortir le resultat
            if i == nb-1 : # si on vient de faire un tour complet (le + à droite va repasser à 0)
                return     # c'est terminé, on a généré toutes les combis
            res[i] = 0 # on a dépassé max => on repasse à 0 et on va incrémenter le + à gauche suivant
        yield ''.join( [alphabet[i] for i in res] )
 
for i in all_words( 'abcd',3 ):
    print i

J'espère que les commentaires sont clairs...
Sinon, je te conseille d'ajouter des traces, tu verras tout de suite comment ça marche.

[sloshy]

Hello,
merci bien d'avoir pris le temps de recoder ca, c'est très claire, il me reste juste à comprendre le yeld (qui est spécifique a python) et ce sera good

[sopsag]

Je suis assez d'accord avec tyrtamos :
si tu veux vraiment casser un code avec ça, ça va être long.
En revanche, le choix de python ou du pur assembleur optimisé avec amour pendant des semaines ne changera pas grand chose.
Car ce qui va être pénalisant, c'est le temps de soumission de ton mot de passe.
En effet, je suppose que pour chaque mot de passe généré, tu vas devoir le soumettre au machin que tu veux casser.
Si par exemple tu veux casser un zip protégé, le temps que tu vas passer à essayer le mot de passe va être beaucoup + long que le temps de le générer avec cette fonction.
Et là, si tu as effectivement 139314069504 possibilités, ça va faire mal...
Avec 10000 tentatives pas seconde, ça va te prendre 5 mois...

[sopsag]

le yield :
je pourrais te dire que ça renvoie un générateur, mais ça risque de ne pas éclairer ta lanterne tout de suite...
Pour faire bref, tu peux voir le yield comme une espèce de return qui suspend la fonction dans son contexte : l'appel suivant reprendra juste après le yield.
Mais je te conseil très vite de lire la foultitude de littérature qu'on trouve sur le sujet !

[N.tox]

Un thread traitant du sujet:
http://www.developpez.net/forums/d65...iable-boucles/

une première solution tiré de ce thread:
http://www.developpez.net/forums/d65...s/#post3875491

Un autre, avec que des generators (mais carrément pas aussi efficace):
http://www.developpez.net/forums/d65...s/#post4097382

[sloshy]

merci beaucoup des explications.
Alors pour le bruteforce je pense que le temps processeur n'est pas important dans ce cas (car c'est le temps réseaux qui compte ici, et le goulot d'étranglement sera toujours le réseaux (en rapport au cpu)).

Ensuite même si on se base sur un cassage de hash par exemple tout dépand de la puissance CPU, un tesla peut test 1157625 hashs par seconde (pour 8000 euro à l'achat), a ce niveau je peux comprendre qu'un code C optimisé soit plus important qu'un code python mais à mon niveau (juste un test pour le travail) ca n'a aucune incidence )

et puis là on a pas encore pris en compte le multithread (mon post suivant d'ailleur).

[eyquem]

to yield, en anglais, c’est produire, donner, céder, abandonner

La composante “céder“ de cette signification explique à mon sens son utilisation comme mot clé dans les fonctions génératrices:
une telle fonction ne livre une valeur que lorsqu’elle y est forcée, c’est à dire lorsque le déroulement de la fonction la mène à rencontrer ce mot clé, qui lui ordonne alors de renvoyer une valeur, la stoppe dans sa progression et la fige dans l’état qu’elle a atteint à ce point.





Pour comprendre ce que signifie “figer“, il faut déjà savoir ce qui se passe pour une fonction normale:

Pour une telle fonction, quand le mot clé return est rencontré, une valeur est envoyée par la fonction vers l’extérieur et elle est fermée et non pas figée.

Extérieur, cela désigne l’espace de noms englobant dans lequel la fonction a été appelée.

Et fermée, cela veut dire que l’espace de noms local de la fonction disparaît: il se dissout dans la mémoire vive.

Cf sur cette question les très intéressantes et indispensables notions que j’ai trouvées là:
http://lfe.developpez.com/tutoriel/p...00000000000000

Les espaces de noms sont créés à des moments différents et ont des durées de vie différentes. (...) L'espace de noms local à une fonction est créé quand celle-ci est appelée et il est effacé quand la fonction se termine ou déclenche une exception qui n'est pas gérée dans la fonction. (En fait, oublié décrit mieux ce qui se passe vraiment.) Évidemment, les appels récursifs ont chacun leur propre espace de noms.

par Guido himself

Par contre, quand le déroulement d’une fonction génératrice bute sur le mot yield, le renvoi de valeur n’est pas suivi de la fermeture de la fonction mais simplement de sa mise en suspens, c’est à dire que:

1- son espace de noms local est maintenu en vie tel quel : l’objet qui implémente cette fonction est gelé dans son état à ce point (toutes les valeurs des variables locales dans la fonction sont conservées intactes).
C’est ce qu’a voulu dire sopsag en parlant de suspension dans son contexte.

La plupart des espaces de noms sont actuellement implémentés comme des dictionnaires, mais cela n'est pas visible (sauf sur les performances peut-être) et pourrait changer dans le futur.

2- lorsque la fonction est appelée une nouvelle fois dans son module englobant, son espace de noms est dégelé et la progression dans la fonction reprend à partir du même état que celui dans lequel elle avait été quittée.

En anglais, cette reprise à un même point est exprimée par le verbe to resume (faux ami !).
J’ai mis pas mal de temps avant de commencer à comprendre les fonctions génératrices. Ça a fait tilt quand j’ai réalisé qu’elles fonctionnent par “resuming“ (excusez le néologisme).
Exemple de resuming dans un autre domaine:
c’est ce qui se passe quand, après qu’un téléchargement d’application ait été interrompu par une coupure de connexion, il reprend à partir du même point, sans avoir à repartir du tout début.




Toute correction d’erreur commise dans mon blabla est bienvenue.

[sopsag]

Juste pour info, à propose de yield :
Avec Windows 95, qui était un OS multitâche non préemptif, il fallait rendre la main soi-même au système de temps en temps sinon on finissait par le faire crasher (il y avait bien d'autres manières d'y arriver ).
L'instruction qui signifiait "rendre la main" était... yield
(Heureusement les windows d'aujourd'hui sont préemptifs, c'est à dire, qu'ils reprennent la main tout seuls pour pouvoir faire leur boulot d'OS.)

[wiztricks]

Bonsoir,

Personnellement, j'aime bien Python car il regroupe agréablement des techniques de programmation anciennes.

Les coroutines qui se cachent derrière les générators en sont un exemple.

C'est une fonctionnalité que j'ai rarement vue utilisée en dehors de programmes écrit en assembleur: il faut pouvoir accéder au contexte d'exécution matériel pour coder cela proprement.

Ceux qui programmaient(1) en assembleur sont tellement souvent dans une recherche extrême qu'arriver à lire et comprendre ce genre de construction peut être épuisant : gestion du contexte, passage de paramètres et transfert de contrôle sont difficiles à démêler.

En C, pour construire des coroutines, on peut utiliser les classiques longjmp et setjmp. Le code étant plus compact, il est souvent plus facile à lire mais c'est une utilisation limite car pas toujours portable.
Note: les générateurs et yield existent dans de nombreux dialectes Lisp, mais les programmeurs Lisp sont presque aussi rares que ceux qui codent en assembleur. (2)

De fait, cette façon particulière d'enlacer appelant et appelé est tellement peu orthodoxe dans les langages 'normaux' qu'elle a quasiment disparu des savoirs faire.

Pourtant, c'était quand même une façon assez simple d'écrire nombre d'algorithmes. Python dépoussière un peu cette technique et permet de l'utiliser sans que ce soit un casse tête à écrire ou à relire.

-W

Notes:
(1) je mets cela au passé, car compétences et nécessité sont aujourd'hui rares. Il y a quelques dizaines d'années un OS était livré avec un assembleur de base qui couvraient pas mal de besoins. De toutes façons, les compilos étaient chers et pas toujours fiables. Les capacités des systèmes étaient plus que réduites: il fallait souvent compter le nombre d'instructions, la place mémoire, ... Des tracas difficile à imaginer aujourd'hui.
(2) Et compte tenu de l'orientation prise par les techniques de traitement des données, c'est bien dommage...

[sopsag]

Note: les générateurs et yield existent dans de nombreux dialectes Lisp, mais les programmeurs Lisp sont presque aussi rares que ceux qui codent en assembleur.

J'ai été et suis encore un grand amateur de Lisp (je me suis même écrit un interpréteur minimaliste) mais je n'ai jamais rencontré quelque chose qui ressemble au yield du python dans ce langage...
Mais bien sûr je ne connais pas tous ses dialectes.

[wiztricks]

La plupart des dialectes Lisp connaissent la notion de coroutines (ce que fait yield). Dans mes souvenirs, je crois qu'Ocaml le fait en utilisant 'yield'.
- W

[sopsag]

Argl ! je ne savais pas qu'Ocaml était considéré comme un dialecte Lisp...

[wiztricks]

Argl ! je ne savais pas qu'Ocaml était considéré comme un dialecte Lisp...

Les informaticiens vivent dans un milieu exigeant une certaine rigueur où il convient d'appeler C.H.A.T un chat et pas autrement : il eut été plus 'juste' d'écrire langage fonctionnel plutôt que 'dialecte Lisp'.

Je m'excuse vis à vis de tout ceux qu'un tel abus (ou liberté) a pu choquer.

- W