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>

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);
}

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.