From: "Timothy L. Nali" <tn0s+@andrew.cmu.edu>
Date: Tue, 11 Jul 95 18:48:06 PDT
To: cypherpunks@toad.com
Subject: Re: Speedup of bruterc4.c
In-Reply-To: <9507111715.AA20916@netmail2.microsoft.com>
Message-ID: <4k0ma8K00iWS06o=cO@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


For linux boxes (or perhaps 486 and pentium machines in general), try
adding the flag -funroll-all-loops to the compile line.

    gcc -O2 -funroll-all-loops -m486 -o brute bruterc4.c


Here are my results on a Linux 486/33
Original code (Adam+Tatu)                               : 5405 keys/sec

Original code with -funroll-all-loops                   : 5991 keys/sec

Original code with Russell's changes                
and a couple of my own and -funroll-all-loops           : 6393 keys/sec



Here are the changes I made:

If we assume that the length of the cyphertext and known text is less
than 256 bytes, then the following works.  This gives you a whopping 40
additional keys/sec.

---------------------------------------------------------------------------
int rc4_eq(unsigned char *buffer_ptr, 
           unsigned char *known, 
           unsigned char *cypher_txt,
           int buffer_len, rc4_key *key)
{
  unsigned int t;
  unsigned int y = 0;
  unsigned char* state;
  unsigned int xorIndex;
  unsigned int counter;

  
  state = &key->state[0];

  for(counter=0;counter < buffer_len;counter++)
  {
    y = (state[counter+1] + y) & 0xFF;
    swap_byte(state[counter+1], state[y]);
    xorIndex = (state[counter+1] + state[y]) & 0xFF;
    buffer_ptr[counter] ^= state[xorIndex];
    if (known[counter] != buffer_ptr[counter])
    {
      memcpy(buffer_ptr,cypher_txt,counter+1);
      return 0;
    }
  }
  return 1;
}
--------------------------------------------------------------------------

Also, I could not get Russell's changes to work exactly as he posted
them (I suspect it's because I'm using a very old linux system).  Here's
my prepare_key function. I basically took out the counter++ parts.

--------------------------------------------------------------------------
/* excellent optimised prepare key by Tatu Ylonen ylo@cs.hut.fi */

void prepare_key(unsigned char *key_data_ptr, int key_data_len, rc4_key *key)
{
  unsigned int t;
  unsigned int index2;
  unsigned char* state;
  unsigned int counter;
  unsigned int k0, k1, k2, k3, k4;

  state = &key->state[0];
  memcpy(state,sequence,256);

  index2 = 0;
  k0 = key_data_ptr[0];
  k1 = key_data_ptr[1];
  k2 = key_data_ptr[2];
  k3 = key_data_ptr[3];
  k4 = key_data_ptr[4];
  for(counter = 0; counter < 255; counter+=5)
  {
    t = state[counter];
    index2 = (index2 + k0 + t) & 0xff;
    state[counter] = state[index2];
    state[index2] = t;


    t = state[counter + 1];
    index2 = (index2 + k1 + t) & 0xff;
    state[counter + 1] = state[index2];
    state[index2] = t;

    t = state[counter + 2];
    index2 = (index2 + k2 + t) & 0xff;
    state[counter + 2]  = state[index2];
    state[index2] = t;


    t = state[counter + 3];
    index2 = (index2 + k3 + t) & 0xff;
    state[counter + 3] = state[index2];
    state[index2] = t;


    t = state[counter + 4];
    index2 = (index2 + k4 + t) & 0xff;
    state[counter + 4]  = state[index2];
    state[index2] = t;

  }
  t = state[255];
  index2 = (index2 + k0 + t) & 0xff;
  state[255] = state[index2];
  state[index2] = t;

}
------------------------------------------------------------------------

_____________________________________________________________________________
 
 Tim Nali            \  "We are the music makers, and we are the dreamers of
 tn0s@andrew.cmu.edu  \   the dreams" -Willy Wonka and the Chocolate Factory