Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Python Discussion :

Petite compétition de skill ?


Sujet :

Contribuez Python

  1. ###raw>post.musername###
    Membre régulier
    Petite compétition de skill ?
    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 !
      1  0

  2. #2
    Membre éclairé
    Est ce que faire du timing attack est autorisé ?

  3. #3
    Membre régulier
    Citation Envoyé par flapili Voir le message
    Est ce que faire du timing attack est autorisé ?
    Aucune idée de ce que c'est ! On va dire que c'est autorisé...

  4. #4
    Expert éminent sénior
    Salut,

    Citation Envoyé par LeNarvalo Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Membre régulier
    Citation Envoyé par wiztricks Voir le message
    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/itertools.html#itertools.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 - ...

  6. #6
    Expert éminent sénior
    Salut,

    Citation Envoyé par LeNarvalo Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  7. ###raw>post.musername###
    Membre régulier
    Citation Envoyé par wiztricks Voir le message
    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.
      0  0

  8. ###raw>post.musername###
    Membre confirmé
    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)
      1  0

  9. #9
    Membre régulier
    @YCL-1 Nice ! =)
    PS : il te manque le caractère ' dans ta liste values

  10. #10
    Membre confirmé
    Citation Envoyé par LeNarvalo Voir le message
    @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.

  11. #11
    Membre éclairé
    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 ?

  12. #12
    Membre régulier
    Citation Envoyé par flapili Voir le message
    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.

  13. #13
    Membre éclairé
    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

  14. #14
    Membre régulier
    Ah ok !
    En effet ça n'a pas l'air tellement utile en ce qui nous intéresse ! ^^

###raw>template_hook.ano_emploi###