Newsgroups: sci.crypt
Path: cactus.org!news.dell.com!swrinde!cs.utexas.edu!howland.reston.ans.net!
+     ix.netcom.com!netcom.com!farid
From: farid@netcom.com (Farid F. El-Wailly)

Subject: Doing Better than XOR in RC4-like Algorithms
Message-ID: 
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
Date: Fri, 11 Nov 1994 21:19:43 GMT
Lines: 131

I'd like to suggest a modification of RC4-like algorithms that would
make them a little more resistant to the key re-use problem.  These
algorithms have a random byte generator that is exclusive-or'ed with
the cleartext to produce the cyphertext.

                         +----------+
               Key ----->|  random  |
                         | Sequence |
                         +----------+
                              |
                              v
                        +-----------+
        Clear Text ---->| Exclusive |----> Cyphertext
         (bytes)        |    or     |       (bytes)
                        +-----------+


If the same key is used to encrypt two files then cryptanalysis is
trivial due to the nature of the exclusive-or. You can cancel out
the random sequence by XORing the two cyphertexts together.

I suggest instead using a non-linear transformation in place of the
exclusive-or, as shown below

                         +----------+
               Key ----->|  random  |
                         | Sequence |
                         +----------+
                              |
                              v
                 +---+     +-----+     +---+
   Clear Text -->| A |---->| XOR |---->| B |-----> Cyphertext
    (bytes)      +---+     +-----+     +---+        (bytes)


Where A is a non-linear 8-bit to 8-bit transformation implemented
via a table lookup.  B is the inverse transformation of A.  What
is neat is that we may already have a 256 entry table of bytes that
can be used for A. In RC4, for example, the "state" table in the key
structure can be used.  All that is needed is to add another table
to the key to implement B, the inverse to the state table A.

The inverse table B, "inv", is initialized the same way as "state"
and it is automatically the inverse of "state". Maintaining the
inverse property is easy. Every time we swap two bytes in "state",
we also swap two bytes in "inv" to keep the inverse property.

            SWAP( state[x], state[y] )
            SWAP( inv[state[x]], inv[state[y]] )

Now when we run the algorithm over cyphertext, the A box reverses the
final B transformation that was done at the end of encryption, the
exclusive-or reverses itself, and the B box reverses the initial A
transformation that was done at the beginning of encryption, giving us
cleartext.

I claim it is very difficult to determine the random sequence or the
cleartext given two cyphertexts generated by using the same key on
two cleartexts.


The following algorithm is based on some C code I saw in this newsgroup
a few weeks ago.


++++++++++++++++++++++++++++++++++++++++++++++++++++++

Header file
   Define the key structure to have two tables state[256] and inv[256];       
        as well as the two byte variables x and y;
   Define the prepare_key function prototype;
   Define the encryption function prototype;


Program file
   Include the header file
   Define a swap_byte function prototype;
   
   Define the prepare_key function
        it is passed( key_data_ptr, key_data_len, pointer_to_key_struct)
   {
        Define the bytes swapByte,index1,index2;
        state and inv refer to the tables in the key structure
        x and y are also in the key structure

        for counter from 0 to 255 by 1 do the following              
        {
        		state[counter] <- counter;
        		inv[counter] <- counter;
        }      
        x and y(in the key structure), index1, and index2 all get cleared
             
        for counter from 0 to 255 by 1 do the following      
        {               
           index2 <- (key_data_ptr[index1] + state[counter] + index2) mod 256
             swap_byte state[counter] and state[index2];            
             swap_byte inv[state[counter]] and inv[state[index2]];            
   
             increment index1 modulo the key_data_len;  
        }       
    }
    
    Define the encryption function
        it is passed (buffer_ptr, buffer_len, pointer_to_key_struct)
    { 
        state and inv refer to the tables in the key structure
        x and y are also in the key structure

        for counter from 0 to buffer_len-1 by 1 do the following      
        {               
             increment x modulo 256;                      
             add state[x] to y modulo 256;               
             swap_byte state[x] and state[y];                        
             swap_byte inv[state[x]] and inv[state[y]];                        
                  
             set temp to state[x] plus state[y] mod 256;                 
                  
             replace buffer_ptr[counter] with
                      inv[state[buffer_ptr[counter]] XOR state[temp]]
         }               
    }
    

++++++++++++++++++++++++++++++++++++++++++++++++

Comments?



-- 
Farid F. El-Wailly                 farid@netcom.com