Discussion :

[Invité]

Salut ! (Je vais encore me faire gronder sur l'endroit où j'ai posté ça...)

Je vous propose une petite compétition sans prétention ni gain d'ailleurs.

Le but étant de créé un script en python afin de cracker un mot de passe par force brut.



Le script devra donc tester toutes les combinaisons possible avec cette chaine de caractère :
l = ''''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~'''
Le script doit afficher le temps qu'il a mis pour trouver le mot de passe (sans tricher, svp).

Les mots de passe à trouver sont les suivants :

1) \F

2) >>N

3) aD48

4) x#&72

5) 3%R@,g

Sous format liste : ['\F','>>N','aD48','x#&72','3%R@,g']
Et voici mes temps déplorables avec mon script alambiqué et mon processeur d'un autre temps :

1) \F - 0.009 seconde(s)

2) >>N - 0.97 seconde(s)

3) aD48 - 13.6794 seconde(s)

4) x#&72 - 3655.1691 seconde(s)

5) 3%R@,g - Résultat l'année prochaine

Et avec un interpréteur en ligne (résultats très variables, du simple au quintuple): https://www.onlinegdb.com/online_python_compiler

1) \F - 0.009 seconde(s)

2) >>N - 3.4013 seconde(s)

3) aD48 - 46.5233 seconde(s)

4) x#&72 - En cours

5) 3%R@,g - A mon avis le serveur va me kicker avant...

A vos jeux !

[flapili]

Est ce que faire du timing attack est autorisé ?

[Invité]

Est ce que faire du timing attack est autorisé ?

Aucune idée de ce que c'est ! On va dire que c'est autorisé...

[wiztricks]

Salut,

Le script doit afficher le temps qu'il a mis pour trouver le mot de passe (sans tricher, svp).

Fabriquer les combinaisons de R caractères avec répétition d'une séquence de N caractères se fait avec la fonction combinations_with_replacement du module itertools.

On sait calculer combien il y aura de combinaisons pour R=2, 3, 4, ... elle est donnée dans la documentation. Donc on sait estimer le temps qu'il faudra pour trouver une combinaison de longueur donnée.

Quel est l'intérêt de gaspiller de l'électricité à attendre des plombes devant son ordinateur pour un résultat connu d'avance?

- W

[Invité]

Salut,



Fabriquer les combinaisons de R caractères avec répétition d'une séquence de N caractères se fait avec la fonction combinations_with_replacement du module itertools.

On sait calculer combien il y aura de combinaisons pour R=2, 3, 4, ... elle est donnée dans la documentation. Donc on sait estimer le temps qu'il faudra pour trouver une combinaison de longueur donnée.

Quel est l'intérêt de gaspiller de l'électricité à attendre des plombes devant son ordinateur pour un résultat connu d'avance?

- W

Faire un pas de plus dans l'auto-destruction de notre planète ? Du coup tu fais comment pour estimer ce temps ? Car il peut être extrêmement variable non pas seulement en fonction du nombre de caractères mais aussi du mot de passe choisi. Par exemple itertools.product affichera le code ZZZZZZZZZZZZZZ à des "millions" d'emplacements plus loin que aaaaaaaaaaaaaa.
Car en réalité il faudrait plus utiliser product non ? https://docs.python.org/fr/3/library...rtools.product

Bref, sans devoir aller jusqu'à plus de 5 caractères, je voulais tester la rapidité de vos scripts. Mais en effet on pourrait très bien l'estimer et s'en servir comme référence infranchissable !? C'est au delà de mes compétences donc si tu veux bien me dire comment faire cette estimation, je suis preneur et la planète te remerciera !

Wahou itertools.product est vraiment plus rapide !

1) \F - 0.002 seconde(s)

2) >>N - 0.164 seconde(s)

3) aD48 - 2.3634 seconde(s)

4) x#&72 - En cours

5) 3%R@,g - ...

[wiztricks]

Salut,

Mais en effet on pourrait très bien l'estimer et s'en servir comme référence infranchissable !? C'est au delà de mes compétences donc si tu veux bien me dire comment faire cette estimation, je suis preneur et la planète te remerciera !

Ouvrez la documentation, elle donne le nombre de combinaisons à tester en fonction de n et de r à multiplier par un temps moyen que l'on peut affiner via des statistiques ou majorer.

Si vous voulez en savoir plus intéressez vous aux calculs de la complexité d'un algorithme.
La littérature sur le sujet est abondante.

- W

[Invité]

Salut,



Ouvrez la documentation, elle donne le nombre de combinaisons à tester en fonction de n et de r à multiplier par un temps moyen que l'on peut affiner via des statistiques ou majorer.

Si vous voulez en savoir plus intéressez vous aux calculs de la complexité d'un algorithme.
La littérature sur le sujet est abondante.

- W

Elle ne donne pas le nombre de combinaisons pour la fonction product, mais bon ce n'est pas très compliqué à calculer :

Code :

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

1
2
3
4
5
>>> l = ''''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~'''
>>> len(l)
94
>>> 94**1+94**2+94**3+94**4+94**5+94**6
697287735690

Peut-on estimer que le temps nécessaire entre la combinaison "aaaaaaaaaaaa" et "baaaaaaaaaaaa" est le même qu'entre "Yaaaaaaaaaaaa" et "Zaaaaaaaaaaaaa" par exemple, ou c'est plus compliqué que ça ?

Je ne pense pas avoir le niveau intellectuel ni les connaissances pour comprendre ce que je risque de lire au sujet du calcul de la complexité des algorithmes.

[YCL-1]

Bonjour,

Je me suis prêté au jeu en essayant d'améliorer mon code, c'est sûr itertools.product est vraiment efficace pour générer les combinaisons.
moi j'étais parti sur une génération avec mémoïsation des résultats,
mais avec 40 millions de combinaisons je consomme 11,2 Go de RAM (à 300 octets par combinaison) et il faut pas moins de 7 milliards de combinaisons pour le 4ème !

En utilisant https://docs.python.org/3/library/fu...ools.lru_cache

Mais le score est médiocre :

Calcul sur un seul CPU i7-2600 @ 3,4 GHz.

Combinaison 1/5: '\\F' 0.008 s
Combinaison 2/5: '>>N' 0.802 s
Combinaison 3/5: 'aD48' 11.129 s

En reprenant la méthode itertools.product on peut encore gagner quelques % en le combinant avec itertools.dropwhile(predicate, iterable)

Qui permet de renvoyer un élément uniquement s'il répond au critère passé en premier argument, c'est l'inverse de itertools.takewhile qui lui permet de renvoyer tous ceux qui ne répondent pas au critère.

Ainsi on gagne un peu :

Methode sans :

Combinaison 1/5: '\\F' 0.002 s
Combinaison 2/5: '>>N' 0.191 s
Combinaison 3/5: 'aD48' 2.798 s

Méthode avec :

Combinaison 1/5: '\\F' 0.002 s
Combinaison 2/5: '>>N' 0.140 s
Combinaison 3/5: 'aD48' 2.022 s

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
# -*- coding: utf-8 -*-
 
import time
from itertools import product, dropwhile
 
 
values = ''''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~'''
comb_len = len(values)
assert len(values) == len(set(values)) # Vérifie que chaque caractère est unique
 
# Les mots de passe à trouver sont les suivants :
# 1) \F
# 2) >>N
# 3) aD48
# 4) x#&72
# 5) 3%R@,g
 
str_comb_to_find_list = ['\\F', '>>N', 'aD48', 'x#&72', '3%R@,g']
max_len = max(len(str_comb_to_find) for str_comb_to_find in str_comb_to_find_list) # Garde-fou
 
for i_comb, str_comb_to_find in enumerate(str_comb_to_find_list): # {
    # Critère d'entrée à comparer : str
    # Interdiction d'utiliser la variable autre que pour la comparaison finale ni d'en connaitre la longueur
    print("Combinaison {}/{}: ".format(i_comb + 1, len(str_comb_to_find_list)), end="")
    time_p_ref = time.perf_counter() # Référence de temps du début du calcul
    key_len = 1 # Taille de la combinaison à générer
    while key_len <= max_len: # {
        str_comb = ""
        for tuple_comb in dropwhile(lambda x: "".join(x) != str_comb_to_find, product(values, repeat=key_len)): # { Pour chaque combinaisons possibles
            str_comb = "".join(tuple_comb)
            if str_comb == str_comb_to_find: # {
                computing_duration_s = time.perf_counter() - time_p_ref
                print("{!r} {:.03f} s".format(str_comb, computing_duration_s))
                break
            # } comb found
        # } for
        if str_comb == str_comb_to_find:
            break
        key_len += 1
    # } while
    if str_comb != str_comb_to_find:
        raise Exception("Combinaison non trouvée !")
# } for each comb_to_find_list

MAJ: Correction sur les caractères, oubli de ' (merci LeNarvalo)

[Invité]

@YCL-1 Nice ! =)
PS : il te manque le caractère ' dans ta liste values

[YCL-1]

@YCL-1 Nice ! =)
PS : il te manque le caractère ' dans ta liste values

Si je triche sur l'énoncé ça va pas le faire..

C'est corrigé merci,

À priori on gagne 30-40% en rajoutant dropwhile.

Après c'est sûr que lambda n'est pas efficace, tout comme sur map c'est surtout dédié à passer une fonction compilé / native, bien plus efficace.
Mais vu que le défit est d'utiliser Python on peut pas espérer des miracles sur du calcul brut, à part diviser de calcul par N CPU bien entendu.

[flapili]

malheureusement je n'est rien de fructueux en essayant d'utiliser du timing attack je doit avoir beaucoup trop de bruits parasites autour.
tout ce que j'arrive à dire pour le 1er mot de passe à trouver est que dans environ 93% des cas "\" est dans les 30 premiers caractères par score mais je bench pendant 3mn avec timeit c'est contre productif sur des chaînes courtes.

La question est donc de savoir à partir de combien de caractère il devient préférable de perdre 3mn par caractère pour réduire de 2/3 l'entendu des recherches ?

[Invité]

malheureusement je n'est rien de fructueux en essayant d'utiliser du timing attack je doit avoir beaucoup trop de bruits parasites autour.
tout ce que j'arrive à dire pour le 1er mot de passe à trouver est que dans environ 93% des cas "\" est dans les 30 premiers caractères par score mais je bench pendant 3mn avec timeit c'est contre productif sur des chaînes courtes.

La question est donc de savoir à partir de combien de caractère il devient préférable de perdre 3mn par caractère pour réduire de 2/3 l'entendu des recherches ?

J'ai rien compris, mais je dirais à partir de 5 caractères puisqu'il faut probablement une petite demi-heure avec itertools uniquement.

[flapili]

le timing attack en gros c'est une exploitation d'une optimisation,

par exemple comparer "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" avec "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" ne prendra pas très longtemps parce que Python va dès le 1er caractère se dire "c'est pas la peine que j'aille plus loin je sais déjà que c'est pas égal", tandis que "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" == "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" prendra plus de temps (à nous aussi humain d'ailleurs), cependant il est possible que Python compare déjà la taille de la chaîne

malheureusement j'arrive à démontrer le contraire :/

Code :

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

1
2
3
4
5
6
7
8
9
10
11
C:\Users\DEVEAUX>python -m timeit "'a' == 'a'"
10000000 loops, best of 5: 26.3 nsec per loop
 
C:\Users\DEVEAUX>python -m timeit "'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' == 'baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'"
10000000 loops, best of 5: 28.9 nsec per loop
 
C:\Users\DEVEAUX>python -m timeit "'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' == 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'"
10000000 loops, best of 5: 26.1 nsec per loop
 
C:\Users\DEVEAUX>python -m timeit "'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' == 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'"
10000000 loops, best of 5: 26.2 nsec per loop

ce qui est un peu décourageant ...

l’écart est trop minime et ne semble pas exploitable, d'autant plus qu'en relançant ou peux obtenir la situation inverse

[Invité]

Ah ok !
En effet ça n'a pas l'air tellement utile en ce qui nous intéresse ! ^^