11
votes

Brute forçage des des avec une clé faible

Je prends un cours sur la cryptographie et je suis coincé sur une mission. Les instructions sont les suivantes:

Le plainte-poste6.txt a été crypté avec des Crypt6.dat à l'aide d'une touche 64 bits donnée sous la forme d'une chaîne de 8 caractères (64 des bits dont chaque 8e bit est ignoré), tous les caractères étant des lettres (minuscule ou majuscule) et chiffres (0 à 9). P>

Pour terminer l'affectation, envoyez-moi la clé de cryptage avant février 12, 23.59. p>

Remarque: je m'attends à obtenir une clé de 8 octets (64 bits). Chaque octet devrait coïncidez avec l'octet correspondant dans ma clé, à l'exception du moins que Bit significatif qui n'est pas utilisé dans des des et ainsi, pourrait être arbitraire. P> BlockQuote>

Voici le code à ma première tentative de Python: P>

#include <stdio.h>      /* fprintf */
#include <stdlib.h>     /* malloc, free, exit */
#include <unistd.h>
#include <string.h>     /* strerror */
#include <signal.h>
#include <openssl/des.h>

static long long unsigned nrkeys = 0; // performance counter

char *
Encrypt( char *Key, char *Msg, int size)
{
        static char*    Res;
        free(Res);
        int             n=0;
        DES_cblock      Key2;
        DES_key_schedule schedule;
        Res = ( char * ) malloc( size );
        /* Prepare the key for use with DES_ecb_encrypt */
        memcpy( Key2, Key,8);
        DES_set_odd_parity( &Key2 );
        DES_set_key_checked( &Key2, &schedule );
        /* Encryption occurs here */
        DES_ecb_encrypt( ( unsigned char (*) [8] ) Msg, ( unsigned char (*) [8] ) Res,
                           &schedule, DES_ENCRYPT );
        return (Res);
}

char *
Decrypt( char *Key, char *Msg, int size)
{
        static char*    Res;
        free(Res);
        int             n=0;
        DES_cblock      Key2;
        DES_key_schedule schedule;
        Res = ( char * ) malloc( size );
        /* Prepare the key for use with DES_ecb_encrypt */
        memcpy( Key2, Key,8);
        DES_set_odd_parity( &Key2 );
        DES_set_key_checked( &Key2, &schedule );
        /* Decryption occurs here */
        DES_ecb_encrypt( ( unsigned char (*) [8]) Msg, ( unsigned char (*) [8]) Res,
                           &schedule, DES_DECRYPT );
        return (Res);
}

void ex_program(int sig);

int main(int argc, char *argv[])
{
    (void) signal(SIGINT, ex_program);

    if ( argc != 4 ) /* argc should be 2 for correct execution */
    {
        printf( "Usage: %s ciphertext plaintext keyspace \n", argv[0] );
        exit(1);
    }

    FILE *f, *g;
    int counter, i, prime = 0, len = 8;
    char cbuff[8], mbuff[8];
    char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy";
    int nbletters = sizeof(letters)-1;
    int entry[len];
    char *password, *decrypted, *plain;

    if(atoi(argv[3]) > nbletters-2) {
        printf("The range must be between 0-%d\n", nbletters-2);
        exit(1);
    }
    prime = atoi(argv[1])

    // read first 8 bytes of the encrypted file
    f = fopen(argv[1], "rb");
    if(!f) {
        printf("Unable to open the file\n");
        return 1;
    }
    for (counter = 0; counter < 8; counter ++) cbuff[counter] = fgetc(f);
    fclose(f);

    // read first 8 bytes of the plaintext file
    g = fopen(argv[2], "r");
    if(!f) {
        printf("Unable to open the file\n");
        return 1;
    }
    for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g);
    fclose(g);

    plain = malloc(8);
    memcpy(plain, mbuff, 8);

    // fill the keys
    for(i=0 ; i<len ; i++) entry[i] = 0;
    entry[len-1] = prime;

    // loop until the length is reached
    do {
        password = malloc(8);
        decrypted = malloc(8);

        // build the pasword
        for(i=0 ; i<len ; i++) password[i] = letters[entry[i]];
        nrkeys++;

        // end of range and notices
        if(nrkeys % 10000000 == 0) {
            printf("Current key: %s\n", password);
            printf("End of range ");
            for(i=0; i<len; i++) putchar(letters[lastKey[i]]);
            putchar('\n');
        }

        // decrypt
        memcpy(decrypted,Decrypt(password,cbuff,8), 8);

        // compare the decrypted with the mbuff
        // if they are equal, exit the loop, we have the password
        if (strcmp(mbuff, decrypted) == 0)
        {
            printf("We've got it! The key is: %s\n", password);
            printf("%lld keys searched\n", nrkeys);
            exit(0);
        }

        free(password);
        free(decrypted);

        // spin up key until it overflows
        for(i=0 ; i<len && ++entry[i] == nbletters; i++) entry[i] = 0;
    } while(i<len);

    return 0;
}

void ex_program(int sig) {
 printf("\n\nProgram terminated %lld keys searched.\n", nrkeys);
 (void) signal(SIGINT, SIG_DFL);
 exit(0);
}


6 commentaires

Peut-être lu sur la structure du des. Il existe des exploits basés sur la manière dont l'information se propage à travers les passes.


Bravo pour ne pas attendre avant la nuit précédente.


Si vous avez de l'argent allongé, et que vous voulez vraiment brute la force, considérez-vous que vous pouvez créer 10 ^ 16 emplois Amazon EC2, chacun qui crypte simplement le plaintre donné avec sa clé allouée.


Vous pouvez toujours essayer de poster cela sur The Crypto Stack Exchange .


Ce gars demande des faiblesses dans le vecteur d'initialisation de l'algorithme. Peut-être qu'ils ont appris quelque chose?


Soyons clairs à l'avance: avec les informations que vous avez fournies, vous ne pouvez pas le faire dans Pure Python sur une seule machine de classe PC.


5 Réponses :


1
votes

Cette réponse peut être complémentaire à d'autres suggestions plus spécifiques, mais la première chose à faire est d'exécuter un profileur . .

Il y a vraiment de beaux exemples ici:

Comment pouvez-vous profiler un script Python?

EDIT:

Pour cette tâche particulière, je le réalise que cela ne vous aidera pas. Une fréquence d'essai de 10 GHz est ... dure sur une seule machine avec une fréquence inférieure à celle-là. Vous pourriez peut-être mentionner quel matériel vous avez disponible. En outre, ne vise pas à le gérer pendant quelques heures. Lorsque vous trouvez une méthode qui donne une probabilité raisonnable de succès dans la semaine, vous le laissez exécuter tout en améliorant vos méthodes.


1 commentaires

Intel I7 2600K, 8 Go de RAM, GTX 580 est ma machine principale. J'ai couru le profileur et la génération de la clé prend la majeure partie du temps, je réécrit cette partie maintenant.



6
votes

Je supposerais que la solution souhaitée est de mettre en œuvre l'algorithme. Ensuite, comme vous vous décryptiez vous-même, vous pouvez faire caution tôt, ce qui, en supposant que le texte brut est également A-ZA-Z0-9, vous donne une chance de 98% de pouvoir m'arrêter après avoir décrit un octet unique, 99,97%. Possibilité d'arrêter après avoir décrit 2 octets et une chance de 99,9995% d'arrêter après 3 octets.

Aussi, utilisez C ou OCAML ou quelque chose comme ça. Vous dépenserez probablement beaucoup plus de temps à faire de la manipulation de chaîne que vous faites Cryption. Ou, au moins, utilisez un multi-traitement et de faire tourner tous vos cœurs ...



1
votes

5 commentaires

J'ai remarqué cela aussi, mais je dois me demander quel est le point de la mission, sinon de mettre en œuvre des craquements.


Il n'est pas nécessaire de fournir une mise en œuvre, mais la clé, mais la mission finale émergera Full des. C'est une concurrence pour atteindre des performances maximales. Vous pourriez aller opencl et louer la calcation de l'AMazon GPU Compute, faites une attaque distribuée ou louez la COPACOBANA. Mais ceux-ci sont un peu sortis de ma ligue :)


Briser la complète des sons plus semblable à "jeter suffisamment d'argent de l'argent" que n'importe quel type de crypto ou de défi codant.


@CODEINCHAOS: Oui, il existe évidemment des informations plus pertinentes dans la mission que l'OP ne nous affiche pas.


@Element: Je vois maintenant. Dans ce cas, une combinaison de cette réponse et de la réponse de CodeInchaos est directement sur le point. Les réponses de CodeInchaos vous indiquent pourquoi il y a pas 62 possibilités pour chaque caractère, mais seulement 31. Il s'agit d'un peu moins de 1 billion de possibilités totales et devrait être faisable par le code dans Jean-Ripper.



5
votes

Il y a un facteur évident 256 Scps-up: Un bit par octet ne fait pas partie de la clé. DES a seulement une clé 56 bits, mais on passe en 64 bits. Déterminez quel est le bit, et jetez des caractères équivalents.


0 commentaires

2
votes

J'ai eu un peu d'aide et c'est une solution en C. Comme je suis un débutant C, il est probablement plein de bugs et de mauvaises pratiques, mais cela fonctionne.

Comme CodeInchaos figuré, seulement 31 Les caractères doivent être testés, car des désignore tous les 8e bit de la clé, ce qui crée par exemple les caractères ASCII B: * 0110001 * 0 code> et c: * 0110001 * 1 code> identique Cryptage / décryptage Lorsqu'il est utilisé dans le cadre de la clé. P>

J'utilise la bibliothèque OpenSSL pour DES DÉCRÉPRÈGE. Sur ma machine, la vitesse qu'elle réalise compte ~ 1,8 million de mots de passe par seconde, ce qui met le temps total pour tester l'ensemble de l'espace clé à environ 5 jours. Cela tombe un jour après la date limite. Beaucoup mieux que le code Python ci-dessus qui se trouve dans le territoire des années. P>

Il reste encore de la place pour améliorer, probablement le code pourrait être optimisé et enfilé. Si je pouvais utiliser tous mes carottes, j'estime que le temps passerait à un peu plus d'une journée, mais je n'ai pas encore d'expérience avec le filetage. P>

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <signal.h>
#include <openssl/des.h>

static long long unsigned nrkeys = 0; // performance counter

char *
Encrypt( char *Key, char *Msg, int size)
{
        static char*    Res;
        free(Res);
        int             n=0;
        DES_cblock      Key2;
        DES_key_schedule schedule;
        Res = ( char * ) malloc( size );
        /* Prepare the key for use with DES_ecb_encrypt */
        memcpy( Key2, Key,8);
        DES_set_odd_parity( &Key2 );
        DES_set_key_checked( &Key2, &schedule );
        /* Encryption occurs here */
        DES_ecb_encrypt( ( unsigned char (*) [8] ) Msg, ( unsigned char (*) [8] ) Res,
                           &schedule, DES_ENCRYPT );
         return (Res);
}

char *
Decrypt( char *Key, char *Msg, int size)
{
        static char*    Res;
        free(Res);
        int             n=0;
        DES_cblock      Key2;
        DES_key_schedule schedule;
        Res = ( char * ) malloc( size );
        /* Prepare the key for use with DES_ecb_encrypt */
        memcpy( Key2, Key,8);
        DES_set_odd_parity( &Key2 );
        DES_set_key_checked( &Key2, &schedule );
        /* Decryption occurs here */
        DES_ecb_encrypt( ( unsigned char (*) [8]) Msg, ( unsigned char (*) [8]) Res,
                           &schedule, DES_DECRYPT );
        return (Res);
}

void ex_program(int sig);

int main()
{
    (void) signal(SIGINT, ex_program);

    FILE *f, *g; // file handlers
    int counter, i, len = 8; // counters and password length
    char cbuff[8], mbuff[8]; // buffers
    char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy"; // reduced letter pool for password brute force
    int nbletters = sizeof(letters)-1;
    int entry[len];
    char *password, *decrypted;

    // read first 8 bytes of the encrypted file
    f = fopen("test2.dat", "rb");
    if(!f) {
        printf("Unable to open the file\n");
        return 1;
    }
    for (counter = 0; counter < 8; counter ++) cbuff[counter] = fgetc(f);
    fclose(f);

    // read first 8 bytes of the plaintext file
    g = fopen("test2.txt", "r");
    if(!f) {
        printf("Unable to open the file\n");
        return 1;
    }
    for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g);
    fclose(g);

    // fill the initial key
    for(i=0 ; i<len ; i++) entry[i] = 0;

    // loop until the length is reached
    do {
        password = malloc(8);
        decrypted = malloc(8);

        // build the pasword
        for(i=0 ; i<len ; i++) password[i] = letters[entry[i]];
        nrkeys++;

        if(nrkeys % 10000000 == 0) {
            printf("Current key: %s\n", password);
        }

        // decrypt
        memcpy(decrypted,Decrypt(password,cbuff,8), 8);

        // compare the decrypted with the mbuff
        // if they are equal, exit the loop, we have the password
        if (strcmp(mbuff, decrypted) == 0)
        {
            printf("We've got it! The key is: %s\n", password);
            printf("%lld keys searched", nrkeys);
            exit(0);
        }

        free(password);
        free(decrypted);

        // spin up key until it overflows
        for(i=0 ; i<len && ++entry[i] == nbletters; i++) entry[i] = 0;
    } while(i<len);

    return 0;
}

void ex_program(int sig) {
 printf("\n\nProgram terminated %lld keys searched.\n", nrkeys);
 (void) signal(SIGINT, SIG_DFL);
 exit(0);
}


1 commentaires

Il suffit d'adapter le programme uniquement sur une partie de l'espace clé (indiqué par le paramètre), puis de l'appeler plusieurs fois en parallèle, par exemple. une fois pour les clés commençant par AM, une fois pour la NZ, une fois pour le matin, une fois pour la NZ et une fois pour 0-9 ... Bien sûr, utilisez des sections de même taille et juste que plusieurs fois que vous avez des noyaux (ou moins vous avez peut toujours utiliser votre ordinateur). Pas besoin de multithreading fantaisie ici.