Difference between revisions of "Enigma/enigma8crack.c"

/**************************************************************************
  #     #
  ##   ##  ######  #####    ####     ##    #    #   #####  ######   ####
  # # # #  #       #    #  #    #   #  #   ##   #     #    #       #    #
  #  #  #  #####   #    #  #       #    #  # #  #     #    #####   #
  #     #  #       #####   #       ######  #  # #     #    #       #
  #     #  #       #   #   #    #  #    #  #   ##     #    #       #    #
  #     #  ######  #    #   ####   #    #  #    #     #    ######   ####

***************************************************************************
Author..: Henrik Thomsen heth@mercantec.dk
Company.: House of Technology at Mercantec ( http://www.mercantec.dk )
date....: 2010 Nov. 28
Version.: 0.00000000002 (Still experimental)
***************************************************************************
Abstract: Enigma8crack is a brute-force attack attempt to crack files
          encrypted with enigma8. Se enigma8.c for details
          NOTE: The wheels are known (The enemy dont know that)

          To find the right wheels order of wheels and the notch setting
          we need a Crib. A crib is a known plaintext message in the
          encrypted message. This program can only find Cribs in the
          begining of the message. If you want to find a crib anywhere
          in the message - you need to expand this program :-)

Purpose.: To be used for fun to challenge our students making multithreaded
          solutions to break the codes.
***************************************************************************
Cavets..: wheels and rotor reflectors made with program makewheel which:
                - Real lousy solution generating random numbers with rand()
                -Real lousy solution solving missing hits in sub rr. missing
                 randomness.
***************************************************************************
Modification log:
***************************************************************************
License:  Free open software but WITHOUT ANY WARRANTY.
Terms..:  see http://www.gnu.org/licenses
**************************************************************************/
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <err.h>
#include "wheels10.h"
#define WHEELSUSED 4 /* total number of Wheels installed in the Enigma */
#define WHEELSTOTAL 10/* total number of Wheels to choice from */

/* Global variables i - need for speed instead of parameters */
char *progname;
int *crib;                /* To hold the known Crib we search for */
int *cipher;              /* To hold the cryted cypher */
int order[WHEELSUSED];    /* Initial wheels installed and in which order */
int position[WHEELSUSED]; /* Inital position of rotors */
int state[WHEELSUSED];    /* To save state when testing if cipher match */

void usage( void ) {
        printf("Usage:\n%s crypted-file Crib\n",progname);
        printf("\n%s A brute-force enigma8 hack\n",progname);
        exit(1);
}
/*simple reentrant Factorial*/
unsigned long fact( unsigned long x ) {
        if ( x > 1 ) {
                return(x * fact( x - 1 ));
        }
        return(1);
}
/* sub tick
  abstract: Wheel 1 is ticked forward after each byte.
             Alle wheels have a notch. When they reach their notch the whell
             will tick the next wheel. See wheel_notch in wheels.h
             When wheel 1 reaches its notch it will tick wheel 2 one
             tick forward. When wheel 2 reaches its notch it will tick
             wheel 3 one tick forward etc...
   input     None it uses global variables wheel_notch, order and
             postition.
   returns   int - returns 0 when last rotor position ticks over fx. 255,255->0,0,0 */
int tick( void ) {
        int i,j,flag;

        for (i=0; i < WHEELSUSED; i++ ) {
                if ( i == 0 ) {  /* First wheel always ticks */
                        position[0]++;
                        if ( position[0] >  255 ) { /* Wheel turn over */
                                position[0]=0;
                        }
                }
                if ( wheel_notch[order[i]] == position[i] ) { /* At notch */
                        if ( i < ( WHEELSUSED-1) ) { /* Last wheel dont tick next */
                                flag=1;
                                /* All preceding wheel at notch, then tick next*/
                                for (j=0; j <= i; j++ ) {
                                        if ( wheel_notch[order[j]] != position[j] ) {
                                                flag = 0;
                                        }
                                }
                                if ( flag == 1) {
                                        position[i+1]++;
                                        if ( position[i+1] > 255 ) {
                                                position[i+1] = 0; /* Wheel turn over */
                                        }
                                }
                        }
                }
        }
        /*Check if all wheels tick from 255 -> 0 */
        for (i=0; i < WHEELSUSED; i++) {
                if ( position[i] != 0 ) {
                        return(1);
                }
        }
        return(0); /* Done with all positions */
}

/* sub rotor
   abstract: Send data through a rotor
   input wh  = wheel number
         pos = position (how many ticks is the wheel rotated)
         n   = data (integer) sent through the wheel
   returns (integer) new value of n after been throgh the wheel*/
int rotor(int wh,int pos,int n) {
        /* Beregn den relative position når hjulet er roteret pso ticks */
        int rel;
        if ( n-pos < 0) {
                n+=256;
        }
        rel = wheel[wh][n-pos]+pos;
        if (rel > 255 ) {
                rel = rel % 256;
        }
        return(rel);
}

/* sub revrotor
   abstract: Send data through a reverse rotor (After Route Reflector)
   input wh  = wheel number
         pos = position (how many ticks is the wheel rotated)
         n   = data (integer) sent through the wheel
   returns (integer) new value of n after been throgh the reverse wheel*/
int revrotor(int wh,int pos,int n) {
        /* Beregn den relative position når hjulet er roteret pso ticks */
        int rel;
        if ( n-pos < 0) {
                n+=256;
        }
        rel = rwheel[wh][n-pos]+pos;
        if (rel > 255 ) {
                rel = rel % 256;
        }
        return(rel);
}

/* sub reflector
   abstract: Send data through the route reflector
    input n  = data (integer) sent through the route reflector
    output   = data (integer) after n has been through the route reflector*/
int reflector(int n) {
        return(rr[n]);
}


/*Find next wheel combination. Dont check if same wheel used twice */
/* Used by installwheels */
int nextwheelcombination() {
        int i;
        for (i=0 ; i < WHEELSUSED ; i++ ) {
                if ( order[i] == WHEELSTOTAL - 1 ) {
                        order[i] = 0;
                } else {
                        order[i]++;
                        return(1);
                }
        }
        return(0);
}
/* sub installwheels
   abstract: To install next wheel combination for brute force attack
    input: none (order[] is global)
    output: int - returns 1 when new combination installed 0 when finished*/
int installwheels( void ) {
        int i,j;
        int flag;
        do {
                flag = 0;
                if ( nextwheelcombination()== 0 ) {
                        return(0); /*Done with all combinations*/
                }
                for ( i = 0; i < WHEELSUSED; i++ ) {
                        for ( j = 0; j < WHEELSUSED; j++ ) {
                                if ( i != j ) {
                                        if ( order[i] == order[j] ) {
                                                flag=1;
                                        }
                                }
                        }
                }
        } while(flag == 1);
        return(1); /* New combination installed */
}
/*sub decchar - Decrypt character
  absratct: Sends a character through the Enigma whells, rr and reverse wheels
  input: char to be decrypted
  output: decrypted character
*/
int decchar( int c ) {
        int i;
        /* Trough rotors */
        for (i=0; i < WHEELSUSED; i++) {
                c = rotor(order[i],position[i],c);
        }
        /* Reflector */
        c = reflector(c);
        /* Trough reverse rotors */
        for (i=0; i < WHEELSUSED; i++) {
                c = revrotor(order[WHEELSUSED-1-i],position[WHEELSUSED-1-i],c);
        }
        return(c);
}

int main( int argc, char *argv[] ) {
        int i,j;
        int wheelcombinations;
        unsigned long longi,longj;
        unsigned long count=0;
        int ciphersize;
        FILE *fpin;
        progname = argv[0];

        if ( argc != 3 ) { /* Wheel name appended */
                usage();
        }

        if ( ! (fpin = fopen(argv[1], "r")) ) {
                err(1,"Can't open file for reading %s",argv[1]);
                exit(1);
        }
        /* Get memory to store the cypher to compare to Crib  */
        ciphersize=strlen(argv[2]);
        cipher = (int *) malloc(ciphersize*sizeof(int));
        if ( cipher == NULL ) {
                err(2,"Can't allocate memory for cleartext message.");
                exit(2);
        }
        /* Read the Cypher - of size Crib - into memory */
        for (i=0; i < ciphersize; i++) {
                if ((cipher[i] = fgetc(fpin)) == EOF) {
                        err(3,"Can't read from cipher file. (Perhaps it's shorter than the Crib");
                        exit(3);
                }
        }
        fclose(fpin);
        /* Get Crib message */
        //crib = (int *) malloc(ciphersize*sizeof(short int));
        crib = (int *) malloc(ciphersize*sizeof(int));
        if ( crib == NULL ) {
                err(4,"Can't allocate memory for crib message.");
                exit(4);
        }
        /*strcpy(crib,argv[2]);*/
        for (i=0; i < ciphersize; i++) {
                crib[i] =  argv[2][i];
        }

        /* Print Startup information to user */
        for (i=0,longi=1,longj=1; i < WHEELSUSED; i++ ) {
                longi=longi * (WHEELSTOTAL - i);
                longj=longj * 256; /* Number of possible notch combinatins */
        }
        printf("There are %li number of ways to install %i wheels out of %i possible wheels\n",
                longi,WHEELSUSED,WHEELSTOTAL);
        printf("There are %li number of wheel startpositions with %i wheels\n",longj,WHEELSUSED);
        printf("That gives a total of %li * %li = %li possible combinations (keys)\n\n",longi,longj,longi*longj);
        /* Initialization of enigma. */
                /* Install wheels from 0,1,2 ... WHEELSUSED-1 */
        for(i=0; i < WHEELSUSED ; i++ ) {
                order[i]=0; /* installwhells will sort out combinations */
        }
        /* Initilization done - now to the crunching*/
        wheelcombinations=0;
        while( installwheels() != 0) {
                printf("\nTrying wheel combination: ");
                for (i=0; i < WHEELSUSED; i++)
                        printf("%i ",order[i]);
                printf(" (%d/%ld)",++wheelcombinations,longi);
                fflush(stdout);
                /* Installed new wheelcombination now start trying wheel combinations */
                /* Start with all notches in position 0 */
                for(i=0; i < WHEELSUSED ; i++ ) {
                        position[i]=0;
                }
                do {
                        count++; /* Just count for test how many times this loop runs*/

                        /* Test if first character fits crib when decoded - the try and match */
                        if (decchar(cipher[0]) == crib[0]) { /* Possible match */
                                /* Save state of wheel positions before attempting to match */
                                for (j=0; j < WHEELSUSED ; j++) {
                                        state[j] = position[j];
                                }
                                for (i=0; (decchar(cipher[i]) == crib[i]) && (i < ciphersize) ; i++){
                                                /*If all wheels tick over from 255->0 - Done with wheel*/
                                                if (tick() == 0) {
                                                        break; /* Next wheels   */
                                                }
                                }
                                /* Reinstate wheel positions as before attempting to match */
                                for (j=0; j < WHEELSUSED ; j++) {
                                        position[j] = state[j];
                                }
                                if (i >= ciphersize - 1) { /*Candidate found */
                                        printf("\rWheels ");
                                        for (i=0; i < WHEELSUSED; i++) {
                                                printf("%i ",order[i]);
                                        }
                                        printf("in startpositions ");
                                        for (i=0; i < WHEELSUSED; i++) {
                                                printf("%i ",position[i]);
                                        }
                                        printf("match the crib.\n");
                                }
                        }
                } while(tick());

        }

        printf("\n\nThere has been %li attempts\n",count);
        free(cipher);
        free(crib);
        exit(0); /* Succes */
}