Brute Forcing Des With A Weak Key

I am taking a course on Cryptography and am stuck on an assignment. The instructions are as follows: The plaintext plain6.txt has been encrypted with DES to encrypt6.dat using a 6

Solution 1:

I would assume the desired solution is to actually implement the algorithmn. Then, since your're decrypting yourself, you can bail early, which, assuming the plain text is also A-Za-z0-9, gives you a 98% chance of being able to stop after decrypting a single byte, a 99.97% chance of stoping after decrypting 2 bytes, and a 99.9995% chance of stopping after 3 bytes.

Also, use C or Ocaml or something like that. You're probably spending MUCH more time doing string manipulation than you are doing cryption. Or, at least use multi-processing and spin up all your cores...

Solution 2:

There is an obvious factor 256 speedup: One bit per byte isn't part of the key. DES has only a 56 bit key, but one passes in 64 bits. Figure out which bit it is, and throw away equivalent characters.

Solution 3:

I've had quite a bit of help and this is a solution in C. As I am a C beginner, it's probably full of bugs and bad practice, but it works.

As CodeInChaos figured out, only 31 characters need to be tested, because DES ignores every 8th bit of the key, making for example ASCII characters b: *0110001*0 and c: *0110001*1 identical in encryption/decryption when used as a part of the key.

I am using the OpenSSL library for DES decryption. On my machine the speed it achieves is ~1.8 million passwords per second, which puts the total time to test the entire key space to around 5 days. This falls a day short of the deadline. A lot better than the Python code above which is in the years territory.

There is still room for improvement, probably the code could be optimized and threaded. If I could use all my cores I estimate the time would go down to a bit more than a day, however I have no experience with threading yet.

#include<stdio.h>#include<unistd.h>#include<string.h>#include<signal.h>#include<openssl/des.h>staticlonglongunsigned nrkeys = 0; // performance counterchar *
Encrypt( char *Key, char *Msg, int size){
        staticchar*    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( ( unsignedchar (*) [8] ) Msg, ( unsignedchar (*) [8] ) Res,
                           &schedule, DES_ENCRYPT );
         return (Res);
}

char *
Decrypt( char *Key, char *Msg, int size){
        staticchar*    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( ( unsignedchar (*) [8]) Msg, ( unsignedchar (*) [8]) Res,
                           &schedule, DES_DECRYPT );
        return (Res);
}

voidex_program(int sig);

intmain(){
    (void) signal(SIGINT, ex_program);

    FILE *f, *g; // file handlersint counter, i, len = 8; // counters and password lengthchar cbuff[8], mbuff[8]; // bufferschar letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy"; // reduced letter pool for password brute forceint 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");
        return1;
    }
    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");
        return1;
    }
    for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g);
    fclose(g);

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

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

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

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

        // decryptmemcpy(decrypted,Decrypt(password,cbuff,8), 8);

        // compare the decrypted with the mbuff// if they are equal, exit the loop, we have the passwordif (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 overflowsfor(i=0 ; i<len && ++entry[i] == nbletters; i++) entry[i] = 0;
    } while(i<len);

    return0;
}

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

Solution 4:

I can't help but notice the wording of the assignment: you are not actually requested to provide a DES implementation or cracker yourself. If that is indeed the case, why don't you take a look at tools such as John the Ripper or hashcat.

Solution 5:

This answer may be complementary to other more specific suggestions but the first thing you should do is run a profiler.

There are really nice examples here:

How can you profile a python script?

EDIT:

For this particular task, I realize it will not help. A trial frequency of 10 GHz is... Hard on a single machine with frequency less than that. Perhaps you could mention what hardware you have available. Also, don't aim for running it during a few hours. When you find a method that gives a reasonable probability of success within the week you have then let it run while improving your methods.