Hi, The following program is the part of my RC4 key search program that actually does the searching, adapted into a small speed test. It is designed to handle any size key, with any number of unknown bits, in any position within the key. There are, of course, problems with it in its current form: 1. It's too slow. I get 50% of the performance of the bruterc4.c on utopia.hacktic.nl (~9500/sec on a 60Mhz Pentium and ~12000/sec on a Sparc 20) 2. It can only handle bit offsets of 0 (i.e. the lower n bits of the key are unknown). I'm unsure of a really fast way of generalising this to any (contiguous) n bits. 3. There are probably bugs. The code is included below. Does anyone have any comments? - Andy --------------------------- begin code fragment ------------------------ /* RC4 Brute Force Key Searcher, by Andy Brown 1995 This part of the package is meant to be portable between most systems so that Unix users can take part in the searching. After all, the kind of really high powered systems that can make a large dent in the key space are not running Windows NT. You will, however, require an ANSII compiler */ #include <stdio.h> #include <time.h> #include <ctype.h> /* function declarations */ int main(void); char *search_range(char *,unsigned long,unsigned long,char *,int, unsigned char *,unsigned char *,int); static void hex_to_bytes(char *,unsigned char *); #define SwapByte(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) #define hexdigit(a) ((a)<10 ? (a)+'0' : (a)-10+'A') #define decdigit(a) (isdigit(a) ? (a)-'0' : toupper(a)-'A'+10) /*****************************/ /* Main function: test speed */ /*****************************/ int main(void) { /* The key has 20 "unknown" bits */ unsigned char *keyhex="0102030405060708090A0B0C0D000000"; unsigned char *first="0"; unsigned char ciphertext[11]= { 0xF2,0xA2,0xA0,0xF6,0x0F,0xBD,0x69,0x98,0xC0,0xFF,0x4C }; char *retval; time_t before,diff; before=time(NULL); retval=search_range(first,0xFFFFF,0,keyhex,0,"hello world",ciphertext,11); diff=time(NULL)-before; if(retval==NULL) fprintf(stderr,"Key not found, bug in key search code\n"); else fprintf(stderr,"Key is: %s\n%ld keys/sec\n",retval,0xFFFFFL/(long)diff); return 0; } /***********************************/ /* Search a region of the keyspace */ /*********************************** Arguments: start_str: ASCII hex representation of the first "search key" testsl: low order 32 bits of the number of keys to test testsh: high order 32 bits of the number of keys to test keyhex: ASCII hex representation of the key "skeleton" Zeros appear in the key throughout the search range firstbit: zero based index of the first unknown bit plaintext: known plaintext ciphertext: corresponding ciphertext textsize: number of bytes of plain/ciphertext NB: A "search key" is an offset into the searchable keyspace, not a full key in itself. It may vary from 0..(2^numbits)-1 Returns: NULL if the key is not found in the search range, otherwise an ASCII hex representation of the key is returned. This pointer must be dynamically allocated with malloc */ char *search_range(char *start_str,unsigned long testsl,unsigned long testsh, char *keyhex,int firstbit, unsigned char *plaintext,unsigned char *ciphertext, int textsize) { unsigned char *start,*key,*skeleton,state[256],index1,index2; char *retval; int keybytes,startbytes,x,y,counter,i,found=0; unsigned long lowcounter,highcounter; /* allocate space for the key bytes and our starting value */ keybytes=strlen(keyhex)/2; if(strlen(keyhex)&1) keybytes++; startbytes=strlen(start_str)/2; if(strlen(start_str)&1) startbytes++; start=(unsigned char *)malloc(keybytes); memset(start,'\0',keybytes); skeleton=(unsigned char *)malloc(keybytes); key=(unsigned char *)malloc(keybytes); /* convert the hex strings to bytes */ hex_to_bytes(start_str,start+keybytes-startbytes); hex_to_bytes(keyhex,skeleton); /* OK, now things get time-critical. We are about to drop into a loop that prepares and tests each candidate key */ for(highcounter=0;highcounter<=testsh;highcounter++) { for(lowcounter=0;lowcounter<testsl;lowcounter++) { /* construct the key from the skeleton and our part */ if(!firstbit) { memcpy(key,skeleton,keybytes); for(i=keybytes-1;i>startbytes;i--) key[i]|=start[i]; } /* prepare the key */ for(counter=0;counter<256;counter++) state[counter]=(unsigned char)counter; x=y=0; index1=index2=0; for(counter=0;counter<256;counter++) { index2=(key[index1]+state[counter]+index2) & 0xFF; SwapByte(state[counter],state[index2]); if(++index1==keybytes) index1=0; } /* do two RC4 operations as a preliminary test. If this fails then test the next one, then the rest. This should result in a lot of rejections before the rest of the loop is entered */ x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[0]==(ciphertext[0]^state[(state[x]+state[y]) & 0xFF])) { x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[1]==(ciphertext[1]^state[(state[x]+state[y]) & 0xFF])) { /* rest of the loop. This will only be entered, on average once every 65536 tests */ for(i=2;i<textsize;i++) { x=(x+1) & 0xFF; y=(state[x]+y) & 0xFF; SwapByte(state[x],state[y]); if(plaintext[i]!=(ciphertext[i]^state[(state[x]+state[y]) & 0xFF])) break; } /* if we got to the end of the loop then that's it. We have won */ if(i==textsize) { found=1; goto endloops; } } } /* increment our key segment */ i=keybytes-1; do { start[i]++; } while(!start[i--]); } } /* free memory */ endloops: free(start); free(skeleton); if(found) { retval=(char *)malloc((keybytes*2)+2); i=0; for(i=0;i<keybytes;i++) { retval[i*2]=hexdigit((key[i]&0xF0)>>4); retval[(i*2)+1]=hexdigit(key[i]&0xF); } retval[i*2]='\0'; return retval; } else return NULL; } /*******************************/ /* convert hex string to bytes */ /******************************* eg. "05FC9" would become 0x00,0x5F,0xC9 */ static void hex_to_bytes(char *str,unsigned char *bytes) { int i,firstzero=(strlen(str)&1) ? 1 : 0; unsigned char b; i=0; while(i<(int)strlen(str)) { if(firstzero) firstzero=0; else { b=(decdigit(str[i]))<<4; i++; } b|=decdigit(str[i]); *bytes++=b; i++; } } -------------------------- end code fragment -----------------------