// hashattack.c

/*
 Written by
 Huang,Jessica C : jessica9@MIT.EDU
 Huang,Kai : kaih@MIT.EDU
 Huang, Edward : eych@MIT.EDU
 Shi,Melissa F : mshi@MIT.EDU
 
 September 25, 2001

 May be freely reproduced for educational or personal use
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "types.h"
#include "hashtable.h"
#include "hashlib.h"


typedef enum { FORWARD, BACKWARD } Direction;

void generateKey( Key k );


// finds and prints out a message consisting of 16 letters
// that hashes 0x00010002 into 0xDC98F5EF using the hash
// function described in 6.857 PS 1 Problem 1-1.
int main( int argc, char *argv[] )
{
    int stime;   // time variables used to seed the random
    long ltime;  // number generator to the current time

    Vect I,              // initial vector
         D;              // final vector
    Hashtable forward,   // values of RC5-Encrypt(m,I)
              backward;  // values of RC5-Decrypt(m,D)

    unsigned long counter = 0;  // counts number of iterations
    Byte *match = NULL;         // used to test for a vector match
    Direction z = FORWARD;      // current step within the iteration
    Key k;                      // key for the iteration
    Vect outVect;               // resulting vector

    // seed the random number generator
    ltime = time( NULL );
    stime = (unsigned int) ltime / 2;
    srand( stime );

    // set initial and final vectors
    I[ 0 ] = 0x0001;
    I[ 1 ] = 0x0002;
    D[ 0 ] = 0xDC98;
    D[ 1 ] = 0xF5EF;

    // clear hashtables of any initial garbage
    initHash( forward );
    initHash( backward );

    // while a match has not been found, keep iterating
    while ( match == NULL ) {

        // forward step within the iteration
        if ( z == FORWARD ) {

            generateKey( k );
            RC5_SETUP( k );

            RC5_ENCRYPT( I, outVect );

            hashPut( forward, outVect, k );
            match = hashGet( backward, outVect );

            z = BACKWARD;

	// backward step within the iteration
        } else {

            RC5_DECRYPT( D, outVect );

            hashPut( backward, outVect, k );
            match = hashGet( forward, outVect );

            z = FORWARD;

            // count the number of iterations
            ++counter;
            if ( counter % 1000 == 0 ) {
                printf( "%d..", counter / 1000 );
                fflush( stdout );
            }

        }
    }

    // print out solution keys in hex and character form
    printf( "\n(" );
    printKeyHex( hashGet( forward, outVect ) );
    printKeyHex( hashGet( backward, outVect ) );
    printf( ")  (" );
    printKeyChar( hashGet( forward, outVect ) );
    printKeyChar( hashGet( backward, outVect ) );
    printf( ")\n" );

    return 0;
}


// generates a random array of 8 letters
void generateKey( Key key )
{
    int r, i;

    for ( i = 0; i < 8; ++i ) {
        r = rand() % 52;
        if ( r < 26 )
            key[ i ] = 'a' + r;
        else
            key[ i ] = 'A' + r - 26;
    }
}